Document Open Access Logo

The Domino Problem is Undecidable on Surface Groups

Authors Nathalie Aubrun, Sebastián Barbieri , Etienne Moutot

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.46.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Nathalie Aubrun
  • LIP, ENS de Lyon - CNRS - UCBL - Université de Lyon, France
Sebastián Barbieri
  • University of British Columbia, Vancouver, Canada
Etienne Moutot
  • LIP, ENS de Lyon - CNRS - UCBL - Université de Lyon, France
  • University of Turku, Finland

Funding

This work was partially supported by the ANR project CoCoGro (ANR-16-CE40-0005).

Cite AsGet BibTex

Nathalie Aubrun, Sebastián Barbieri, and Etienne Moutot. The Domino Problem is Undecidable on Surface Groups. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.46

Abstract

We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientable surface of genus at least 2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • tilings
  • substitutions
  • SFTs
  • decidability
  • domino problem

Metrics

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

Related Versions

References

  1. Nathalie Aubrun and Jarkko Kari. Tiling Problems on Baumslag-Solitar groups. In MCU'13, pages 35-46, 2013. Google Scholar
  2. Alexis Ballier and Emmanuel Jeandel. Tilings and model theory. First Symposium on Cellular Automata Journées Automates Cellulaires., 2008. Google Scholar
  3. Alexis Ballier and Maya Stein. The domino problem on groups of polynomial growth. Groups, Geometry, and Dynamics, 12(1):93-105, March 2018. URL: https://doi.org/10.4171/ggd/439.
  4. Sebastián Barbieri and Mathieu Sablik. The Domino Problem for Self-similar Structures. In Pursuit of the Universal, pages 205-214. Springer International Publishing, 2016. URL: https://doi.org/10.1007/978-3-319-40189-8_21.
  5. Robert Berger. The Undecidability of the Domino Problem. PhD thesis, Harvard University, 1964. Google Scholar
  6. Valérie Berthé and Michel Rigo, editors. Sequences, Groups, and Number Theory. Springer International Publishing, 2018. URL: https://doi.org/10.1007/978-3-319-69152-7.
  7. Brian H. Bowditch. Cut points and canonical splittings of hyperbolic groups. Acta Mathematica, 180(2):145-186, 1998. URL: https://doi.org/10.1007/bf02392898.
  8. Vaughn Climenhaga and Anatole Katok. From Groups to Geometry and Back (Student Mathematical Library). American Mathematical Society, 2017. Google Scholar
  9. David Cohen and Chaim Goodman-Strauss. Strongly aperiodic subshifts on surface groups. Groups, Geometry, and Dynamics, 11(3):1041-1059, 2017. URL: https://doi.org/10.4171/ggd/421.
  10. David Bruce Cohen. The large scale geometry of strongly aperiodic subshifts of finite type. Advances in Mathematics, 308:599-626, 2017. Google Scholar
  11. Martin J. Dunwoody. The accessibility of finitely presented groups. Inventiones Mathematicae, 81(3):449-457, October 1985. URL: https://doi.org/10.1007/bf01388581.
  12. Chaim Goodman-Strauss. A hierarchical strongly aperiodic set of tiles in the hyperbolic plane. Theoretical Computer Science, 411(7):1085-1093, 2010. URL: https://doi.org/10.1016/j.tcs.2009.11.018.
  13. Emmanuel Jeandel. Aperiodic Subshifts on Polycyclic Groups. CoRR, abs/1510.02360, 2015. URL: http://arxiv.org/abs/1510.02360.
  14. Emmanuel Jeandel. Translation-like Actions and Aperiodic Subshifts on Groups. CoRR, abs/1508.06419, 2015. URL: http://arxiv.org/abs/1508.06419.
  15. Jarkko Kari. On the Undecidability of the Tiling Problem. In Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 74-82, 2008. Google Scholar
  16. Abraham Karrass, Alfred Pietrowski, and Donald Solitar. Finite and infinite cyclic extensions of free groups. Journal of the Australian Mathematical Society, 16(04):458, December 1973. URL: https://doi.org/10.1017/s1446788700015445.
  17. Dietrich Kuske and Markus Lohrey. Logical aspects of Cayley-graphs: the group case. Annals of Pure and Applied Logic, 131(1-3):263-286, 2005. URL: https://doi.org/10.1016/j.apal.2004.06.002.
  18. Douglas A Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995. Google Scholar
  19. Maurice Margenstern. The domino problem of the hyperbolic plane is undecidable. Theoretical Computer Science, 407(1-3):29-84, November 2008. URL: https://doi.org/10.1016/j.tcs.2008.04.038.
  20. David E. Muller and Paul E. Schupp. The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science, 37(0):51-75, 1985. URL: https://doi.org/10.1016/0304-3975(85)90087-8.
  21. Raphael M Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12:177-209, 1971. Google Scholar
  22. Hao Wang. Proving theorems by pattern recognition II. Bell System Technical Journal, 40(1-3):1-41, 1961. Google Scholar
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 Imprint Privacy Contact