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.
Additional Information
- Jung-Chao Ban
- Affiliation: Department of Applied Mathematics, National Dong Hwa University, Hualien 970003, Taiwan, Republic of China
- MR Author ID: 684625
- Email: jcban@gms.ndhu.edu.tw
- Chih-Hung Chang
- Affiliation: Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 81148, Taiwan, Republic of China
- MR Author ID: 858274
- Email: chchang@nuk.edu.tw
- Received by editor(s): September 15, 2015
- Received by editor(s) in revised form: January 17, 2016
- Published electronically: May 30, 2017
- Additional Notes: This work was partially supported by the Ministry of Science and Technology, ROC (Contract Nos. MOST 105-2115-M-259-006-MY2 and 105-2115-M-390-001-MY2). The first author was supported by the National Center for Theoretical Sciences, ROC
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 8389-8407
- MSC (2010): Primary 37B10, 37B50
- DOI: https://doi.org/10.1090/tran/6906
- MathSciNet review: 3710629