wickberg@delta.eecs.nwu.edu (John Wickberg) (06/28/90)
<> 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
marek@ucr.edu (marek chrobak) (06/28/90)
In article <9329@accuvax.nwu.edu> wickberg@delta.eecs.nwu.edu (John Wickberg) writes: > >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? No specific language has been proven to be not in 2DPDA. As far as I know, all proofs of such results are based, in essence, on diagonalization. In fact, the problem is not trivial even when the pushdown is just a counter (2DCA). Duris and Galil (TCS 21) proved that 2DCA is strictly contained in 2DPDA. I proved (JCSS 30) that 2DCA is strictly contained in 2NCA (nondeterministic). > If not, what >is the nature of the difficulty of the proof? Give it a try, you'll see. Best, Marek -- ----------------------------------------------------------------------- Marek Chrobak email: marek@ucrmath.ucr.edu Math & CS, UC Riverside phone: (714) 787-3769 -----------------------------------------------------------------------