Conference paper

Publication year: 2011

Pages: 83-96

Journal: Theoretical Computer Science

Volume number: 412

Issue number: 1-2

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2010.08.024

Conference: International Workshop on the Complexity of Simple Programs

Publisher: Elsevier

Abstract: 
Multi-head finite automata were introduced and first investigated by Rabin and Scott in 1964 and Rosenberg in 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. Additionally the conversions between different types of multi-head finite automata induce in most cases size bounds that cannot be bounded by any recursive function, so-called non-recursive trade-oil's. 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. (C) 2010 Elsevier B.V. All rights reserved.

Harvard Citation style: Holzer, M., Kutrib, M. and Malcher, A. (2011) Complexity of multi-head finite automata: Origins and directions, Theoretical Computer Science, 412(1-2), pp. 83-96. https://doi.org/10.1016/j.tcs.2010.08.024

APA Citation style: Holzer, M., Kutrib, M., & Malcher, A. (2011). Complexity of multi-head finite automata: Origins and directions. Theoretical Computer Science. 412(1-2), 83-96. https://doi.org/10.1016/j.tcs.2010.08.024