Defect theorem in the plane

Włodzimierz Moczurad

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 4, page 403-409
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Moczurad, Włodzimierz. "Defect theorem in the plane." RAIRO - Theoretical Informatics and Applications 41.4 (2007): 403-409. <http://eudml.org/doc/250043>.

@article{Moczurad2007,
abstract = { 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). },
author = {Moczurad, Włodzimierz},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Defect theorem; codes; polyominoes; labelled polyominoes},
language = {eng},
month = {8},
number = {4},
pages = {403-409},
publisher = {EDP Sciences},
title = {Defect theorem in the plane},
url = {http://eudml.org/doc/250043},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Moczurad, Włodzimierz
TI - Defect theorem in the plane
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/8//
PB - EDP Sciences
VL - 41
IS - 4
SP - 403
EP - 409
AB - 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).
LA - eng
KW - Defect theorem; codes; polyominoes; labelled polyominoes
UR - http://eudml.org/doc/250043
ER -

References

top
  1. P. Aigrain, and D. Beauquier, Polyomino tilings, cellular automata and codicity. Theoret. Comput. Sci.147 (1995) 165–180.  
  2. D. Beauquier, and M. Nivat, A codicity undecidable problem in the plane. Theoret. Comput. Sci.303 (2003) 417–430.  
  3. J. Berstel, and D. Perrin, Theory of Codes. Academic Press (1985).  
  4. V. Bruyère, Cumulative defect. Theoret. Comput. Sci.292 (2003) 97–109.  
  5. T. Harju, and J. Karhumäki, Many aspects of the defect effect. Theoret. Comput. Sci.324 (2004) 35–54.  
  6. J. Karhumäki, Some open problems in combinatorics of words and related areas. TUCS Technical Report359 (2000).  
  7. J. Karhumäki, and S. Mantaci, Defect Theorems for Trees. Fund. Inform.38 (1999) 119–133.  
  8. J. Karhumäki, and J. Maňuch, Multiple factorizations of words and defect effect. Theoret. Comput. Sci.273 (2002) 81–97.  
  9. J. Karhumäki, J. Maňuch, and W. Plandowski, A defect theorem for bi-infinite words. Theoret. Comput. Sci.292 (2003) 237–243.  
  10. M. Lothaire, Combinatorics on Words. Cambridge University Press (1997).  
  11. M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002).  
  12. S. Mantaci, and A. Restivo: Codes and equations on trees. Theoret. Comput. Sci.255 (2001) 483–509.  
  13. J. Maňuch, Defect Effect of Bi-infinite Words in the Two-element Case. Discrete Math. Theor. Comput. Sci.4 (2001) 273–290.  
  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.  
  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).  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.