×

zbMATH — the first resource for mathematics

Classification of sofic projective subdynamics of multidimensional shifts of finite type. (English) Zbl 1353.37036
The authors study which 1D subshifts arise as projective subdynamics of a 2D shift of finite type (SFT), that is as the set of rows occuring in its 2D configurations. One can distinguish between stable or unstable projective subdynamics depending on whether the 1D subshift is realized as the set of rows of a finite-width strip avoiding the forbidden patterns of the 2D subshift.
It is proven that infinite stable projective subdynamics of 2D SFTs are exactly the sofic subshifts that have positive entropy or a so-called good set of periods (a condition linking its periods and that of a minimal cover) but no universal period (configurations should not be too close to being periodic).
Moreover, the sofic subshifts that arise as unstable projective subdynamics of a 2D SFT are exactly those of infinite type that have positive entropy or no universal period.
The finite union of projective subdynamics (resp. stable) of SFTs is itself the projective subdynamics (resp. stable) of some SFT, whenever it contains two periodic configurations. The projective subdynamics of a 2D SFT with the uniform filling property are stable.
The article presents several general (long) constructions, and gives specific examples, including effective subshifts that cannot be projective subdynamics of SFTs.

MSC:
37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] [AS] N. Aubrun and M. Sablik, Simulation of recursively enumerable subshifts by two dimensional SFT and a generalization, preprint.
[2] Balister, Paul; Bollob\'as, B\'ela; Quas, Anthony, Entropy along convex shapes, random tilings and shifts of finite type, Illinois J. Math., 46, 3, 781-795, (2002) · Zbl 1025.37010
[3] Ballier, Alexis; Guillon, Pierre; Kari, Jarkko, Limit sets of stable and unstable cellular automata, Fund. Inform., 110, 1-4, 45-57, (2011) · Zbl 1234.68276
[4] Berger, Robert, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66, 72 pp., (1966) · Zbl 0199.30802
[5] Boyle, Mike; Pavlov, Ronnie; Schraudner, Michael, Multidimensional sofic shifts without separation and their factors, Trans. Amer. Math. Soc., 362, 9, 4617-4653, (2010) · Zbl 1207.37011
[6] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to algorithms, xxii+1180 pp., (2001), MIT Press: Cambridge, MA:MIT Press · Zbl 1047.68161
[7] Durand, Bruno; Romashchenko, Andrei; Shen, Alexander, Fixed-point tile sets and their applications, J. Comput. System Sci., 78, 3, 731-764, (2012) · Zbl 1244.05049
[8] Fogg, N. Pytheas, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics 1794, xviii+402 pp., (2002), Springer-Verlag: Berlin:Springer-Verlag · Zbl 1014.11015
[9] Formenti, Enrico; K\rurka, Petr, Subshift attractors of cellular automata, Nonlinearity, 20, 1, 105-117, (2007) · Zbl 1121.37016
[10] Hochman, Michael, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176, 1, 131-167, (2009) · Zbl 1168.37002
[11] Hurd, Lyman Porter, The application of formal language theory to the dynamical behavior of cellular automata, 127 pp., (1988), ProQuest LLC, Ann Arbor, MI
[12] Johnson, Aimee; Kass, Steve; Madden, Kathleen, Projectional entropy in higher dimensional shifts of finite type, Complex Systems, 17, 3, 243-257, (2007) · Zbl 1167.37319
[13] Kari, Jarkko, Rice’s theorem for the limit sets of cellular automata, Theoret. Comput. Sci., 127, 2, 229-254, (1994) · Zbl 0824.68078
[14] [kurka] P. Kurka, Topological dynamics of one-dimensional cellular automata, Encyclopedia of Complexity and System Sciences Part 20, Springer-Verlag (2009), 9246–9268.
[15] Lind, Douglas; Marcus, Brian, An introduction to symbolic dynamics and coding, xvi+495 pp., (1995), Cambridge University Press: Cambridge:Cambridge University Press · Zbl 1106.37301
[16] Maass, Alejandro, On the sofic limit sets of cellular automata, Ergodic Theory Dynam. Systems, 15, 4, 663-684, (1995) · Zbl 0864.58030
[17] Maass, Alejandro, Some coded systems that are not unstable limit sets of cellular automata. Cellular automata and cooperative systems, Les Houches, 1992, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 396, 433-449, (1993), Kluwer Acad. Publ.: Dordrecht:Kluwer Acad. Publ. · Zbl 0856.68106
[18] Robinson, Raphael M., Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12, 177-209, (1971) · Zbl 0197.46801
[19] Robinson, E. Arthur, Jr.; Sahin, Ay\cse A., Mixing properties of nearly maximal entropy measures for \(\textbf{Z}^d\) shifts of finite type, Colloq. Math., 84/85, part 1, 43-50, (2000) · Zbl 0969.28009
[20] [sch] M. Schraudner, One-dimensional projective subdynamics of uniformly mixing \(\mathbbZ^D\) shifts of finite type, Ergodic Theory Dynam. Systems., published online July 3, 2014, DOI 10.1017/etds.2014.2.
[21] Ward, Thomas, Automorphisms of \(\mathbf{Z}^d\)-subshifts of finite type, Indag. Math. (N.S.), 5, 4, 495-504, (1994) · Zbl 0823.28007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.