With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way ordered restarting automaton and its extended variant into devices that compute transductions of pictures, and we study the resulting classes of transductions in detail.
Accepté le :
DOI : 10.1051/ita/2016025
Mots-clés : Picture language, restarting automaton, transformation, rational function
@article{ITA_2016__50_4_351_0,
author = {Mr\'az, Franti\v{s}ek and Otto, Friedrich and Pr\r{u}\v{s}a, Daniel},
title = {Some classes of rational functions for pictures},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {351--369},
publisher = {EDP-Sciences},
volume = {50},
number = {4},
year = {2016},
doi = {10.1051/ita/2016025},
mrnumber = {3614550},
zbl = {1362.68152},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2016025/}
}
TY - JOUR AU - Mráz, František AU - Otto, Friedrich AU - Průša, Daniel TI - Some classes of rational functions for pictures JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2016 SP - 351 EP - 369 VL - 50 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2016025/ DO - 10.1051/ita/2016025 LA - en ID - ITA_2016__50_4_351_0 ER -
%0 Journal Article %A Mráz, František %A Otto, Friedrich %A Průša, Daniel %T Some classes of rational functions for pictures %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2016 %P 351-369 %V 50 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2016025/ %R 10.1051/ita/2016025 %G en %F ITA_2016__50_4_351_0
Mráz, František; Otto, Friedrich; Průša, Daniel. Some classes of rational functions for pictures. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 351-369. doi : 10.1051/ita/2016025. http://www.numdam.org/articles/10.1051/ita/2016025/
A. Anselmo, D. Giammarresi and M. Madonia, From determinism to non-determinism in recognizable two-dimensional languages. In DLT 2007. In vol. 4588 of Lect. Notes Comput. Sci. Edited by T. Harju, J. Karhumäki and A. Lepistö. Springer, Heidelberg (2007) 36–47. | MR | Zbl
, and , A computational model for tiling recognizable two-dimensional languages. Theor. Comput. Sci. 410 (2009) 3520–3529. | DOI | MR | Zbl
and , Recognizable picture languages. Int. J. Pattern Recognition and Artificial Intelligence 6 (1992) 241–256. | DOI
D. Giammarresi and A. Restivo, Two-dimensional languages. In vol. 3 of Handbook of Formal Languages. Edited by G. Rozenberg and A. Salomaa. Springer, New York, NY, USA (1997) 215–267. | MR
R.C. Gonzalez and R.E. Woods, Digital Image Processing. Prentice-Hall, Englewood Cliffs, New Jersey, 3rd edition (2007).
, , and , On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 287–311. | MR | Zbl
K. Kwee and F. Otto, On some decision problems for stateless deterministic ordered restarting automata. In DCFS 2015, Proc. In vol. 9118 of Lect. Notes Comput. Sci. Edited by J. Shallit and A. Okhotin. Springer, Heidelberg (2015) 165–176. | MR
K. Kwee and F. Otto, On the effects of nondeterminism on ordered restarting automata. In SOFSEM 2016, Proc. In vol. 9587 of Lect. Notes Comput. Sci. Edited by R.M. Freivalds, G. Engels and B. Catania. Springer, Heidelberg (2016) 369–380. | MR
, and , Complexity of two-dimensional patterns. J. Stat. Phys. 91 (1998) 909–951. | DOI | MR | Zbl
F. Mráz and F. Otto, Extended two-way ordered restarting automata for picture languages. In LATA 2014. In vol. 8370 of Lect. Notes Comput. Sci. Edited by A.-H. Dediu, C. Martín-Vide, J.-L. Sierra-Rodríguez and B. Truthe. Springer, Heidelberg (2014) 541–552. | MR
F. Mráz and F. Otto, Ordered restarting automata for picture languages. In SOFSEM 2014, Proc. In vol. 8327 of Lect. Notes Comput. Sci. Edited by V. Geffert, B. Preneel, B. Rovan, J. Štuller and A. Min Tjoa. Springer, Heidelberg (2014) 431–442. | MR
F. Mráz, F. Otto and D. Průša, On a class of rational functions for pictures. In Seventh Workshop on Non-Classical Models of Automata and Applications (NCMA 2015), Proc. In vol. 318 of booksocg.at. Edited by R. Freund, M. Holzer, N. Moreira and R. Reis Oesterreichische Computer Gesellschaft, Wien (2015) 159–176.
F. Otto, On the descriptional complexity of deterministic ordered restarting automata. In DCFS 2014, Proc. In vol. 8614 of Lect. Notes Comput. Sci. Edited by H. Jürgensen, J. Karhumäki and A. Okhotin. Springer, Heidelberg (2014) 318–329.
F. Otto, Restarting automata for picture languages: A survey on recent developments. In CIAA 2014, Proc. In vol. 8587 of Lect. Notes Comput. Sci. Edited by M. Holzer and M. Kutrib. Springer, Heidelberg (2014) 16–41. | MR | Zbl
F. Otto and K. Kwee, Deterministic ordered restarting automata that compute functions. In DLT 2015, Proc. In vol. 9168 of Lect. Notes Comput. Sci. Edited by I. Potapov. Springer, Heidelberg (2015) 401–412. | MR
and , Deterministic ordered restarting automata for picture languages. Acta Informatica 52 (2015) 593–623. | DOI | MR | Zbl
and , Restarting tiling automata. Int. J. Found. Comput. Sci. 24 (2013) 863–878. | DOI | MR | Zbl
, and , Two-dimensional Sgraffito automata. RAIRO: ITA 48 (2014) 505–539. | MR | Zbl
Cité par Sources :
