Matrix characterization of multidimensional subshifts of finite type

Puneet Sharma, Dileep Kumar


Let X ⊂ AZd be a 2-dimensional subshift of finite type. We prove that any 2-dimensional subshift of finite type can be characterized by a square matrix of infinite dimension. We extend our result to a general d-dimensional case. We prove that the multidimensional shift space is non-empty if and only if the matrix obtained is of positive dimension. In the process, we give an alternative view of the necessary and sufficient conditions obtained for the non-emptiness of the multidimensional shift space. We also give sufficient conditions for the shift space X to exhibit periodic points.


multidimensional shift spaces; shifts of finite type; periodicity in multidimensional shifts of finite type

Subject classification

37B10; 37B20; 37B50.

Full Text:



J. C. Ban, W. G. Hu, S. S. Lin and Y. H. Lin, Verification of mixing properties in two-dimensional shifts of finite type, arXiv:1112.2471v2.

M.-P. Beal, F. Fiorenzi and F. Mignosi, Minimal forbidden patterns of multi-dimensional shifts, Int. J. Algebra Comput. 15 (2005), 73-93.

R. Berger, The undecidability of the Domino Problem, Mem. Amer. Math. Soc. 66 (1966).

M. Boyle, R. Pavlov and M. Schraudner, Multidimensional sofic shifts without separation and their factors, Transactions of the American Mathematical Society 362, no. 9 (2010), 4617-4653.

X.-C. Fu, W. Lu, P. Ashwin and J. Duan, Symbolic representations of iterated maps, Topological Methods in Nonlinear Analysis 18 (2001), 119-147.

J. Hadamard, Les surfaces a coubures opposees et leurs lignes geodesiques, J. Math. Pures Appi. 5 IV (1898), 27-74.

M. Hochman, On dynamics and recursive properties of multidimensional symbolic dynamics, Invent. Math. 176:131 (2009).

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics 171, no. 3 (2010), 2011-2038.

B. P. Kitchens, Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts, Universitext. Springer-Verlag, Berlin, 1998.

S. Lightwood, Morphisms from non-periodic $Z^2$-subshifts I: Constructing embeddings from homomorphisms, Ergodic Theory Dynam. Systems 23, no. 2 (2003), 587-609.

D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995.

A. Quas and P. Trow, Subshifts of multidimensional shifts of finite type, Ergodic Theory and Dynamical Systems 20, no. 3 (2000), 859-874.

R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177-209.

C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379-423, 623-656.

H. H. Wicke and J. M. Worrell, Jr., Open continuous mappings of spaces having bases of countable order, Duke Math. J. 34 (1967), 255-271.

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM

Esta revista se publica bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Universitat Politècnica de València

e-ISSN: 1989-4147