Picture codes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 537-550.

We introduce doubly-ranked (DR) monoids in order to study picture codes. We show that a DR-monoid is free iff it is pictorially stable. This allows us to associate with a set C of pictures a picture code B(C) which is the basis of the least DR-monoid including C. A weak version of the defect theorem for pictures is established. A characterization of picture codes through picture series is also given.

DOI : 10.1051/ita:2006038
Classification : 94B60
Mots-clés : picture codes, picture series 
@article{ITA_2006__40_4_537_0,
     author = {Bozapalidis, Symeon and Grammatikopoulou, Archontia},
     title = {Picture codes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {537--550},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {4},
     year = {2006},
     doi = {10.1051/ita:2006038},
     mrnumber = {2277047},
     zbl = {1117.94015},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2006038/}
}
TY  - JOUR
AU  - Bozapalidis, Symeon
AU  - Grammatikopoulou, Archontia
TI  - Picture codes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 537
EP  - 550
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006038/
DO  - 10.1051/ita:2006038
LA  - en
ID  - ITA_2006__40_4_537_0
ER  - 
%0 Journal Article
%A Bozapalidis, Symeon
%A Grammatikopoulou, Archontia
%T Picture codes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 537-550
%V 40
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2006038/
%R 10.1051/ita:2006038
%G en
%F ITA_2006__40_4_537_0
Bozapalidis, Symeon; Grammatikopoulou, Archontia. Picture codes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 537-550. doi : 10.1051/ita:2006038. http://www.numdam.org/articles/10.1051/ita:2006038/

[1] P. Aigrain and D. Beauquier, Polyomino Tiling, Cellular Automata and Codicity. Theoret. Comput. Sci. 147 (1995) 165-180. | Zbl

[2] D. Beauquier and M. Nivat, A Codicity Undecidable Problem in the Plane. Theoret. Comput. Sci. 303 (2003) 417-430. | Zbl

[3] J. Berstel and D. Perrin. Theory of Codes. Academic Press, New York (1985). | MR | Zbl

[4] S. Bozapalidis and A. Grammatikopoulou, Recognizable Picture Series. J. Automat. Combin. 10 (2005) 159-183.

[5] D. Giammarresi and A. Restivo. Two-Dimensional Languages, in Handbook Formal Languages, Beyond Words, edited by G. Rozenberg and A. Salomaa. Springer 3 (1997) 215-267,

[6] K. Hashiguchi, T. Kundi and S. Jimbo, Finite Codes over Free Binoids. J. Automat. Languages Combin. 7 (2002) 505-518. | Zbl

[7] M. Latteux and D. Simplot, Context-Sensitive String Languages and Recognizable Picture Languages. Inform. Comput. 138 (1997) 160-169. | Zbl

[8] M. Latteux and D. Simplot, Recognizable Picture Languages and Domino Tiling. Theoret. Comput. Sci. 178 (1997) 275-283. | Zbl

[9] O. Matz, Regular Expressions and Context-free Grammars for Picture Languages, in Proc. STACS'97-LNCS. Springer-Verlag 1200 (1997) 283-294.

[10] O. Matz, On Piecewise Testable, Starfree and Recognizable Picture Languages, in Foundations of Software Science and Computation Structures, edited by M. Nivat. Springer-Verlag, Berlin 1378 (1998). | MR

[11] K. Reinhard, On some Recognizable Picture-languages, in Mathematical Foundations of Computer Science edited by L. Brim, J. Gruska and J. Zlatuška. Lect. Notes Comput. Sci. 1450 (1998) 760-770.

[12] D. Simplot, A Characterization of Recognizable Picture Languages by Tilings by Finite Sets. Theoret. Comput. Sci. 218 (1999) 297-323. | Zbl

[13] R. Siromoney, V.R. Dare and K.G. Subramanian, Infinite Arrays and Infinite Computations. Theoret. Comput. Sci. 24 (1983) 195-205. | Zbl

[14] R. Siromoney, K.G. Subramanian and V.R. Dare, Infinite Arrays and Controlled Deterministic Table 0L Array Systems. Theoret. Comput. Sci. 33 (1984) 3-11. | Zbl

[15] T. Wilke, Star-free Picture Expressions Are Strictly Weaker Than First-order Logic, in Proc. ICALP'97-LNCS. Springer-Verlag (1997) 1256 347-357.

Cité par Sources :