Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Classification of sofic projective subdynamics of multidimensional shifts of finite type

Authors: Ronnie Pavlov and Michael Schraudner
Journal: Trans. Amer. Math. Soc. 367 (2015), 3371-3421
MSC (2010): Primary 37B50; Secondary 37B10, 37B40
Published electronically: November 4, 2014
MathSciNet review: 3314811
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Motivated by Hochman's notion of subdynamics of a $ \mathbb{Z}^d$ subshift (2009), we define and examine the projective subdynamics of $ \mathbb{Z}^d$ shifts of finite type (SFTs) where we restrict not only the action but also the phase space. We show that any $ \mathbb{Z}$ sofic shift of positive entropy is the projective subdynamics of a $ \mathbb{Z}^2$ ( $ \mathbb{Z}^d$) SFT, and that there is a simple condition characterizing the class of zero-entropy $ \mathbb{Z}$ sofic shifts which are not the projective subdynamics of any $ \mathbb{Z}^2$ SFT. We define notions of stable and unstable subdynamics in analogy with the notions of stable and unstable limit sets in cellular automata theory, and discuss how our results fit into this framework. One-dimensional strictly sofic shifts of positive entropy admit both a stable and an unstable realization, whereas $ \mathbb{Z}$ SFTs only allow for stable realizations and a particular class of zero-entropy proper $ \mathbb{Z}$ sofics only allows for an unstable realization. Finally, we prove that the union of finitely many $ \mathbb{Z}^k$ subshifts, all of which are realizable in $ \mathbb{Z}^d$ SFTs, is again realizable when it contains at least two periodic points, that the projective subdynamics of $ \mathbb{Z}^2$ SFTs with the uniform filling property (UFP) are always stable, thus sofic, and we exhibit a class of non-sofic $ \mathbb{Z}$ subshifts which are not the projective subdynamics of any $ \mathbb{Z}^d$ SFT.

References [Enhancements On Off] (What's this?)

  • [1] N. Aubrun and M. Sablik, Simulation of recursively enumerable subshifts by two dimensional SFT and a generalization, preprint.
  • [2] Paul Balister, Béla Bollobás, and Anthony Quas, Entropy along convex shapes, random tilings and shifts of finite type, Illinois J. Math. 46 (2002), no. 3, 781-795. MR 1951240 (2003j:37023)
  • [3] Alexis Ballier, Pierre Guillon, and Jarkko Kari, Limit sets of stable and unstable cellular automata, Fund. Inform. 110 (2011), no. 1-4, 45-57. MR 2868073 (2012m:37017)
  • [4] Robert Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No. 66 (1966), 72. MR 0216954 (36 #49)
  • [5] Mike Boyle, Ronnie Pavlov, and Michael Schraudner, Multidimensional sofic shifts without separation and their factors, Trans. Amer. Math. Soc. 362 (2010), no. 9, 4617-4653. MR 2645044 (2011g:37037)
  • [6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 2nd ed., MIT Press, Cambridge, MA, 2001. MR 1848805 (2002e:68001)
  • [7] Bruno Durand, Andrei Romashchenko, and Alexander Shen, Fixed-point tile sets and their applications, J. Comput. System Sci. 78 (2012), no. 3, 731-764. MR 2900032,
  • [8] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR 1970385 (2004c:37005)
  • [9] Enrico Formenti and Petr Kůrka, Subshift attractors of cellular automata, Nonlinearity 20 (2007), no. 1, 105-117. MR 2285107 (2008e:37007),
  • [10] Michael Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math. 176 (2009), no. 1, 131-167. MR 2485881 (2009m:37023),
  • [11] Lyman Porter Hurd, The application of formal language theory to the dynamical behavior of cellular automata, ProQuest LLC, Ann Arbor, MI, 1988. Thesis (Ph.D.)-Princeton University. MR 2636496
  • [12] Aimee Johnson, Steve Kass, and Kathleen Madden, Projectional entropy in higher dimensional shifts of finite type, Complex Systems 17 (2007), no. 3, 243-257. MR 2373706 (2008m:37028)
  • [13] Jarkko Kari, Rice's theorem for the limit sets of cellular automata, Theoret. Comput. Sci. 127 (1994), no. 2, 229-254. MR 1275817 (95g:68079),
  • [14] P. Kurka, Topological dynamics of one-dimensional cellular automata, Encyclopedia of Complexity and System Sciences Part 20, Springer-Verlag (2009), 9246-9268.
  • [15] Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092 (97a:58050)
  • [16] Alejandro Maass, On the sofic limit sets of cellular automata, Ergodic Theory Dynam. Systems 15 (1995), no. 4, 663-684. MR 1346395 (96h:58093),
  • [17] Alejandro Maass, 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., vol. 396, Kluwer Acad. Publ., Dordrecht, 1993, pp. 433-449. MR 1267985 (95f:68175)
  • [18] Raphael M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177-209. MR 0297572 (45 #6626)
  • [19] E. Arthur Robinson Jr. and Ayşe A. Şahin, Mixing properties of nearly maximal entropy measures for $ {\bf Z}^d$ shifts of finite type. part 1, Colloq. Math. 84/85 (2000), no. part 1, 43-50. Dedicated to the memory of Anzelm Iwanik. MR 1778838 (2001i:37008)
  • [20] M. Schraudner, One-dimensional projective subdynamics of uniformly mixing $ \mathbb{Z}^D$ shifts of finite type, Ergodic Theory Dynam. Systems., published online July 3, 2014, DOI 10.1017/etds.2014.2.
  • [21] Thomas Ward, Automorphisms of $ \mathbf {Z}^d$-subshifts of finite type, Indag. Math. (N.S.) 5 (1994), no. 4, 495-504. MR 1307966 (97a:28014),

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 37B50, 37B10, 37B40

Retrieve articles in all journals with MSC (2010): 37B50, 37B10, 37B40

Additional Information

Ronnie Pavlov
Affiliation: Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, British Columbia V6T 1Z2, Canada

Michael Schraudner
Affiliation: Centro de Modelamiento Matemático, Universidad de Chile, Av. Blanco Encalada 2120, Santiago, Chile

Keywords: $\mathbb{Z}^d$, multidimensional shift of finite type, sofic systems, subsystem, projective subdynamics, uniform filling property, Sturmian shifts, periodic points
Received by editor(s): January 4, 2012
Received by editor(s) in revised form: May 6, 2013
Published electronically: November 4, 2014
Additional Notes: The second author was partially supported by Basal project CMM, Universidad de Chile, by FONDECYT projects 3080008 and 1100719 and by CONICYT Proyecto Anillo ACT 1103.
Article copyright: © Copyright 2014 by the authors

American Mathematical Society