Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!sdd.hp.com!decwrl!hayes.fai.alaska.edu!accuvax.nwu.edu!delta.eecs.nwu.edu!wickberg
From: wickberg@delta.eecs.nwu.edu (John Wickberg)
Newsgroups: comp.theory
Subject: Is there a CFL not accepted by 2-DPDA?
Message-ID: <9329@accuvax.nwu.edu>
Date: 27 Jun 90 18:16:55 GMT
Sender: news@accuvax.nwu.edu
Reply-To: wickberg@delta.eecs.nwu.edu (John Wickberg)
Distribution: usa
Organization: Northwestern U, Evanston IL, USA
Lines: 11

<>
In "Introduction to Automata Theory, Languages, and Computation" by
Hopcroft and Ullman, a statement is made that languages accepted by
a two-way DPDA can be recognised in linear time and that no one has
proven that there is a CFL that is not accepted by a 2DPDA (this can
be found at the end of chapter 5).

Has a CFL been proven not to be accepted by a 2DPDA?  If not, what
is the nature of the difficulty of the proof?

John Wickberg