Document Open Access Logo

The Aperiodic Domino Problem in Higher Dimension

Authors Antonin Callard , Benjamin Hellouin de Menibus

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.19.pdf
  • Filesize: 0.88 MB
  • 15 pages

Document Identifiers

Author Details

Antonin Callard
  • Université Paris-Saclay, ENS Paris-Saclay, Département Informatique, 91190 Gif-sur-Yvette, France
Benjamin Hellouin de Menibus
  • Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91400 Orsay, France

Acknowledgements

The authors are grateful to the three referees for their many remarks and improvements. The first author is grateful to the Excellence group for being such cheerful co-interns and friends.

Cite As Get BibTex

Antonin Callard and Benjamin Hellouin de Menibus. The Aperiodic Domino Problem in Higher Dimension. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.19

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.
[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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Subshift
  • periodicity
  • aperiodicity
  • domino problem
  • subshift of finite type
  • sofic subshift
  • effective subshift
  • tilings
  • computability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nathalie Aubrun and Mathieu Sablik. Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Mathematicae, 126:35-63, 2013. URL: https://doi.org/10.1007/s10440-013-9808-5.
  2. Robert Berger. The Undecidability of the Domino Problem. Number 66 in Memoirs of the American Mathematical Society. American Mathematical Society, 1966. Google Scholar
  3. Valérie Berthé and Michel Rigo. Combinatorics, Words and Symbolic Dynamics. Number 159 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2016. URL: https://doi.org/10.1017/CBO9781139924733.
  4. Antonin Callard and Pascal Vanier. Computational Characterization of Surface Entropies for ℤ² Subshifts of Finite Type. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 122:1-122:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.122.
  5. Bruno Durand, Andrei E. Romashchenko, and Alexander Shen. Effective closed subshifts in 1D can be implemented in 2D. In Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig, editors, Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, volume 6300 of Lecture Notes in Computer Science, pages 208-226. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15025-8_12.
  6. Shmuel Friedland. On the entropy of ℤ^d subshifts of finite type. Linear Algebra and its Applications, 252(1):199-220, 1997. URL: https://doi.org/10.1016/0024-3795(95)00676-1.
  7. Silvère Gangloff and Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. Discrete & Continuous Dynamical Systems - A, 39(4):1975-2000, 2019. URL: https://doi.org/10.3934/dcds.2019083.
  8. Anaël Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier. Aperiodic points in ℤ²-subshifts. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 128:1-128:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.128.
  9. David Harel. Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness. Journal of the ACM, 33(1):224-248, 1986. URL: https://doi.org/10.1145/4904.4993.
  10. Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones mathematicae, 176:131-167, 2008. URL: https://doi.org/10.1007/s00222-008-0161-7.
  11. Michael Hochman. On the automorphism groups of multidimensional shifts of finite type. Ergodic Theory and Dynamical Systems, 30:809-840, 2009. URL: https://doi.org/10.1017/S0143385709000248.
  12. Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics, 171(3):2011-2038, 2010. URL: https://doi.org/10.4007/annals.2010.171.2011.
  13. Konrad Jacobs and Michael Keane. 0-1-sequences of Toeplitz type. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 13(2):123-131, 1969. URL: https://doi.org/10.1007/BF00537017.
  14. Emmanuel Jeandel and Pascal Vanier. The Undecidability of the Domino Problem, pages 293-357. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-57666-0_6.
  15. Tom Meyerovitch. Growth-type invariants for ℤ^d subshifts of finite type and arithmetical classes of real numbers. Inventiones mathematicae, 184:567-589, 2011. URL: https://doi.org/10.1007/s00222-010-0296-1.
  16. Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d'Analyse Mathématique, 53(1):139-186, 1989. URL: https://doi.org/10.1007/BF02793412.
  17. Piergiorgio Odifreddi. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Elsevier, 1989. Google Scholar
  18. Ronnie Pavlov and Michael Schraudner. Entropies realizable by block gluing ℤ^d shifts of finite type. Journal d'Analyse Mathématique, 126(1):113-174, 2015. URL: https://doi.org/10.1007/s11854-015-0014-4.
  19. Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones mathematicae, 12:177-209, 1971. URL: https://doi.org/10.1007/BF01418780.
  20. Robert I. Soare. Turing Computability: Theory and Applications. Theory and Applications of Computability. Springer, 1st edition, 2016. URL: https://doi.org/10.1007/978-3-642-31933-4.
  21. Linda Brown Westrick. Seas of squares with sizes from a Π₁⁰ set. Israel Journal of Mathematics, 222:431-462, 2017. URL: https://doi.org/10.1007/s11856-017-1596-6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact