Picture codes
Symeon Bozapalidis; Archontia Grammatikopoulou
RAIRO - Theoretical Informatics and Applications (2006)
- Volume: 40, Issue: 4, page 537-550
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topBozapalidis, 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- P. Aigrain and D. Beauquier, Polyomino Tiling, Cellular Automata and Codicity. Theoret. Comput. Sci.147 (1995) 165–180.
- D. Beauquier and M. Nivat, A Codicity Undecidable Problem in the Plane. Theoret. Comput. Sci.303 (2003) 417–430.
- J. Berstel and D. Perrin. Theory of Codes. Academic Press, New York (1985).
- S. Bozapalidis and A. Grammatikopoulou, Recognizable Picture Series. J. Automat. Combin.10 (2005) 159–183.
- 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,
- K. Hashiguchi, T. Kundi and S. Jimbo, Finite Codes over Free Binoids. J. Automat. Languages Combin.7 (2002) 505–518.
- M. Latteux and D. Simplot, Context-Sensitive String Languages and Recognizable Picture Languages. Inform. Comput.138 (1997) 160–169.
- M. Latteux and D. Simplot, Recognizable Picture Languages and Domino Tiling. Theoret. Comput. Sci.178 (1997) 275–283.
- O. Matz, Regular Expressions and Context-free Grammars for Picture Languages, in Proc. STACS'97-LNCS. Springer-Verlag 1200 (1997) 283–294.
- 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).
- 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.
- D. Simplot, A Characterization of Recognizable Picture Languages by Tilings by Finite Sets. Theoret. Comput. Sci.218 (1999) 297–323.
- R. Siromoney, V.R. Dare and K.G. Subramanian, Infinite Arrays and Infinite Computations. Theoret. Comput. Sci.24 (1983) 195–205.
- 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.
- 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.