Non-Recursive Trade-Offs for Deterministic Restarting Automata

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.