Konferenzpaper

Jahr der Veröffentlichung: 2011

Seiten: 83-96

Zeitschrift: Theoretical Computer Science

Bandnummer: 412

Heftnummer: 1-2

ISSN: 0304-3975

eISSN: 1879-2294

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

Konferenz: International Workshop on the Complexity of Simple Programs

Verlag: 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-Zitierstil: 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-Zitierstil: 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