On the complexity of 2-monotone restarting automata

Abstrakt

The R-automaton is the weakest nondeterministic version of the restarting automaton. We show that the class L(R) of languages recognized by R-automata is under set inclusion incomparable to the class of Church-Rosser languages and to the class of growing context-sensitive languages.

This already holds for 2-monotone R-automata. In addition, 2-monotone R-automata can recognize some NP-complete languages.