×

Defect theorem in the plane. (English) Zbl 1144.68048

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

MSC:

68R15 Combinatorics on words
05B50 Polyominoes
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML

References:

[1] P. Aigrain , and D. Beauquier , Polyomino tilings, cellular automata and codicity . Theoret. Comput. Sci. 147 ( 1995 ) 165 - 180 . Zbl 0873.68139 · 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 · Zbl 1053.68067
[3] J. Berstel , and D. Perrin , Theory of Codes . Academic Press ( 1985 ). MR 797069 | Zbl 0587.68066 · Zbl 0587.68066
[4] V. Bruyère , Cumulative defect . Theoret. Comput. Sci. 292 ( 2003 ) 97 - 109 . Zbl 1063.68080 · 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 · Zbl 1078.68083
[6] J. Karhumäki , Some open problems in combinatorics of words and related areas . TUCS Technical Report 359 ( 2000 ). MR 1805376 · Zbl 0969.68528
[7] J. Karhumäki , and S. Mantaci , Defect Theorems for Trees . Fund. Inform. 38 ( 1999 ) 119 - 133 . Zbl 0935.68083 · 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 · 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 · Zbl 1063.68069
[10] M. Lothaire , Combinatorics on Words . Cambridge University Press ( 1997 ). MR 1475463 | Zbl 0874.20040 · Zbl 0874.20040
[11] M. Lothaire , Algebraic Combinatorics on Words . Cambridge University Press ( 2002 ). MR 1905123 | Zbl 1001.68093 · Zbl 1001.68093
[12] S. Mantaci , and A. Restivo : Codes and equations on trees . Theoret. Comput. Sci. 255 ( 2001 ) 483 - 509 . Zbl 0974.68095 · 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 · Zbl 0981.68124
[14] W. Moczurad , Algebraic and algorithmic properties of brick codes . Ph.D. Thesis, Jagiellonian University, Poland ( 2000 ). · Zbl 1094.68577
[15] W. Moczurad , Brick codes: families, properties, relations . Intern. J. Comput. Math. 74 ( 2000 ) 133 - 150 . Zbl 1094.68577 · 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 · 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 · Zbl 1091.05016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.