Journalartikel

Jahr der Veröffentlichung: 2017

Seiten: 149-164

Zeitschrift: Theoretical Computer Science

Bandnummer: 682

ISSN: 0304-3975

eISSN: 1879-2294

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

Verlag: Elsevier

Abstract: 
One-way multi-head finite automata are considered towards their ability to perform reversible computations. It is shown that, for every number k >= 1 of heads, there are problems which can be solved by one-way k-head finite automata, but not by any one-way reversible k-head finite automaton. Additionally, a proper head hierarchy is obtained for one-way reversible multi-head finite automata. Closure properties and decidability problems are investigated as well. It turns out that one-way reversible finite automata with two heads are still a powerful model, since almost all commonly studied problems are not even semidecidable. Finally, descriptional complexity aspects are studied and non-recursive trade-offs are shown. (C) 2016 Elsevier B.V. All rights reserved.

Harvard-Zitierstil: Kutrib, M. and Malcher, A. (2017) One-way reversible multi-head finite automata, Theoretical Computer Science, 682, pp. 149-164. https://doi.org/10.1016/j.tcs.2016.11.006

APA-Zitierstil: Kutrib, M., & Malcher, A. (2017). One-way reversible multi-head finite automata. Theoretical Computer Science. 682, 149-164. https://doi.org/10.1016/j.tcs.2016.11.006