. "O slo\u017Eitosti 2-monotonn\u00EDch restartovac\u00EDch automt\u016F"@cs . "Universit\u00E4t Kassel" . "577851" . "RIV/00216208:11320/04:00002955!RIV/2005/GA0/113205/N" . . . "11320" . "Kassel, SRN" . . "On the complexity of 2-monotone restarting automata"@en . "4"^^ . "P(GA201/02/1456), P(GA201/04/2102), Z(MSM 113200005)" . "RIV/00216208:11320/04:00002955" . "O slo\u017Eitosti 2-monotonn\u00EDch restartovac\u00EDch automt\u016F"@cs . . "2"^^ . . . . "29"^^ . "On the complexity of 2-monotone restarting automata" . "On the complexity of 2-monotone restarting automata" . "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."@cs . . . "On the complexity of 2-monotone restarting automata"@en . "4./04" . "[A10E3A27E1F2]" . . . . "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." . . . "Mr\u00E1z, Franti\u0161ek" . . . "Pl\u00E1tek, Martin" . "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 . "complexity;2-monotone;restarting;automata"@en . . . .