Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1877

Preprint Number 1877

Previous Next Preprint server

1877. Laurent Bartholdi
Monadic second-order logic and the domino problem on self-similar graphs

Submission date: 5 November 2020


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 graph's 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 already prove undecidability of the domino problem for a class of self-similar groups, answering a question by Barbieri and Sablik, and some examples including one of linear growth.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2011.02735: pdf, ps.

Last updated: March 23 2021 09:21 Please send your corrections to: