Skip to Main content Skip to Navigation
Conference papers

The aperiodic Domino problem in higher dimension

Benjamin Hellouin de Menibus 1 Antonin Callard 1 
1 GALaC - Graphes, Algorithmes et Combinatoire
LISN - Laboratoire Interdisciplinaire des Sciences du Numérique, AAC - Algorithmes, Apprentissage et Calcul
Abstract : The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. [8] proved that this problem is co-recursively enumerable (Π 1 0-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (Σ 1 1-complete), in higher dimension: d ≥ 4 in the finite type case, d ≥ 3 for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2-and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
Complete list of metadata
Contributor : Benjamin Hellouin de Menibus Connect in order to contact the contributor
Submitted on : Monday, February 14, 2022 - 5:04:51 PM
Last modification on : Friday, August 5, 2022 - 9:27:32 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Benjamin Hellouin de Menibus, Antonin Callard. The aperiodic Domino problem in higher dimension. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Mar 2022, Marseille, France. pp.1-15, ⟨10.4230/LIPIcs.STACS.2022.18⟩. ⟨hal-03573476⟩



Record views


Files downloads