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 words is not a code then the words can be expressed as a product of at most 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 ( 1 or 1 rectangles).
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita:2007018/
[1] Polyomino tilings, cellular automata and codicity. Theoret. Comput. Sci. 147 (1995) 165-180. | Zbl
, and ,[2] A codicity undecidable problem in the plane. Theoret. Comput. Sci. 303 (2003) 417-430. | Zbl
, and ,[3] Theory of Codes. Academic Press (1985). | MR | Zbl
, and ,[4] Cumulative defect. Theoret. Comput. Sci. 292 (2003) 97-109. | Zbl
,[5] Many aspects of the defect effect. Theoret. Comput. Sci. 324 (2004) 35-54. | Zbl
, and ,[6] Some open problems in combinatorics of words and related areas. TUCS Technical Report 359 (2000). | MR
,[7] Defect Theorems for Trees. Fund. Inform. 38 (1999) 119-133. | Zbl
, and ,[8] Multiple factorizations of words and defect effect. Theoret. Comput. Sci. 273 (2002) 81-97. | Zbl
, and ,[9] A defect theorem for bi-infinite words. Theoret. Comput. Sci. 292 (2003) 237-243. | Zbl
, , and ,[10] Combinatorics on Words. Cambridge University Press (1997). | MR | Zbl
,[11] Algebraic Combinatorics on Words. Cambridge University Press (2002). | MR | Zbl
,[12] Codes and equations on trees. Theoret. Comput. Sci. 255 (2001) 483-509. | Zbl
, and :[13] Defect Effect of Bi-infinite Words in the Two-element Case. Discrete Math. Theor. Comput. Sci. 4 (2001) 273-290. | Zbl
,[14] Algebraic and algorithmic properties of brick codes. Ph.D. Thesis, Jagiellonian University, Poland (2000).
,[15] Brick codes: families, properties, relations. Intern. J. Comput. Math. 74 (2000) 133-150. | Zbl
,[16] Decidability of simple brick codes, in Mathematics and Computer Science III (Algorithms, Trees, Combinatorics and Probabilities), Trends in Mathematics. Birkhäuser (2004). | MR | Zbl
, and ,[17] Some open problems in decidability of brick (labelled polyomino) codes, in Cocoon 2004 Proceedings. Lect. Notes Comput. Sci. 3106 (2004) 72-81. | Zbl
, and ,Cité par Sources :