[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Theory of Cellular Automata: from the Past and Present to Some Path Towards the Future

  • Conference paper
  • First Online:
Cellular Automata (ACRI 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14978))

  • 127 Accesses

Abstract

This is an extended abstract about the research regarding theory of cellular automata: an overall overview of the past and current investigations along with an outlook on some promising research directions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 39.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 49.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Acerbi, L., Dennunzio, A., Formenti, E.: Surjective multidimensional cellular automata are non-wandering: a combinatorial proof. Inf. Process. Lett. 113(5–6), 156–159 (2013)

    Article  MathSciNet  Google Scholar 

  2. Acerbi, L., Dennunzio, A., Formenti, E.: Conservation of some dynamical properties for operations on cellular automata. Theoret. Comput. Sci. 410(38–40), 3685–3693 (2009)

    Article  MathSciNet  Google Scholar 

  3. Amoroso, S., Patt, Y.: Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures. J. Comput. Syst. Sci. 6, 448–464 (1972)

    Article  Google Scholar 

  4. Bandini, S., Mauri, G.: Multilayered cellular automata. Theor. Comput. Sci. 217(1), 99–113 (1999)

    Article  MathSciNet  Google Scholar 

  5. Bandini, S., Mauri, G., Pavesi, G., Simone, C.: Parallel simulation of reaction-diffusion phenomena in percolation processes: a model based on cellular automata. Future Gener. Comput. Syst. 17(6), 679–688 (2001)

    Article  Google Scholar 

  6. Béaur, P., Kari, J.: Effective projections on group shifts to decide properties of group cellular automata. Int. J. Found. Comput. Sci. 35(1 &2), 77–100 (2024)

    Article  MathSciNet  Google Scholar 

  7. Bernardi, V., Durand, B., Formenti, E., Kari, J.: A new dimension sensitive property for cellular automata. Theor. Comput. Sci. 345, 235–247 (2005)

    Article  MathSciNet  Google Scholar 

  8. Blanchard, F., Kůrka, P., Maass, A.: Topological and measure-theoretic properties of one-dimensional cellular automata. Physica D 103, 86–99 (1997)

    Article  MathSciNet  Google Scholar 

  9. Blanchard, F., Tisseur, P.: Some properties of cellular automata with equicontinuity points. Ann. Inst. Henri Poincaré, Probabilité et Statistiques 36, 569–582 (2000)

    Google Scholar 

  10. Bouré, O., Fatès, N., Chevrier, V.: Probing robustness of cellular automata through variations of asynchronous updating. Nat. Comput. 11(4), 553–564 (2012)

    Article  MathSciNet  Google Scholar 

  11. Boyle, M., Kitchens, B.: Periodic points for cellular automata. Indag. Math. 10, 483–493 (1999)

    Article  MathSciNet  Google Scholar 

  12. Cattaneo, G., Dennunzio, A., Margara, L.: Chaotic subshifts and related languages applications to one-dimensional cellular automata. Fund. Inform. 52, 39–80 (2002)

    MathSciNet  Google Scholar 

  13. Cattaneo, G., Finelli, M., Margara, L.: Investigating topological chaos by elementary cellular automata dynamics. Theor. Comput. Sci. 244, 219–241 (2000)

    Article  MathSciNet  Google Scholar 

  14. Cattaneo, G., Dennunzio, A., Margara, L.: Solution of some conjectures about topological properties of linear cellular automata. Theor. Comput. Sci. 325(2), 249–271 (2004)

    Article  MathSciNet  Google Scholar 

  15. Cattaneo, G., Formenti, E., Manzini, G., Margara, L.: Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z} _m\). Theor. Comput. Sci. 233(1–2), 147–164 (2000)

    Article  Google Scholar 

  16. Chopard, B.: Cellular automata and lattice boltzmann modeling of physical systems. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 287–331. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-540-92910-9_9

    Chapter  Google Scholar 

  17. Chopard, B., Luthi, P.O.: Lattice boltzmann computations and applications to physics. Theor. Comput. Sci. 217(1), 115–130 (1999)

    Article  MathSciNet  Google Scholar 

  18. Chopard, B., Masselot, A.: Cellular automata and lattice boltzmann methods: a new approach to computational fluid dynamics and particle transport. Future Gener. Comput. Syst. 16(2–3), 249–257 (1999)

    Article  Google Scholar 

  19. Codenotti, B., Margara, L.: Transitive cellular automata are sensitive. Am. Math. Mon. 103(1), 58–62 (1996)

    Article  MathSciNet  Google Scholar 

  20. Culik, K., Yu, S.: Undecidability of cellular automata classification schemes. Complex Syst. 2, 177–190 (1988)

    Google Scholar 

  21. Dennunzio, A., Formenti, E., Manzoni, L., Mauri, G.: m-Asynchronous cellular automata: from fairness to quasi-fairness. Natural Comput. 12, 561–572 (2013)

    Article  MathSciNet  Google Scholar 

  22. Dennunzio, A., Guillon, P., Masson, B.: Sand automata as cellular automata. Theor. Comput. Sci. 410, 3962–3974 (2009)

    Article  MathSciNet  Google Scholar 

  23. Dennunzio, A.: From one-dimensional to two-dimensional cellular automata. Fund. Inform. 115(1), 87–105 (2012)

    MathSciNet  Google Scholar 

  24. Dennunzio, A., Di Lena, P., Formenti, E., Margara, L.: Periodic orbits and dynamical complexity in cellular automata. Fund. Inform. 126(2–3), 183–199 (2013)

    MathSciNet  Google Scholar 

  25. Dennunzio, A., Formenti, E., Grinberg, D., Margara, L.: Chaos and ergodicity are decidable for linear cellular automata over \((\mathbb{Z} /m\mathbb{Z} )^n\). Inf. Sci. 539, 136–144 (2020)

    Article  Google Scholar 

  26. Dennunzio, A., Formenti, E., Grinberg, D., Margara, L.: Dynamical behavior of additive cellular automata over finite abelian groups. Theor. Comput. Sci. 843, 45–56 (2020)

    Article  MathSciNet  Google Scholar 

  27. Dennunzio, A., Formenti, E., Grinberg, D., Margara, L.: Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption. Inf. Sci. 563, 183–195 (2021)

    Article  MathSciNet  Google Scholar 

  28. Dennunzio, A., Formenti, E., Grinberg, D., Margara, L.: An efficiently computable characterization of stability and instability for linear cellular automata. J. Comput. Syst. Sci. 122, 63–71 (2021)

    Article  MathSciNet  Google Scholar 

  29. Dennunzio, A., Formenti, E., Manzoni, L.: Computing issues of asynchronous CA. Fund. Inform. 120(2), 165–180 (2012)

    MathSciNet  Google Scholar 

  30. Dennunzio, A., Formenti, E., Manzoni, L., Margara, L., Porreca, A.E.: On the dynamical behaviour of linear higher-order cellular automata and its decidability. Inf. Sci. 486, 73–87 (2019)

    Article  Google Scholar 

  31. Dennunzio, A., Formenti, E., Manzoni, L., Mauri, G., Porreca, A.E.: Computational complexity of finite asynchronous cellular automata. Theor. Comput. Sci. 664, 131–143 (2017)

    Article  MathSciNet  Google Scholar 

  32. Dennunzio, A., Formenti, E., Margara, L.: An easy to check characterization of positive expansivity for additive cellular automata over a finite abelian group. IEEE Access 11, 121246–121255 (2023)

    Article  Google Scholar 

  33. Dennunzio, A., Formenti, E., Margara, L.: An efficient algorithm deciding chaos for linear cellular automata over \((\mathbb{Z} /m\mathbb{Z} )^n\) with applications to data encryption. Inf. Sci. 657, 119942 (2024)

    Article  Google Scholar 

  34. Dennunzio, A., Formenti, E., Provillard, J.: Non-uniform cellular automata: classes, dynamics, and decidability. Inf. Comput. 215, 32–46 (2012)

    Article  MathSciNet  Google Scholar 

  35. Dennunzio, A., Formenti, E., Provillard, J.: Local rule distributions, language complexity and non-uniform cellular automata. Theor. Comput. Sci. 504, 38–51 (2013)

    Article  MathSciNet  Google Scholar 

  36. Dennunzio, A., Formenti, E., Provillard, J.: Three research directions in non-uniform cellular automata. Theor. Comput. Sci. 559, 73–90 (2014)

    Article  MathSciNet  Google Scholar 

  37. Dennunzio, A., Formenti, E., Weiss, M.: Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues. Theor. Comput. Sci. 516, 40–59 (2014)

    Article  MathSciNet  Google Scholar 

  38. Dennunzio, A., di Lena, P., Formenti, E., Margara, L.: On the directional dynamics of additive cellular automata. Theor. Comput. Sci. 410(47–49), 4823–4833 (2009)

    Article  MathSciNet  Google Scholar 

  39. Durand, B.: The surjectivity problem for 2D cellular automata. J. Comput. Syst. Sci. 49(3), 718–725 (1994)

    Article  MathSciNet  Google Scholar 

  40. Durand, B.: Global properties of cellular automata. In: Goles, E., Martinez, S. (eds.) Cellular Automata and Complex Systems. Kluwer (1998)

    Google Scholar 

  41. Durand, B., Formenti, E., Varouchas, G.: On undecidability of equicontinuity classification for cellular automata. Disc. Math. Theor. Comput. Sci. AB, 117–128 (2003)

    Google Scholar 

  42. Fatès, N.: Stochastic cellular automata solutions to the density classification problem - when randomness helps computing. Theory Comput. Syst. 53(2), 223–242 (2013)

    Article  MathSciNet  Google Scholar 

  43. Fatès, N.: A guided tour of asynchronous cellular automata. J. Cell. Autom. 9(5–6), 387–416 (2014)

    MathSciNet  Google Scholar 

  44. Fatès, N., Thierry, E., Morvan, M., Schabanel, N.: Fully asynchronous behavior of double-quiescent elementary cellular automata. Theor. Comput. Sci. 362(1–3), 1–16 (2006)

    Article  MathSciNet  Google Scholar 

  45. Fuks, H.: Solving two-dimensional density classification problem with two probabilistic cellular automata. J. Cell. Autom. 10(1–2), 149–160 (2015)

    MathSciNet  Google Scholar 

  46. Goles, E., Lobos, F., Montealegre, P., Ruivo, E.L.P., de Oliveira, P.P.B.: Computational complexity of the stability problem for elementary cellular automata. J. Cell. Autom. 15(4), 261–304 (2020)

    MathSciNet  Google Scholar 

  47. Goles, E., Maldonado, D., Montealegre, P., Ollinger, N.: On the complexity of the stability problem of binary freezing totalistic cellular automata. Inf. Comput. 274, 104535 (2020)

    Article  MathSciNet  Google Scholar 

  48. Goles, E., Montalva-Medel, M., Montealegre, P., Ríos-Wilson, M.: On the complexity of generalized Q2R automaton. Adv. Appl. Math. 138, 102355 (2022)

    Article  MathSciNet  Google Scholar 

  49. Goles, E., Montealegre, P.: The complexity of the asynchronous prediction of the majority automata. Inf. Comput. 274, 104537 (2020)

    Article  MathSciNet  Google Scholar 

  50. Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3, 320–375 (1969)

    Article  MathSciNet  Google Scholar 

  51. Hurd, L.P., Kari, J., Culik, K.: The topological entropy of cellular automata is uncomputable. Ergodic Theory Dyn. Syst. 12, 255–265 (1992)

    Article  MathSciNet  Google Scholar 

  52. Ito, M., Osato, N., Nasu, M.: Linear cellular automata over \(\mathbb{Z} _m\). J. Comput. Syst. Sci. 27, 125–140 (1983)

    Article  Google Scholar 

  53. Kamilya, S., Kari, J.: Nilpotency and periodic points in non-uniform cellular automata. Acta Informatica 58(4), 319–333 (2021)

    Article  MathSciNet  Google Scholar 

  54. Kari, J.: The nilpotency problem of one dimensional cellular automata. SIAM J. Comput. 21, 571–586 (1992)

    Article  MathSciNet  Google Scholar 

  55. Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48, 149–182 (1994)

    Article  MathSciNet  Google Scholar 

  56. Kari, J.: Rice’s theorem for the limit set of cellular automata. Theor. Comput. Sci. 127(2), 229–254 (1994)

    Article  MathSciNet  Google Scholar 

  57. Kari, J.: Theory of cellular automata: a survey. Theor. Comput. Sci. 334(1–3), 3–33 (2005)

    Article  MathSciNet  Google Scholar 

  58. Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21(3), 571–586 (1992)

    Article  MathSciNet  Google Scholar 

  59. Kari, J.: Linear cellular automata with multiple state variables. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 110–121. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-46541-3_9

    Chapter  Google Scholar 

  60. Kůrka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic Theory Dyn. Syst. 17, 417–433 (1997)

    Article  MathSciNet  Google Scholar 

  61. Kůrka, P.: Topological and Symbolic Dynamics, vol. 11 of Cours Spécialisés, Société Mathématique de France (2004)

    Google Scholar 

  62. Lukkarila, V.: Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. J. Cell. Autom. 5(3), 241–272 (2010)

    MathSciNet  Google Scholar 

  63. Mairesse, J., Marcovici, I.: Around probabilistic cellular automata. Theor. Comput. Sci. 559, 42–72 (2014)

    Article  MathSciNet  Google Scholar 

  64. Manenti, L., Manzoni, S., Bandini, S.: A stochastic cellular automata for modeling pedestrian groups distribution. J. Cell. Autom. 8(5–6), 321–332 (2013)

    MathSciNet  Google Scholar 

  65. Manzini, G., Margara, L.: Attractors of linear cellular automata. J. Comput. Syst. Sci. 58(3), 597–610 (1999)

    Article  MathSciNet  Google Scholar 

  66. Manzini, G., Margara, L.: A complete and efficiently computable topological classification of d-dimensional linear cellular automata over \(\mathbb{Z} _m\). Theor. Comput. Sci. 221(1–2), 157–177 (1999)

    Article  Google Scholar 

  67. Manzoni, L.: Asynchronous cellular automata and dynamical properties. Nat. Comput. 11(2), 269–276 (2012)

    Article  MathSciNet  Google Scholar 

  68. Manzoni, L., Umeo, H.: The firing squad synchronization problem on CA with multiple updating cycles. Theor. Comput. Sci. 559, 108–117 (2014)

    Article  MathSciNet  Google Scholar 

  69. Mariot, L.: Enumeration of maximal cycles generated by orthogonal cellular automata. Nat. Comput. 22(3), 477–491 (2023)

    Article  MathSciNet  Google Scholar 

  70. Mariot, L., Manzoni, L.: A classification of s-boxes generated by orthogonal cellular automata. Nat. Comput. 23(1), 5–16 (2024)

    Article  MathSciNet  Google Scholar 

  71. Maruoka, A., Kimura, M.: Conditions for injectivity of global maps for tessellation automata. Inf. Control 32, 158–162 (1976)

    Article  MathSciNet  Google Scholar 

  72. Meyerovitch, T.: Finite entropy for multidimensional cellular automata. Ergodic Theory Dyn. Syst. 28, 1243–1260 (2008)

    Article  MathSciNet  Google Scholar 

  73. Moore, E.F.: Machine models of self-reproduction. Proc. Symp. Appl. Math. 14, 13–33 (1962)

    Google Scholar 

  74. Myhill, J.: The converse to Moore’s garden-of-eden theorem. Proc. Am. Math. Soc. 14, 685–686 (1963)

    MathSciNet  Google Scholar 

  75. de Oliveira, P.P.B., Formenti, E., Perrot, K., Riva, S., Ruivo, E.L.P.: Non-maximal sensitivity to synchronism in elementary cellular automata: exact asymptotic measures. Theor. Comput. Sci. 926, 21–50 (2022)

    Article  MathSciNet  Google Scholar 

  76. Plénet, T., Bagnoli, F., Yacoubi, S.E., Raïevsky, C., Lefèvre, L.: Synchronization of elementary cellular automata. Nat. Comput. 23(1), 31–40 (2024)

    Article  MathSciNet  Google Scholar 

  77. Plénet, T., Yacoubi, S.E., Raïevsky, C., Lefèvre, L.: Observability and reconstructibility of bounded cellular automata. Int. J. Syst. Sci. 53(14), 2901–2917 (2022)

    Article  MathSciNet  Google Scholar 

  78. Sutner, K.: De Bruijn graphs and linear cellular automata. Complex Syst. 5, 19–30 (1991)

    MathSciNet  Google Scholar 

  79. Sutner, K.: On the computational complexity of finite cellular automata. J. Comput. Syst. Sci. 50(1), 87 (1995)

    Article  MathSciNet  Google Scholar 

  80. Theyssier, G., Sablik, M.: Topological dynamics of cellular automata: dimension matters. Theory Comput. Syst. 48, 693–714 (2011)

    Article  MathSciNet  Google Scholar 

  81. Thorimbert, Y., Lätt, J., Chopard, B.: Coupling of lattice Boltzmann shallow water model with lattice Boltzmann free-surface model. J. Comput. Sci. 33, 1–10 (2019)

    Article  MathSciNet  Google Scholar 

  82. Toupance, P., Chopard, B., Lefèvre, L.: System reduction: an approach based on probabilistic cellular automata. Nat. Comput. 23(1), 17–29 (2024)

    Article  MathSciNet  Google Scholar 

  83. Umeo, H.: How to synchronize cellular automata - recent developments -. Fund. Informaticae 171(1–4), 393–419 (2020)

    MathSciNet  Google Scholar 

  84. Wacker, S., Worsch, T.: On completeness and decidability of phase space invertible asynchronous cellular automata. Fund. Informaticae 126(2–3), 157–181 (2013)

    Article  MathSciNet  Google Scholar 

  85. Wolnik, B., Dziemianczuk, M., Baets, B.D.: Non-uniform number-conserving elementary cellular automata. Inf. Sci. 626, 851–866 (2023)

    Article  Google Scholar 

  86. Worsch, T.: Towards intrinsically universal asynchronous CA. Nat. Comput. 12(4), 539–550 (2013)

    Article  MathSciNet  Google Scholar 

  87. Yacoubi, S.E., Plénet, T., Dridi, S., Bagnoli, F., Lefèvre, L., Raïevsky, C.: Some control and observation issues in cellular automata. Complex Syst. 30(3), 391–413 (2021)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336, 20126, Milan, MI, Italy

    Alberto Dennunzio

Authors
  1. Alberto Dennunzio
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto Dennunzio .

Editor information

Editors and Affiliations

  1. University of Florence, Sesto Fiorentino, Italy

    Franco Bagnoli

  2. Ghent University, Ghent, Belgium

    Jan Baetens

  3. University of Milano-Bicocca, Milan, Italy

    Stefania Bandini

  4. University of Florence, Sesto Fiorentino, Italy

    Tommaso Matteuzzi

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dennunzio, A. (2024). Theory of Cellular Automata: from the Past and Present to Some Path Towards the Future. In: Bagnoli, F., Baetens, J., Bandini, S., Matteuzzi, T. (eds) Cellular Automata. ACRI 2024. Lecture Notes in Computer Science, vol 14978. Springer, Cham. https://doi.org/10.1007/978-3-031-71552-5_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-71552-5_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-71551-8

  • Online ISBN: 978-3-031-71552-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation