Affiliations: Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. [email protected]
Correspondence:
[†]
Address for correspondence: Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany
Note: [*] Some of the results of this paper have been announced at NCMA 2017, Prague, August 2017. An extended abstract appeared in the proceedings of that conference [1].
Abstract: A complete taxonomy is presented for restarting automata without auxiliary symbols. In this taxonomy, the language classes that are accepted by deterministic and nondeterministic, monotone, weakly monotone, and non-monotone, shrinking and length-reducing restarting automata are compared to each other with respect to inclusion. As it turns out, the 45 types of restarting automata considered yield 29 different classes of languages. By presenting a collection of rather simple example languages, it is shown that, for any two of these language classes ℒ1 and ℒ2, the class ℒ1 is a subclass of ℒ2 if and only if ℒ1 is defined by a type of restarting automaton that is a restriction of a type of restarting automaton that defines the class ℒ2.
