The decidability equivalence for Schreier graphs of contracting self-similar groups
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Laurent Bartholdi, “Monadic second-order logic and the domino problem on self-similar graphs”, arXiv:2011.02735 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.