Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 7 min ago
Peer-reviewedCC BYGroups, Geometry, and Dynamics

Monadic second-order logic and the domino problem on self-similar graphs

  • Laurent Bartholdi
Open at sourcePDFDOICite

Abstract

We consider the domino problem on Schreier graphs of self-similar groups, and more generally their monadic second-order logic. On the one hand, we prove that if the group is bounded, then the domino problem on the graph is decidable; furthermore, under an ultimate periodicity condition, all its monadic second-order logic is decidable. This covers, for example, the Sierpiński gasket graphs and the Schreier graphs of the Basilica group. On the other hand, we prove undecidability of the domino problem for a class of self-similar groups, answering a question by Barbieri and Sablik, and study some examples including one of linear growth.

Related

  1. Monadic Second-Order Logic in HOL: Deep and Shallow with Automated Faithfulness (Extended Preprint)
    Christoph Benzmueller, Daniel Kirchner
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  2. Degree similar and net-degree similar signed graphs
    Matteo Cavaleri, Alfredo Donno
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On the horizon problem over the product of self-similar fractals
    Gurubachan, S. Verma, V. V. M. S. Chandramouli
    arXivPreprintCC BY 4.0Full textDynamical systemsarXiv
  4. Planar graphs whose second largest eigenvalue does not exceed 1
    Zihao Geng, Zhiwen Wang, Wen-Jun Li +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The second reconstruction transition for random graphs from 2-neighborhoods
    Yiming Chen
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@article{bartholdi2026monadic,
  title = {{Monadic second-order logic and the domino problem on self-similar graphs}},
  author = {Laurent Bartholdi},
  journal = {Groups, Geometry, and Dynamics},
  year = {2026},
  month = nov,
  doi = {10.4171/ggd/689},
  url = {https://hal.science/hal-05849727v1},
  note = {CC BY},
}
RIS
TY  - JOUR
TI  - Monadic second-order logic and the domino problem on self-similar graphs
AU  - Laurent Bartholdi
PY  - 2026
DA  - 2026/11/03
JO  - Groups, Geometry, and Dynamics
DO  - 10.4171/ggd/689
UR  - https://hal.science/hal-05849727v1
AB  - We consider the domino problem on Schreier graphs of self-similar groups, and more generally their monadic second-order logic. On the one hand, we prove that if the group is bounded, then the domino problem on the graph is decidable; furthermore, under an ultimate periodicity condition, all its monadic second-order logic is decidable. This covers, for example, the Sierpiński gasket graphs and the Schreier graphs of the Basilica group. On the other hand, we prove undecidability of the domino problem for a class of self-similar groups, answering a question by Barbieri and Sablik, and study some examples including one of linear growth.
SN  - 1661-7207
SN  - 1661-7215
ER  -