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