The Aperiodic Domino Problem in Higher Dimension
| Autor: | Callard, Antonin, Hellouin de Menibus, Benjamin |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
computability
Mathematics::Dynamical Systems Mathematics::Operator Algebras Subshift sofic subshift tilings periodicity Nonlinear Sciences::Cellular Automata and Lattice Gases domino problem Theory of computation ��� Models of computation aperiodicity Theory of computation ��� Problems reductions and completeness Computer Science::Formal Languages and Automata Theory subshift of finite type effective subshift |
| DOI: | 10.4230/lipics.stacs.2022.19 |
| Popis: | 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. LIPIcs, Vol. 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), pages 19:1-19:15 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|