Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


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

Authors: Jung-Chao Ban and Chih-Hung Chang
Journal: Trans. Amer. Math. Soc. 369 (2017), 8389-8407
MSC (2010): Primary 37B10, 37B50
Published electronically: May 30, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Nathalie Aubrun and Marie-Pierre Béal, Tree-shifts of finite type, Theoret. Comput. Sci. 459 (2012), 16-25. MR 2974235,
  • [2] Nathalie Aubrun and Marie-Pierre Béal, Sofic tree-shifts, Theory Comput. Syst. 53 (2013), no. 4, 621-644. MR 3084356,
  • [3] 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.
  • [4] Jung-Chao Ban and Chih-Hung Chang, The topological pressure of linear cellular automata, Entropy 11 (2009), no. 2, 271-284. MR 2534637,
  • [5] 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,
  • [6] 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,
  • [7] Robert L. Devaney, An introduction to chaotic dynamical systems, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1986. MR 811850
  • [8] G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320-375. MR 0259881
  • [9] 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,
  • [10] Bruce P. Kitchens, Symbolic dynamics: One-sided, two-sided and countable state Markov shifts, Universitext, Springer-Verlag, Berlin, 1998. MR 1484730
  • [11] Tien Yien Li and James A. Yorke, Period three implies chaos, Amer. Math. Monthly 82 (1975), no. 10, 985-992. MR 0385028
  • [12] Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092
  • [13] 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,
  • [14] 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,
  • [15] 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.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 37B10, 37B50

Retrieve articles in all journals with MSC (2010): 37B10, 37B50

Additional Information

Jung-Chao Ban
Affiliation: Department of Applied Mathematics, National Dong Hwa University, Hualien 970003, Taiwan, Republic of China

Chih-Hung Chang
Affiliation: Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 81148, Taiwan, Republic of China

Keywords: Symbolic dynamics, tree-shift, chaos, irreducible, mixing, periodic tree, graph representation, labeled graph
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
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society