. "12"^^ . "On the complexity of 2-monotone restarting automata" . "3340" . . "RIV/00216208:11320/04:00003536" . "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." . . . . . "[686CE45F77F2]" . "O lev\u011B-monoton\u00EDch deterministick\u00FDch restartovac\u00EDch automatech"@cs . "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."@en . "577852" . "P(GA201/02/1456), P(GA201/04/2102), Z(MSM 113200005)" . "Lecture Notes In Computer Science" . "RIV/00216208:11320/04:00003536!RIV/2005/GA0/113205/N" . "Mr\u00E1z, Franti\u0161ek" . "On the complexity of 2-monotone restarting automata" . . "2004" . . "complexity;2-monotone;restarting;automata"@en . . . "On the complexity of 2-monotone restarting automata"@en . "2"^^ . . "11320" . "0302-9743" . . . . "4"^^ . "237;248" . . "Pl\u00E1tek, Martin" . . . "O lev\u011B-monoton\u00EDch deterministick\u00FDch restartovac\u00EDch automatech"@cs . "R-automat je nejslab\u0161\u00EDm nedeterministick\u00FDm modelem restartovac\u00EDch automat\u016F. Ukazujeme, \u017Ee t\u0159\u00EDda rozpozn\u00E1van\u00FDch R-automaty je neporovnateln\u00E1 inkluz\u00ED s t\u0159\u00EDdou Church-Rosserov\u00FDch jazyk\u016F a t\u0159\u00EDdou rostouc\u00EDch kontextov\u00FDch jazyk\u016F. To plat\u00ED ji\u017E pro 2-monotonn\u00ED R-automaty. Nav\u00EDc, 2-monotonn\u00ED R-automaty m\u016F\u017Eou rozpozn\u00E1vat n\u011Bkter\u00E9 NP-\u00FApln\u00E9 jazyky.\u00ED doby letu usuzujeme n"@cs . "On the complexity of 2-monotone restarting automata"@en . . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . . .