Publication at Faculty of Mathematics and Physics |
2008
Abstract
The R-automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jancar et al. to model the so-called analysis by reduction. Here it is shown that the class L(R) of languages that are accepted by R-automata is incomparable under set inclusion to the class CRL of Church-Rosser languages and to the class GCSL of growing context-sensitive languages.
In fact this already holds for the class L(2-mon-R) of languages that are accepted by 2-monotone R-automata. In addition, we prove that already the latter class contains NP-complete languages, showing that already the 2-monotone R-automaton has a surprisingly large expressive power.