Non-Recursive Trade-Offs for Deterministic Restarting Automata
Markus Holzer, Martin Kutrib, Jens Reimann · Journal of automata, languages and combinatorics · 2007
We investigate the descriptional complexity of deterministic restarting automata, an automaton model inspired from linguistics. Variants of deterministic and monotone restarting automata build a strict hierarchy whose top is characterized by the Church-Rosser languages and whose bottom is characterized by the deterministic context-free languages. It is shown that between nondeterministic pushdown automata and any level of the hierarchy there are savings in the size of description which cannot be bounded by any recursive function. Interestingly, the converse is also true for the Church-Rosser languages. Moreover, there are non-recursive trade-offs between the family of Church-Rosser languages and any other level of the hierarchy.