Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A class of nonsofic multidimensional shift spaces

Author: Ronnie Pavlov
Journal: Proc. Amer. Math. Soc. 141 (2013), 987-996
MSC (2010): Primary 37B50; Secondary 37B10, 37A15
Published electronically: July 31, 2012
MathSciNet review: 3003690
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In one dimension, sofic shifts are fairly well understood and are special examples of shift spaces which must satisfy very restrictive properties. However, in multiple dimensions there are very few known conditions which guarantee nonsoficity of a shift space. In this paper, we show that for any $ \mathbb{Z}^d$ sofic shift $ X$ which satisfies a uniform mixing condition called block gluing in all directions $ \vec {e_2}, \ldots , \vec {e_d}$, the set of legal rows of $ X$ in the $ \vec {e_1}$-direction has a synchronizing word. This allows us to define a (new) large class of nonsofic $ \mathbb{Z}^d$ shift spaces.

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

  • [1] N. Aubrun and M. Sablik, Simulation of effective shift spaces by two-dimensional subshifts of finite type, Acta Appl. Math., to appear.
  • [2] R. Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. 66 (1966). MR 0216954 (36:49)
  • [3] M. Boyle, R. Pavlov, and M. Schraudner, Multidimensional sofic shifts without separation and their factors, Trans. Amer. Math. Soc. 362 (2010), 4617-4653. MR 2645044 (2011g:37037)
  • [4] A. Desai, Subsystem entropy for $ \mathbb{Z}^d$ sofic shifts, Indagationes Mathematicae 17 (2006), no. 3, 353-360. MR 2321105 (2009h:37020)
  • [5] B. Durand, A. Romashchenko, and A. Shen, Fixed point sets and their applications, J. Comput. System Sci., to appear.
  • [6] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics 1794, Springer, Berlin, 2002. MR 1970385 (2004c:37005)
  • [7] M. Hochman, On the dynamics and recursive properties of multidimensional symbolic
    , Inventiones Mathematicae 176 (2009), no. 1, 131-167. MR 2485881 (2009m:37023)
  • [8] F. Hahn and Y. Katznelson, On the entropy of uniquely ergodic transformations, Trans. Amer. Math. Soc. 126 (1967), 335-360. MR 0207959 (34:7772)
  • [9] E. Jeandel, personal communication.
  • [10] A. Johnson, S. Kass, and K. Madden, Projectional entropy in higher dimensional shifts of finite type, Complex Systems 17 (2007), no. 3, 243-257. MR 2373706 (2008m:37028)
  • [11] D. Lind and B. Marcus, Introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092 (97a:58050)
  • [12] R. Pavlov and M. Schraudner, Projectional subdynamics of $ \mathbb{Z}^d$ shifts of finite type, submitted.
  • [13] P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics 79, Springer-Verlag, Berlin, 1982. MR 648108 (84e:28017)
  • [14] H. Wang, Proving theorems by pattern recognition. II, AT&T Bell Labs. Tech. J. 40 (1961), 1-41.

Similar Articles

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

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

Additional Information

Ronnie Pavlov
Affiliation: Department of Mathematics, University of Denver, 2360 S. Gaylord Street, Denver, Colorado 80208

Keywords: $\mathbb{Z}^{d}$, shift of finite type, sofic, multidimensional
Received by editor(s): March 25, 2011
Received by editor(s) in revised form: August 2, 2011
Published electronically: July 31, 2012
Communicated by: Bryna Kra
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society