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

    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.


    Volume: DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
    Section: Proceedings
    Published on: January 1, 2011
    Imported on: January 31, 2017
    Keywords: multidimensional symbolic dynamics,effective dynamics,tilings,simulation,undecidability,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

    Share

    Consultation statistics

    This page has been seen 145 times.
    This article's PDF has been downloaded 263 times.