DFKI-LT - Left-To-Right Parsing and Bilexical Context-Free Grammars

Mark-Jan Nederhof, Giorgio Satta
Left-To-Right Parsing and Bilexical Context-Free Grammars
in: Sergei Nirenburg, Douglas Appelt, Fabio Ciravegna, Robert Dale (eds.):
1 Proceedings of the 6th Applied Natural Language Processing Conference and 1st Meeting of the North American Chapter of the Association for Computational Linguistics (ANLP-NAACL'00), April 29 - May 3, Pages 272-279, Seattle, Washington, USA, o.A., 2000
We compare the asymptotic time complexity of left-to-right and bidirectional parsing techniques for bilexical context-free grammars, a grammar formalism that is an abstraction of language models used in several state-of-the-art real-world parsers. We provide evidence that left-to-right parsing cannot be realised within acceptable time-bounds if the so called correct-prefix property is to be ensured. Our evidence is based on complexity results for the representation of regular languages.
Files: BibTeX, Nederhof:2000:LRPb.pdf