Simple Networks on Complex Cellular Automata: From de Bruijn Diagrams to Jump-Graphs

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 networksdetermined by travelling self-localisations, or gliders.