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},
year = {2006},
publisher = {EDP Sciences},
volume = {40},
number = {4},
doi = {10.1051/ita:2006038},
mrnumber = {2277047},
zbl = {1117.94015},
language = {en},
url = {https://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 - https://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 https://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
[1] and, Polyomino Tiling, Cellular Automata and Codicity. Theoret. Comput. Sci. 147 (1995) 165-180. | Zbl
[2] and, A Codicity Undecidable Problem in the Plane. Theoret. Comput. Sci. 303 (2003) 417-430. | Zbl
[3] and. Theory of Codes. Academic Press, New York (1985). | Zbl | MR
[4] and, Recognizable Picture Series. J. Automat. Combin. 10 (2005) 159-183.
[5] and. Two-Dimensional Languages, in Handbook Formal Languages, Beyond Words, edited by G. Rozenberg and A. Salomaa. Springer 3 (1997) 215-267,
[6] , and, Finite Codes over Free Binoids. J. Automat. Languages Combin. 7 (2002) 505-518. | Zbl
[7] and, Context-Sensitive String Languages and Recognizable Picture Languages. Inform. Comput. 138 (1997) 160-169. | Zbl
[8] and, Recognizable Picture Languages and Domino Tiling. Theoret. Comput. Sci. 178 (1997) 275-283. | Zbl
[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] , and, Infinite Arrays and Infinite Computations. Theoret. Comput. Sci. 24 (1983) 195-205. | Zbl
[14] , and, Infinite Arrays and Controlled Deterministic Table 0L Array Systems. Theoret. Comput. Sci. 33 (1984) 3-11. | Zbl
[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 :
