Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!deccrl!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!sci.kun.nl!cs.kun.nl!janos
From: janos@cs.kun.nl (Janos Sarbo)
Newsgroups: comp.theory
Subject: context-free parsing
Summary: Parsing in linear time
Keywords: parsing, complexity
Message-ID: <2933@wn1.sci.kun.nl>
Date: 11 Apr 91 14:44:21 GMT
Sender: root@sci.kun.nl
Organization: University of Nijmegen, The Netherlands
Lines: 4

We have heard that someone has found a proof that it is not possible
that all (unambiguous) context-free grammars can be parsed in linear
time. If you have a reference about this please send it to
	  markjan@cs.kun.nl