Some results concerning automata on two-dimensional tapes
Óscar H. Ibarra, Ricahad T. Melson · International Journal of Computer Mathematics · 1974
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)