Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version)
- 1 January 1981
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 177-188
- https://doi.org/10.1145/800076.802471
Abstract
We define a language L and show that is cannot be recognized by any two way deterministic counter machine. It is done by fooling any given such machine; i.e. showing that if it accepts L' @@@@ L, then L'-L @@@@ &fgr;. For this purpose, an argument stronger than the well known crossing sequence argument needs to be introduced. Since L is accepted by a two-way deterministic pushdown automaton, we consequently show that one pushdown stack is more powerful than one counter for deterministic two-way machines.Keywords
This publication has 0 references indexed in Scilit: