Defect theorem in the plane
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 4, pp. 403-409.

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

DOI : https://doi.org/10.1051/ita:2007018
Classification : 68Q70,  68R15
Mots clés : defect theorem, codes, polyominoes
@article{ITA_2007__41_4_403_0,
title = {Defect theorem in the plane},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {403--409},
publisher = {EDP-Sciences},
volume = {41},
number = {4},
year = {2007},
doi = {10.1051/ita:2007018},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007018/}
}
TY  - JOUR
TI  - Defect theorem in the plane
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
DA  - 2007///
SP  - 403
EP  - 409
VL  - 41
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007018/
UR  - https://doi.org/10.1051/ita:2007018
DO  - 10.1051/ita:2007018
LA  - en
ID  - ITA_2007__41_4_403_0
ER  - 
Moczurad, Włodzimierz. Defect theorem in the plane. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 4, pp. 403-409. doi : 10.1051/ita:2007018. http://www.numdam.org/articles/10.1051/ita:2007018/

[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

Cité par Sources :