On Nondeterministic Ordered Restarting Automata

13^th September 2016, 13:00 Ashton Lecture Theater
Prof. Friedrich Otto
Fachgebiet Theoretische Informatik
Fachbereich Elektrotechnik/Informatik
Universität Kassel
Wilhelmshöher Allee 71-73
D-34121 Kassel
Germany

Abstract

While (stateless) deterministic ordered restarting automata accept exactly the regular languages,
it is known that nondeterministic ordered restarting automata accept some languages that
are not even growing context-sensitive. In fact, the class of languages accepted by these automata
is an abstract family of languages that is incomparable to the (deterministic) linear languages,
the (deterministic) context-free languages, and the growing context-sensitive languages with respect to inclusion, and the emptiness problem is decidable for these automata. These results are derived by using a Cut-and-Paste Lemma for nondeterministic ordered restarting automata that is based on Higman's theorem. Here we extend the arguments used in that proof to actually derive a real Pumping Lemma for these automata. Based on this Pumping Lemma, it can be shown that the finiteness problem is also decidable for these automata, and that the only unary languages these automata accept are the regular ones. In addition, we present a new and simplified proof for the fact that stateless ordered restarting automata only accept regular languages.