Journal article

Publication year: 2021

Pages: 397-425

Journal: Acta Informatica

Volume number: 58

Issue number: 4

ISSN: 0001-5903

eISSN: 1432-0525

DOI Link: https://doi.org/10.1007/s00236-020-00389-0

Publisher: Springer

Abstract: 
There are two types of stateless deterministic ordered restarting automata that both characterize the class of regular languages: the stl-det-ORWW-automaton and the stl-det-ORRWW-automaton. For the former a notion of reversibility has been introduced and studied that is very much tuned to the way in which restarting automata work. Here we suggest another, more classical, notion of reversibility for stl-det-ORRWW-automata, and we show that each regular language is accepted by such a reversible stl-det-ORRWW-automaton. We study the descriptional complexity of these automata, showing that they are exponentially more succinct than nondeterministic finite-state acceptors. We also look at the case of unary input alphabets.

Harvard Citation style: Otto, F. and Wendlandt, M. (2021) Reversibility for stateless ordered RRWW-automata, Acta Informatica, 58(4), pp. 397-425. https://doi.org/10.1007/s00236-020-00389-0

APA Citation style: Otto, F., & Wendlandt, M. (2021). Reversibility for stateless ordered RRWW-automata. Acta Informatica. 58(4), 397-425. https://doi.org/10.1007/s00236-020-00389-0