Pierre Guillon

Projective subdynamics and universal shifts
dmtcs:2969 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2011,
DMTCS Proceedings vol. AP, Automata 2011  17th International Workshop on Cellular Automata and Discrete Complex Systems

https://doi.org/10.46298/dmtcs.2969
Projective subdynamics and universal shifts
Authors: Pierre Guillon
NULL
Pierre Guillon
We study the projective subdynamics of twodimensional shifts of finite type, which is the set of onedimensional configurations that appear as columns in them. We prove that a large class of onedimensional shifts can be obtained as such, namely the effective subshifts which contain positiveentropy sofic subshifts. The proof involves some simple notions of simulation that may be of interest for other constructions. As an example, it allows us to prove the undecidability of all nontrivial properties of projective subdynamics.