Nov 14, 11 AM in ICT-411 "An introduction to multidimensional symbolic dynamics"
At Software Science Departmental seminar on Wednesday, Nov 14, 2018 at 11:00 AM Pierre Guillon (CNRS,France, Institut Poncelet, Moscow) will talk about "An introduction to multidimensional symbolic dynamics".
The seminar will take place in ICT-411.
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 through linear algebra, graph theory, automata theory. The 2D version of this object, however, corresponds to tilings by Wang tiles, and relies strongly on computability theory.
We will give some examples of hardness result, all based on the existence of aperiodic tilings.