Journalartikel

Jahr der Veröffentlichung: 2021

Seiten: 397-425

Zeitschrift: Acta Informatica

Bandnummer: 58

Heftnummer: 4

ISSN: 0001-5903

eISSN: 1432-0525

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

Verlag: 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-Zitierstil: 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-Zitierstil: 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