Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems

Carlos Gómez-Rodrı́guez, Marco Kuhlmann, and Giorgio Satta. Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems. In Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 276–284, Los Angeles, USA, 2010.

Abstract

The use of well-nested linear context-free rewriting systems has been empirically motivated for modeling of the syntax of languages with discontinuous constituents or relatively free word order. We present a chart-based parsing algorithm that asymptotically improves the known running time upper bound for this class of rewriting systems. Our result is obtained through a linear space construction of a binary normal form for the grammar at hand.

Links