On Multi-Head Finite Automata
Arnold L. Rosenberg · IBM Journal of Research and Development · 1966
Let Mnbe the class of languages defined by n-head finite automata. The Boolean and Kleene closure properties of Mnare investigated, and a relationship between Mnand the class of sets of n-tuples of tapes defined by n-tape finite automata is established. It is shown that the classes Miform a hierarchy; and that, moreover, for all n, there is a context-free language (CFL) in Mn+1−Mn. It is further shown that there is a CFL which is in no Mnfor any integer n. Finally, several decision properties of the multi-head languages are established.