 | Pierre Guillon (Université d’Aix-Marseille и Лаборатория Понселе) «Computational Aspects of Multidimensional Symbolic Dynamics« |
|
КОЛЛОКВИУМ ЛАБОРАТОРИИ ИМ. ЧЕБЫШЕВА Лаборатория Чебышева, аудитория 105 (14-я линия В. О., 29) чт. 6 июня 18:15 Pierre Guillon (Université d’Aix-Marseille и Лаборатория Понселе) Computational Aspects of Multidimensional Symbolic Dynamics 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. |