Affiliations: Fachbereich Mathematik/Informatik, Universität
Kassel, Germany | Charles University, Department of Computer Science,
Praha, Czech Republic. platek@ksi.ms.mff.cuni.cz
Note: [] Address for correspondence: Charles University, Faculty of
Mathematics and Physics, Department of Computer Science, Malostranské
nám. 25, 118 00 PRAHA 1, Czech Republic
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-monotone. Moreover, we present a
transformation of this kind of restarting automata into contextual grammars
with regular selection.
