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

Abstract

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.

Cited by in corpus (6)

• Logarithmic Space and Permutations
• A Survey of Multi-Tape Automata
• Asynchronous Multi-Tape Automata Intersection: Undecidability and Approximation
• A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata
• An in-between "implicit" and "explicit" complexity: Automata
• Language Inference with Multi-head Automata through Reinforcement Learning