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

  • Laurent Bartholdi

    Universität des Saarlandes, Saarbrücken, Germany
Monadic second-order logic and the domino problem on self-similar graphs cover
Download PDF

This article is published open access under our Subscribe to Open model.

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.

Cite this article

Laurent Bartholdi, Monadic second-order logic and the domino problem on self-similar graphs. Groups Geom. Dyn. 16 (2022), no. 4, pp. 1423–1459

DOI 10.4171/GGD/689