SPACE HIERARCHIES OF TWO-DIMENSIONAL ALTERNATING TURING MACHINES, PUSHDOWN AUTOMATA AND COUNTER AUTOMATA

摘要

This paper investigates the space hierarchies of the language classes for two dimensional Turing machines (2-TM's), two-dimensional pushdown automata (2-PDA's) and two-dimensional counter automata (2CA's) with small space.