Defect theorem in the plane

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

Received: 16 January 2006
Accepted: 7 December 2006

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