Some classes of rational functions for pictures
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 4, pp. 351-369.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016025
Classification : 68Q45
Mots clés : Picture language, restarting automaton, transformation, rational function
Mráz, František 1 ; Otto, Friedrich 2 ; Průša, Daniel 3

1 Charles University, Faculty of Mathematics and Physics, Department of Computer Science, Malostranské nám. 25, 118 00 Praha 1, Czech Republic.
2 Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany.
3 Czech Technical University, Faculty of Electrical Engineering, Karlovo nám. 13, 121 35 Prague 2, Czech Republic.
@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://archive.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://archive.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://archive.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, Tome 50 (2016) no. 4, pp. 351-369. doi : 10.1051/ita/2016025. http://archive.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

A. Anselmo, D. Giammarresi and M. Madonia, A computational model for tiling recognizable two-dimensional languages. Theor. Comput. Sci. 410 (2009) 3520–3529. | DOI | MR | Zbl

D. Giammarresi and A. Restivo, 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).

P. Jančar, F. Mráz, M. Plátek and J. Vogel, 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

K. Lindgren, C. Moore and M. Nordahl, 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 books@ocg.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

F. Otto and F. Mráz, Deterministic ordered restarting automata for picture languages. Acta Informatica 52 (2015) 593–623. | DOI | MR | Zbl

D. Průša and F. Mráz, Restarting tiling automata. Int. J. Found. Comput. Sci. 24 (2013) 863–878. | DOI | MR | Zbl

D. Průša, F. Mráz and F. Otto, Two-dimensional Sgraffito automata. RAIRO: ITA 48 (2014) 505–539. | MR | Zbl

Cité par Sources :