Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems
2009 (English)In: Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009, 539-547 p.Conference paper (Refereed)
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, deﬁned 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.
Place, publisher, year, edition, pages
2009. 539-547 p.
Language Technology (Computational Linguistics) Language Technology (Computational Linguistics)
Research subject Computational Linguistics
IdentifiersURN: urn:nbn:se:uu:diva-105319OAI: oai:DiVA.org:uu-105319DiVA: diva2:221080
NAACL HLT 2009. May 31-June 5, Boulder, Colorado