Periodic Orbits and Dynamical Complexity in Cellular Automata

• Autorzy: Dennunzio A. , Di Lena P. , Formenti E. , Margara L.
• Języki publikacji: EN

Abstrakty

EN

We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are temporally but not spatially periodic for a given surjective automaton. The cardinality of this set turns out to be inversely related to the dynamical complexity of the cellular automaton. In particular, we show that for surjective Cellular Automata, the set of strictly temporally periodic configurations has strictly positive measure if and only if the cellular automaton is equicontinuous. Furthermore, we show that the set of strictly temporally periodic configurations is dense for almost equicontinuous surjective cellular automata, while it is empty for the positively expansive ones. In the class of additive cellular automata, the set of strictly temporally periodic points can be either dense or empty. The latter happens if and only if the cellular automaton is topologically transitive. This is not true for general transitive Cellular Automata, where the set of of strictly temporally periodic points can be non-empty and non-dense.

Słowa kluczowe

EN

cellular automata; spatially and temporally periodic configurations; symbolic dynamics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 183--199
• Opis fizyczny: Bibliogr. 42 poz.

Twórcy

autor

Dennunzio A.

• Università degli Studi di Milano–Bicocca, Dipartimento di Informatica, Sistemistica e Comunicazione, Viale Sarca 336, 20126 Milano, Italy

autor

Di Lena P.

• Università degli Studi di Bologna, Dipartimento di Informatica - Scienza e Ingegneria, Mura Anteo Zamboni 7, 40127 Bologna, Italy

autor

Formenti E.

• Université de Nice-Sophia Antipolis, Laboratoire I3S, 2000 Route des Colles, 06903 Sophia Antipolis, France

autor

Margara L.

• Università degli Studi di Bologna, Dipartimento di Informatica - Scienza e Ingegneria, Mura Anteo Zamboni 7, 40127 Bologna, Italy

Bibliografia

