2009/06/17 by Markus Holzer, Martin Kutrib, Andreas Malcher · 2 citations
Computer Science · #cs.CC #cs.FL
paper · pdf · doi:10.4204/eptcs.1.9
published as EPTCS 1, 2009, pp. 93-107
arxiv created 2009/06/17 · arxiv updated 2009/12/01
Multi-head finite automata were introduced in (Rabin, 1964) and (Rosenberg, 1966). Since that time, a vast literature on computational and descriptional complexity issues on multi-head finite automata documenting the importance of these devices has been developed. Although multi-head finite automata are a simple concept, their computational behavior can be already very complex and leads to undecidable or even non-semi-decidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. These strong negative results trigger the study of subclasses and alternative characterizations of multi-head finite automata for a better understanding of the nature of non-recursive trade-offs and, thus, the borderline between decidable and undecidable problems. In the present paper, we tour a fragment of this literature.