Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems
Carlos Gómez‐Rodríguez, Marco Kuhlmann, Giorgio Satta · 2010
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. 1