Multi-Head Finite Automata: Characterizations, Concepts and Open Problems

Markus Holzer
Martin Kutrib
Andreas Malcher

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.

In Turlough Neary, Damien Woods, Tony Seda and Niall Murphy: Proceedings International Workshop on The Complexity of Simple Programs (CSP 2008), Cork, Ireland, 6-7th December 2008, Electronic Proceedings in Theoretical Computer Science 1, pp. 93–107.
Published: 25th June 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.1.9 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org