Polyomino tilings, cellular automata and codicity

AbstractAs usual, a 4-connex finite part of Z2 is called a polyomino. Recognizing whether a given polyomino can be tiled by translated copies of tiles taken from a given family of polyominoes is obviously decidable. On the contrary, deciding whether a given set of polyominoes is a code has been shown to be undecidable (Beauquier and Nivat, 1993). In this paper, we define various classes of codes and study the complexity of tiling recognition for these classes and their mutual relations. Specially, we study the class of polyominoe families, which we call neighbourhood codes, which generate tilings which are recognizable by cellular automata using only neighbourhood relations. We prove that there exist codes which are not neighbourhood codes, and we give an example of such a code