Computation by multi-head finite automata

Abstract

Families of languages recognized by multi-head writing finite automata are considered. For n≥1, an n-head writing finite automaton (n-wfa) is a finite state device with n one-way read-write heads on a single input tape. Relationships between families of languages recognized by n-wfa (Wn) and other models (e.g. n-head nonwriting finite automata, linear-bounded automata, and real-time buffer automata) are established. A complexity measure is defined for computations by two-head writing finite automata. This measure is obtained from a sequence which encodes the motion of the two heads. A relationship between complexity classes for 2-wfa and one-tape off-line Turing machines is then derived. Using this relationship, a number of sets are shown to be unrecognizable by any 2-wfa. The incomparability of W2 and families of languages recognized by pushdown automata, n-head pushdown automata, and one-way stack automata is thereby established.