The Domino Problem for Self-similar Structures

Sebastián Barbieri (1, 2) , Mathieu Sablik (3)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 MC2 - Modèles de calcul, Complexité, Combinatoire
3 I2M - Institut de Mathématiques de Marseille

We define the domino problem for tilings over self-similar structures of Z(d) given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.

Mots clés: TILINGS

Domaines: Systèmes dynamiques [math.DS]

Sebastián Barbieri, Mathieu Sablik. The Domino Problem for Self-similar Structures. 12th Conference on Computability in Europe (CiE), Univ Paris 13; Univ Paris 7; Assoc Computabil Europe; Assoc Symbol Log; European Assoc Theoret Comp Sci, Jun 2016, Paris, France. pp.205-214, ⟨10.1007/978-3-319-40189-8_21⟩. ⟨hal-01489000⟩