Reversible Computations of One-Way Counter Automata

Martin Kutrib
(Institut für Informatik, Universität Giessen)
Andreas Malcher
(Institut für Informatik, Universität Giessen)

Deterministic one-way time-bounded multi-counter automata are studied with respect to their ability to perform reversible computations, which means that the automata are also backward deterministic and, thus, are able to uniquely step the computation back and forth. We study the computational capacity of such devices and obtain separation results between irreversible and reversible k-counter automata for superpolynomial time. For exponential time we obtain moreover an infinite and tight hierarchy with respect to the number of counters. This hierarchy is shown with Kolmogorov complexity and incompressibility arguments. In this way, on passing we can prove this hierarchy also for ordinary counter automata. This improves the known hierarchy for ordinary counter automata in the sense that here we consider a weaker acceptance condition. Then, it turns out that k+1 reversible counters are not better than k ordinary counters and vice versa. Finally, almost all usually studied decidability questions turn out to be undecidable and not even semidecidable for reversible multi-counter automata, if at least two counters are provided.

In Henning Bordihn, Géza Horváth and György Vaszil: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), Debrecen, Hungary, August 26-27, 2022, Electronic Proceedings in Theoretical Computer Science 367, pp. 126–142.
Published: 27th August 2022.

ArXived at: https://dx.doi.org/10.4204/EPTCS.367.9 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org