Publication at Faculty of Mathematics and Physics |
2005
Abstract
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.