• [1] L. Acerbi, A. Dennunzio, and E. Formenti. Conservation of some dynamical properties for operations on cellular automata. Theoretical Computer Science, 410:3685-3693,2009.
• [2] L. Acerbi, A. Dennunzio, and E. Formenti. Surjective multidimensional cellular automata are non-wandering: A combinatorial proof. Information Processing Letters, 113(38-40): 156-159,2013.
• [3] T. Alarcon, H.M. Byrne, and P.K. Maini. A cellular automaton model for tumour growth in inhomogeneous environment. Journal of Theoretical Biology, 225:257-274,2003.
• [4] F. Blanchard. Dense periodic points in cellular automata. http://www.math.iupui.edu/^mmisiure/open/.
• [5] F. Blanchard and A. Maass. Dynamical properties of expansive one-sided cellular automata. Israel Journal of Mathematics, 99:149-174, 1997.
• [6] F. Blanchard and P. Tisseur. Some properties of cellular automata with equicontinuity points. Annales de l’Institut Henri Poincare, Probabilite et Statistiques, 36:569-582, 2000.
• [7] M. Boyle. Open problems in symbolic dynamics. Geometric and Probabilistic Structures in Dynamics, Contemporary Mathematics, 469:69-118, 2008.
• [8] M. Boyle and L. Bryant. Jointly periodic points in cellular automata: computer explorations and conjectures. Experimental Mathematics, 16:293-302, 2007.
• [9] M. Boyle and B. Kitchens. Periodic points for onto cellular automata. Indagationes Mathematicae, 10:483493, 1999.
• [10] G. Cattaneo, A. Dennunzio, and F. Farina. A full cellular automaton to simulate predator-prey systems. In ACRI, volume 4173 of Lecture Notes in Computer Science, pages 446-451. Springer, 2006.
• [11] G. Cattaneo, A. Dennunzio, E. Formenti, and J. Provillard. Non-uniform cellular automata. In LATA, volume 5457 of Lecture Notes in Computer Science, pages 302-313. Springer, 2009.
• [12] G. Cattaneo, A. Dennunzio, and L. Margara. Chaotic subshifts and related languages applications to onedimensional cellular automata. Fundamenta Informaticae, 52:39-80, 2002.
• [13] G. Cattaneo, A. Dennunzio, and L. Margara. Solution of some conjectures about topological properties of linear cellular automata. Theoretical Computer Science, 325:249-271, 2004.
• [14] G. Cattaneo and L Margara. Topological definitions of chaos applied to cellular automata dynamics. In Lubos Brim, Jozef Gruska, and Jin Zlatuska, editors, Mathematical Foundations of Computer Science 1998, volume 1450 of Lecture Notes in Computer Science, pages 816-824. Springer Berlin Heidelberg, 1998.
• [15] J. Cervelle, A. Dennunzio, and E. Formenti. Chaotic behavior of cellular automata. In B. Meyers, editor, Mathematical basis of cellular automata, Encyclopedia of Complexity and System Science. Springer Verlag, 2009.
• [16] P. Chaudhuri, D. Chowdhury, S. Nandi, and S. Chattopadhyay. Additive Cellular Automata Theory and Applications, volume 1. IEEE Press, 1997.
• [17] B. Chopard. Cellular automata and lattice Boltzmann modeling of physical systems. In G. Rozenberg et al., editor, Handbook of Natural Computing: Theory, Experiments, and Applications. Springer, 2012.
• [18] B. Codenotti and L. Margara. Transitive cellular automata are sensitive. The American Mathematical Monthly, 103:58-62, 1996.
• [19] M. D’Amico, G. Manzini, and L. Margara. On computing the entropy of cellular automata. Theoretical Computer Science, 290:1629-1646,2003.
• [20] A. Dennunzio. From one-dimensional to two-dimensional cellular automata. Fundamenta Informaticae, 115:87-105,2012.
• [21] A. Dennunzio, P. Di Lena, E. Formenti, and L. Margara. On the directional dynamics of additive cellular automata. Theoretical Computer Science, 410:4823-4833, 2009.
• [22] A. Dennunzio and E. Formenti. Decidable properties of 2d cellular automata. In 12th Conference on Developments in Language Theory (DLT 2008), volume 5257 of Lecture Notes in Computer Science, pages 264-275. Springer-Verlag, 2008.
• [23] A. Dennunzio, E. Formenti, and P. Kurka. Cellular automata dynamical systems. In G. Rozenberg et al., editor, Handbook of Natural Computing: Theory, Experiments, and Applications, pages 25-75. Springer, 2012.
• [24] A. Dennunzio, E. Formenti, and J. Provillard. Local rule distributions, language complexity and non-uniform cellular automata. Theoretical Computer Science, 2012. In press.
• [25] A. Dennunzio, E. Formenti, and J. Provillard. Non-uniform cellular automata: Classes, dynamics, and decidability. Information and Computation, 215:32-46, 2012.
• [26] A. Dennunzio, E. Formenti, and M. Weiss. Multidimensional cellular automata: closing property, quasiexpansivity, and (un)decidability issues. Theoretical Computer Science, Submitted, 2013.
• [27] A. Dennunzio, E. Formenti, and M. Weiss. 2d cellular automata: dynamics and undecidability. In Proceedings of 6th Conference on Computability in Europe (CiE 2010), 2010.
• [28] A. Dennunzio, P. Guillon, and B. Masson. Stable dynamics of sand automata. In IFIP TCS, volume 273 of IFIP, pages 157-169. Springer, 2008.
• [29] A. Dennunzio, P. Guillon, and B. Masson. Sand automata as cellular automata. Theoretical Computer Science, 410:3962-3974,2009.
• [30] R. L. Devaney. An Introduction to chaotic dynamical systems. Addison-Wesley, second edition, 1989.
• [31] P. Di Lena and L. Margara. Computational complexity of dynamical systems: the case of cellular automata. Information and Computation, 206:1104-1116,2008.
• [32] F. Farina and A. Dennunzio. A Predator-Prey Cellular Automaton with Parasitic Interactions and Environmental Effects. FundamentaInformaticae, 83:337-353,2008.
• [33] G. A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathematical System Theory, 3:320-375, 1969.
• [34] J. Kari and K. Zhang. Two transitive cellular automata and their strictly periodic points. Preprint, 2013.
• [35] L.B. Kier, P.G. Seybold, and C.-K. Cheng. Modeling Chemical Systems using Cellular Automata. Springer, 2005.
• [36] P. Kurka. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory & Dynamical Systems, 17:417-433,1997.
• [37] C.G. Langton. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D: Nonlinear Phenomena, 42:12 - 37, 1990.
• [38] K. LindgrenandM.G. Nordahl. Universal computation in simple one-dimensional cellular automata. Complex Systems, 4:299-318, 1990.
• [39] G. Manzini and L. Margara. A complete and efficiently computable topological classification of D- dimensional linear cellular automata over Zm. Theoretical Computer Science, 221(1-2):157-177,1999.
• [40] R. Meester and J.E. Steif. Higher-dimensional subshifts of finite type, factor maps and measure of maximal entropy. Pacific Journal of Mathematics, 200:497-318,2001.
• [41] M. Nasu. Textile Systems for Endomorphisms and automorphisms of the shift, volume 114 of Memoires of the American Mathematical Society. American Mathematical Society, 1995.
• [42] S. Wolfram. A new kind of science. Wolfram-Media, 2002.