Defect theorem in the plane

Moczurad, Włodzimierz

doi:10.1051/ita:2007018

Moczurad, Włodzimierz

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

Résumé

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$ $\times$ 1 or 1 $\times$ $n$ rectangles).

DOI : 10.1051/ita:2007018

Classification : 68Q70, 68R15
Mots clés : defect theorem, codes, polyominoes

@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},
     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
AU  - Moczurad, Włodzimierz
TI  - Defect theorem in the plane
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 403
EP  - 409
VL  - 41
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007018/
DO  - 10.1051/ita:2007018
LA  - en
ID  - ITA_2007__41_4_403_0
ER  -

%0 Journal Article
%A Moczurad, Włodzimierz
%T Defect theorem in the plane
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 403-409
%V 41
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007018/
%R 10.1051/ita:2007018
%G en
%F 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) no. 4, pp. 403-409. doi : 10.1051/ita:2007018. http://www.numdam.org/articles/10.1051/ita:2007018/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

[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

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

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

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

[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

[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

[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 | Zbl

[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

Cité par Sources :