RAIRO-Theor. Inf. Appl.
Volume 52, Number 2-3-4, April–December 2018
8th Workshop on Non-classical Models of Automata and Applications (NCMA 2016)
|Page(s)||235 - 251|
|Published online||18 January 2019|
34109 Kassel, Germany.
2 Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 25 Prague 1, Czech Republic.
* Corresponding author: email@example.com
Here, we study the cyclic extensions of 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 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.
Mathematics Subject Classification: 68Q45
Key words: Picture language / Sgraffito automaton / restarting automaton / cyclic move operation
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.