%
% GENERATED FROM https://www.coli.uni-saarland.de
%    by   : anonymous
%    IP   : coli2006.lst.uni-saarland.de
%    at   : Mon, 05 Feb 2024 15:43:17 +0100 GMT
%    
% Selection : Reference #949
%




@InProceedings{Nederhof_Satta:2000_1,
      AUTHOR = {Nederhof, Mark-Jan and Satta, Giorgio},
      TITLE = {Left-To-Right Parsing and Bilexical Context-Free Grammars},
      YEAR = {2000},
      BOOKTITLE = {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},
      EDITOR = {Nirenburg, Sergei and Appelt, Douglas and Ciravegna, Fabio and Dale, Robert},
      ADDRESS = {Seattle, Washington, USA},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof-satta00.ps.gz},
      ABSTRACT = {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.},
      ANNOTE = {COLIURL : Nederhof:2000:LRPb.pdf Nederhof:2000:LRPb.ps}
}