DMTCS Proceedings, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems

Font Size:  Small  Medium  Large

Projective subdynamics and universal shifts

Pierre Guillon

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.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional