uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems
Departamento de Computación, Universidade da Coruña.
Uppsala University, Disciplinary Domain of Humanities and Social Sciences, Faculty of Languages, Department of Linguistics and Philology. (Datorlingvistik)ORCID iD: 0000-0002-2492-9872
Department of Information Engineering, University of Padua.
Department of Informatics, University of Sussex.
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)
Abstract [en]

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.

Place, publisher, year, edition, pages
2009. 539-547 p.
National Category
Language Technology (Computational Linguistics) Language Technology (Computational Linguistics)
Research subject
Computational Linguistics
URN: urn:nbn:se:uu:diva-105319OAI: oai:DiVA.org:uu-105319DiVA: diva2:221080
NAACL HLT 2009. May 31-June 5, Boulder, Colorado
Available from: 2009-06-03 Created: 2009-06-03 Last updated: 2013-07-17

Open Access in DiVA

No full text

Other links


Search in DiVA

By author/editor
Kuhlmann, Marco
By organisation
Department of Linguistics and Philology
Language Technology (Computational Linguistics)Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 228 hits
ReferencesLink to record
Permanent link

Direct link