Voir la notice de l'article provenant de la source Numdam
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.
Otto, Friedrich 1 ; Mráz, František 1
@article{ITA_2018__52_2-3-4_235_0,
author = {Otto, Friedrich and Mr\'az, Franti\v{s}ek},
editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
title = {Automata with cyclic move operations for picture languages},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {235--251},
publisher = {EDP-Sciences},
volume = {52},
number = {2-3-4},
year = {2018},
doi = {10.1051/ita/2018018},
mrnumber = {3915311},
zbl = {1423.68263},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018018/}
}
TY - JOUR AU - Otto, Friedrich AU - Mráz, František ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - Automata with cyclic move operations for picture languages JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 235 EP - 251 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018018/ DO - 10.1051/ita/2018018 LA - en ID - ITA_2018__52_2-3-4_235_0 ER -
%0 Journal Article %A Otto, Friedrich %A Mráz, František %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T Automata with cyclic move operations for picture languages %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 235-251 %V 52 %N 2-3-4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018018/ %R 10.1051/ita/2018018 %G en %F ITA_2018__52_2-3-4_235_0
Otto, Friedrich; Mráz, František. Automata with cyclic move operations for picture languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 235-251. doi: 10.1051/ita/2018018
Cité par Sources :