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

ACL ID N10-1035
Title Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems
Venue Human Language Technologies
Session Main Conference
Year 2010
Authors

The use of well-nested linear context-free rewriting systems has been empirically moti- vated for modeling of the syntax of languages with discontinuous constituents or relatively free word order. We present a chart-based pars- ing 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.