Multi angle About the domino problem on finitely generated groups - Lecture 1
Auteurs : Aubrun, Nathalie (Auteur de la Conférence)
CIRM (Editeur )
Loading the player...
Résumé : Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given finitely presented group $0$, is there an algorithm that determines if the group $G$ is tilable with a finite set of tiles? In this lecture I will start with a presentation of two different proofs of the undecidability of the domino problem on $Z^2$. Then we will discuss the case of finitely generated groups. Finally, the emptiness problem for general subshifts will be tackled.Codes MSC :
03B25 - Decidability of theories and sets of sentences
37B50 - Multi-dimensional shifts of finite type, tiling dynamics
68Q45 - Formal languages and automata