Hierarchy and expansiveness in 2D subshifts of finite type

Charalampos Zinoviadis
I2M, Aix-Marseille Université

Date(s) : 10/03/2015   iCal
11 h 00 min - 12 h 00 min

In a 2D subshift of finite type (SFT), a direction l is called expansive if every point is uniquely determined by its contents along a finite strip of slope l.
We are interested in dynamical and computational properties of 2D subshifts of finite type with a unique direction of non-expansiveness (extremely deterministic). We prove, among other things, that the non-emptiness problem of extremely expansive 2D SFT is undecidable. The proofs and constructions are based on the notion of simulation and self-simulation, which was first used by Gacs and later by Durand, Romaschenko and Shen. In this talk, we are going to state the results and try to give a basic intuitive idea of the specific problems that arise when we try to construct extremely deterministic 2D SFT.




Retour en haut