Monotone deterministic RL-automata don't need auxiliary symbols.

Abstrakt

It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-, left-, or right-left-monotone. Actually in these cases it suffices to admit delete operations instead of the more general rewrite operations.

In addition, we characterize the class of languages that are accepted by left-monotone deterministic two-way restarting automata by a combination of deterministic pushdown automata and deterministic generalized sequential machines.