Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version)
Pavol D riš, Zvi Galil · 1981
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 ≠ φ. 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.