File(s) under permanent embargo
Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems
chapter
posted on 2023-06-08, 00:22 authored by Carlos Gómez-Rodríguez, Marco Kuhlmann, Giorgio Satta, David WeirDavid WeirLinear 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.
History
Publication status
- Published
Publisher
Association for Computational LinguisticsPage range
539-547Pages
9.0Event name
NAACL '09 Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational LinguisticsEvent type
conferenceBook title
Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational LinguisticsISBN
9781932432411Department affiliated with
- Informatics Publications
Notes
NAACL HLT 2009; May 31 - June 5, 2009Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC