On graph induced symbolic systems





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


In this paper, we investigate shift spaces arising from a multidimensional graph G. In particular, we investigate nonemptiness and existence of periodic points for a multidimensional shift space. We derive sufficient conditions under which these questions can be answered affirmatively. We investigate the structure of the shift space using the generating matrices. We prove that any d-dimensional shift of finite type is finite if and only if it is conjugate to a shift generated through permutation matrices. We prove that if any triangular pattern of the form a b c can be extended to a 1 x 1 square then the two dimensional shift space possesses periodic points. We introduce the notion of an E-pair for a two dimensional shift space. Using the notion of an E-pair, we derive sufficient conditions for non-emptiness of the two dimensional shift space under discussion.


Download data is not yet available.

Author Biographies

Prashant Kumar, Indian Institute of Technology Jodhpur

Department of Mathematics

Puneet Sharma, Indian Institute of Technology Jodhpur

Department of Mathematics


A. Ballier, B. Durand, and E. Jeandel, Structural aspects of tilings, Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008.

R. Berger, The undecidability of the Domino Problem, Mem. Amer. Math. Soc. 66 (1966). https://doi.org/10.1090/memo/0066

E. M. Coven, A. S. A. Johnson, N. Jonoska, and K. Madden, The symbolic dynamics of multidimensional tiling systems, Ergodic Theory And Dynamical Systems 23, no. 2 (2003), 447-460. https://doi.org/10.1017/S014338570200113X

X.-C. Fu, W. Lu, P. Ashwin, and J. Duan, Symbolic representations of iterated maps, Topological Methods in Nonlinear Analysis, Journal of the Juliusz Schauder Center 18 (2001), 119-147. https://doi.org/10.12775/TMNA.2001.027

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. https://doi.org/10.4007/annals.2010.171.2011

E. Jeandel and P. Vanier, Characterizations of periods of multi-dimensional shifts, Ergodic Theory and Dynamical Systems 35, no. 2 (2013), 431-460. https://doi.org/10.1017/etds.2013.60

A. S. A. Johnson, and K. M. Madden, The decomposition theorem for two-dimensional shifts of finite type, Proceedings of the American Mathematical Society 127, no. 5 (1999), 1533-1543. https://doi.org/10.1090/S0002-9939-99-04678-X

N. Jonoska and J. B. Pirnot, Finite state automata representing two-dimensional subshifts, Theoretical Computer Science 410, no. 37 (2009), 3504--3512. https://doi.org/10.1016/j.tcs.2009.03.015

B. P. Kitchens, Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts, Universitext. Springer-Verlag, Berlin, 1998. https://doi.org/10.1007/978-3-642-58822-8_7

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

D. Lind, and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. https://doi.org/10.1017/CBO9780511626302

D. Lind, and K. Schmidt, Symbolic and algebraic dynamical systems, Handbook of Dynamical Systems, Elsevier Science, Volume 1, Part A (2002), 765-812. https://doi.org/10.1016/S1874-575X(02)80012-1

A. Quas, and P. Trow, Subshifts of Multidimensional shifts of finite type, Ergodic Theory and Dynamical Systems 20, no. 3 (2000), 859-874. https://doi.org/10.1017/S0143385700000468

C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379-423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

P. Sharma and D. Kumar, Matrix characterization of multidimensional subshifts of finite type, Applied General Topology 20, no. 2 (2019), 407-418. https://doi.org/10.4995/agt.2019.11541

P. Sharma and D. Kumar, Multidimensional shifts and finite matrices, Topology Proceedings 57 (2021), 241-257.




How to Cite

P. Kumar and P. Sharma, “On graph induced symbolic systems”, Appl. Gen. Topol., vol. 24, no. 2, pp. 359–378, Oct. 2023.



Regular Articles