2026-07-22T07:15:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15829 2024-03-06T10:56:17Z ddc:004 open_access

The Aperiodic Domino Problem in Higher Dimension Callard, Antonin Hellouin de Menibus, Benjamin Subshift periodicity aperiodicity domino problem subshift of finite type sofic subshift effective subshift tilings computability 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. [Grandjean et al., 2018] proved that this problem is co-recursively enumerable (Π₀¹-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (Σ₁¹-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonin Callard and Benjamin Hellouin de Menibus 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.19 urn:nbn:de:0030-drops-158296 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.19 eng https://creativecommons.org/licenses/by/4.0/legalcode