Journal article

Publication year: 2020

Pages: 1021-1049

Journal: International Journal of Foundations of Computer Science

Volume number: 31

Issue number: 8

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054120420022

Publisher: World Scientific Publishing

Abstract: 
It is well known that reversible finite automata do not accept all regular languages, that reversible pushdown automata do not accept all deterministic context-free languages, and that reversible queue automata are less powerful than deterministic real-time queue automata. It is of significant interest from both a practical and theoretical point of view to close these gaps. We here extend these reversible models by a preprocessing unit which is basically a reversible injective and length-preserving finite state transducer. It turns out that preprocessing the input using such weak devices increases the computational power of reversible deterministic finite automata to the acceptance of all regular languages, whereas for reversible pushdown automata the accepted family of languages lies strictly in between the reversible deterministic context-free languages and the real-time deterministic context-free languages. For reversible queue automata the preprocessing of the input leads to machines that are stronger than real-time reversible queue automata, but less powerful than real-time deterministic (irreversible) queue automata. Moreover, it is shown that the computational power of all three types of machines is not changed by allowing the preprocessing finite state transducer to work irreversibly. Finally, we examine the closure properties of the family of languages accepted by such machines.

Harvard Citation style: Axelsen, H., Kutrib, M., Malcher, A. and Wendlandt, M. (2020) Boosting Reversible Pushdown and Queue Machines by Preprocessing, International Journal of Foundations of Computer Science, 31(8), pp. 1021-1049. https://doi.org/10.1142/S0129054120420022

APA Citation style: Axelsen, H., Kutrib, M., Malcher, A., & Wendlandt, M. (2020). Boosting Reversible Pushdown and Queue Machines by Preprocessing. International Journal of Foundations of Computer Science. 31(8), 1021-1049. https://doi.org/10.1142/S0129054120420022