Picture codes

Symeon Bozapalidis; Archontia Grammatikopoulou

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 4, page 537-550
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Bozapalidis, Symeon, and Grammatikopoulou, Archontia. "Picture codes." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 537-550. <http://eudml.org/doc/249714>.

@article{Bozapalidis2006,
abstract = { 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. },
author = {Bozapalidis, Symeon, Grammatikopoulou, Archontia},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Picture codes; picture series.; picture series},
language = {eng},
month = {11},
number = {4},
pages = {537-550},
publisher = {EDP Sciences},
title = {Picture codes},
url = {http://eudml.org/doc/249714},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Bozapalidis, Symeon
AU - Grammatikopoulou, Archontia
TI - Picture codes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 4
SP - 537
EP - 550
AB - 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.
LA - eng
KW - Picture codes; picture series.; picture series
UR - http://eudml.org/doc/249714
ER -

References

top
  1. P. Aigrain and D. Beauquier, Polyomino Tiling, Cellular Automata and Codicity. Theoret. Comput. Sci.147 (1995) 165–180.  
  2. D. Beauquier and M. Nivat, A Codicity Undecidable Problem in the Plane. Theoret. Comput. Sci.303 (2003) 417–430.  
  3. J. Berstel and D. Perrin. Theory of Codes. Academic Press, New York (1985).  
  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.  
  7. M. Latteux and D. Simplot, Context-Sensitive String Languages and Recognizable Picture Languages. Inform. Comput.138 (1997) 160–169.  
  8. M. Latteux and D. Simplot, Recognizable Picture Languages and Domino Tiling. Theoret. Comput. Sci.178 (1997) 275–283.  
  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).  
  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.  
  13. R. Siromoney, V.R. Dare and K.G. Subramanian, Infinite Arrays and Infinite Computations. Theoret. Comput. Sci.24 (1983) 195–205.  
  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.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.