The decidability equivalence for Schreier graphs of contracting self-similar groups
Let be a contracting self-similar group. Its limit space is the associated limit space of the self-similar action, and a limit space is finitely ramified when it has finite ramification in the sense used for self-similar groups. The domino problem and the monadic second-order theory are considered on all Schreier graphs of .
Decidability equivalence. The following are equivalent:
- The domino problem is decidable on all Schreier graphs of .
- The monadic second-order theory is decidable on all Schreier graphs of .
- The limit space of is finitely ramified.
This conjecture proposes a precise equivalence between algorithmic tiling decidability, monadic second-order decidability, and finite ramification of the limit space for contracting self-similar groups. The supplied text gives no resolution, so the conjecture remains open.
References
Primary source
Laurent Bartholdi, “Monadic second-order logic and the domino problem on self-similar graphs”, arXiv:2011.02735 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.