Deterministic two-way restarting automata don't need auxiliary symbols if they are (right-, left-, or right-left-) monotone

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.