Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Basic Concepts of Cellular Automata Read chapter Read first chapter

2012 | OriginalPaper | Chapter

Cellular Automata Dynamical Systems

Authors : Alberto Dennunzio, Enrico Formenti, Petr Kůrka

Published in: Handbook of Natural Computing

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present recent studies on cellular automata (CAs) viewed as discrete dynamical systems. In the first part, we illustrate the relations between two important notions: subshift attractors and signal subshifts, measure attractors and particle weight functions. The second part of the chapter considers some operations on the space of one-dimensional CA configurations, namely, shifting and lifting, showing that they conserve many dynamical properties while reducing complexity. The final part reports recent investigations on two-dimensional CA. In particular, we report a construction (slicing construction) that allows us to see a two-dimensional CA as a one-dimensional one and to lift some one-dimensional results to the two-dimensional case.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Basic Concepts of Cellular Automata
next chapter Algorithmic Tools on Cellular Automata
Literature
Acerbi L, Dennunzio A, Formenti E (2007) Shifting and lifting of cellular automata. In: Third conference on computability in Europe (CiE 2007), Lecture notes in computer science, vol 4497. Springer, Siena, Italy, pp 1–10
Akin E (1991) The general topology of dynamical systems. American Mathematical Society, Providence, RI
Amoroso S, Patt YN (1972) Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J Comput Syst Sci 6:448–464MathSciNetCrossRefMATH
Bernardi V, Durand B, Formenti E, Kari J (2005) A new dimension sensitive property for cellular automata. Theor Comput Sci 345:235–247MathSciNetCrossRefMATH
Blanchard F, Tisseur P (2000) Some properties of cellular automata with equicontinuity points. Ann Inst Henri Poincaré, Probabilité et Statistiques 36:569–582MathSciNetCrossRefMATH
Cattaneo G, Finelli M, Margara L (2000) Investigating topological chaos by elementary cellular automata dynamics. Theor Comput Sci 244:219–241MathSciNetCrossRefMATH
Cattaneo G, Dennunzio A, Margara L (2002) Chaotic subshifts and related languages applications to one-dimensional cellular automata. Fundam Inf 52:39–80MathSciNetMATH
Cattaneo G, Dennunzio A, Margara L (2004) Solution of some conjectures about topological properties of linear cellular automata. Theor Comput Sci 325:249–271MathSciNetCrossRefMATH
Cervelle J, Dennunzio A, Formenti E (2008) Chaotic behavior of cellular automata. In: Meyers B (ed) Mathematical basis of cellular automata, Encyclopedia of complexity and system science. Springer, Berlin, Germany
Chaudhuri P, Chowdhury D, Nandi S, Chattopadhyay S (1997) Additive cellular automata theory and applications, vol 1. IEEE Press, Mountain View, CAMATH
Chopard B (2012) Cellular automata and lattice Boltzmann modeling of physical systems. Handbook of natural computing. Springer, Heidelberg, Germany
de Sá PG, Maes C (1992) The Gacs-Kurdyumov-Levin automaton revisited. J Stat Phys 67(3/4):507–522CrossRefMATH
Dennunzio A, Formenti E (2008) Decidable properties of 2D cellular automata. In: Twelfth conference on developments in language theory (DLT 2008), Lecture notes in computer science, vol 5257. Springer, New York, pp 264–275
Dennunzio A, Formenti E (2009) 2D cellular automata: new constructions and dynamics, 410(38–40):3685–3693
Dennunzio A, Guillon P, Masson B (2008) Stable dynamics of sand automata. In: Fifth IFIP conference on theoretical computer science. TCS 2008, Milan, Italy, September, 8–10, 2008, vol 273, IFIP, Int. Fed. Inf. Process. Springer, Heidelberg, Germany, pp 157–179
Di Lena P (2006) Decidable properties for regular cellular automata. In: Fourth IFIP conference on theoretical computer science. TCS 2006, Santiago, Chile, August, 23–24, 2006, IFIP, Int. Fed. Inf. Process. vol 209. Springer, pp 185–196
Di Lena P, Margara L (2008) Computational complexity of dynamical systems: the case of cellular automata. Inf Comput 206:1104–1116CrossRefMATH
Durand B (1993) Global properties of 2D cellular automata: some complexity results. In: MFCS, Lecture notes in computer science, vol 711. Springer, Berlin, Germany, pp 433–441
Durand B (1998) Global properties of cellular automata. In: Goles E, Martinez S (eds) Cellular automata and complex systems. Kluwer, Dordrecht, The Netherlands
Farina F, Dennunzio A (2008) A predator-prey cellular automaton with parasitic interactions and environmental effects. Fundam Inf 83:337–353MathSciNetMATH
Gacs P, Kurdyumov GL, Levin LA (1978) One-dimensional uniform arrays that wash out finite islands. Peredachi Informatiki 14:92–98
Kari J (2008) Tiling problem and undecidability in cellular automata. In: Meyers B (ed) Mathematical basis of cellular automata, Encyclopedia of complexity and system science. Springer, Heidelberg, Germany
Kůrka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Th Dynam Syst 17:417–433CrossRefMATH
Kůrka P (2003a) Cellular automata with vanishing particles. Fundam Inf 58:1–19
Kůrka P (2003b) Topological and symbolic dynamics, Cours spécialisés, vol 11. Société Mathématique de France, Paris
Kůrka P (2005) On the measure attractor of a cellular automaton. Discrete Continuous Dyn Syst 2005 (suppl):524–535
Kůrka P (2007) Cellular automata with infinite number of subshift attractors. Complex Syst 17(3):219–230
Kůrka P (2008) Topological dynamics of one-dimensional cellular automata. In: Meyers B (ed) Mathematical basis of cellular automata, Encyclopedia of complexity and system science. Springer, Heidelberg, Germany
Kůrka P, Maass A (2000) Limit sets of cellular automata associated to probability measures. J Stat Phys 100(5/6):1031–1047CrossRefMATH
Lind D, Marcus B (1995) An introduction to symbolic dynamics and coding. Cambridge University Press, CambridgeCrossRefMATH
Mitchell M, Crutchfield JP, Hraber PT (1994) Evolving cellular automata to perform computations: mechanisms and impediments. Physica D 75:361–391CrossRefMATH
Moore EF (1962) Machine models of self-reproduction. Proc Symp Appl Math 14:13–33
Nasu M (1995) Textile systems for endomorphisms and automorphisms of the shift, Memoires of the American Mathematical Society, vol 114. American Mathematical Society, Providence, RI
Pivato M (2008) The ergodic theory of cellular automata. In: Meyers B (ed) Mathematical basis of cellular automata, Encyclopedia of complexity and system science. Springer, Heidelberg, Germany
Sablik M (2008) Directional dynamics for cellular automata: a sensitivity to the initial conditions approach. Theor Comput Sci 400:1–18MathSciNetCrossRefMATH
Shereshevsky MA (1993) Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indagat Math 4:203–210MathSciNetCrossRefMATH
Shereshevsky MA, Afraimovich VS (1992) Bipermutative cellular automata are topologically conjugate to the one-sided Bernoulli shift. Random Comput Dyn 1:91–98MathSciNet
Theyssier G, Sablik M (2008) Topological dynamics of 2D cellular automata. In: Computability in Europe (CIE’08), Lecture notes in computer science, vol 5028, pp 523–532
Wolfram S (1986) Theory and applications of cellular automata. World Scientific, SingaporeMATH
Metadata
Title
Cellular Automata Dynamical Systems
Authors
Alberto Dennunzio
Enrico Formenti
Petr Kůrka
Copyright Year
2012
Publisher
Springer Berlin Heidelberg
Book
Handbook of Natural Computing

Print ISBN: 978-3-540-92909-3

Electronic ISBN: 978-3-540-92910-9

Copyright Year: 2012

DOI
https://doi.org/10.1007/978-3-540-92910-9_2

Premium Partner

    Image Credits