RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

| Abstract | PDF (112.7 KB) | References |

Theoret. Informatics Appl. 41, 403-409 (2007)
DOI: 10.1051/ita:2007018

Defect theorem in the plane

Wlodzimierz Moczurad

Institute of Computer Science, Jagiellonian University, Nawojki 11, 30-072 Kraków, Poland; wkm@ii.uj.edu.pl

(Received January 16, 2006. Accepted December 7, 2006. Published online 17 August 2007.)

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

Mathematics Subject Classification. 68Q70, 68R15

Key words: Defect theorem -- codes -- polyominoes

© EDP Sciences 2007