Geodesic
Monadic second-order logic and the domino problem on self-similar graphs
Laurent Bartholdi1 orcid
1Universität des Saarlandes, Saarbrücken, Germany
Groups, geometry, and dynamics, Tome 16 (2022) no. 4, pp. 1423-1459

Voir la notice de l'article provenant de la source EMS Press

DOI

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.
DOI : 10.4171/ggd/689
Classification : 03-XX, 05-XX, 20-XX
Mots-clés : Wang tiles, monadic second-order logic, self-similar graphs

Laurent Bartholdi  1

1 Universität des Saarlandes, Saarbrücken, Germany 
Laurent Bartholdi. Monadic second-order logic and the domino problem on self-similar graphs. Groups, geometry, and dynamics, Tome 16 (2022) no. 4, pp. 1423-1459. doi: 10.4171/ggd/689
@article{10_4171_ggd_689,
     author = {Laurent Bartholdi},
     title = {Monadic second-order logic and the domino problem on self-similar graphs},
     journal = {Groups, geometry, and dynamics},
     pages = {1423--1459},
     year = {2022},
     volume = {16},
     number = {4},
     doi = {10.4171/ggd/689},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/ggd/689/}
}
TY  - JOUR
AU  - Laurent Bartholdi
TI  - Monadic second-order logic and the domino problem on self-similar graphs
JO  - Groups, geometry, and dynamics
PY  - 2022
SP  - 1423
EP  - 1459
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4171/ggd/689/
DO  - 10.4171/ggd/689
ID  - 10_4171_ggd_689
ER  - 
%0 Journal Article
%A Laurent Bartholdi
%T Monadic second-order logic and the domino problem on self-similar graphs
%J Groups, geometry, and dynamics
%D 2022
%P 1423-1459
%V 16
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4171/ggd/689/
%R 10.4171/ggd/689
%F 10_4171_ggd_689

Cité par Sources :