Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems
Carlos Gómez-Rodrı́guez, Marco Kuhlmann, Giorgio Satta, and David J. Weir. 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 (NAACL), pages 539–547, Boulder, CO, USA, 2009.
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.