Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)

Pavol Duris, Zvi Galil

Browse the full STOC paper archive.