HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Projective subdynamics and universal shifts

Abstract : We study the projective subdynamics of two-dimensional shifts of finite type, which is the set of one-dimensional configurations that appear as columns in them. We prove that a large class of one-dimensional shifts can be obtained as such, namely the effective subshifts which contain positive-entropy 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 non-trivial properties of projective subdynamics.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, September 9, 2015 - 11:14:55 AM
Last modification on : Monday, March 29, 2021 - 3:24:02 PM
Long-term archiving on: : Monday, December 28, 2015 - 11:08:53 PM


Publisher files allowed on an open archive




Pierre Guillon. Projective subdynamics and universal shifts. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. pp.123-134, ⟨10.46298/dmtcs.2969⟩. ⟨hal-01196136⟩



Record views


Files downloads