Journal article
On the complexity of 2-monotone restarting automata



Publication Details
Authors:
Otto, F.; Mraz, F.; Jurdzinski, T.; Platek, M.
Publication year:
2008
Journal:
Theory of Computing Systems
Pages range:
488-518
Volume number:
42
Start page:
488
End page:
518
ISSN:
1432-4350

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.


Authors/Editors

Last updated on 2019-01-11 at 16:05