The decidability equivalence for Schreier graphs of contracting self-similar groups

About 6 years old · traced to

Let GG 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 GG.

Decidability equivalence. The following are equivalent:

  1. The domino problem is decidable on all Schreier graphs of GG.
  2. The monadic second-order theory is decidable on all Schreier graphs of GG.
  3. The limit space of GG 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

Never refreshed

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.