Document Open Access Logo

From Linear to Additive Cellular Automata

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.125.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Alberto Dennunzio
  • Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Milano, Italy
Enrico Formenti
  • Université Côte d'Azur, CNRS, I3S, Nice, France
Darij Grinberg
  • Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach-Walke, Germany
Luciano Margara
  • Department of Computer Science and Engineering, University of Bologna, Cesena, Italy

Cite As Get BibTex

Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. From Linear to Additive Cellular Automata. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 125:1-125:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.125

Abstract

This paper proves the decidability of several important properties of additive cellular automata over finite abelian groups. First of all, we prove that equicontinuity and sensitivity to initial conditions are decidable for a nontrivial subclass of additive cellular automata, namely, the linear cellular automata over 𝕂ⁿ, where 𝕂 is the ring ℤ/mℤ. The proof of this last result has required to prove a general result on the powers of matrices over a commutative ring which is of interest in its own.
Then, we extend the decidability result concerning sensitivity and equicontinuity to the whole class of additive cellular automata over a finite abelian group and for such a class we also prove the decidability of topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to it. Finally, a decidable characterization of injectivity and surjectivity for additive cellular automata over a finite abelian group is provided in terms of injectivity and surjectivity of an associated linear cellular automata over 𝕂ⁿ.

Subject Classification

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

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. Conservation of some dynamical properties for operations on cellular automata. Theoretical Computer Science, 410(38-40):3685-3693, 2009. Google Scholar
  2. 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
  3. Nino Boccara and Henryk Fuks. Number-conserving cellular automaton rules. Fundam. Inform., 52(1-3):1-13, 2002. Google Scholar
  4. 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
  5. 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
  6. 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
  7. Gianpiero Cattaneo, Enrico Formenti, Giovanni Manzini, and Luciano Margara. Ergodicity, transitivity, and regularity for linear cellular automata over ℤ_m. Theoretical Computer Science, 233(1-2):147-164, 2000. Google Scholar
  8. Alberto Dennunzio. From one-dimensional to two-dimensional cellular automata. Fundamenta Informaticae, 115(1):87-105, 2012. Google Scholar
  9. 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
  10. 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, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 68:1-68:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.68.
  11. Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear and additive cellular automata. Preprint available on arXiv, 2019. URL: http://arxiv.org/abs/1907.08565.
  12. Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. Chaos and ergodicity are decidable for linear cellular automata over (ℤ/mℤ)ⁿ. Preprint submitted to an international journal, 2020. Google Scholar
  13. Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. Dynamical behavior of additive cellular automata over finite abelian groups. Preprint submitted to an international journal, 2020. Google Scholar
  14. 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. Information Sciences, 486:73-87, 2019. Google Scholar
  15. Alberto Dennunzio, Enrico Formenti, and Julien Provillard. Non-uniform cellular automata: Classes, dynamics, and decidability. Information and Computation, 215:32-46, 2012. Google Scholar
  16. 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
  17. Alberto Dennunzio, Enrico Formenti, and Julien Provillard. Three research directions in non-uniform cellular automata. Theoretical Computer Science, 559:73-90, 2014. Google Scholar
  18. 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
  19. Alberto Dennunzio, Pietro Di Lena, Enrico Formenti, and Luciano Margara. On the directional dynamics of additive cellular automata. Theoretical Computer Science, 410(47-49):4823-4833, 2009. Google Scholar
  20. Bruno Durand, Enrico Formenti, and Zsuzsanna Róka. Number-conserving cellular automata I: decidability. Theoretical Computer Science, 299(1-3):523-535, 2003. Google Scholar
  21. Bruno Durand, Enrico Formenti, and Georges Varouchas. On undecidability of equicontinuity classification for cellular automata. In 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
  22. Fabio Farina and Alberto Dennunzio. A predator-prey cellular automaton with parasitic interactions and environmental effects. Fundamenta Informaticae, 83(4):337-353, 2008. Google Scholar
  23. Enrico Formenti and Aristide Grange. Number conserving cellular automata II: dynamics. Theoretical Compututer Science, 304(1-3):269-290, 2003. Google Scholar
  24. 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
  25. 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
  26. Masanobu Ito, Nobuyasu Osato, and Masakazu Nasu. Linear cellular automata over ℤ_m. Journal of Computer and Systems Sciences, 27:125-140, 1983. Google Scholar
  27. Jarkko Kari. Rice’s theorem for the limit sets of cellular automata. Theoretical Computer Science, 127(2):229-254, 1994. Google Scholar
  28. 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
  29. Petr Kůrka. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory and Dynamical Systems, 17(2):417–433, 1997. Google Scholar
  30. Giovanni Manzini and Luciano Margara. Attractors of linear cellular automata. Journal of Computer & System Sciences, 58(3):597-610, 1999. Google Scholar
  31. Giovanni Manzini and Luciano Margara. A complete and efficiently computable topological classification of d-dimensional linear cellular automata over ℤ_m. Theoretical Computer Science, 221(1-2):157-177, 1999. Google Scholar
  32. Edward Forrest Moore. Machine models of self-reproduction. Proceedings of Symposia in Applied Mathematics, 14:13-33, 1962. Google Scholar
  33. John Myhill. The converse to Moore’s garden-of-eden theorem. Proceedings of the American Mathematical Society, 14:685-686, 1963. Google Scholar
  34. Shinji Takesue. Staggered invariants in cellular automata. Complex Systems, 9:149-168, 1995. 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