eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2011-01-01
DMTCS Proceedings vol. AP,...
Proceedings
10.46298/dmtcs.2969
2969
journal article
Projective subdynamics and universal shifts
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.
https://dmtcs.episciences.org/2969/pdf
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]