Gómez-Rodríguez, Carlos, Kuhlmann, Marco, Satta, Giorgio and Weir, David (2009) Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems. In: Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics. Association for Computational Linguistics, pp. 539-547. ISBN 9781932432411
![]() |
PDF
Restricted to SRO admin only Download (182kB) |
Abstract
Linear Context-free Rewriting Systems (LCFRS) is an expressive grammar formalism with applications in syntax-based machine translation. The parsing complexity of an LCFRS is exponential in both the rank of a production, defined as the number of nonterminals on its right-hand side, and a measure for the discontinuity of a phrase, called fan-out. In this paper, we present an algorithm that transforms an LCFRS into a strongly equivalent form in which all productions have rank at most 2, and has minimal fan-out. Our results generalize previous work on Synchronous Context-Free Grammar, and are particularly relevant for machine translation from or to languages that require syntactic analyses with discontinuous constituents.
Item Type: | Book Section |
---|---|
Additional Information: | NAACL HLT 2009; May 31 - June 5, 2009 |
Schools and Departments: | School of Engineering and Informatics > Informatics |
Depositing User: | David Weir |
Date Deposited: | 06 Feb 2012 19:52 |
Last Modified: | 13 Nov 2013 16:40 |
URI: | http://sro.sussex.ac.uk/id/eprint/22699 |
View download statistics for this item
📧 Request an update