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 sofic shift which satisfies a uniform mixing condition called block gluing in all directions , the set of legal rows of in the -direction has a synchronizing word. This allows us to define a (new) large class of nonsofic shift spaces.

**[1]**N. Aubrun and M. Sablik,*Simulation of effective shift spaces by two-dimensional subshifts of finite type*, Acta Appl. Math., to appear.**[2]**Robert Berger,*The undecidability of the domino problem*, Mem. Amer. Math. Soc. No.**66**(1966), 72. MR**0216954****[3]**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**, 10.1090/S0002-9947-10-05003-8**[4]**Angela Desai,*Subsystem entropy for ℤ^{𝕕} sofic shifts*, Indag. Math. (N.S.)**17**(2006), no. 3, 353–359. MR**2321105**, 10.1016/S0019-3577(06)80037-6**[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, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR**1970385****[7]**Michael Hochman,*On the dynamics and recursive properties of multidimensional symbolic systems*, Invent. Math.**176**(2009), no. 1, 131–167. MR**2485881**, 10.1007/s00222-008-0161-7**[8]**Frank Hahn and Yitzhak Katznelson,*On the entropy of uniquely ergodic transformations*, Trans. Amer. Math. Soc.**126**(1967), 335–360. MR**0207959**, 10.1090/S0002-9947-1967-0207959-1**[9]**E. Jeandel, personal communication.**[10]**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****[11]**Douglas Lind and Brian Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092****[12]**R. Pavlov and M. Schraudner,*Projectional subdynamics of shifts of finite type*, submitted.**[13]**Peter Walters,*An introduction to ergodic theory*, Graduate Texts in Mathematics, vol. 79, Springer-Verlag, New York-Berlin, 1982. MR**648108****[14]**H. Wang,*Proving theorems by pattern recognition. II*, AT&T Bell Labs. Tech. J.**40**(1961), 1-41.

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

Email:
rpavlov@du.edu

DOI:
https://doi.org/10.1090/S0002-9939-2012-11382-6

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.