Polyomino tilings, cellular automata and codicity. (English) Zbl 0873.68139

Summary: As usual, a 4-connex finite part of \({\mathbb{Z}}^{2}\) 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). 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.


68Q80 Cellular automata (computational aspects)


Full Text: DOI


[1] Aigrain, P.; Nivat, M., A characterization of convex domino-tilable polyominoes by their diagonal sections, ()
[2] Beauquier, D., Undecidable problem about rational sets and contour words of polyominoes, Inform. process. lett., 37, 257-263, (1991) · Zbl 0714.68055
[3] Beauquier, D.; Nivat, M., Tiling pictures of the plane with two bars, a horizontal and a vertical one, () · Zbl 0754.05030
[4] Beauquier, D.; Nivat, M., Codicity and simplicity in the plane, () · Zbl 0754.05030
[5] Berger, R., Undecidability of the domino problem, () · Zbl 0199.30802
[6] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York · Zbl 1022.94506
[7] Chlebus, B., Domino-tiling games, J. comput. system sci., 32, 374-392, (1986) · Zbl 0618.68045
[8] Cosnard, M., Recouvrement de pièces trapézoïdales par H2 — V2, ()
[9] Freeman, H., Computer processing of line drawing images, Comput. surveys, 6, 57-98, (1974) · Zbl 0287.68067
[10] Giammaresi, D.; Restivo, A., Recognizable picture languages, ()
[11] Maire, O., Reconnaissance de recouvrements et génération d’images du plan, ()
[12] Robson, M., Le recouvrement d’une figure par Hm — vn est NP-complet, ()
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.