On the descriptional complexity of stateless deterministic ordered restarting automata

Stateless deterministic ordered restarting automata accept exactly the regular languages. Here we study the descriptional complexity of these automata, taking the size of the tape alphabet as the complexity measure. We present a construction that turns a stateless deterministic ordered restarting automaton that works on an alphabet of size n into an equivalent nondeterministic finite-state acceptor of size at most 2(O(n)), and we prove that this bound is sharp (with respect to its order of magnitude). In addition, we investigate the descriptional complexity of some operations for regular languages that are given through stateless deterministic ordered restarting automata. Based on these results we then show that many decision problems, like emptiness, finiteness, and inclusion, are PSPACE-complete for these automata. Finally, we propose three ways of associating relations to deterministic ordered restarting automata. In the most general setting, we obtain succinct representations for all rational relations, in the most restricted setting, we obtain exactly those rational functions that map the empty word to itself, and by extending the stateless deterministic ordered restarting automaton into a transducer, we obtain exactly all those transductions on words that are MSO-definable. (c) 2017 Elsevier Inc. All rights reserved.