Tree-shifts: Irreducibility, mixing, and the chaos of tree-shifts

Ban, Jung-Chao; Chang, Chih-Hung

doi:10.1090/tran/6906

Tree-shifts: Irreducibility, mixing, and the chaos of tree-shifts
HTML articles powered by AMS MathViewer

by Jung-Chao Ban and Chih-Hung Chang PDF

Trans. Amer. Math. Soc. 369 (2017), 8389-8407 Request permission

Abstract:

Topological behavior, such as chaos, irreducibility, and mixing of a one-sided shift of finite type, is well elucidated. Meanwhile, the investigation of multidimensional shifts, for instance, textile systems, is difficult and only a few results have been obtained so far.

This paper studies shifts defined on infinite trees, which are called tree-shifts. Infinite trees have a natural structure of one-sided symbolic dynamical systems equipped with multiple shift maps and constitute an intermediate class between one-sided shifts and multidimensional shifts. We have shown not only an irreducible tree-shift of finite type but also a mixing tree-shift that is chaotic in the sense of Devaney. Furthermore, the graph and labeled graph representations of tree-shifts are revealed so that the verification of irreducibility and mixing of a tree-shift is equivalent to determining the irreducibility and mixing of matrices, respectively. This extends the classical results of one-sided symbolic dynamics.

A necessary and sufficient condition for the irreducibility and mixing of tree-shifts of finite type is demonstrated. Most important of all, the examination can be done in finite steps with an upper bound.

References

Nathalie Aubrun and Marie-Pierre Béal, Tree-shifts of finite type, Theoret. Comput. Sci. 459 (2012), 16–25. MR 2974235, DOI 10.1016/j.tcs.2012.07.020
Nathalie Aubrun and Marie-Pierre Béal, Sofic tree-shifts, Theory Comput. Syst. 53 (2013), no. 4, 621–644. MR 3084356, DOI 10.1007/s00224-013-9456-1
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, 2015.
Jung-Chao Ban and Chih-Hung Chang, The topological pressure of linear cellular automata, Entropy 11 (2009), no. 2, 271–284. MR 2534637, DOI 10.3390/e11020271
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
Ethan M. Coven, Aimee Johnson, Nataša Jonoska, and Kathleen Madden, The symbolic dynamics of multidimensional tiling systems, Ergodic Theory Dynam. Systems 23 (2003), no. 2, 447–460. MR 1972231, DOI 10.1017/S014338570200113X
Robert L. Devaney, An introduction to chaotic dynamical systems, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1986. MR 811850
G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375. MR 259881, DOI 10.1007/BF01691062
Aimee S. A. Johnson and Kathleen M. Madden, The decomposition theorem for two-dimensional shifts of finite type, Proc. Amer. Math. Soc. 127 (1999), no. 5, 1533–1543. MR 1476140, DOI 10.1090/S0002-9939-99-04678-X
Bruce P. Kitchens, Symbolic dynamics, Universitext, Springer-Verlag, Berlin, 1998. One-sided, two-sided and countable state Markov shifts. MR 1484730, DOI 10.1007/978-3-642-58822-8
T. Y. Li and James A. Yorke, Period three implies chaos, Amer. Math. Monthly 82 (1975), no. 10, 985–992. MR 385028, DOI 10.2307/2318254
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
Douglas Lind and Klaus Schmidt, Symbolic and algebraic dynamical systems, Handbook of dynamical systems, Vol. 1A, North-Holland, Amsterdam, 2002, pp. 765–812. MR 1928527, DOI 10.1016/S1874-575X(02)80012-1
Johannes Müller and Christoph Spandl, Embeddings of dynamical systems into cellular automata, Ergodic Theory Dynam. Systems 29 (2009), no. 1, 165–177. MR 2470631, DOI 10.1017/S0143385708080036
J. L. Verdu-Mas, R. C. Carrasco, and J. Calera-Rubio, Parsing with probabilistic strictly locally testable tree languages, Pattern Analysis and Machine Intelligence, IEEE Transactions 27 (2005), 1040–1050.