Pierre Guillon (Aix-Marseille University and Poncelet Lab)
Chebyshev Laboratory Colloquium
Thursday June 6 18:15 room 105 (14-th line V.I., 29)
A 1D subshift of finite type (SFT) is a set of biinfinite words over a given finite alphabet, defined by prohibiting a finite set of finite patterns. 1D SFT can be studied thanks to linear algebra, graph, and automata theory. The 2D version of this object, however, corresponds to tilings by Wang tiles, and relies more on computability and complexity theory. We will survey many recent results that formalize this idea: undecidability of emptiness, uncomputable language, characterization of entropies and of traces, automorphism group, self-simulation… If time permits, we will conclude with the open questions, especially in the larger setting of Cayley graphs.
Everyone is welcome!