Document Open Access Logo

Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties

Authors Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.68.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Alberto Dennunzio
  • Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
Enrico Formenti
  • Universite Côte d'Azur, CNRS, I3S, France
Darij Grinberg
  • School of Mathematics, University of Minnesota, Minneapolis, USA
Luciano Margara
  • Department of Computer Science and Engineering, University of Bologna, Campus of Cesena, Via dell'Università 50, 47521 Cesena, Italy

Cite As Get BibTex

Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.68

Abstract

We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e. , with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. 
As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be true also for the general case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Cellular Automata
  • Symbolic Dynamics
  • Complex Systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Luigi Acerbi, Alberto Dennunzio, and Enrico Formenti. Shifting and Lifting of Cellular Automata. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings, volume 4497 of Lecture Notes in Computer Science, pages 1-10. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73001-9.
  2. Luigi Acerbi, Alberto Dennunzio, and Enrico Formenti. Conservation of some dynamical properties for operations on cellular automata. Theor. Comput. Sci., 410(38-40):3685-3693, 2009. Google Scholar
  3. Luigi Acerbi, Alberto Dennunzio, and Enrico Formenti. Surjective multidimensional cellular automata are non-wandering: A combinatorial proof. Inf. Process. Lett., 113(5-6):156-159, 2013. Google Scholar
  4. Nobuo Aoki. Ergodic Automorphisms of Compact Metric Groups are Isomorphic to Bernoulli Shifts. Publications mathématiques et informatique de Rennes, S4:1-10, 1975. Google Scholar
  5. Vincent Bernardi, Bruno Durand, Enrico Formenti, and Jarkko Kari. A New Dimension Sensitive Property for Cellular Automata. In Jirí Fiala, Václav Koubek, and Jan Kratochvíl, editors, Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, volume 3153 of Lecture Notes in Computer Science, pages 416-426. Springer, 2004. Google Scholar
  6. Nino Boccara and Henryk Fuks. Number-conserving cellular automaton rules. Fundam. Inform., 52(1-3):1-13, 2002. Google Scholar
  7. Mike Boyle and Bruce Kitchens. Periodic points for onto cellular automata. Indagationes Mathematicae, 10(4):483-493, 1999. Google Scholar
  8. Lieven Le Bruyn and Michel Van den Bergh. Algebraic properties of linear cellular automata. Linear algebra and its applications, 157:217-234, 1991. Google Scholar
  9. Gianpiero Cattaneo, Alberto Dennunzio, and Fabio Farina. A Full Cellular Automaton to Simulate Predator-Prey Systems. In Samira El Yacoubi, Bastien Chopard, and Stefania Bandini, editors, Cellular Automata, 7th International Conference on Cellular Automata, for Research and Industry, ACRI 2006, Perpignan, France, September 20-23, 2006, Proceedings, volume 4173 of Lecture Notes in Computer Science, pages 446-451. Springer, 2006. Google Scholar
  10. Gianpiero Cattaneo, Alberto Dennunzio, Enrico Formenti, and Julien Provillard. Non-uniform Cellular Automata. In Adrian-Horia Dediu, Armand-Mihai Ionescu, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 302-313. Springer, 2009. Google Scholar
  11. Gianpiero Cattaneo, Alberto Dennunzio, and Luciano Margara. Solution of some conjectures about topological properties of linear cellular automata. Theoretical Computer Science, 325(2):249-271, 2004. Google Scholar
  12. Gianpiero Cattaneo, Enrico Formenti, Giovanni Manzini, and Luciano Margara. Ergodicity, transitivity, and regularity for linear cellular automata over ℤ_m. Theor. Comput. Sci., 233(1-2):147-164, 2000. Google Scholar
  13. Bruno Codenotti and Luciano Margara. Transitive Cellular Automata are Sensitive. The American Mathematical Monthly, 103(1):58-62, 1996. Google Scholar
  14. Michele d'Amico, Giovanni Manzini, and Luciano Margara. On computing the entropy of cellular automata. Theoretical Computer Science, 290(3):1629-1646, 2003. Google Scholar
  15. Manfred Denker, Christian Grillenberger, and Karl Sigmund. Ergodic Theory on Compact Spaces, volume 527 of Lecture Notes in Mathematics. Springer-Verlag Berlin Heidelberg, 1976. Google Scholar
  16. Alberto Dennunzio. From One-dimensional to Two-dimensional Cellular Automata. Fundamenta Informaticae, 115(1):87-105, 2012. Google Scholar
  17. Alberto Dennunzio, Pietro Di Lena, Enrico Formenti, and Luciano Margara. Periodic Orbits and Dynamical Complexity in Cellular Automata. Fundamenta Informaticae, 126(2-3):183-199, 2013. Google Scholar
  18. Alberto Dennunzio, Enrico Formenti, and Luca Manzoni. Computing Issues of Asynchronous CA. Fundamenta Informaticae, 120(2):165-180, 2012. Google Scholar
  19. Alberto Dennunzio, Enrico Formenti, and Luca Manzoni. Reaction systems and extremal combinatorics properties. Theoretical Computer Science, 598:138-149, 2015. Google Scholar
  20. Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, and Antonio E. Porreca. On the dynamical behaviour of linear higher-order cellular automata and its decidability. Inf. Sci., 486:73-87, 2019. Google Scholar
  21. Alberto Dennunzio, Enrico Formenti, Luca Manzoni, and Antonio E. Porreca. Ancestors, descendants, and gardens of Eden in reaction systems. Theoretical Computer Science, 608:16-26, 2015. Google Scholar
  22. Alberto Dennunzio, Enrico Formenti, and Julien Provillard. Non-uniform cellular automata: Classes, dynamics, and decidability. Information and Computation, 215:32-46, 2012. Google Scholar
  23. Alberto Dennunzio, Enrico Formenti, and Julien Provillard. Local rule distributions, language complexity and non-uniform cellular automata. Theoretical Computer Science, 504:38-51, 2013. Google Scholar
  24. Alberto Dennunzio, Enrico Formenti, and Julien Provillard. Three research directions in non-uniform cellular automata. Theoretical Computer Science, 559:73-90, 2014. Google Scholar
  25. Alberto Dennunzio, Enrico Formenti, and Michael Weiss. Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues. Theoretical Computer Science, 516:40-59, 2014. Google Scholar
  26. Alberto Dennunzio, Pierre Guillon, and Benoît Masson. Stable Dynamics of Sand Automata. In Giorgio Ausiello, Juhani Karhumäki, Giancarlo Mauri, and C.-H. Luke Ong, editors, Fifth IFIP International Conference On Theoretical Computer Science - TCS 2008, IFIP 20th World Computer Congress, TC 1, Foundations of Computer Science, September 7-10, 2008, Milano, Italy, volume 273 of IFIP, pages 157-169. Springer, 2008. Google Scholar
  27. Robert Luke Devaney. An Introduction to Chaotic Dynamical Systems. Addison-Wesley advanced book program. Addison-Wesley, 1989. Google Scholar
  28. Pietro di Lena and Luciano Margara. Computational complexity of dynamical systems: The case of cellular automata. Inf. Comput., 206(9-10):1104-1116, 2008. Google Scholar
  29. Bruno Durand, Enrico Formenti, and Zsuzsanna Róka. Number-conserving cellular automata I: decidability. Theor. Comput. Sci., 299(1-3):523-535, 2003. Google Scholar
  30. Bruno Durand, Enrico Formenti, and Georges Varouchas. On undecidability of equicontinuity classification for cellular automata. In Michel Morvan and Eric Rémila, editors, Discrete Models for Complex Systems, DMCS'03, Lyon, France, June 16-19, 2003, volume AB of Discrete Mathematics and Theoretical Computer Science Proceedings, pages 117-128. DMTCS, 2003. Google Scholar
  31. Michele Finelli, Giovanni Manzini, and Luciano Margara. Lyapunov Exponents versus Expansivity and Sensitivity in Cellular Automata. J. Complexity, 14(2):210-233, 1998. Google Scholar
  32. Enrico Formenti and Aristide Grange. Number conserving cellular automata II: dynamics. Theor. Comput. Sci., 304(1-3):269-290, 2003. Google Scholar
  33. Enrico Formenti, Jarkko Kari, and Siamak Taati. On the hierarchy of conservation laws in a cellular automaton. Natural Computing, 10(4):1275-1294, 2011. Google Scholar
  34. Pierre Guillon and Gaétan Richard. Revisiting the Rice Theorem of Cellular Automata. In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, volume 5 of LIPIcs, pages 441-452. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. Google Scholar
  35. G. A. Hedlund. Endomorphisms and Automorphisms of the shift Dynamical System. Mathematical Systems Theory, 3:320-375, 1969. Google Scholar
  36. Masanobu Ito, Nobuyasu Osato, and Masakazu Nasu. Linear cellular automata over ℤ_m. Journal of Computer and Systems Sciences, 27:125-140, 1983. Google Scholar
  37. Jarkko Kari. The Nilpotency Problem of One-Dimensional Cellular Automata. SIAM J. Comput., 21(3):571-586, 1992. Google Scholar
  38. Jarkko Kari. Reversibility and Surjectivity Problems of Cellular Automata. J. Comput. Syst. Sci., 48(1):149-182, 1994. Google Scholar
  39. Jarkko Kari. Rice’s theorem for the limit sets of cellular automata. Theor. Comput. Sci., 127(2):229-254, 1994. Google Scholar
  40. Jarkko Kari. Linear Cellular Automata with Multiple State Variables. In Horst Reichel and Sophie Tison, editors, STACS 2000, volume 1770 of LNCS, pages 110-121. Springer-Verlag, 2000. Google Scholar
  41. P. Kůrka. Topological and Symbolic Dynamics. Volume 11 of Cours Sṕecialiśes. Socíet́e Math́ematique de France, 2004. Google Scholar
  42. Ville Lukkarila. Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata. J. Cellular Automata, 5(3):241-272, 2010. Google Scholar
  43. Giovanni Manzini and Luciano Margara. A Complete and Efficiently Computable Topological Classification of D-dimensional Linear Cellular Automata over ℤ_m. Theor. Comput. Sci., 221(1-2):157-177, 1999. Google Scholar
  44. Giovanni Manzini and Luciano Margara. Attractors of Linear Cellular Automata. J. Comput. Syst. Sci., 58(3):597-610, 1999. Google Scholar
  45. E. F. Moore. Machine models of self-reproduction. Proceedings of Symposia in Applied Mathematics, 14:13-33, 1962. Google Scholar
  46. T. K. Subrahmonian Moothathu. Homogenity of surjective cellular automata. Discrete and continuous dynamical systems, 13:195-202, 2005. Google Scholar
  47. J. Myhill. The converse to Moore’s garden-of-eden theorem. Proceedings of the American Mathematical Society, 14:685-686, 1963. Google Scholar
  48. Mazi Shirvani and Thomas D. Rogers. Ergodic endomorphisms of compact abelian groups. Communications in Mathematical Physics, 118:401-410, 1988. Google Scholar
  49. Shinji Takesue. Staggered invariants in cellular automata. Complex Systems, 9:149-168, 1995. Google Scholar
  50. Peter Walters. An introduction to ergodic theory, volume 79 of Grauate text in mathematics. Springer-Verlag, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact