Abstract
We overview networks which characterise dynamics in cellular automata. These networks are derived from one-dimensional cellular automaton rules and global states of the automaton evolution: de Bruijn diagrams, subsystem diagrams, basins of attraction, and jump-graphs. These networks are used to understand properties of spatially-extended dynamical systems: emergence of non-trivial patterns, self-organisation, reversibility and chaos. Particular attention is paid to networks determined by travelling self-localisations, or gliders.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Repository Rule 54 http://uncomp.uwe.ac.uk/genaro/Rule54.html.
- 2.
Repository Rule 110 http://uncomp.uwe.ac.uk/genaro/Rule110.html.
- 3.
Complex Cellular Automata Repository http://uncomp.uwe.ac.uk/genaro/Complex_CA_repository.html.
- 4.
Gliders in Rule 110 http://uncomp.uwe.ac.uk/genaro/rule110/glidersRule110.html.
- 5.
Discrete Dynamics Lab http://www.ddlab.org.
References
Adamatzky, A. (ed.): Game of Life Cellular Automata. Springer, London (2010)
Adamatzky, A., Martínez, G.J. (eds.): Designing Beauty: The Art of Cellular Automata. Springer, Berlin (2016)
Chen, B., Chen, F., Martínez, G.J., Tong, D.: A symbolic dynamics perspective of the game of three-dimensional life. Complex Syst. 25(1) (2016)
Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1), 1–40 (2004)
Devaney, R.: Chaotic Dynamical Systems. Addison-Wesley (1989)
Guan, J., Chen, F.: On symbolic representations of one-dimensional cellular automata. J. Cell. Autom. 10(1–2), 53–63 (2015)
Gutowitz, H.A., Victor, J.D., Knight, B.W.: Local structure theory for cellular automata. Physica D 28, 18–48 (1987)
Li, P., Li, Z., Halang, W.A., Chen, G.: Li–Yorke chaos in a spatiotemporal chaotic system. Chaos, Solitons Fractals 33(2), 335–341 (2007)
Martínez, G.J.: A note on elementary cellular automata classification. J. Cell. Autom. 8(3–4), 233–259 (2013)
Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates. Chaos, Fractals Solitons 28(1), 100–111 (2006)
Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Complete characterization of structure of rule 54. Complex Syst. 23(3), 259–293 (2014)
McIntosh, H.V.: Wolfram’s class IV automata and a good life. Physica D 45(1–3), 105–121 (1990)
McIntosh, H.V.: Linear cellular automata via de Bruijn diagrams. http://delta.cs.cinvestav.mx/~mcintosh/cellularautomata/Papers_files/debruijn.pdf. Cited 10 August (1991)
McIntosh, H.V.: Reversible cellular automata. http://delta.cs.cinvestav.mx/~mcintosh/cellularautomata/Papers_files/rca.pdf. Cited 10 April (1991)
McIntosh, H.V.: One Dimensional Cellular Automata. Luniver Press, Bristol (2009)
Martínez, G.J., McIntosh, H.V., Mora, J.C.S.T.: Gliders in rule 110. Int. J. Unconv. Comput. 2(1), 1–49 (2006)
Martínez, G.J., McIntosh, H.V., Mora, J.C.S.T., Vergara, S.V.C.: Determining a regular language by glider-based structures called phases fi_1 in rule 110. J. Cell. Autom. 3(3), 231–270 (2008)
Martínez, G.J., Mora, J.C.S.T., Zenil, H.: Computation and universality: class IV versus class III cellular automata. J. Cell. Autom. 7(5–6), 393–430 (2013)
Mora, J.C.S.T., Vergara, S.V.C., Martínez, G.J., McIntosh, H.V.: Procedures for calculating reversible one-dimensional cellular automata. Physica D 202, 134–141 (2005)
von Neumann, J.: Theory of self-reproducing automata. In: Burks, A.W. (ed.) University of Illinois Press, Urbana (1966)
Voorhees, B.H.: Computational Analysis of One-Dimensional Cellular Automata. World Scientific Series on Nonlinear Science, Series A, vol. 15, Singapore (1996)
Tian, C., Chen, G.: Chaos in the sense of LiYorke in coupled map lattices. Physica A 376, 246–252 (2007)
Wuensche, A., Lesser, M.: The Global Dynamics of Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, Addison-Wesley Publishing Company (1992)
Wolfram, S.: Cellular Automata and Complexity. Addison-Wesley Publishing Company, Colorado (1994)
Wuensche, A.: Exploring Discrete Dynamics, 2nd edn. Luniver Press, Bristol (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer-Verlag GmbH Germany
About this chapter
Cite this chapter
Martínez, G.J., Adamatzky, A., Chen, B., Chen, F., Seck-Tuoh-Mora, J.C. (2018). Simple Networks on Complex Cellular Automata: From de Bruijn Diagrams to Jump-Graphs. In: Zelinka, I., Chen, G. (eds) Evolutionary Algorithms, Swarm Dynamics and Complex Networks. Emergence, Complexity and Computation, vol 26. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-55663-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-662-55663-4_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-55661-0
Online ISBN: 978-3-662-55663-4
eBook Packages: EngineeringEngineering (R0)