On Expansivity and Pseudo-Orbit Tracing Property for Cellular Automata

• Autorzy: Jalonen Joonatan , Kari Jarkko

Identyfikatory

DOI

10.3233/FI-2020-1881

• Języki publikacji: EN

Abstrakty

EN

Ultimate expansivity extends concepts of expansivity and positive expansivity. We consider one-sided variants of ultimate expansivity and pseudo-orbit tracing property (also known as the shadowing property) for surjective one-dimensional cellular automata. We show that ultimately right (or left) expansive surjective cellular automata are chain-transitive; this improves a result by Boyle that expansive reversible cellular automata are chain-transitive. We then use this to show that left-sided pseudo-orbit tracing property and right-sided ultimate expansivity together imply pseudo-orbit tracing property for surjective cellular automata. This reproves some known results, most notably some of Nasu’s. Our result improves Nasu’s result by dropping an assumption of chain-recurrence, however, we remark that this improvement can also be achieved using the Poincaré recurrence theorem. The pseudo-orbit tracing property implies that the trace subshifts of the cellular automaton are sofic shifts. We end by mentioning that among reversible cellular automata over full shifts we have examples of right expansive cellular automata with non-sofic traces, as well as examples of cellular automata with left pseudo-orbit tracing property but non-sofic traces, illustrating that neither assumption can be dropped from the theorem mentioned above. This paper is a generalized and improved version of a conference paper presented in AUTOMATA 2018.

Słowa kluczowe

EN

cellular automata; expansivity; pseudo-orbit tracing property

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 239--259
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Jalonen Joonatan

• Department of Mathematics and Statistics, University of Turku, Finland

autor

Kari Jarkko

• Department of Mathematics and Statistics, University of Turku, Finland

Bibliografia

• [1] Park K. Entropy of a Skew Product with a Z2-action. Pacific Journal of Mathematics, 1996. 172:227-241. URL https://projecteuclid.org/euclid.pjm/1102366193.
• [2] Kůrka P. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory and Dynamical Systems, 1997. doi:10.1017/S014338579706985X.
• [3] Nasu M. Textile systems for Endomorphisms and Automorphisms of the Shift, volume 546. American Mathematical Society, 1995.
• [4] Blanchard F, Maass A. Dynamical properties of expansive one-sided cellular automata. Israel Journal of Mathematics, 1997. 99:149-174. doi:10.1007/BF02760680.
• [5] Boyle M, Fiebig D, Fiebig UR. A dimension group for local homeomorphisms and endomorphisms of one-sided shifts of finite type. Journal fr die reine und angewandte Mathematik, 1997. 487:27-59. doi: 10.1515/crll.1997.487.27.
• [6] Nasu M. The Dynamics of Expansive Invertible Onesided Cellular Automata, 2002. doi:10.1090/S0002-9947-02-03062-3.
• [7] Nasu M. Textile systems and one-sided resolving automorphisms and endomorphisms of the shift, 2008. doi:10.1017/S0143385707000375.
• [8] Kůrka P. Topological and symbolic dynamics, volume 11. Société Mathématique de France, 2003. ISBN-2856291430, 9782856291436.
• [9] Kůrka P. Topological dynamics of one-dimensional cellular automata. Encyclopedia of Complexity and System Sciences (R,.A.Meyers, ed.) Part 20, 2009. pp. 9246-9268.
• [10] Boyle M. Some sofic shifts cannot commute with nonwandering shifts of finite type. Illinois Journal of Mathematics, 2004. 48(4):1267-1277. doi:10.1215/ijm/1258138511.
• [11] Jalonen J, Kari J. On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata. In: Proceedings of AUTOMATA 2018: Cellular Automata and Discrete Complex Systems, volume 10875 of Lecture Notes in Computer Science. 2018 pp. 57-71. doi:10.1007/978-3-319-92675-9_5.
• [12] Lind D, Marcus B. An introduction to symbolic dynamics and coding. Cambridge University Press, 1995. ISBN 0-521-55124-2. doi:doi:10.1017/CBO9780511626302.
• [13] Maruoka A, Kimura M. Inform. Control, 1976. 32(2):158-162. doi:10.1016/S0019-9958(76)90195-9.
• [14] Weiss B. Subshifts of finite type and sofic systems. Monatshefte für Mathematik, 1973. 77:462-474. doi:10.1007/BF01295322.
• [15] Parry W. Intrinsic Markov chains. Transactions of American Mathematical Society, 1964. 112:55-66. doi:10.1090/S0002-9947-1964-0161372-1.
• [16] Meester R, Steif J. Higher-Dimensional Subshifts of Finite Type, Factor Maps and Measures of Maximal Entropy. Pacific Journal of Mathematics, 2001. 200(2):497510. doi:10.2140/pjm.2001.200.497.
• [17] Boyle M, Lind D. Expansive subdynamics. Transactions of the American Mathematical Society, 1997. 349(1):55-102. URL https://www.jstor.org/stable/2155304.
• [18] Jalonen J, Kari J. Conjugacy of One-Dimensional One-Sided Cellular Automata is Undecidable. In: SOFSEM 2018: Theory and Practice of Computer Science, volume 10706 of Lecture Notes in Computer Science. Edizioni della Normale, Cham, 2018 pp. 227-238. doi:10.1007/978-3-319-73117-9_16.
• [19] Kari J. Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences, 1994. 48:149-182. doi:10.1016/S0022-0000(05)80025-X.
• [20] Pavlov R, Schraudner M. Classification of sofic projective subdynamics of multidimensional shifts of finite type, 2015. doi:10.1090/S0002-9947-2014-06259-4.
• [21] Taati S. Cellular automata reversible over limit set, 2007.
• [22] Kari J, Lukkarila V. Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata. Algorithmic Bioprocesses, Natural Computing Series, 2009. pp. 639-660. doi:10.1007/978-3-540-88869-7_32.
• [23] Dartnell P, Maass A, Schwartz F. Combinatorial constructions associated to the dynamics of one-sided cellular automata. Theoretical Computer Science, 2003. 304:485-497. doi:10.1016/S0304-3975(03)00290-1.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).

Research supported by the Academy of Finland Grant 296018