"Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata"@en . "RIV/00216208:11320/07:00206133!RIV10-MSM-11320___" . "Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata"@en . "Machines, Computations, and Universality" . "424049" . "12"^^ . . . . . . "Berlin" . . . "Berlin" . . "11320" . . . "2"^^ . "Springer-Verlag" . "Hierarchical; Relaxations; Correctness; Preserving; Property; Restarting; Automata"@en . "P(1ET100300517), Z(MSM0021620838)" . . "2007-01-01+01:00"^^ . "RIV/00216208:11320/07:00206133" . "978-3-540-74592-1" . "3"^^ . . . . "Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata" . "Otto, Friedrich" . "Pl\u00E1tek, Martin" . "A nondeterministic restarting automaton M is said to be (strongly) correctness preserving, if, for each cycle u proves(c)(M) v, the word v belongs to the complete language L-C(M) accepted by M, if the word u does. Here, in order to differentiate between nondeterministic restarting automata that are correctness preserving and nondeterministic restarting automata in general we introduce two gradual relaxations of the correctness preserving property. These relaxations lead to an infinite two-dimensional hierarchy of classes of languages with membership problems that are decidable in polynomial time." . "[F25E2C9E21A9]" . . . "Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata" . . . . "000249744600020" . . "A nondeterministic restarting automaton M is said to be (strongly) correctness preserving, if, for each cycle u proves(c)(M) v, the word v belongs to the complete language L-C(M) accepted by M, if the word u does. Here, in order to differentiate between nondeterministic restarting automata that are correctness preserving and nondeterministic restarting automata in general we introduce two gradual relaxations of the correctness preserving property. These relaxations lead to an infinite two-dimensional hierarchy of classes of languages with membership problems that are decidable in polynomial time."@en . . . "Mr\u00E1z, Franti\u0161ek" . .