Contribution in edited book
On the complexity of 2-monotone restarting automata
Publication Details
Authors: | Jurdzinski, T.; Otto, F.; Mraz, F.; Platek, M. |
Editor: | Calude, C.S., Calude, E. and Dinneen, M.J. |
Publisher: | Springer |
Place: | Berlin |
Publication year: | 2004 |
Pages range : | 237-248 |
Book title: | Developments in Language Theory, Proceedings DLT 2004 |
Title of series: | Lecture Notes in Computer Science 3340 |
Abstract
The R-automaton is the weakest form of the restarting automaton. It is shown that the class of languages accepted by these automata is incomparable under set inclusion to the class of growing context-sensitive languages. In fact, this already holds for the class of languages that are accepted by 2-monotone R-automata. Further it is shown that already this class contains NP-complete languages. Thus.. already the 2-monotone R-automaton has a surprisingly large expressive power.
The R-automaton is the weakest form of the restarting automaton. It is shown that the class of languages accepted by these automata is incomparable under set inclusion to the class of growing context-sensitive languages. In fact, this already holds for the class of languages that are accepted by 2-monotone R-automata. Further it is shown that already this class contains NP-complete languages. Thus.. already the 2-monotone R-automaton has a surprisingly large expressive power.
Projects
