A Comprehensive Taxonomy of Cellular Automata
arXiv:2401.08408 · doi:10.1016/j.cnsns.2024.108362
Abstract
Cellular automata (CAs) are fully-discrete dynamical models that have received much attention due to the fact that their relatively simple setup can nonetheless express highly complex phenomena. Despite the model's theoretical maturity and abundant computational power, the current lack of a complete survey on the 'taxonomy' of various families of CAs impedes efficient and interdisciplinary progress. This review paper mitigates that deficiency; it provides a methodical overview of five important CA 'families': asynchronous, stochastic, multi-state, extended-neighbourhood, and non-uniform CAs. These five CA families are subsequently presented from four angles. First, a rigorous mathematical definition is given. Second, we map prominent variations within each CA family, as such highlighting mathematical equivalences with types from other families. Third, we discuss the genotype and phenotype of these CA types by means of mathematical tools, indicating when established tools break down. Fourth, we conclude each section with a brief overview of applications related to information theory and mathematical modelling.
48 pages, 7 figures, 5 tables, 386 references
References in corpus (39)
- The large-scale organization of metabolic networks
- Evolutionary prisoner's dilemma game on a square lattice
- Topology of evolving networks: local events and universality
- Cellular Automata Models of Road Traffic
- Evolutionary Games and Computer Simulations
- A review of wildland fire spread modelling, 1990-present 3: Mathematical analogues and simulation models
- Percolation on complex networks: Theory and application
- Self-Organization of Mobile Populations in Cyclic Competition
- Reliable Cellular Automata with Self-Organization
- Lyapunov Exponents in Random Boolean Networks
- Characterizing the network topology of the energy landscapes of atomic clusters
- Damage spreading and Lyapunov exponents in cellular automata
- Coarse-graining of cellular automata, emergence, and the predictability of complex systems
- Rule 54: Exactly solvable model of nonequilibrium statistical mechanics
- Non-deterministic density classification with diffusive probabilistic cellular automata
- Synchronization and Maximum Lyapunov Exponents of Cellular Automata
- Cellular automata and Lyapunov exponents
- Exact results for one dimensional stochastic cellular automata for different types of updates
- Topology regulates pattern formation capacity of binary cellular automata on graphs
- Outer-totalistic cellular automata on graphs
- Stochastic Cellular Automata Model for Stock Market Dynamics
- Authorship Attribution Based on Life-Like Network Automata
- Nonergodic Quantum Dynamics from Deformations of Classical Cellular Automata
- A Full Computation-relevant Topological Dynamics Classification of Elementary Cellular Automata
- Mountain formation by repeated, inhomogeneous crustal failure in a neutron star
- Network Automata: Coupling structure and function in real-world networks
- Asymptotic Behaviour and Ratios of Complexity in Cellular Automata
- Space-time directional Lyapunov exponents for cellular automata
- How to make dull cellular automata complex by adding memory: Rule 126 case study
- On Damage Spreading Transitions
- From deterministic cellular automata to coupled map lattices
- A split-and-perturb decomposition of number-conserving cellular automata
- Reversibility of d-State Finite Cellular Automata
- Analytical and cellular automaton approach to a generalized SEIR model for infection spread in an open crowded space
- Phase transitions in random mixtures of elementary cellular automata
- Effects of Boundary Conditions on Single-File Pedestrian Flow
- A study of fuzzy and many-valued logics in cellular automata
- A Cellular Automaton Model for Diffusive and Dissipative Systems
- Totalistic two-dimensional cellular automata exhibiting global periodic behavior