Some results concerning automata on two-dimensional tapes

Abstract

Hierarchies of automata operating on two-dimensional tapes are investigated. In particular, it is shown that finite automata with n+3 markers (n+2 heads) are strictly more powerful than those with n markers (n heads)

Keywords:

• Automata On Two-Dimensional Tapes
• Multi-Head Automata
• Finite Automata
• Pushdown Automata
• Hierarchy Theorems

C.R. Categories:

• 5.22

†This research was supported in part by the National Science Foundation under Grant GJ-35614 and by the University of Minnesota Grant 438-0806-8520-02.

†This research was supported in part by the National Science Foundation under Grant GJ-35614 and by the University of Minnesota Grant 438-0806-8520-02.

Notes

†This research was supported in part by the National Science Foundation under Grant GJ-35614 and by the University of Minnesota Grant 438-0806-8520-02.