November 30, 2015

Sebastian Barbieri (ENS-Lyon)

We define the domino problem for subshifts where the symbols are restrained to subsets of Z^d. More specifically, we focus on subsets which have a self-similar structure defined by a family of substitutions. In this setting we exhibit non-trivial families of structures where the domino problem is decidable and undecidable. Amongst those we show that the Sierpinski triangle has decidable domino problem, while the Sierpinski carpet has undecidabe domino problem.