Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952042 | Theoretical Computer Science | 2017 | 16 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Kutrib, Andreas Malcher,