Top

Published in:

2012 | OriginalPaper | Chapter

Basic Concepts of Cellular Automata

Author : Jarkko J. Kari

Published in: Handbook of Natural Computing

Publisher: Springer Berlin Heidelberg

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

search-config

AI-assisted search

Off

Abstract

This chapter reviews some basic concepts and results of the theory of cellular automata (CA). Topics discussed include classical results from the 1960s, relations between various concepts of injectivity and surjectivity, and dynamical system concepts related to chaos in CA. Most results are reported without full proofs but sometimes examples are provided that illustrate the idea of a proof. The classical results discussed include the Garden-of-Eden theorem and the Curtis–Hedlund–Lyndon theorem, as well as the balance property of surjective CA. Different variants of sensitivity to initial conditions and mixing properties are introduced and related to each other. Also, algorithmic aspects and undecidability results are mentioned.

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

next chapter Cellular Automata Dynamical Systems

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

Berger R (1966) The undecidability of the domino problem. Mem Amer Math Soc 66:1–72

Berlekamp ER, Conway JH, Guy RK (1982) Winning ways for your mathematical plays, vol II, chap 25. Academic, London

Blanchard F, Maass A (1997) Dynamical properties of expansive one-sided cellular automata. Israel J Math 99:149–174MathSciNetMATHCrossRef

Blanchard F, Tisseur P (2000) Some properties of cellular automata with equicontinuity points. Ann Inst Henri Poincaré, Probab Stat 36(5):569–582MathSciNetMATHCrossRef

Burks A (1970) Von Neumann's self-reproducing automata. In: Burks A (ed) Essays on cellular automata, University of Illinois Press, Champaign, pp 3–64

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

Cook M (2004) Universality in elementary cellular automata. Complex Syst 15:1–40MathSciNetMATH

Czeizler E, Kari J (2005) A tight linear bound on the neighborhood of inverse cellular automata. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M (eds) ICALP, Lecture notes in computer science, vol 3580, Springer, Berlin, pp 410–420

Devaney RL (1986) An introduction to chaotic dynamical systems. Benjamin/Cummings, Menlo Park, CAMATH

Durand B (1998) Global properties of cellular automata. In: Goles E, Martinez S (eds) Cellular automata and complex systems. Kluwer, Dordrecht

Durand B, Formenti E, Varouchas G (2003) On undecidability of equicontinuity classification for cellular automata. In: Morvan M, Remila E (eds) Discrete models for complex systems, DMCS’03, DMTCS Conference Volume AB, Lyon, France, pp 117–128

Gardner M (1970) The fantastic combinations of John Conway's new solitaire game “ Life ”. Sci Am 223(4): 120–123CrossRef

Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theor 3:320–375MathSciNetMATHCrossRef

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

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

Kari J, Ollinger N (2008) Periodicity and immortality in reversible computing. In: Ochmanski E, Tyszkiewicz J (eds) MFCS, Lecture notes in computer science, vol 5162, Springer, Berlin, pp 419–430

Kari J, Vanier P, Zeume T (2009) Bounds on non-surjective cellular automata. In: Královic R, Urzyczyn P (eds) MFCS, Lecture notes in computer Science, vol 5734, Springer, Berlin, pp 439–450

Kůrka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Theor Dyn Syst 17:417–433MATHCrossRef

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

Maruoka A, Kimura M (1976) Condition for injectivity of global maps for tessellation automata. Inform Control 32(2):158–162. doi: 10.1016/S0019-9958(76)90195-9, URL http://www.sciencedirect.com/science/article/B7MFM-4DX4D7R-V/2/409f935b249fa44868bb569dffb5eb37

Moore EF (1962) Machine models of self-reproduction. In: Bellman RE (ed) Proceedings of symposia in applied mathematics XIV: “Mathematical problems in the biological sciences”, AMS, pp 17–33

Myhill J (1963) The converse of Moore's Garden-of-Eden theorem. Proc Am Math Soc 14:685–686MathSciNetMATH

von Neumann J (1966) Theory of self-reproducing automata. In: Burks AW (ed) University of Illinois Press, Urbana, London

Sablik M, Theyssier G (2008) Topological dynamics of 2D cellular automata. In: CiE ’08: Proceedings of the 4th conference on computability in Europe, Springer, Berlin, Heidelberg, pp 523–532

Shereshevsky MA (1993) Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indag Math 4(2):203–210MathSciNetMATHCrossRef

Sutner K (1991) De Bruijn graphs and linear cellular automata. Complex Syst 5:19–31MathSciNetMATH

Wang H (1961) Proving theorems by pattern recognition - ii. Bell Syst Tech J 40:1–42

Wolfram S (ed) (1986) Theory and applications of cellular automata. World Scientific, SingaporeMATH

Wolfram S (2002) A new kind of science. Wolfram Media, Champaign, IL, USAMATH

Title: Basic Concepts of Cellular Automata
Author: Jarkko J. Kari
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_1

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner