Nondeterministic Ordered Restarting Automata

Research paper by Kent Kwee, Friedrich Otto

Indexed on: 02 Jul '18Published on: 29 Jun '18Published in: International Journal of Foundations of Computer Science


International Journal of Foundations of Computer Science, Volume 29, Issue 04, Page 663-685, June 2018. While (stateless) deterministic ordered restarting automata accept exactly the regular languages, it has been observed that nondeterministic ordered restarting automata (ORWW-automata for short) are more expressive. Here we show that the class of languages accepted by the latter automata is an abstract family of languages that is incomparable to the linear, the context-free, and the growing context-sensitive languages with respect to inclusion, and that the emptiness problem is decidable for these languages. In addition, we give a construction that turns a stateless ORWW-automaton into a nondeterministic finite-state acceptor for the same language.