Abstrakt
Here we introduce and study cyclic extensions of deterministic Sgraffito automata and of deterministic two-dimensional two-way ordered restarting automata for picture languages. Such a cyclically extended automaton can move in a single step from the last column (or row) of a picture to the first column (or row).
For deterministic Sgraffito automata, we show that this cyclic extension does not increase the expressive power of the model, while for deterministic two-dimensional two-way restarting automata, the expressive power is strictly increased by allowing cyclic moves. In fact, for the latter automata, we take the number of allowed cyclic moves in any column or row as a parameter, and we show that already with a single cyclic move per column (or row) the deterministic two-dimensional extended two-way restarting automaton can be simulated.
On the other hand, we show that two cyclic moves per column or row already give the same expressive power as any finite number of cyclic moves. Finally, we show that for one-row pictures (that is, strings), already one cyclic move suffices.