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.
DOI : 10.1051/ita/2018018
Mots clés : Picture language, Sgraffito automaton, restarting automaton, cyclic move operation
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2018018/
[1] , and , From determinism to non-determinism in recognizable two-dimensional languages, in Proc. of DLT 2007, edited by , and . Vol. 4588 of Springer, Heidelberg (2007) 36–47 | MR | Zbl
[2] , and , Deterministic and unambiguous families within recognizable two-dimensional languages. 98 (2010) 143–166 | MR | Zbl
[3] and , Automata on a 2-dimensional tape, in Proc. of SWAT 1967. IEEE Computer Society, Washington, DC, USA (1967) 155–160
[4] and , Deterministically and sudoku-deterministically recognizable picture languages, in Preproc. of LATA 2007, Report 35/07, edited by , and . Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona (2007) 175–186
[5] and , Growing context-sensitive languages and Church-Rosser languages. 141 (1998) 1–36 | MR | Zbl
[6] , , and , Scanning pictures the boustrophedon way, in Proc. of 17th Intern. Workshop IWCIA – Combinatorial Image Analysis, edited by , and . Vol. of 9448 Springer, Heidelberg (2015) 202–216 | MR
[7] and , Recognizable picture languages. Int. J. Pattern Recogn. Artif. Intell. 6 (1992) 241–256 | DOI
[8] and , Two-dimensional languages. Vol. 3 of Handbook of Formal Languages, edited by and . Springer New York, NY, USA (1997) 215–267 | MR
[9] , One-tape, off-line Turing machine computations. Inform. Cont. 8 (1965) 553–578 | DOI | MR | Zbl
[10] , , and , Restarting automata, in Proc. of FCT’95, edited by . Vol. 965 of Springer, Heidelberg (1995) 283–292 | MR
[11] and , New results on alternating and non-deterministic two-dimensional finite-state automata, in Proc. of STACS 2001, edited by and . Vol. 2010 of Springer, Heidelberg 2001 396–406 | MR | Zbl
[12] , and , Complexity of two-dimensional patterns. J. Stat. Phys. 91 (1998) 909–951 | DOI | MR | Zbl
[13] and , Extended two-way ordered restarting automata for picture languages, in Proc. of LATA 2014, edited by , , , and . Vol. 8370 of Springer Heidelberg (2014) 541–552 | MR | Zbl
[14] and , Ordered restarting automata for picture languages, in Prof. of SOFSEM 2014, edited by , , , and . Vol. 8327 of Springer Heidelberg (2014) 431–442 | MR | Zbl
[15] , and uša, On a class of rational functions for pictures, in Proc. of Seventh Workshop on Non-Classical Models of Automata and Applications (NCMA 2015), edited by , , and . Vol. 318 of books@ocg.at.Oesterreichische Computer Gesellschaft Wien (2015) 159–176
[16] , and uša, Some classes of rational functions for pictures. RAIRO: ITA 50 (2016) 351–369 | Numdam | MR
[17] and , Deterministic ordered restarting automata for picture languages. 52 (2015) 593–623 | MR | Zbl
[18] and , Cyclically extended variants of Sgraffito and restarting automata for picture languages, in Proc. of Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016), edited by , , and . Vol. 321 of books@ocg.at.Oesterreichische Computer Gesellschaft Wien (2016) 259–273
[19] and , Restarting tiling automata, in Proc. of CIAA 2012, edited by and . Vol. 7381 of Springer Heidelberg (2012) 289–300 | MR | Zbl
[20] and , Two-dimensional Sgraffito automata, in Proc. of DLT 2012, edited by and . Vol. 7410 of Springer Heidelberg (2012) 251–262 | MR | Zbl
[21] and , Restarting tiling automata. Int. J. Found. Comput. Sci. 24 (2013) 863–878 | DOI | MR | Zbl
[22] , and , Comparing two-dimensional one-marker automata to Sgraffito automata, in Proc. of CIAA 2013, edited by . Vol. 7982 of Lect. Notes Comput. Sci. Springer, Heidelberg (2013) 268–279 | MR | Zbl
[23] , and , New results on deterministic Sgraffito automata, in Proc. of DLT 2013, edited by and . Vol. 7907 of Springer Heidelberg (2013) 409–419 | MR | Zbl
[24] , and , Two-dimensional Sgraffito automata. RAIRO: ITA 48 (2014) 505–539 | MR
Cité par Sources :
