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.[-]

Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape or subset of the infinite grid? If we look for a tiling of the whole grid, this is the domino problem which is known to be undecidable for Z2 and many other groups. In this talk we focus on infinite snake tilings. Originally the infinite snake problem asks is there exists a tiling of a self-avoiding bi-infinite path on the grid Z2. In this talk I present how to expand the scope of domino snake problems to finitely generated groups to understand how the underlying structure affects computability. This is joint work with Nicolás Bitar.[-]

Subshifts are set of colorings of a group by a finite alphabet that respect local constraints, given by some forbidden patterns ode m. The asymmetric version of Lovász local lemma reveals particularly useful to prove the existence of a coloring inside a subshift, i.e. a coloring that avoids all the forbidden patterns. In this talk I will present some sufficient conditions on the set of forbidden patterns to get at least one coloring. Then we will see as an application why every group possesses a strongly aperiodic subshift (joint work with Sebastián Barbieri and Stéphan Thomassé).[-]