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 of pictures a picture code which is the basis of the least DR-monoid including . A weak version of the defect theorem for pictures is established. A characterization of picture codes through picture series is also given.
@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] Polyomino Tiling, Cellular Automata and Codicity. Theoret. Comput. Sci. 147 (1995) 165-180. | Zbl
and ,[2] A Codicity Undecidable Problem in the Plane. Theoret. Comput. Sci. 303 (2003) 417-430. | Zbl
and ,[3] Theory of Codes. Academic Press, New York (1985). | MR | Zbl
and .[4] Recognizable Picture Series. J. Automat. Combin. 10 (2005) 159-183.
and ,[5] Two-Dimensional Languages, in Handbook Formal Languages, Beyond Words, edited by G. Rozenberg and A. Salomaa. Springer 3 (1997) 215-267,
and .[6] Finite Codes over Free Binoids. J. Automat. Languages Combin. 7 (2002) 505-518. | Zbl
, and ,[7] Context-Sensitive String Languages and Recognizable Picture Languages. Inform. Comput. 138 (1997) 160-169. | Zbl
and ,[8] Recognizable Picture Languages and Domino Tiling. Theoret. Comput. Sci. 178 (1997) 275-283. | Zbl
and ,[9] Regular Expressions and Context-free Grammars for Picture Languages, in Proc. STACS'97-LNCS. Springer-Verlag 1200 (1997) 283-294.
,[10] 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] 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] A Characterization of Recognizable Picture Languages by Tilings by Finite Sets. Theoret. Comput. Sci. 218 (1999) 297-323. | Zbl
,[13] Infinite Arrays and Infinite Computations. Theoret. Comput. Sci. 24 (1983) 195-205. | Zbl
, and ,[14] Infinite Arrays and Controlled Deterministic Table 0L Array Systems. Theoret. Comput. Sci. 33 (1984) 3-11. | Zbl
, and ,[15] 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 :