Publication at Faculty of Mathematics and Physics |
2004
Abstract
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.