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

From papers

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.

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

No solutions have been posted yet.