Affiliations: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. {kutrib, malcher, matthias.wendlandt}@informatik.uni-giessen.de
Correspondence:
[*]
Address for correspondence: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
Abstract: Deterministic finite automata equipped with the storage medium of a queue are investigated towards their ability to perform reversible computations, that is, computations in which every occurring configuration has exactly one successor and exactly one predecessor. A first result is that any queue automaton can be simulated by a reversible one. So, reversible queue automata are as powerful as Turing machines. Therefore it is of natural interest to impose time restrictions to queue automata. Here we consider quasi realtime and realtime computations. It is shown that every reversible quasi realtime queue automaton can be sped up to realtime. On the other hand, under realtime conditions reversible queue automata are less powerful than general queue automata. Furthermore, we exhibit a lower bound of Ω(n2log(n)) time steps for realtime queue automata witness languages to be accepted by any equivalent reversible queue automaton. We study the closure properties of reversible realtime queue automata and obtain similar results as for reversible deterministic pushdown automata. Finally, we investigate decidability questions and obtain that all commonly studied questions such as emptiness, finiteness, or equivalence are not semidecidable for reversible realtime queue automata. Furthermore, it is not semidecidable whether an arbitrary given realtime queue automaton is reversible.
