Restarting automata and combinations of constraints

Abstrakt

Recently, j-left, j-right- and j-right-left-monotone restarting automata (j>=1) have been studied. We introduce combinations of these degrees of monotonicity (together with their strong variants).

Concentrating on deterministic restarting automata, we show some interesting differences between one-way and two-way restarting automata with respect to several combinations of degrees of monotonicity.