Two-Dimensional Input Tapes with One-Counter Languages Not Accepted by Deterministic Rebound Automata
Makoto Sakamoto, Hiroaki Kawano, Makoto Saito · Institutional Repositories DataBase (IRDB) · 2004
Abstract M.Blum and C.Hewitt first proposed two-dimensional automata as a computational model of two- dimensional pattern processing, and investigated their pattern recognition abilities[1]. Since then, many researchers have been investigating a lot of properties about automata on a two-dimensional tape. However, there are a lot more open problems. For instance, it was unknown whether there exists a language accepted by a two-way nondeterministic one counter automaton, but not accepted by any deterministic rebound au- tomaton. In this paper, we try to solve this problem, and show that there exists such a language.