Succinct description of regular languages by weak restarting automata

AbstractThe descriptional complexity of restarting automata is investigated. We distinguish the classes of weak restarting automata, i.e., classical restarting automata accepting exactly the regular languages. In order to investigate the descriptional power gained by the additional structural resources of restarting automata, we study the trade-offs in the number of states when changing the representation to classical finite automata. The bounds shown are tight in the exact number of states. Interestingly, for a particular class we can show the tight bounds 2n+1 and 2n for DFA and NFA conversion, respectively, by a fooling set technique. So, the power gained by the resources given to restarting automata seems to be different compared with nondeterminism