Publication at Faculty of Mathematics and Physics |
2007
Abstract
A nondeterministic restarting automaton M is said to be (strongly) correctness preserving, if, for each cycle , 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.