A class of nonsofic multidimensional shift spaces

Pavlov, Ronnie

doi:10.1090/S0002-9939-2012-11382-6

A class of nonsofic multidimensional shift spaces
HTML articles powered by AMS MathViewer

by Ronnie Pavlov PDF

Proc. Amer. Math. Soc. 141 (2013), 987-996 Request permission

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

N. Aubrun and M. Sablik, Simulation of effective shift spaces by two-dimensional subshifts of finite type, Acta Appl. Math., to appear.
Robert Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. 66 (1966), 72. MR 216954
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, DOI 10.1090/s0002-9947-10-05003-8
Angela Desai, Subsystem entropy for $\Bbb Z^d$ sofic shifts, Indag. Math. (N.S.) 17 (2006), no. 3, 353–359. MR 2321105, DOI 10.1016/S0019-3577(06)80037-6
B. Durand, A. Romashchenko, and A. Shen, Fixed point sets and their applications, J. Comput. System Sci., to appear.
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, DOI 10.1007/b13861
Michael Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math. 176 (2009), no. 1, 131–167. MR 2485881, DOI 10.1007/s00222-008-0161-7
Frank Hahn and Yitzhak Katznelson, On the entropy of uniquely ergodic transformations, Trans. Amer. Math. Soc. 126 (1967), 335–360. MR 207959, DOI 10.1090/S0002-9947-1967-0207959-1
E. Jeandel, personal communication.
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
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
R. Pavlov and M. Schraudner, Projectional subdynamics of $\mathbb {Z}^d$ shifts of finite type, submitted.
Peter Walters, An introduction to ergodic theory, Graduate Texts in Mathematics, vol. 79, Springer-Verlag, New York-Berlin, 1982. MR 648108
H. Wang, Proving theorems by pattern recognition. II, AT&T Bell Labs. Tech. J. 40 (1961), 1–41.