Aufsatz in einer Fachzeitschrift
On the complexity of 2-monotone restarting automata
Details zur Publikation
Autor(inn)en: | Otto, F.; Mraz, F.; Jurdzinski, T.; Platek, M. |
Publikationsjahr: | 2008 |
Zeitschrift: | Theory of Computing Systems |
Seitenbereich: | 488-518 |
Jahrgang/Band : | 42 |
Erste Seite: | 488 |
Letzte Seite: | 518 |
ISSN: | 1432-4350 |
Zusammenfassung, 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.
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.
