Journal article

Publication year: 2016

Pages: 341-368

Journal: Fundamenta Informaticae

Volume number: 148

Issue number: 3-4

ISSN: 0169-2968

eISSN: 1875-8681

DOI Link: https://doi.org/10.3233/FI-2016-1438

Publisher: SAGE Publications

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 Omega (n(2)/log(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.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2016) Reversible Queue Automata, Fundamenta Informaticae, 148(3-4), pp. 341-368. https://doi.org/10.3233/FI-2016-1438

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2016). Reversible Queue Automata. Fundamenta Informaticae. 148(3-4), 341-368. https://doi.org/10.3233/FI-2016-1438