Two-dimensional automata with rotated inputs (projection-type) (Q1062451)

This paper introduces a new type of automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape x by first scanning the tape x from various sides with parallel/sequential array readers, and by then scanning the pair of the halting state configurations (i.e., projections) generated by these array readers with a multitape finite automaton. We mainly concentrate on investigating the accepting power of two-dimensional automata which consist of one-way parallel/sequential array readers and a multiple finite automaton operating in real time.