Stateless deterministic ordered restarting automata characterize the class of regular languages. Here we introduce a notion of
for these automata and show that each regular language is accepted by such a reversible stateless deterministic ordered restarting automaton. We study the descriptional complexity of these automata, showing that they are exponentially more succinct than nondeterministic finite-state acceptors. We also look at the case of unary input alphabets.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten