The code problem for directed figures
Kolarz, Michał
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 489-506 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2011005
Classification:  68R15,  68R99 
@article{ITA_2010__44_4_489_0,
     author = {Kolarz, Micha\l },
     title = {The code problem for directed figures},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {489-506},
     doi = {10.1051/ita/2011005},
     mrnumber = {2775408},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2010__44_4_489_0}
}

Kolarz, Michał. The code problem for directed figures. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 489-506. doi : 10.1051/ita/2011005. http://gdmltest.u-ga.fr/item/ITA_2010__44_4_489_0/

[1] P. Aigrain and D. Beauquier, Polyomino tilings, cellular automata and codicity. Theoret. Comput. Sci. 147 (1995) 165-180. | Zbl 0873.68139

[2] D. Beauquier and M. Nivat, A codicity undecidable problem in the plane. Theoret. Comput. Sci. 303 (2003) 417-430. | Zbl 1053.68067

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

[4] G. Costagliola, F. Ferrucci and C. Gravino, Adding symbolic information to picture models: definitions and properties. Theoret. Comput. Sci. 337 (2005) 51-104. | Zbl 1077.68041

[5] M. Kolarz and W. Moczurad, Directed figure codes are decidable. Discrete Mathematics and Theoretical Computer Science 11 (2009) 1-14. | Zbl 1193.68155

[6] S. Mantaci and A. Restivo, Codes and equations on trees. Theoret. Comput. Sci. 255 (2001) 483-509. | Zbl 0974.68095

[7] W. Moczurad, Defect theorem in the plane. RAIRO-Theor. Inf. Appl. 41 (2007) 403-409. | Zbl 1144.68048

[8] M. Moczurad and W. Moczurad, Decidability of simple brick codes, in Mathematics and Computer Science, Vol. III (Algorithms, Trees, Combinatorics and Probabilities). Trends in Mathematics, Birkhäuser (2004), 541-542. | Zbl 1094.68051

[9] M. Moczurad and W. Moczurad, Some open problems in decidability of brick (labelled polyomino) codes, in Cocoon 2004 Proceedings. Lect. Notes Comput. Sci. 3106 (2004) 72-81. | Zbl 1091.05016