Defect theorem in the plane
Moczurad, Włodzimierz
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 403-409 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We consider the defect theorem in the context of labelled polyominoes, i.e., two-dimensional figures. The classical version of this property states that if a set of n words is not a code then the words can be expressed as a product of at most n-1 words, the smaller set being a code. We survey several two-dimensional extensions exhibiting the boundaries where the theorem fails. In particular, we establish the defect property in the case of three dominoes (n × 1 or 1 × n rectangles).

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007018
Classification:  68Q70,  68R15 
@article{ITA_2007__41_4_403_0,
     author = {Moczurad, W\l odzimierz},
     title = {Defect theorem in the plane},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {41},
     year = {2007},
     pages = {403-409},
     doi = {10.1051/ita:2007018},
     zbl = {pre05301988},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_4_403_0}
}

Moczurad, Włodzimierz. Defect theorem in the plane. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 403-409. doi : 10.1051/ita:2007018. http://gdmltest.u-ga.fr/item/ITA_2007__41_4_403_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). | MR 797069 | Zbl 0587.68066

[4] V. Bruyère, Cumulative defect. Theoret. Comput. Sci. 292 (2003) 97-109. | Zbl 1063.68080

[5] T. Harju, and J. Karhumäki, Many aspects of the defect effect. Theoret. Comput. Sci. 324 (2004) 35-54. | Zbl 1078.68083

[6] J. Karhumäki, Some open problems in combinatorics of words and related areas. TUCS Technical Report 359 (2000). | MR 1805376

[7] J. Karhumäki, and S. Mantaci, Defect Theorems for Trees. Fund. Inform. 38 (1999) 119-133. | Zbl 0935.68083

[8] J. Karhumäki, and J. Maňuch, Multiple factorizations of words and defect effect. Theoret. Comput. Sci. 273 (2002) 81-97. | Zbl 0996.68145

[9] J. Karhumäki, J. Maňuch, and W. Plandowski, A defect theorem for bi-infinite words. Theoret. Comput. Sci. 292 (2003) 237-243. | Zbl 1063.68069

[10] M. Lothaire, Combinatorics on Words. Cambridge University Press (1997). | MR 1475463 | Zbl 0874.20040

[11] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093

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

[13] J. Maňuch, Defect Effect of Bi-infinite Words in the Two-element Case. Discrete Math. Theor. Comput. Sci. 4 (2001) 273-290. | Zbl 0981.68124

[14] W. Moczurad, Algebraic and algorithmic properties of brick codes. Ph.D. Thesis, Jagiellonian University, Poland (2000).

[15] W. Moczurad, Brick codes: families, properties, relations. Intern. J. Comput. Math. 74 (2000) 133-150. | Zbl 1094.68577

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

[17] 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