# A Comprehensive Taxonomy of Cellular Automata

Michiel Rollier<EMAIL_ADDRESS>Kallil M.C. Zielinski  Aisling J.
Daly  Odemir M. Bruno  Jan M. Baetens

###### 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.

###### keywords:

Discrete Dynamical Systems , Cellular Automata , Elementary , Asynchronous ,
Stochastic , Multiple-state , Network Automata , Non-uniform

††journal: Information Sciences

[ugent] organization=BionamiX, Fac. of Bioscience Engineering, Ghent
University, addressline=Coupure Links, 653, city=Ghent, postcode=9000,
country=Belgium

[usp] organization=São Carlos Institute of Physics, University of São Paulo,
addressline=Av. Trab. São Carlense, 400, city=São Carlos, postcode=13566-590,
country=Brazil

We distinguish five families of cellular automata (CAs) from elementary CAs.

CA types from distinct families are often mathematically equivalent.

CA families are mathematically examined by means of their genotype and
phenotype.

We discuss applications related to information theory and mathematical
modelling.

This survey has a wide scope and a comprehensive bibliography.

##  1 Introduction

###  1.1 Definition

A cellular automaton (CA) is a discrete dynamical system, first defined by
John von Neumann while attempting to mimic and explain biological self-
replication [339]. He describes an $n$-dimensional ($n$-D) regular lattice
whose cells can take a discrete number of states. The state of every cell is
evaluated at regular time steps, obeying a rule that only depends on the
states of cells in its proximity. We represent such an object as a sextuple
$\mathcal{C}$ as follows.

######  Definition 1.1 (Cellular automaton).

A cellular automaton (CA) is a sextuple
$\mathcal{C}=\langle\mathcal{T},S,s,s_{0},\mathcal{N},\phi\rangle$, where

  1. 1.

$\mathcal{T}$ is a countably infinite regular tessellation of an
$n$-dimensional Euclidean space $\mathbb{R}^{n}$ consisting of cells $c_{i}$,
$i\in\mathbb{Z}$;

  2. 2.

$S$ is a finite set of $k$ states, often $S\subset\mathbb{Z}$

  3. 3.

The output function $s:\mathcal{T}\times\mathbb{Z}\rightarrow S$ yields the
state value of cell $c_{i}$ at the $t$-th discrete time step, i.e.
$s(c_{i},t)$;

  4. 4.

The function $s_{0}:\mathcal{T}\rightarrow S$ assigns to every cell $c_{i}$ an
initial state, i.e. $s(c_{i},0)=s_{0}(c_{i})$;

  5. 5.

The neighbourhood function
$\mathcal{N}:\mathcal{T}\rightarrow\mathcal{P}(\mathcal{T})$ maps every cell
$c_{i}$ to a finite subset of $\mathcal{T}$,

$\mathcal{N}(c_{i})=\\{c_{i,1},\ldots,c_{i,{|\mathcal{N}|}}\\}\equiv\\{c_{i,j}\\}_{j=1}^{|\mathcal{N}|},$

where $c_{i,j}$ is the $j$-th neighbour of cell $c_{i}$.

  6. 6.

The function $\phi:S^{|\mathcal{N}|}\rightarrow S$ determines the state of
cell $c_{i}$, i.e.

$s(c_{i},t+1)=\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),$

where $\tilde{s}(\mathcal{N}(c_{i}),t)$ is the tuple
$\left(s(c_{i_{j}},t)\right)^{|\mathcal{N}|}_{j=1}$. This function $\phi$ is
called the ‘local update rule’.

By acting on all cells, $\phi$ induces a ‘global update rule’
$\Phi:S^{\mathbb{Z}^{n}}\rightarrow S^{\mathbb{Z}^{n}}$ on the space of all
possible configurations.

Despite their simple nature, CAs are capable of generating spectacular
complexity; some have even been proven to be computationally universal [350].
The potential of this “new kind of science” [353] has lead to an increasingly
wide interest from scholars over the entire scientific landscape [296],
roughly classified into three axes of study [107]: pure mathematics, computer
science, and mathematical modelling. While the maths of CAs is concerned with
formal CA structures and symbolic dynamics [161], the latter two approaches
are associated with a number of applications, a selection of which we list in
Tab. 1.1. In virtually all of these domains, however, one or more of the
properties of the CA ‘sensu stricto’ as defined in Def. 1.1, are generalised.
This results in abandoning uniformity, locality, and/or synchronicity [45],
and allows for what we may call CAs ‘sensu lato’.

Table 1.1: An overview of CAs used in various research domains, accompanied with references to (topical) surveys, influential classical papers, and more recent work. Citations are colour-coded according to the CA family the application principally makes use of (ACA, SCA, MSCA, ENCA, $\nu$CA, cf. Tab. 1.5). Citations coloured black either use ECAs, or are not easily identified with a single CA family. Research domain |  Surveys |  Classical papers |  Recent work
---|---|---|---
Computer science
Artificial life |  [148] |  [176, 177, 317] |  [263]
Computer architecture |  [232] |  [47, 167] |  [190], [367], [61]
Computational tasks |  [227, 229] |  [325], [310] |  [290], [233, 257]
Cryptography |  [266] |  [352, 1], [173], [303] |  [230], [343, 320, 77]
Data compression |  [284] |  [81], [173], [240, 341] |  [67, 373, 13], [222]
Pattern recognition |  [203] |  [238], [202] |  [112]
Mathematical modelling
Biology |  [104, 16, 53, 364] |  [169], [151], [307, 258] |  [233, 166], [205]
Chemistry |  [269, 218] |  [304, 169, 168], [70, 272], [370], [345] |  [368, 126], [332]
Ecology |  [142, 264, 36], [101] |  [138], [141], [271] |  [58], [220]
Epidemiology |  [134, 91] |  [114, 221, 216], [278] |  [124, 231, 157, 298, 191], [65], [241], [86, 217, 103]
Geology |  [265, 156] |  [140, 14], [78] |  [165], [197], [62]
Medical science |  [280] |  [66], [243, 258], [160], [15] |  [242, 193], [133, 105]
Forest fires |  [321, 259] |  [73, 137] |  [237, 188], [375, 113]
Physics |  [71, 148], [52, 148] |  [225, 336], [329], [351, 182] |  [55], [147, 165]
Sociology |  [139] |  [183, 249] |  [308], [342]
Traffic |  [348, 199], [119] |  [297, 239] |  [204], [256]
Urban planning |  [295, 3, 68] |  [347], [75, 74] |  [189], [365], [153]

The goal of this review paper is to map the taxonomy of the most influential
CA variations that go beyond the classical definition in Def. 1.1,
additionally indicating the implications of the particular extension on the
mathematical structure and behaviour, and listing a number of prominent
applications. Rather than an in-depth discussion of the applications, or a
lengthy collection of scrutinous formal proofs, our ambition is to establish
an overview of the CA landscape starting from its definition.

While Bhattacharjee et al. [45] established a similar survey, the merit of our
work lies in its highly systematic approach. Our hope is that this will help
the reader to observe the large collection of CA extensions not as a melting
pot of trial and error, but as a well-structured family tree. Like a
taxonomist, we identify various CA families, each containing several types
with distinct definition variations. Unlike in biological taxonomy, however,
we encounter CA types that belong to multiple families, due to a demonstrated
mathematical equivalence.

###  1.2 Elementary CAs

One type of CA sensu stricto, the so-called ‘elementary’ CA (ECA), has been
studied extensively [350, 349, 186], and serves as the CA archetype. This is
due to the observation that such CAs are the simplest non-trivial type
(leaving 1-neighbour binary CAs aside [37]). The ECA is defined by further
narrowing Def. 1.1 as follows:

######  Definition 1.2 (Elementary cellular automaton).

An elementary cellular automaton (ECA) is a sextuple
$\mathcal{C}=\langle\mathcal{T},S,s,s_{0},\mathcal{N},\phi\rangle$, where

  1. 1.

$\mathcal{T}$ is a countably infinite regular tessellation of the 1-D
Euclidean space $\mathbb{R}$ consisting of cells $c_{i}$, $i\in\mathbb{Z}$;

  2. 2.

$S$ is the binary set $\\{0,1\\}$;

  3. 3.

The output function $s:\mathcal{T}\times\mathbb{Z}\rightarrow S$ yields the
state value of cell $c_{i}$ at the $t$-th discrete time step, i.e.
$s(c_{i},t)$;

  4. 4.

The function $s_{0}:\mathcal{T}\rightarrow S$ assigns to every cell $c_{i}$ an
initial state, i.e. $s(c_{i},0)=s_{0}(c_{i})$;

  5. 5.

The neighbourhood function $\mathcal{N}:\mathcal{T}\rightarrow\mathcal{T}^{3}$
maps every cell $c_{i}$ to the set
$\mathcal{N}(c_{i})=\\{c_{i-1},c_{i},c_{i+1}\\};$

  6. 6.

The local update rule $\phi:S^{3}\rightarrow S$ determines the cell state
evolution, i.e. $s(c_{i},t+1)=\phi(s(c_{i-1},t),s(c_{i},t),s(c_{i+1},t)).$

This setup allows for $2^{2^{3}}=256$ local update rules $\phi$ commonly
referred to as elementary or ‘Wolfram’ rules, and denoted by an integer
$W(\phi)$ from 0 to 255 calculated on the basis of the rule table [353]. We
observe two symmetries: the CA’s overall dynamics remain the same when taking
the mirror image (‘reflection’), and upon switching states (‘complement’).
This implies that we are left with only 88 independent rules (see e.g. [186]).
Some of these very simple rules are still capable of generating complexity
[76], e.g. rule 110 (Fig. 1.1).

Figure 1.1: Rule table (left) and a spacetime diagram (right) for elementary
rule 110, which can generate complex behaviour [76], despite its minimal set-
up.

Practically all CA-related research outside pure mathematics considers a
finite tessellation $\mathcal{T}^{*}\subset\mathcal{T}$ consisting of $N$
cells $\\{c_{i}\ |\ 0<i\leq N\\}$, in order to allow for ‘in silico’
simulations. It is then required to specify the neighbourhood of boundary
cells $c_{1}$ and $c_{N}$, resulting in a slight alteration of Def. 1.2:

######  Definition 1.3 (Finite ECA with boundary conditions).

A finite ECA with $N$ cells and boundary conditions (BCs) is a sextuple
$\mathcal{C}=\langle\mathcal{T}^{*},S,s,s_{0},\mathcal{N},\phi\rangle$, as
defined in Def. 1.2, with changes to properties 1 and 5:

  1. 1\.

$\mathcal{T}^{*}$ is a finite regular tessellation of $\mathbb{R}$ consisting
of $N$ cells $\\{c_{1},\ldots,c_{N}\\}$;

  2. 5\.

The neighbourhood function
$\mathcal{N}:\mathcal{T}^{*}\rightarrow(\mathcal{T}^{*})^{3}\cup\\{c_{0},c_{N+1}\\}$
maps every internal cell $c_{i}$ to the set
$\mathcal{N}(c_{i})=\\{c_{i-1},c_{i},c_{i+1}\\}$.

We rename $\mathcal{T}^{*}\rightarrow\mathcal{T}$ for notational convenience
and assume a finite number of cells in this survey, unless stated otherwise.
The BCs specify the state of ‘fictitious’ cells $c_{0}$ and $c_{N+1}$, most
commonly identifying $s(c_{0})=s(c_{N})$ and $s(c_{N+1})=s(c_{1})$ (periodic
boundary conditions). We provide an overview of possible BCs in Tab. 1.2. The
choice for particular BCs can significantly affect the dynamics of the system,
in particular the propagation of information and the emergence of patterns
[195].

Table 1.2: Overview of possible 1-D ECA boundary conditions (BCs), based on LuValle [195] and Bhattacharjee et al. [45]. BC type |  Definition |  Description
---|---|---
Null |  N/A |  The boundary is not defined and only cells that have a meaningful neighbourhood are updated. Information is lost and the CA is finite in time.
Fixed |  $s(c_{0},t)=s_{0}$, $s(c_{N+1},t)=s_{N+1}$, $s_{0},s_{N+1}\in S$ |  The partially fixed state of neighbourhoods of $c_{1},c_{N}$ generally decreases the number of possible local update results.
Periodic |  $s(c_{0})=s(c_{N})$, $s(c_{N+1})=s(c_{1})$ |  Synonymous to “cyclic” BCs. No cell ‘sees’ the boundary. Conceptually and mathematically close to an infinite $\mathcal{T}$.
Adiabatic |  $s(c_{0})=s(c_{1})$, $s(c_{N+1})=s(c_{N})$ |  Related to Neumann BCs for numerical solutions of (P)DEs. Decreases the number of possible update values.
Reflexive |  $s(c_{0})=s(c_{2})$, $s(c_{N+1})=s(c_{N-1})$ |  Also related to Neumann BCs for numerical solutions of (P)DEs. Decreases the number of possible update values.
Intermediate |  $s(c_{0})=s(c_{i})$, $s(c_{N+1})=s(c_{j})$ for some $i,j\in\\{1,\ldots,N\\}$ |  Generalisation of previous BCs. For symmetry, typically $i+j=M+1$. If $2<i,j<M-1$, all possible state configurations are still possible.
Random |  $s(c_{0},t),s(c_{N+1},t)\in S$ |  Entirely random choice for every time step $t$.
Distributed |  $s(c_{0},t),s(c_{N+1},t)\sim P(S)$ |  Most general case: a random choice is made for a particular probability distribution over $S$.

ECAs have historically gotten attention as random number generators [352], for
inspiring computer processor design [267], and they have served as toy models,
e.g. in traffic modelling [283]. Occasionally, the effect of BCs on such
mathematical models is explicitly investigated, e.g. in pedestrian flow models
[374]. It should be clear, however, that the number of practical applications
of ECAs is limited, which motivates extensions to non-classical CAs. The five
CA families discussed in this paper will be defined as a (often minor)
variation on Def. 1.2, tacitly including the possibility of adding BCs such as
in Def. 1.3.

###  1.3 CA properties as taxonomic tools

Research into the nature and behaviour of CAs has generated a large amount of
jargon denoting particular properties that allow for CA classification. In a
recent survey, Vispoel et al. [337] distinguishes four approaches for
characterising CAs: (i) classification based on the rule table, (ii)
identification of global properties, (iii) a division into behavioural
classes, and (iv) quantification based on local properties. The former two may
be called ‘genotypic’ (Tab. 1.3), and the latter ‘phenotypic’ (Tab. 1.4),
because they resp. take information from the model setup (definition) and the
model outcome (simulation).

Table 1.3: Mathematical tools and concepts used for characterising and classifying CAs based on the genotype (model definition). The first reference indicates the original academic work. Selection largely copied from Vispoel et al. [337]. Tool/concept |  Brief description |  References
---|---|---
Rule table parameters
Langton’s parameter |  Fraction $\lambda$ of neighbourhood configurations that are not mapped to the quiescent state. |  [178]
Mean-field parameters |  Generalisation of Langton’s $\lambda$. |  [132]; [186, 131]
$Z$-reverse parameter |  Measure for number of possible predecessors of a state configuration. |  [363]; [178, 361, 362]
$\mu$-sensitivity |  The average number of changes in the local update function’s output when changing the state of a single neighbourhood cell. |  [90]; [49]
Obstruction parameter |  The fraction of neighbourhood pairs for which the CA rule is additive. |  [340];
Kolmogorov complexity |  Entropy-related measure of rule table complexity. Often estimated by Lempel-Ziv complexity. |  [170]; [378, 50, 152]
Global properties
Attractor structure |  Investigates the structure between all possible subsequent configurations. |  [146]; [212, 363, 135]
Topological dynamics |  Applies a number of concept from dynamical systems theory (e.g. topological concepts such as equicontinuity, sensitivity, transitivity, and positive expansivity) to the space of all possible CA configurations. |  [172]; [212, 300, 93, 98]
Formal language theory |  Computational approach to studying CA attractors. Configurations are ‘words’, and transition rules are ‘grammar’. |  [314]; [82, 180, 376, 92]
$D$-spectrum |  The number of distinct densities occurring in the periodic part of the CA’s phase space trajectory. |  [106]
Rényi entropy |  Spatial, temporal or local parameterised generalisation of Shannon entropy on the space of CA configurations. |  [277]; [359, 186]
Computational complexity |  Judges whether computational problems are in principle solvable, and classifies CAs according to the predictability of their rule. |  [322]; [127, 323, 324]

Table 1.4: Mathematical tools and concepts used for characterising and classifying CAs based on the phenotype (model outcome). The first reference indicates the original academic work. Selection largely copied from Vispoel et al. [337]. Tool/concept |  Brief description |  References
---|---|---
Behavioural classes
Wolfram classes |  Identifies ECA phenotype classes I (homogeneous), II (periodic), III (chaotic), IV (complex). |  [350]; [178]
Li-Packard classes |  Characterises ECA phenotype as null, fixed point, periodic, locally chaotic, chaotic. |  [186]; [185]
Culik-Yu classes |  Formal definition of Wolfram classes. |  [83]
Local properties
Mean-field theory |  Measure of time-dependent configuration averages, most notably mean state density. |  [349]; [301]
Local structure theory |  Generalisation of mean-field theory to properties of blocks of cells. |  [132]; [131]
Two-point correlation |  Measure for spatial correlations between local configuration structures. |  [349]
Lyapunov exponents |  Quantifies the sensitivity to initial conditions based on analysis of the difference pattern. |  [305]; [187, 247, 327, 79, 30, 33]
Kolmogorov complexity |  Time-dependent entropy-related measure of configuration complexity. |  [170]; [371, 372, 245]
Spectral properties |  Investigates the CA frequency spectrum via some well-defined notion of a discrete Fourier transform. |  [244]; [247, 24, 289]

We will use some of these properties as tools to distinguish between various
CA families and types, either by demonstrating that the properties differ with
those of their elementary counterpart, or by arguing that the properties are
ill-defined for the non-classical CA at hand.

###  1.4 Overview of CA selection and presentation of our methodology

All five CA families that (generally) require an extension of the classical
definition are listed in Tab. 1.5. For completeness we highlight that this
table contains CAs for which some non-trivial version of the definition is
still within the domain of the classical CA (e.g. a $k$-state CA). On the
other hand, some families are omitted, either because we consider them both
rare and inert (e.g. ‘polygeneous’ CAs [57]), or because they are too remote
from the canonical research field and would deserve a separate survey (e.g.
quantum CAs [26]).

Table 1.5: List of CA families discussed in this review paper. An asterisk (∗) indicates that such a complete survey is missing, followed by cited papers that perform a partial review. CA family |  Nature of the definition extension |  Surveys
---|---|---
Asynchronous (ACA) |  The local update rule $\phi$ no longer applies to all cells simultaneously. |  [299], [37], [107]
Stochastic (SCA) |  Cells update their state (partially) randomly with regards to location, timing, or update rule. |  ∗[27], [201], [286]
Multi-state (MSCA) |  The state space is no longer binary but $k$-nary or continuous. |  ∗[7], [223], [32]
Extended neighbourhood (ENCA) |  The neighbourhood $\mathcal{N}(c_{i})$ of a cell $c_{i}$ is larger in space and/or time, differently shaped, or no longer consist of its direct (‘physical’) neighbours. |  ∗[211], [21], [369]
Non-uniform ($\nu$CA) |  The local rule $\phi$ can take more arguments than simply the neighbourhood configuration, allowing for heterogeneity. |  [95], [45]

We follow the same approach within each of the five families of non-classical
CAs. First, we motivate the family’s existence and formalise its definition.
Second, we present the taxonomy of the various CA (sub)types belonging to the
family at hand, generally guided by the kind and the degree of the extension.
We highlight when particular definitions encompass others within the same
family, and especially when they are mathematically equivalent across
families. Third, we demonstrate how the genotype and phenotype of these CAs
compare to that of ECAs and other CA families. We indicate when a particular
characteristic (referring to Tabs. 1.4 and 1.3) breaks down, inhibiting a
quantitative comparison. Fourth, we briefly discuss how the unique character
of the CA family allows for a number of applications (referring to Tab. 1.1).

##  2 Asynchronous CAs

###  2.1 Motivation and definition

Global synchronisation of the local update rule is contradictory to the CA
philosophy (claiming to be ‘fully local’), and often does not reflect the
nature of the modelled phenomenon; nature has no ‘central clock’ [292]. For
these reasons, the assumption of synchrony was challenged by Priese [268]
(investigating the mathematical and computer-scientific implications), and
Ingerson and Buvel [150] (with a more phenomenological approach).

Of course synchrony does occur in nature (see e.g. references in [274]), but
rather than interpreting this observation as a justification for top-down
synchrony-by-design, it better suits the spirit of CA research to regard this
as a challenge to find bottom-up synchrony emerging from the dynamical system.
In fact, it was counter-intuitively shown in the recent past that global
synchronisation (from arbitrary initial conditions) can even only be achieved
by going beyond synchronous deterministic updating [281]. In any case, this
suggests that the study of asynchronous CAs (ACAs) is not merely an exercise
in computational tinkering, but motivated by the principles of a proper
scientific model.

Expanding on the ECA paradigm, we define elementary ACAs by expanding Def.
1.2.

######  Definition 2.1 (Asynchronous cellular automaton).

An asynchronous cellular automaton (ACA) is identical to an ECA (Def. 1.2),
with the exception of the sixth property, which becomes:

  * 6.

The dynamics of cell $c_{i}$ at time $t$ is determined by either the identity
rule (the state remains unchanged), or one of the possible elementary Wolfram
rules $\phi:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$.

Spatiotemporal variations in this choice define the various ACA subtypes.

###  2.2 ACA taxonomy

Despite the long tradition of ACAs, no overall consensus exists in literature
on what defines a particular subtype, nor on its nomenclature. Relatively
recent work concerned with statistics on ACA spacetime diagrams (e.g. [107,
37, 299]), has however somewhat converged on a number of subtypes, of which we
display the taxonomy below.

####  2.2.1 Spatial ACA variations

##### Partially asynchronous CAs

An ‘$\alpha$-asynchronous CA’, also known as an $m$-ACA [94] or block-
sequential ACA [25], allows for partial synchrony, and is contrasted with what
Fatès calls fully asynchronous updating [107]. Whether or not a cell is
updated depends on the ‘synchrony rate’ $\alpha\in[0,1]$. The limit situation
where $\alpha=1$ reduces the ACA to the synchronous case, while $\alpha=0$
induces an entirely static CA.

The synchrony rate is mostly (and most generally) interpreted as a probability
on a cell-per-cell basis:

$\displaystyle
s(c_{i},t+1)=\begin{cases}\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{with
probability }\alpha,\\\ s(c_{i},t),&\text{with probability
}1-\alpha.\end{cases}$ (2.1)

We identify the set of updated cell indices at time step $t$ as
$Z(t)\subseteq\\{1,\ldots,N\\}$. Since $|Z(t)|\sim\text{Bin}(N,\alpha)$, with
expectation value $\alpha N$, Eq. (2.1) is (up to a rounding error) equivalent
with

$\displaystyle
s(c_{i},t+1)=\begin{cases}\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{if
}i\in Z(t),\\\ s(c_{i},t),&\text{else}.\end{cases}$ (2.2)

Clearly, there are many other ways to choose the set $Z(t)$, resulting in
different dynamics. Worsch [357], for example, discusses a particular type
called a ‘neighbourhood-independent’ ACA, additionally demanding that
neighbouring cells cannot update simultaneously. It is more common practice,
however, to demand that the number of updated cells per time step is always
exactly $\lfloor\alpha N\rfloor$. The fixed-size subset $Z(t)$ is typically
chosen in an entirely stochastic fashion, allowing for $\dbinom{N}{|Z(t)|}$
choices. Note that if $Z(t)=Z$ is static, we arrive at a trivial two-rule
spatially non-uniform CA, where one of the rules is the identity operator (see
Section 6).

Some authors have explored updating different cells with different fixed
periods or phases (e.g. Ingerson and Buvel [150]) which is equivalent to
deterministically selecting $Z(t)$ at any time step. Note, however, how in
these cases one tyrant overthrows another: the global deterministic clock is
replaced by a global deterministic selection of the update set. Such a non-
stochastic $Z(t)$ is interesting from a mathematical point of view, however,
as Worsch [357] demonstrated that for all deterministic choices of $Z(t)$, a
single ACA with a radius-1 rule can simulate all others. That is to say:
precisely the same dynamics are achieved by either (i) choosing a set $Z(t)$
given a rule $\phi$, or (ii) choosing a rule $\phi$ given a set $Z(t)$.
Similar equivalences were shown by Aracena et al. [25] for random Boolean
networks (see Section 5) with various asynchronous update schemes. In a
classical paper, Golze [125] showed how to construct a synchronous CA in $d+1$
dimensions from an ACA in $d$ dimensions, by reinterpreting time as a spatial
dimension.

The ACA is fully asynchronous if $|Z(t)|=1$. Many authors, including
Schönfisch and De Roos [299], consider full synchrony to be more natural in
the context of mathematical modelling, because physical time can be infinitely
divided (up to the Planck limit). Synchrony, in other words, is a fictional
notion, as events are never really simultaneous.

##### Fully asynchronous CAs

The most general approach to fully asynchronous CAs, a ‘random independent’
ACA from a uniform choice, is to select and update a single cell at random,
i.e.

$\displaystyle
s(c_{i},t+1)=\begin{cases}\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{if
}i=k,\\\ s(c_{i},t),&\text{else},\end{cases}$ (2.3)

where $k$ is chosen randomly and independently from the set
$\\{1,\ldots,N\\}$. The number of updates of cell $i$ in $N$ time steps is
again binomially distributed $\sim\text{Bin}(N,1/N)$ with expectation value 1.
Next, for ‘randomly ordered’ ACAs with a ‘random new sweep’, we further impose
that updating the $N$ cells occurs in cycles. That is to say: every $N$-th
time step, a permutation of the tuple $(1,\ldots,N)$ is randomly chosen, and
the cells are updated in this order. This prevents cells from updating more
than once every cycle, and makes sure any given cell is updated at least once
after $2N$ time steps. Narrowing this down further, said permutation is chosen
randomly but only once (‘random fixed sweep’), resulting in any given cell
being updated after exactly $N$ time steps. One may distinguish further the
particular case where the updating happens according to ascending cell number,
in a ‘line-by-line sweep’. This assures, after all, that always precisely one
neighbour will have been just updated, resulting in spatial correlations
[270]. In any of these fully-asynchronous cases, the expectation value for the
number of time steps between two consecutive updates is simply $N$ (see Tab. 1
in [299] for all statistics).

####  2.2.2 Temporal ACA variations

Schönfisch and De Roos distinguish ‘step-driven’ and ‘time-driven’
asynchronous updating [299]. In the former approach – tacitly assumed up to
this point – some rhythmic notion of discrete time remains. In the latter
approach, discrete time is abandoned and the update of a cell depends on some
continuous time-dependent probability, typically according to an exponential
distribution. The difference between CAs with various temporal asynchronies is
arbitrary, however. After all, due to the unidirectionality of time, a
bijective mapping between step-driven updates (computer time) and time-driven
updates (physical time) is always possible [107].

###  2.3 ACA genotype and phenotype

Introducing asynchronous updating affects the way CAs can be described
mathematically, as well as the way they behave dynamically.

####  2.3.1 The ACA genotype

All metrics used to classify the rule table (Tab. 1.3, top) are still fully
applicable to any of the above ACA types, with respect to the rule $\phi$ that
updates the selected ACA cells. The rule table itself could be extended to
include, with a particular probability, the identity operator; this is however
identical to the rule table of a stochastic CA, and will therefore be
discussed in Section 3.

Global properties (Tab. 1.3, bottom) are affected not only by the local rule
$\phi$, but also by the selected subset $Z(t)$. Generally, therefore, the
mathematics regarding attractor structure and topological dynamics now involve
$Z(t)$, hindering closed expressions, but some progress was made for
particular cases. Hansson et al. [136] formally identified all 1-D ACAs with
periodic boundary conditions (including non-elementary CAs) that are
independent of the asynchronous update order. Amongst these ACAs, Macauley and
Mortveit [196] reviewed and catalogued those with a random fixed sweep for all
104 ECA rules for which the set of periodic points is independent of update
sequence. Manzoni [207] generalised a number of mathematical properties (e.g.
surjectivity and injectivity) to study periodic orbits in the space of
configurations of fully-asynchronous CAs, highlighting how these formal
results can contribute to expanding knowledge of properties that are already
known for synchronous CAs.

Regarding computational complexity, some ACAs have been shown to support
universality [4]. While more recent universal ACAs [109] are less complex than
the original proposals, they however still require non-uniformity of the local
update rule (see Section 6).

####  2.3.2 The ACA phenotype

Spacetime diagrams of ACAs can be analysed in exactly the same fashion as
those of ECAs, keeping in mind that fewer cell updates occur during a fixed
time interval. For a fair comparison, ACA diagrams are therefore typically
cropped to only show configurations after (on average) all cell states are
updated. Behavioural classifications and local properties (Tab. 1.4) can
subsequently be deduced from the resulting diagram, e.g. entropy-based
classification [181]. Notably, the choice of $Z(t)$ introduces additional
degrees of freedom that can be perturbed when investigating the CA phenotype,
especially when results are plotted against the quasi-continuous $\alpha$
parameter. Fatès [107] emphasises that this is of particular help in the
(computational) study of self-organisation and robustness.

Baetens et al. [35] use Lyapunov exponents to examine the stability of 2-D
totalistic ACAs, comparing four fully-asynchronous update schemes. Using mean-
field theory based on a large number of simulations, they show that
introducing asynchronicity strongly affects stability and may even change the
CA’s Wolfram class. This is confirmed in the study by Bouré et al. [54], who
additionally suggest that the robustness properties of a system may actually
be used to probe the desired update scheme of the underlying mathematical
model. Lumer and Nicolis had done similar research some ten years prior [192]
on 2-D continuous CAs (or ‘coupled-map lattices’, see Section 4). Using tools
directly related to the Lyapunov exponents, they demonstrated that ACAs remain
stable for higher values of the logistic map’s nonlinearity parameter,
compared to their synchronous counterpart, especially for a random new sweep.
Perhaps most convincing in its simplicity, however, is the study by Bandini et
al. [37]. These authors show that non-trivial phenotypical change arises from
some type of full asynchrony for 9 out of the 16 one-neighbourhood CAs,
despite being even simpler than ECAs.

###  2.4 Applications of ACAs

Next to being of strictly methodological interest, ACAs are applied in the
study of parallel computation (e.g. [145]), and for a wide range of
mathematical models [291, 130, 43, 41]. Applications are generally motivated
by the ACA’s demonstrated enriched phenotype, and by a sense of realism (no
central clock).

####  2.4.1 Computational advances

Faced with practical considerations, most notably the scaling of semiconductor
elements and the demand for long-range interconnection [232], early research
into nano-scale computers had shifted from Von Neumann’s theoretical automaton
to simpler CAs by the early 90s [47]. Peper et al. [261] showed how not only
ACAs support integration into electrical circuits, but how asynchronicity
actually allows for the construction of ‘delay-insensitive’ circuits [164].
The relatively recent work by Fei et al. [109] discusses a 3-state, 10-rule
ACA that uses its asynchronicity for the 2-D crossing of signals.
Asynchronicity in these computational units therefore protects the system from
inherent noise [123], and is required for efficient information transfer.

Beyond hardware implementations, asynchronicity has its merits in solving
computational tasks such as the prisoner’s dilemma [145], where asynchronicity
is sometimes even required for the existence of a solution. Ruivo et al. [288]
discuss a 4-neighbour ACA that solves the global synchronisation problem –
which is impossible for synchronous CAs [281]. Asynchronous solutions have
also been put forward to tackle the density problem [330] and the parity
problem [290].

####  2.4.2 ACAs in mathematical modelling

Asynchronicity has been used for CA-based modelling in every domain listed in
Tab. 1.1. Most notably, ACAs are used in biology and chemistry, where the loss
of synchrony is almost invariably either a way of including stochasticity, or
a pragmatic choice for (speedy) computation. In biology, for example,
Messinger et al. [219] use partial asynchrony for investigating biology-
inspired task-performing dynamics, and Sieburg et al. [307] use the fully
asynchronous variation to simulate HIV infection in an artificial immune
system. In chemical modelling, Perez-Brokate et al. [262] reviewed ‘blocked’
$\alpha$-asynchronism to model corrosion, Seybold et al. [304] used stochastic
partial asynchronicity to simulate chemical kinetics, and Kier et al. [168]
reviewed similar simulations for ACAs with a random new sweep. Full
asynchronicity with a random order is also imposed onto Van der Weeën et al.’s
CA model for photocatalytic degradation [335]. We stress, however, that none
of these examples use ‘pure’ ACAs, but rather CAs with more than one
extension, typically including multiple states and an extended neighbourhood
(cf. Sections 4 and 5).

More interesting than listing how all ACA types are used in various domains of
science, is to highlight a number of applications in mathematical modelling
where the asynchronicity itself was studied. Ruxton [291] studied the effect
of four update types in a very simple ecological model (see also Ref. [142])
of stochastic and temporally non-uniform ACAs. He shows how this choice
strongly affects the average time until extinction, and generalises these
results in later work [292]. Another early biological work, by Gunji [130],
shows how macroscopic patterns on mollusc can be generated by various ACA
types, indicating that the particular update scheme influences the emergent
patterns even more than the choice of the local update rule. Bezbradica et al.
[43] studied the effect of various updating schemes in the context of
molecular pharmacology, and found that a random independent ACA hosts the most
robust models of structural chemical interactions. Such stabilising effects
had already been accentuated a decade earlier by Bersini and Detours [41] for
an abstract immune network model. Similar effects are observed for stochastic
CAs, which we will investigate in the next section. We observe how this is
largely the consequence of the high similarity between both definitions of the
CA extensions.

##  3 Stochastic CAs

###  3.1 Motivation and definition

Most natural processes appear to exhibit some degree of unpredictability, and
randomness has been long identified as a driving force for many types of
structure formation, e.g. morphogenesis [333]. Adding stochasticity to CAs
therefore again expresses realism in mathematical modelling [292]. From a
methodological point of view, a non-deterministic setup also significantly
affects a CA’s emergent behaviour, e.g. in terms of sensitive dependence on
initial conditions [34]. The motivation for stochastic CAs (SCAs, also
‘probabilistic’ CAs) is therefore very similar to that for partially
asynchronous CAs, and so is its definition; most generally, we again alter the
sixth property in Def. 1.2.

######  Definition 3.1 (Stochastic cellular automaton).

A stochastic cellular automaton (SCA) is identical to an ECA (Def. 1.2), with
the exception of the sixth property:

  * 6.

The dynamics of cell $c_{i}$ at time step $t$ is governed by

$\displaystyle
s(c_{i},t+1)=\begin{cases}\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{with
probability }p,\\\ \psi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{with
probability }1-p.\end{cases}$ (3.1)

Typically $p$ is independent of time and space, clearly reducing to the
elementary case if $p=1$. Time and/or space dependence is however often
desirable with applications in mind; these options generate the landscape of
SCA types discussed next.

###  3.2 SCA taxonomy

We first observe some notable special cases. When $\psi$ is the identity rule
in Eq. (3.1), the SCA reduces to an $\alpha$-asynchronous CA (cf. Eq. (2.1)),
with $\alpha=p$. We also observe that if rules $\phi$ and $\psi$ are not
complementary, i.e. when $W(\phi)+W(\psi)\neq 255$, the CA is only partially
stochastic, as some neighbourhood configurations will generate an identical
outcome for both $\phi$ and $\psi$. At the opposite side of the stochastic
spectrum we find SCAs with complementary ‘null’ rules $\phi$ and
$\psi=\phi^{\text{C}}$ with $W(\phi)=255-W(\phi^{\text{C}})=0$. This induces
complete neighbourhood independence and loss of information, which for $p=1/2$
clearly leads to pure noise. Due to its simplicity and its intuitive link to
sociological behaviour, we additionally highlight the ‘majority SCA’ [313],
which is equivalent to choosing $W(\phi)=232$ and $W(\psi)=51$ in Eq. (3.1).

####  3.2.1 Spatial SCA variations

##### Local space dependence

The state transition of a cell is determined by the states of its neighbouring
cells in the classical sense, but may also be influenced by this neighbourhood
in a stochastic (yet local) sense. Observe a particular SCA where the
probability $p$ is also neighbourhood-dependent:

$\displaystyle s(c_{i},t+1)=\begin{cases}1,&\text{with probability
}p(\tilde{s}(\mathcal{N}(c_{i}))),\\\ 0,&\text{with probability
}1-p(\tilde{s}(\mathcal{N}(c_{i}))).\end{cases}$ (3.2)

Because for ECAs there are $k^{|\mathcal{N}|}=8$ different neighbourhood
configurations, such an SCA is entirely defined by the octuple
$\mathbf{p}=(p(0,0,0),\ldots,p(1,1,1))=(p_{0},\ldots,p_{7})\in[0,1]^{8}$. Note
how this matches the definition in Eq. (3.1), if we demand that
$\psi=\phi^{\text{C}}$, and if we perform a suitable permutation of
$\mathbf{p}$. Clearly, many choices for $\mathbf{p}$ are possible; we
highlight two that induce some structure between the tuple’s elements.

Diploid CAs are a type of neighbourhood-dependent SCAs proposed by Fatès
[108], and are motivated by a formal investigation into symmetry breaking in
biological systems resulting from inherent stochasticity. This particular type
of SCA is based on the definition in Eq. (3.2), but reduces the dimensionality
of $\mathbf{p}$ from eight to three by setting

$\displaystyle
p(\tilde{s}(\mathcal{N}(c_{i})))=\lambda\phi(\tilde{s}(\mathcal{N}(c_{i})))+(1-\lambda)\psi(\tilde{s}(\mathcal{N}(c_{i}))).$
(3.3)

For a non-trivial diploid CA, we have that $\phi\neq\psi$ and $0<\lambda<1$,
such that (again referring to Eq. (3.2)) $p\in\\{0,\lambda,1-\lambda,1\\}$, or
$p\in\\{\lambda,1-\lambda\\}$ if $\psi=\phi^{\text{C}}$. For a particular
$\lambda\in(0,1)$ there are 8088 pairs $\\{\phi,\psi\\}$ that result in a
unique diploid rule [108].

Mairesse and Marcovici [201] discuss some particular cases of two-state,
$|\mathcal{N}|=2$ SCAs that also rely on a reduction of the probability tuple
dimensionality. These cases are entirely defined by $k^{|\mathcal{N}|}=4$
probabilities in the quadruple $\mathbf{p}=(p_{0},p_{1},p_{2},p_{3})$.
Clearly, such CAs are of very little interest for applications, but they do
invite exhaustive mathematical treatment. Four special one-parameter cases are
the ‘noisy additive SCA’ with parameters $(0,p,p,0)$, the ‘symmetric noisy
additive SCA’ with parameters $(1-p,p,p,1-p)$, the ‘Stavskaya SCA’ with
parameters $(0,p,p,p)$, and the ‘directed-animals SCA’ with parameters
$(p,0,0,0)$.

##### Global space dependence

If the probability $p=p(c_{i})$ depends on the position of the cell, the SCA
is globally space-dependent and cannot be considered uniform. After all, two
transition rules with different associated probabilities may be considered as
distinct rules altogether. We investigate spatially non-uniform CAs in Section
6. Here, we simply note that many applications require a position-dependent
probability due to some global parameter, e.g. temperature in Vichniac’s Ising
model [336] (see Section 3.4).

####  3.2.2 Temporal SCA variations

Most generally, the probability may again depend on some global model
parameter, which is now time-dependent, such that $p=p(t)$. This breaks
uniformity, but now in a temporal sense, and is again hard to map due to its
highly idiosyncratic ties to the model at hand.

What can be investigated methodologically is what is known as a ‘temporally
stochastic CA’ [286]. Here all cells also follow either rule $\phi$ or rule
$\psi$ in a spatially uniform sense, but the global parameter that decides
this assignment is stochastic:

$\displaystyle\left(s(c_{i},t+1)\right)_{i=1}^{N}=\begin{cases}\Phi(\left(s(c_{i},t)\right)_{i=1}^{N}),&\text{with
probability }1-q,\\\ \Psi(\left(s(c_{i},t)\right)_{i=1}^{N}),&\text{with
probability }q.\end{cases}$ (3.4)

Recall that $\Phi:S^{N}\rightarrow S^{N}$ (resp. $\Psi$) is the global
transition rule induced by the local transition rule $\phi$ (resp. $\psi$).
Probability $q$ is called the ‘temporal noise rate’, as a sporadic global
update according to $\Psi$ is often considered a transient noisy ‘hiccup’ in
the system. Note that this again fits into the general definition of SCAs
(Def. 3.1) upon setting

$\displaystyle p(t)=\begin{cases}1,&\text{with probability }1-q,\\\
0,&\text{with probability }q.\end{cases}$

###  3.3 SCA genotype and phenotype

Introducing stochasticity generates a number of interesting differences and
subtleties regarding both input and output of the dynamical system, as
compared to ECAs. Below we discuss the SCA genotype and phenotype
respectively, again referring to Tabs. 1.4 and 1.3 for background information.

####  3.3.1 The SCA genotype

In terms of the rule table parameters, a naive extension for SCAs consists of
applying the definition to either of the applying rules $\phi$ or $\psi$, or
to a probability-weighted average of both. From Def. 3.1, the mean-field rule
table parameters, and hence the Langton parameter, may for example be defined
as

$\displaystyle M_{i}=\sum_{\begin{subarray}{c}\mathcal{N}\text{ with }i\\\
\text{non-}q\text{ values}\end{subarray}}\biggl{(}p[\phi(\mathcal{N})\neq
q]+(1-p)[\psi(\mathcal{N})\neq q]\biggr{)},$

where the square brackets output 0 or 1 depending on the truth condition, and
$q$ is the quiescent state. Note how this definition naturally allows for
summing over a neighbourhood-dependent probability $p=p(\mathcal{N})$. Despite
the elegance of these parameter extensions, it is not a priori evident (and in
general untrue [286]) that the properties of the SCA update rule are
‘somewhere in between’ of those of its constituent rules. An extension rooted
in a weighted average is therefore not necessarily useful. Investigating
correlations between particular SCA rule-table property definitions and their
actual behaviour is an open direction of further inquiry.

A different, global approach arises from the observation that consecutive SCA
configurations form a Markov chain on the state space $S^{N}\rightarrow
S^{N}$. This allows for adopting the Markov chain formalism in the study of CA
attractor structure, mapping and analysing the distribution of future
configurations. The main topics of interest are (i) short-term time-dependent
behaviour, (ii) long-term steady-state behaviour, and (iii) the study of the
‘absorption time’ [260], to which some theoretical insight has been provided
[59, 12]. A recurring theme is to determine whether or not a particular SCA is
ergodic, i.e. whether it will have visited all $2^{N}$ configurations for
$t\rightarrow\infty$. Maes and Shlosman provided a sequence of general
criteria for ergodicity in SCAs [200]. Particular SCAs may however require a
more tailor-made approach, e.g. Holroyd et al.’s recent proof of ergodicity
related to a ‘percolation game’ [143].

####  3.3.2 The SCA phenotype

An analysis of SCA spacetime diagrams is generally mathematically identical to
that of ECAs. It may, however, reveal distinct classifications or local
properties due to inherent randomness.

Regarding classification, first note that no SCA can be considered truly
homogeneous or periodic, as randomness will disturb any repetitive pattern in
consecutive configurations. Additionally, while Wolfram’s class IV
(complexity) may still be a pertinent classification visually, the capacity to
support universal computation can no longer be an argument for assigning this
class. Indeed, Arrighi et al. showed that universal SCAs do not exist [27].
Roy et al. [286] exhaustively investigated the classification of temporally
stochastic CAs, for all $3825$ combinations of non-equivalent Wolfram rules.
They show i.a. that (i) two rules that are classified as chaotic, may join
forces in an SCA to generate periodicity (and vice versa), and that (ii) a
behavioural phase transition may occur for particular values of the temporal
noise rate. We note that the quantitative results of their research are
contingent on what constitutes a ‘class’, which is mathematically
insufficiently defined for SCAs, and for CAs in general [83]. This nonetheless
does not affect the validity of the qualitative observations, demonstrating
paradoxically that randomness can aid stability.

Regarding local properties, the phenomenology of an SCA can be investigated in
function of the probability $p$, often demonstrating ‘jumps’ in behaviour when
$p$ surpasses a particular value. Such a jump may indicate a phase transition
or a system bifurcation. Baetens et al. [34] mapped such dynamics of SCAs by
means of a sensitivity measure, the maximum Lyapunov exponent, and the Lempel-
Ziv complexity, for a large number of simulations of SCAs. Their research is
limited to SCAs with $\psi$ the identity operator, such that the results apply
to $\alpha$-asynchronous CAs as well. They demonstrate that an SCA’s
sensitivity to initial conditions and its tendency towards chaos is highly
dependent on the update probability; a small change in $p$ may radically alter
the system’s behaviour. Similar results have been achieved for diploid SCAs
where $\psi$ is not the identity rule. Fatès [108] demonstrates second-order
phase transitions and symmetry breaking when varying the mixing parameter
$\lambda$, by mean-field analysis of (kinks) density. Cirillo et al. [72]
studies this in more detail (stochastic ‘reset’), and provides some
theoretical justifications of Fatès’s numerical results for mixtures with the
null rule. Also majority-voter SCAs exhibit such behaviour, both in one [59],
and two dimensions [313].

###  3.4 Applications of SCAs

Above-mentioned methodological advances have inspired applications in computer
science and mathematical modelling (and vice versa). Systems that are robust
to noise – or even require noise – are especially valuable in the former,
while the phenomenological richness provided by SCA phase transitions is
highly relevant for the latter.

####  3.4.1 Computational advances

Robustness to noise is a highly desirable property of nanoscale computing
systems, so a lot of research has been done on CAs that can ‘remember
information’ [117]. Specific computational tasks may also be solved by SCAs,
most notably the density classification problem (e.g. [115]).

####  3.4.2 SCAs in mathematical modelling

A classical SCA application is Vichniac’s implementation of the Ising model
for ferromagnetism [336]. He shows that an approach with deterministic CAs
leads to a “feedback catastrophe”, which not at all represents the observed
physical behaviour of magnetic metals. This is solved by associating a
temperature-dependent transition probability to each of the possible
neighbourhood configurations, and is therefore another curious example of a
system that requires randomness to achieve stability.

As Baetens et al. [34] conclude, an SCA’s propensity for phase transitions
necessitates scrutiny while developing a discrete mathematical model.
Additionally, the inclusion of stochastic parameters of course generates a
much wider spectrum of conceivable model setups. While sometimes an exhaustive
grid search is feasible (e.g. [334]), genetic algorithms exist to help
determining which stochastic rule may be most pertinent to describe (and
predict) the physical data at hand (e.g. [48]). The latter approach was
recently used for parameter optimisation for an SCA-based epidemiological
model for COVID-19 [124], acquiring quite remarkable results. The latter model
(and many other non-toy models) also includes extended neighbourhoods (Section
5) and multiple states, to which we turn next.

##  4 Multi-state CAs

###  4.1 Motivation and definition

The general definition of Von Neumann (cf. Def. 1.1) allows for more than two
states, but the ECA definition (Def. 1.2) should be generalised to accommodate
more than two states.

######  Definition 4.1 (Multi-state cellular automaton).

A multi-state cellular automaton (MSCA) is identical to an ECA (Def. 1.2),
with the exception of the second property:

  1. 2.

$S$ is the state set, which may or may not be finite, and which may or may not
have some structure imposed on it.

MSCAs serve as a basis for a wide variety of applications [275, 118, 312, 370,
18, 248] because it is rarely the case that a natural system allows only two
discrete states. Still, an in-depth understanding of the dynamics of such
models and a robust mathematical framework is mostly lacking.

Most of the theoretical work on CAs has been done for two-state CAs. This is
in part due to the observation that for some (mostly computational)
objectives, the study of binary-state CAs is rich enough by itself. It was
shown, for example, that replicating machines in the framework of CAs could
also be established in a two-state CA [40]. It is also due to the overwhelming
complexity of the mathematics when allowing more than two states: considering
three rather than two states in a 1-D $r=1$ CA increases the number of
possible local update rules from 256 to $\sim 10^{13}$. While this can be an
advantage, e.g. for random number generation [46], it often obstructs
theoretical progress.

MSCAs with a continuous state space are called continuous CAs (CCAs). Rucker
raises a number of objections against the study of CCAs [287], the most
important of which is redundancy. CCAs are similar to well-established finite-
difference methods for numerically solving differential equations [353], and
also similar to coupled-map lattices [120]. Rucker also emphasises that the CA
approach is different, however, being more rooted in computational experiment
and observation, rather than theory and proof.

###  4.2 MSCA taxonomy

Below, we first distinguish between ternary, $k$-nary, and continuous-valued
CAs, zooming in on a particular type of continuous-valued CA called ‘fuzzy’
CAs. Note that we no longer distinguish between spatial and temporal
variations, as variations only affect the state space and its internal
structures.

##### Ternary and $k$-nary CAs

Generally, for $k$-nary CAs we find $k^{k^{|\mathcal{N}|}}$ possible local
update rules. It is shown that a CA with a local rule defined for a particular
neighbourhood is equivalent to a CA with neighbourhood size three and a
different state space [316], by ‘pooling’ cells together (see Fig. 4.1). This
implies that only considering the $|\mathcal{N}|=3$ case is sufficiently
general.

Figure 4.1: Complexity trade-off between neighbourhood size, number of cells,
and number of states. Here a $k=2,|\mathcal{N}|=5$ CA with 50 cells is
simulated by a $k=5,|\mathcal{N}|=3$ CA with 10 cells, without loss of
information in either direction.

Following the convention for ECAs, a ternary CA rule can be identified by
associating the number $s_{i}\in\\{0,1,2\\}$ with each of the 27 possible
neighbourhoods. This may in turn be translated to a decimal number, i.e.

$\displaystyle(s_{26}\ldots
s_{0})_{3}=\left(\sum_{i=0}^{26}3^{i}s_{i}\right)_{10},$

where the subscript indicates the numeral base. Due to the quickly increasing
number of possible neighbourhood configurations for increasing $k$, often only
totalistic $k$-nary CAs with $S=\\{0,\ldots,k-1\\}$ are considered (see e.g.
[353]). This reduces the number of rules (or “codes”) to
$k^{(k-1)|\mathcal{N}|+1}$.

##### Continuous-valued CAs

A $k$-nary CA in the limit of $k\rightarrow\infty$, where the state space is
typically mapped to $S=[0,1]$, can take an infinite number of values. If
additionally $S$ is continuous, the entire object is called a continuous-
valued (or simply continuous) CA (CCA).

A complete rule table would now be infinitely large. In order to nonetheless
quantify transition rules, the state set $S$ is considered to be a field, and
some (neighbourhood-dependent) function applies on its elements. In the
language of coupled-map lattices, this is called a ‘map’, and the ‘coupling’
is achieved by including the neighbourhood. Wolfram showed that CCAs can also
display the rich and often chaotic dynamics found in their discrete
counterparts [353].

Referring back to Section 3, we note that a neighbourhood-dependent SCA is a
particular case of a CCA, provided we interpret the continuous values as
probabilities for the cells to be either in state 0 or state 1. An SCA is
entirely determined by the tuple $\mathbf{p}=(p_{0},\ldots,p_{7})$, such that
the continuous local update rule becomes

$\phi(s_{i-1},s_{i},s_{i+1})=p_{0}\overline{s_{i-1}}\ \overline{s_{i}}\
\overline{s_{i+1}}+p_{1}\overline{s_{i-1}}\ \overline{s_{i}}\
s_{i+1}+p_{2}\overline{s_{i-1}}s_{i}\overline{s_{i+1}}+p_{3}\overline{s_{i-1}}s_{i}s_{i+1}\\\
+p_{4}s_{i-1}\overline{s_{i}}\
\overline{s_{i+1}}+p_{5}s_{i-1}\overline{s_{i}}s_{i+1}+p_{6}s_{i-1}s_{i}\overline{s_{i+1}}+p_{7}s_{i-1}s_{i}s_{i+1},$

where $\overline{s_{i}}=1-s_{i}$, and $s_{i}$ is shorthand notation for
$P(s(c_{i},t)=1)$. Other particular relationships can be inferred for specific
types of SCAs, such as diploid SCAs.

##### Fuzzy CAs

Fuzzification is understood as generalising Boolean-logical and, or and not
operators such that they can operate on all elements in $S$, typically with
the aim of expressing a ‘degree of truth’ rather than simply true (1) or false
(0) [64]. Fuzzy-state CAs (FCAs) constitute a particular type of MSCAs where
the state space $S$ is the unit interval, but where the governing rules are
defined from a binary-state CA. The FCA framework forms an elegant bridge
between $k$-nary CAs and continuous CAs, which allows for a more well-defined
analysis of chaotic dynamic behaviour.

The FCA local rule is defined as the ‘fuzzification’ of the local rule of a
binary CA; it is defined from a rule written as a Boolean expression (cf.
[353] p. 884) in ‘disjunctive normal form’. Wolfram’s rule $18$, for example,
can be expressed as

$\displaystyle\phi(s_{i-1},s_{i},s_{i+1})=(\overline{s_{i-1}}\land\overline{s_{i}}\land
s_{i+1})\lor(s_{i-1}\land\overline{s_{i}}\land\overline{s_{i+1}}),$

where $\land$ and $\lor$ denote the logical and and or, respectively, and an
overbar denotes the not operator.

For a formal definition and a better application-driven methodology, we refer
to Doostfatemeh and Kremer [99]. Note that CAs have also been called ‘fuzzy’
when referring not to the states themselves, but rather to the choice of a
deterministic transition rule applying to a non-continuous CA [7]. These CAs
are however more akin to SCAs.

###  4.3 MSCA genotype and phenotype

####  4.3.1 The MSCA genotype

Most rule table parameters remain well-defined for $k$-nary CAs. Provided
$q\in S$ is a quiescent state, the definition of the Langton parameter
$\lambda$ still holds. As a matter of fact the parameter was originally
introduced for examining the rule space of $|\mathcal{N}|\geq 5,k\geq 4$ CAs
[178], and the paper’s main results are only valid for rule spaces
significantly larger than that of ECAs. The resulting $\lambda$ values are
roughly correlated to the four Wolfram classes. The $Z$-reverse and
obstruction parameters still hold for deterministic $k$-nary CAs. The
$\mu$-sensitivity can also be computed, but some care should be taken in
defining (or perhaps quantifying) a ‘change of state’, as now more than one
option is available.

Global properties of $k$-nary CAs are generally difficult or impossible to
achieve or even define, in part again due to undecidability [83]. More becomes
possible when some structure is imposed on $S$ (e.g. linearity allows for a
study of attractor structures [206]) or when particular rules are investigated
in detail (e.g. rule 2460N in 2-D [306]). Conversely, it is also possible to
determine particular types of $k$-nary CA that are required to possess a
specific property. For example, Bhattacharjee et al. [44] pinpoint a number of
reversible $k$-state finite CAs. More recently, Wolnik et al. [356] shared a
formula for finding all number-conserving $k$-state CAs, and showed that the
only reversible number-conserving ternary CAs are shifts that are
intrinsically 1-D [354].

For fuzzy CA, one could of course simply adopt all rule table parameters
associated with the ECA the fuzzy CA is defined from. Due to the definition of
fuzzification, this should indeed reflect the FCA’s properties when $\forall
i:s_{i}\in\\{0,1\\}$, but it is not obvious how the rule table parameters are
to be interpreted when $s_{i}\in\ ]0,1[$. Neither is it evident that such
parameters would convey useful information; after all, FCAs and binary CAs can
exhibit similarities [42], but fuzzy logic may also lead to entirely different
behaviour. Flocchini et al. [111] show, for example, how a randomly
initialised FCA based on rule 90 will evolve to a homogeneous value of $1/2$,
while paradoxically its Boolean counterpart is entirely aperiodic [154]. For
the characterisation of an FCA rule, and for all types of continuous CAs, it
is therefore generally more insightful to adopt the formalism of coupled-map
lattices, e.g. for determining steady states (attractors). An overview thereof
is provided by Kaneko [159] and more recently by Bunimovich [56].

####  4.3.2 The MSCA phenotype

A classification of $k$-nary CAs according to emergent behaviour is generally
still possible, and often even more systematic (cf. Langton parameter).
Nonetheless, no classification appears to be entirely deterministic, which is
complicated even further by the large number of variations on periodicity or
complexity with larger $k$.

Local properties require some attention in order to apply for $k$-nary CAs,
but the finiteness of the state set $S$ generally enables a logical extension
of the definition. Welch [346], for example, extended the definition of
Lempel-Ziv complexity to accommodate any symbol, in the context of data
compression. For many other properties, however, the nature of the extension
depends on whether $S$ is additive or not. E.g. state density is no longer a
single value when states have no mathematical relationship, such as the $S$,
$I$ and $R$ states in epidemiology – what is $S+R$ supposed to mean?
Additionally, as the state at the previous time step may be important for the
measured property, a change of state is no longer unambiguous. This is
highlighted in the recent publication by Vispoel et al. [338], continuing work
on the Lyapunov exponent for ternary CAs initiated by Baetens and De Baets
[32].

Behaviour-based classification of CCAs is typically based on the attractor
structure associated with the update function (map), i.e. the location and
type of fixed point(s). This behaviour generally changes (and bifurcations can
occur) for different parameter values of the map, such as the $r$ parameter in
the logistic map. For FCAs an exhaustive classification is provided by
Mingarelli [224]. Most mean-field parameters and correlation functions can
easily be extended for CCAs, but measures for sensitivity to initial
conditions and complexity are again generally better expressed using the tools
and methods developed for coupled-map lattices.

###  4.4 Applications of MSCAs

####  4.4.1 Computational advances

Applications of MSCAs within the domain of computer science are as old as the
entire research field, as Von Neumann’s universal constructor [339] required
29 states. Computational tasks are generally more difficult to solve, e.g. the
density problem for ternary CAs [116]. The additional complexity of adding
more states can however also be exploited, such as in random number generation
[46].

####  4.4.2 MSCAs in mathematical modelling

Some successful work on the edge of theory and application has been done,
including a multi-state extension of the Ising model [358], the Greenberg-
Hastings model for excitable media [128], and studies in artificial life in
three-state CAs [360].

Examples of $k$-nary CA applications for mathematical modelling are of course
widespread, because realism almost invariably requires more than two states.
Examples include biological competition [275], pattern classification [118,
89], epidemiology [191, 312], immunology [85], reaction-diffusion [370],
forest fire modelling [18], stock market dynamics [38], and traffic flow
modelling [248].

FCAs have been applied in the context of pattern recognition [202], but also
in artificial life research [276], forest fire modelling [235], or for
modelling snowflakes on a hexagonal grid [80]. As indicated, dynamics of more
general CCAs essentially overlap with finite difference methods for partial
differential equations, and are especially useful for modelling physics [329].
Some notable examples of CCAs used in this fashion are a CA model for diffuse
and dissipative systems [69], the reproduction of the Navier-Stokes equation
in theoretical hydrodynamics [351], a model for groundwater dynamics [273],
and a model for seismic elastodynamics [179]. Conversely, PDEs can simulate
CAs with complex behaviour [251].

##  5 CAs with extended neighbourhoods

###  5.1 Motivation and definition

A CA as defined in Defs. 1.1 and 1.2 is characterised by local and uniform
interaction: a cell only interacts with its neighbours, and the definition of
this neighbourhood $\mathcal{N}$ is identical relative to any cell $c_{i}$ in
the tessellation $\mathcal{T}$. This is narrowed further for ECAs (Def. 1.2),
where $\mathcal{T}$ is a tessellation of $\mathbb{R}$ and
$\mathcal{N}(c_{i})=\\{c_{i-1},c_{i},c_{i+1}\\}$ is limited to its direct
neighbours in one dimension.

This neighbourhood definition is of course quite restrictive. From a
mathematical point of view, it is of interest to study the effect of altering
the neighbourhood size and regularity on the dynamical behaviour. As a
neighbourhood of maximal size is identical to a global system, varying
neighbourhood parameters allows for the examination and quantification of
‘quasi-local’ systems. Moreover, from the perspective of mathematical
modelling, relaxing the neighbourhood condition is nearly always
indispensable. First, in terms of dimensionality: 3-D events can often be
reduced to 2-D models by omitting the least influential dimension (in a top-
view fashion), but losing another dimension often means losing important
information. Second, in terms of neighbourhood size: many phenomena cannot
realistically be assumed to only and fully rely on its closest neighbours, and
even if they would, these neighbours are rarely distributed in a perfect grid,
such that an approach more akin to mean-field theory presents itself. Third,
‘local’ interactions can be physically and temporally separated, and may very
well differ for distinct elements in the model. This is an important
difference between e.g. a lattice of magnetic dipole moments in the Ising
model, and an irregular grid (network) of friends on the Internet. Both the
methodological and the application-driven perspective on this family of
extended CAs motivate further inquiry.

A so-called ‘adjacency matrix’ $\mathbf{A}$ contains all neighbourhood
information, and consists of elements $A_{ij}$ that are non-zero if cell
$c_{i}$ contains cell $c_{j}$ in its (non-local) neighbourhood. If $\forall
i,j:A_{ij}\in\\{0,1\\}$, this allows for $2^{N^{2}}$ possibilities. For ECAs
with periodic BCs, the adjacency matrix alone is sufficient for expressing all
neighbourhoods since $\mathbf{A}$ is tridiagonal.

Other interesting CA families are identified with particular choices for
$\mathbf{A}$, and are discussed next. They are all spatial or temporal
variations of the following definition extension:

######  Definition 5.1 (Extended-neighbourhood cellular automaton).

A finite (size-$N$) extended-neighbourhood cellular automaton (ENCA) is a
sextuple $\mathcal{C}=\langle\mathcal{T},S,s,s_{0},\mathbf{A},\phi\rangle$,
defined as in Def. 1.2 with the exception of properties 5 and 6:

  1. 5\.

The adjacency matrix $\mathbf{A}$ is implicitly defined as

$\mathcal{N}(c_{i})=\left\\{c_{j}|A_{ij}\neq 0\right\\}_{j=1}^{N},$

where $A_{ij}$ is an element of $\mathbf{A}$ and $\mathcal{N}(c_{i})$ is the
neighbourhood of cell $c_{i}$.

  2. 6\.

The function $\phi:S^{|\mathcal{N}|(t+1)}\rightarrow S$ determines the state
of cell $c_{i}$, i.e.

$s(c_{i},t+1)=\phi(\tilde{s}(\mathcal{N}(c_{i}),0),\tilde{s}(\mathcal{N}(c_{i}),1),\ldots,\tilde{s}(\mathcal{N}(c_{i}),t)),$

where $\tilde{s}(\mathcal{N}(c_{i}),t)$ is the tuple
$\left(s(c_{j},t)|A_{ij}(t)\neq 0\right)^{N}_{j=1}$. This function $\phi$ is
called the ‘local update rule’.

###  5.2 ENCA taxonomy

####  5.2.1 Spatial ENCA variations

##### Larger local neighbourhood

First, consider enlarging the neighbourhood size symmetrically (although some
authors discuss asymmetric neighbourhoods as well [37]) around the cell with a
radius $r\in\mathbb{N}$ such that $|\mathcal{N}|=2r+1$. The elements of the
adjacency matrix then become

$\displaystyle
A_{ij}=\delta_{ij}+\sum_{k=1}^{r}(\delta_{(i+k)j}+\delta_{i(j+k)}),$ (5.1)

where $\delta_{ij}$ is the Kronecker delta, with indices mod $N$. The number
of possible local update rules now increases to $k^{k^{2r+1}}$. More
systematic approaches to an enlarged neighbourhood are sometimes considered to
enable a mathematical description and a link to other CA families, e.g. [163].

##### Higher dimensions and irregular tessellations

Second, virtually all applications require CAs with more than one spatial
dimension. In a regular square grid with $N^{2}$ cells, two symmetrical
neighbourhoods are typically considered, called the Von Neumann neighbourhood
and the Moore neighbourhood. The former consists of the central cell and all
directly adjacent cells, while the latter additionally contains all diagonally
adjacent cells. Mathematically, these neighbourhoods are the simplest non-
trivial form of ‘templates’ $H_{r}^{(n)}$ and $J_{r}^{(n)}$, first defined by
Cole [293]:

$\displaystyle H_{r}^{(n)}=\left\\{\mathbf{a}\ \biggl{|}\
\sum_{i=0}^{n-1}|a_{i}|\leq r\right\\},\qquad J_{r}^{(n)}=\left\\{\mathbf{a}\
\biggl{|}\ \max\limits_{0\leq i\leq n-1}\\{|a_{i}|\\}\leq r\right\\}.$

Here, $n$ is the CA dimension, and $\mathbf{a}$ is the vector indicating the
location of neighbourhood cells, relative to the central cell. Note that
$H_{r}^{(1)}=J_{r}^{(1)}$. Butler [60] demonstrated that (in two dimensions)
any CA with Moore neighbourhood of radius $r$ can be simulated by a CA with a
larger state space and Von Neumann neighbourhood of radius $r^{\prime}>r$, but
performing calculations $r^{\prime}/r$ times faster. These definitions can be
extended to more general shapes and into higher dimensions (e.g. [31]), but
the fact remains that any $n$-D CA can be reduced to a 1-D CA with an extended
neighbourhood.

The classical CA paradigm is built on the assumption that the tessellation
$\mathcal{T}$ is defined over a regular domain. Yamada and Amoroso [366]
showed that any CA on a regular tessellation can be simulated by a CA on a
different regular tessellation, provided we alter the state space. The most
well-researched alternative is the hexagonal grid [39]. CAs defined on
irregular tessellations were examined by Baetens and De Baets [29]. Examples
include a Voronoi-like tessellation [8] and Penrose tilings [254]. Margenstern
[208] has gone even further, by considering CAs defined on hyperbolic space.

##### Network automata

Third, neighbourhoods can be so irregular and/or non-local that it no longer
makes sense to consider a CA as ‘cellular’. All cells (now typically called
‘nodes’) are connected in a so-called ‘network automaton’ (NA, also: ‘graph
CA’ or ‘nonlocal CA’) [331], where the connectivity of nodes may again be
represented in the adjacency matrix $\mathbf{A}$. The neighbourhood size
$|\mathcal{N}(c_{i})|$ now generally depends on the node, and in the context
of network theory it is often referred to as the ‘node degree’. In general,
the value $A_{ij}$ representing the connection from node $c_{i}$ to $c_{j}$
may be any positive real number, where typically a higher value indicates a
‘stronger’ connection.

This of course allows for a virtually endless structural variation of
networks, whose properties are studied in the field of ‘complex networks’
[84]. When other NA properties such as state space and local update rule are
still sufficiently reminiscent of the classical CA paradigm, e.g. for random
Boolean networks [122], theoretical knowledge and practical applications may
nonetheless be transferred between both research domains.

####  5.2.2 Temporal ENCA variations

The adjacency matrix $\mathbf{A}$ may be time-dependent, such that
neighbourhoods can vary as the CA evolves. Such CAs were suggested by
Ilachinski [149] and coined ‘structurally dynamic’ CAs. This dynamic
structuring of neighbourhoods may be random, preserve some statistical
property, be dependent on the state of the node, etcetera [17]. It may even
allow for adding or removing nodes, which is studied in percolation theory
[184]. This again opens Pandora’s box of possible variations, and takes us
beyond the scope of this CA-centred review paper. Within the confines of this
review, however, we discuss the static temporal ENCA types named ‘memory CAs’,
and the related concept of ‘reversible’ CAs.

##### Memory CA

An ECA is considered to be memoryless in the sense that the new state of a
cell depends on the neighbourhood configuration at the preceding time step
only. This can however be extended by considering past states in the evolution
of the CA, which particularly Alonso-Sanz has intensively researched (e.g.
[23]). Mathematically, the local update rule in Def. 1.2 is extended such that
$s(c_{i},t+1)=\phi(m(\mathcal{N}(c_{i}),t))$, where

$m(\mathcal{N}(c_{i}),t)=\biggl{(}\tilde{s}(\mathcal{N}(c_{i}),0),\allowbreak\tilde{s}(\mathcal{N}(c_{i}),1),\allowbreak\ldots,\allowbreak\tilde{s}(\mathcal{N}(c_{i}),t)\biggr{)}.$

Many ways of incorporating neighbourhoods in previous time steps present
themselves, some of which support the design of desirable (complex) behaviour
[213]. One particular ENCA type is the ‘average memory CA’ [21], where at
every time step $t$, and for each cell, one computes a weighted mean of all
states since the initial configuration. More often, however, the local rule
incorporates a limited memory in the state transition [9]; it is said to be of
order $M$ if it depends on $M$ previous time steps. Motivated by physical
realism, a variation of memory CAs where some cells have a longer memory than
others – i.e. non-uniform memory CAs, see Section 6 – has also been explored
[285].

##### Reversible CA

CAs are generally not ‘reversible’, meaning that a particular configuration
may have multiple predecessors: only six of the 256 ECAs are reversible,
indeed [353], and all are trivial. As temporal reversibility (or technically,
CPT invariance) is a fundamental symmetry in physics, CA models that aim to
describe physics ideally reflect this property [209]. Additionally,
reversibility is desirable from a computer architecture perspective [329].

Reversibility can be induced in ECAs by involving second-order memory ($M=2$)
[209]. The new state of a cell is inverted if two steps previously the cell
was in state $1$, i.e.

$\displaystyle
s(c_{i},t+1)=\begin{cases}\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{if
}s(c_{i},t-1)=0,\\\ 1-\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{if
}s(c_{i},t-1)=1.\end{cases}$

The resulting rule is simply called $W(\phi)$ with a suffix ‘R’; some examples
of 1-D reversible CAs and their respective rule tables are shown in Fig. 5.1.
Similar procedures have been investigated for 2-D CAs [19], and generalised
for reversible CAs supported by higher-order memory [302]. As an important
remark in the context of our taxonomic treatment, Toffoli [328] showed that
any $n$-D CA can be simulated by a reversible CA of dimension $n+1$.

Figure 5.1: Rule 30 can be made reversible by imposing the complementary rule
(rule 225) if the updated cell was in state 1 two time steps ago. The rule
table is on the left, and two resulting spacetime diagrams, which are clearly
symmetric under time reversal, are on the right.

###  5.3 ENCA genotype and phenotype

The family of ENCAs contains a relatively wide variety of types. We discuss
the genotype and phenotype of these types in the same order as these were
presented above, and note that they generally exhibit less characteristic
overlap than types in other CA families.

####  5.3.1 The ENCA genotype

When the neighbourhood size increases, this affects the rule table parameter
values, as many more neighbourhood configurations make up the rule table. The
definition of these parameters however remains identical (cf. Tab. 1.3), again
demonstrated by the fact that e.g. the Langton parameter was originally
investigated for $|\mathcal{N}|=5$ [178]. Global properties are also still
well-defined for larger neighbourhoods, but can become much more involved as
there are many more possible configuration transitions. One way to circumvent
this, is to only consider totalistic rules, e.g. when identifying global
periodicity [51]. Also recall the complexity trade-off between a CA with a
larger neighbourhood and a CA with more states [316], which may aid to
rephrase particular definitions. One such example is given in Fig. 5.2.

Figure 5.2: Complexity trade-off between neighbourhood size, number of time
steps, and number of states. Here a $k=2$, $|\mathcal{N}|=5$ CA is simulated
by a $k=8,|\mathcal{N}|=3$ CA with the same number of cells, but twice the
number of time steps.

When the neighbourhood is irregular (i.e. for NAs) but the neighbourhood size
is homogeneous, Li [185] showed that rule table parameter definitions can be
generalised. This no longer holds when the local update rule does not operate
on a neighbourhood with fixed size; this rule, then, is therefore almost
always phrased in a totalistic fashion. Marr and Hutt [210], for example,
determine a node state update based on the weighted density of states over all
neighbouring nodes,

$\displaystyle
s(c_{i},t+1)=\phi\left(\dfrac{1}{|\mathcal{N}(c_{i})|}\sum\limits_{c_{j}\in\mathcal{N}(c_{i})}A_{ij}s(c_{j},t)\right).$

This type of local update function allows for analysis, but not in the sense
of the classical rule table. A similar consideration holds for global
properties of the NA, and it is generally advised to make use of tools and
properties devised for the analysis of complex networks, in particular in
relationship to the node degree distribution [84].

Memory CAs can have a rule table, as we illustrated in Fig. 5.1. If
additionally the memory CA is reversible, only half of the rule table contains
all required information for constructing rule table parameters. However, if
the memory degree $M$ is large, such a rule table may become impractically
large, impeding an elegant generalisation of the rule table parameters in Tab.
1.4. When previous states are weighed, the resulting memory CA of course runs
into the same issues as the CCAs discussed in Section 4.

As for CAs with a larger neighbourhood size, generally the space of possible
(subsequent) configurations in a memory CA increases in size, resulting in
more involved global properties. The particular case of the reversible CA,
however, strongly limits possible dynamics: every configuration has one and
only one successor and predecessor. This generally strongly simplifies global
mathematical description [234].

####  5.3.2 The ENCA phenotype

Subsequent 1-D configurations of ENCAs with a larger neighbourhood can still
be described with local properties defined for ECAs. Due to more distant (but
still local) information transfer, spatial correlations are generally achieved
on shorter time scales. We also observe that simply the size of the
neighbourhood may affect the global behavioural class [163].

Phenotypical classification and quantification of ENCAs in higher dimensions
and – especially – with irregular tessellations, requires some attention. The
behavioural classes that are employed for 1-D CAs generally apply for CAs in
two or more dimensions [255]. However, Gerling [121] observed drastically
different behaviour for 3-D CAs. Generally, the much larger variety of
dynamical outcomes in higher dimensions suggests that a richer classification
(i.e. more than four classes) may be informative [318].

In terms of local properties of dynamical behaviour (cf. Tab. 1.4) of $n$-D
CAs, either the metric should be extended into $n$ dimensions, or some measure
for direction should be provided. As an example for the first case, consider
some local structure theory where a particular property is averaged over an
$n$-D block or sphere. For the second case, imagine the Lyapunov exponent
related to the spread of a difference pattern in one specified direction,
which could be averaged over all directions [338], or directing according to
some perturbation front [79]. Baetens and De Baets [28] use Lyapunov exponents
for totalistic CAs with irregular tessellations, demonstrating that even
something as drastic as a phase transition can be induced by solely altering
the topology.

Network automata disregard all sense of ‘geographical’ direction. Behaviour on
networks can however still be classified in the classical sense, e.g.
according to the Li-Packard classes [185]. In particular, by adjusting a
number of entropy definitions to the context of a complex network, Marr and
Hütt [210] showed that outer-totalistic NAs on various network types can
evolve according to all four Wolfram behavioural classes. They also observed
that the fraction of such NAs that exhibit complex behaviour shrinks for
increasing neighbourhood size [211]. At the same time, the analysis of
emergent NA dynamics can be used to classify the type of network itself when
the adjacency matrix is unknown, e.g. by running a NA based on the Game of
Life [226].

Local properties can still be investigated when the ‘direction’ required in
the original definition from a particular node is generalised as some well-
defined path through the network. The generalisation of i.a. the Lyapunov
exponent [194], then, allows for quantifying the robustness of an NA to
topological variations. NAs exhibit topology-induced phase transitions [28],
and topology influences an NA’s tendency towards self-organisation [122].

CAs with memory are typically characterised with the canonical behavioural
classes. Interestingly, adding memory to ECAs can also induce a class
transition. Martínez et al. [214] show that almost half of all ECAs will
completely transform their behaviour when information from up to ten previous
time steps is taken into account. In particular, adding memory to CAs based on
elementary rules can help ‘design’ complex behaviour [215]. This is confirmed
by Ninagawa et al. [246].

###  5.4 Applications of ENCAs

####  5.4.1 Computational advances

1-D binary CAs with a larger neighbourhood are typically more suited than ECAs
to solve computational problems such as density classification, even though no
finite-radius perfect solution exists [175]. This is because they allow a
wider range of rules, and because they represent some ‘intermediate’ model
between a purely local and global model. In the context of cryptography,
randomness properties of a 1-D CA have also been investigated [250] for larger
radii. In particular, $r=2$ (‘pentavalent’) CAs were shown to be advantageous
for a type of plain text cryptography called stream cipher design [174], while
still remaining computationally feasible.

Most applications of ENCAs, however, require more than one dimension and/or
special tessellations. The performance difference between the (2-D) Moore and
Von Neumann neighbourhoods has been reported for image cryptography [2].
Adamatzky [10] showed that hexagonal grids can support logical operations by
generating gliders reminiscent of the Game of Life, and also Penrose tilings
were shown to support some variation on the Game of Life [254].

Turning to NAs, many computation-related questions remain open, but some
advances have clearly been made. Watts [344] examined the majority and
synchronisation problems for small-world networks, showing that a local
majority rule was typically sufficient for solving the problem, despite being
inadequate for regular networks [88]. Darabos et al. [87] considered a wider
range of network architectures, but still concluded that a small-world network
is superior for solving the density or synchronisation problem.

Memory CAs, finally, also appear to facilitate density classification [22],
although more research into their relation to computational problems is
required.

####  5.4.2 ENCAs in mathematical modelling

Nearly all CA applications in mathematical modelling require a CA with more
than one spatial dimension. Some authors have explicitly examined the
influence of 2-D tessellations on model properties. Hopman and Leamy [144],
for example, compared irregular triangular tessellations in elastodynamics
with the rectangular case [179]. Also for geographical applications such as
urban growth modelling, triangular [252] and irregularly-shaped CAs [319] are
routinely applied. In social sciences, Flache showed that many general
properties are robust to variation in the grid structure [110].

Mathematical modelling has a rich history involving complex networks, with
networks optimised for representing i.a. metabolic [155], social [326], and
biological [100] networks. When no direct access to the network’s adjacency
matrix is available, an analysis of the dynamical behaviour induced by an NA
may serve as a tool for categorising the network type, useful for e.g.
authorship attribution of written text [198]. With this aim, Miranda et al.
[226] proposed an NA running an extended definition of the Game of Life, using
measures such as Shannon entropy and word entropy in the decision process.
This work was refined more recently by Ribas et al. [279] and Zielinski et al.
[377]. NAs are of course also used when, inversely, the network is known but
the emergent dynamical behaviour is not. Such applications likewise cover a
wide spectrum of research areas, ranging from urban planning [253] to fungal
growth [315].

for memory CAs, finally, the most obvious application of memory CAs is again
found in their relation to reversibility and (hence) conservation [162]. This
property justifies its use in modelling e.g. Newtonian mechanics [20],
although also here the number of practical applications found in the
literature is limited.

##  6 Non-uniform CA

###  6.1 Motivation and definition

A final extension to CAs allows for different cells to follow different rules,
i.e. the cells behave in a ‘non-uniform’ fashion. CAs in which rule uniformity
is abandoned are therefore called non-uniform CAs (or ‘heterogeneous’ CAs,
e.g. [119]), often abbreviated as $\nu$CAs. Now, the local update rule depends
on the cell identity $i$ and time step $t$, so we have $\phi=\phi(i,t)$.
Cattaneo et al. [63] identify three reasons to relax the uniformity
constraint. First, generality, as some models may require local interactions
to be dependent on some global spatial positioning. Second, the investigation
of structural stability, because some emergent properties may be strongly
dependent on all cells following the same rule, implying that some of the CA
behaviour is ‘artificial’. Third, reliability (robustness to noise),
particularly in the context of fast parallel computation. These motivations
are highly similar to those for ACAs and SCAs, and we will in fact show that
in many cases the mathematics is similar (or identical) as well.

In principle, $\nu$CAs may have an arbitrary number and type of local update
rules that depend on time and space. The simplest non-trivial size-$N$ $\nu$CA
allows for two local elementary update rules, say $\phi$ and $\psi$. We arrive
at the following definition:

######  Definition 6.1 (Non-uniform cellular automaton).

A non-uniform cellular automaton ($\nu$CA) is identical to an ECA (Def. 1.2),
with the exception of the sixth property:

$\displaystyle
s(c_{i},t+1)=\begin{cases}\phi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{if
}i\in Z(t),\\\ \psi(\tilde{s}(\mathcal{N}(c_{i}),t)),&\text{else},\end{cases}$
(6.1)

where the set $Z(t)\subseteq\\{1,\ldots,N\\}$ generally changes over time and
determines the ‘rule allocation’.

We refer to $|Z(t)|/N=\nu(t)\in[0,1]$ as the degree of non-uniformity, where
$\nu=1/2$ represents maximal non-uniformity. Note that if $\psi$ is the
identity rule ($W(\psi)=204$), this is equivalent to the general definition of
$\alpha$-asynchronous CAs (Def. 2.1 and Section 2), with $\nu=\alpha$. In that
spirit, the set $Z(t)$ again allows for distinguishing between various types
of $\nu$CAs.

###  6.2 Non-uniform CA taxonomy

####  6.2.1 Spatial $\nu$CA variations

If $Z(t)=Z$, the rule allocation is static. Clearly, for a two-rule size-$N$
$\nu$CA, there are $2^{N}$ possible rule allocations in total, and
$\dbinom{N}{|Z|}$ for a particular $\nu$. We may, however, distinguish between
various types.

First, a stochastic rule allocation, for which every cell has a probability
$p$ (resp. $1-p$) of following rule $\phi$ (resp. $\psi$), such that
$|Z|\sim\text{Bin}(N,p)$, and $\text{E}[\nu]=p$. This of course is identical
to the general definition of an SCA (Def. 3.1). This setup is of interest
because, especially for $p=1/2$, it is the ‘least global’ non-uniform rule
allocation, which is still in line with the CA philosophy of maximal locality
[45], and which generally still allows for mathematical generalisations. As
with SCAs, we may additionally demand that $|Z(t)|$ is constant.

Second, only a single cell may behave differently, i.e. $Z=\\{j|0<j\leq N\\}$.
This is of interest in the research of robustness to noise due to permanent
failures [97], allowing the quantification of the effect of one ‘rogue cell’.

Third, $Z$ can be chosen such that the rule allocation is periodic, e.g.
$Z=\\{2j\ |\ 0<j\leq N/2\ \land j\in\mathbb{N}\\}$, or more generally

$\displaystyle Z=\bigcup\limits_{k=0}^{N/T-1}\\{1+kT,\ldots,\nu T+kT\\}.$
(6.2)

Here $T$ represents the period, in such a way that $N$ is a whole multiple of
$T$, and $\nu=n/N$ with $n\in\\{0,\ldots,N\\}$. This approach represents a
setup that more conveniently enables properties with a closed mathematical
expression.

The fourth type is the most general one, where $Z$ is entirely ‘user-defined’
at the global level. One notable case that is especially relevant for
mathematical modelling may be called clustered rule allocation, for which
adjacent cells are on average more likely to follow the same rule. Such
clusters may be generated stochastically, but typically they are defined by
the modeller based on a spatial distribution of e.g. geographical features.
For instance, in a wildfire model [18], this may be understood as geographical
regions containing water versus those containing soil, for which different
rules apply.

The CA’s non-uniformity can be further increased, going beyond Def. 6.1. This
is done by including more rules (that need not be elementary), which generally
implies more variation and less mathematical oversight. Three mathematical
types of these ‘general’ $\nu$CAs allow for the generalisation of properties
of uniform CAs, so-called default-rule, structural-period, and radius-$r$
$\nu$CAs [95]. As all three definitions require some symmetry around a central
cell, the artificiality of their setup generally impedes any interesting
application beyond mere mathematical constructions.

####  6.2.2 Temporal $\nu$CA variations

If $Z(t)$ is time-dependent, we may distinguish between purely temporal and
spatiotemporal non-uniformity.

##### Purely temporal $\nu$CAs

If (for binary $\nu$CAs) $Z(t)$ identifies at time $t$ either all cells or
none of the cells, the CA is spatially uniform, but its global update function
can change over time. For a two-rule $\nu$CA, this may be expressed as a set
$\widetilde{Z}\subseteq\\{0,\ldots,t_{\text{f}}\\}$ with $2^{t_{\text{f}}+1}$
possible choices, where $t_{\text{f}}$ is the final time step in the
simulation. We may identify the same general variations as for the spatially
non-uniform case, with a similar motivation. Note that the stochastic case,
where $\widetilde{Z}\sim\text{Bin}(t_{\text{f}}+1,q)$ determines whether
global rule $\Phi$ (reps. $\Psi$) applies with probability $q$ (resp. $1-q$)
is entirely equivalent to a temporal SCA [286] (cf. Section 3.2.2).

##### Spatiotemporal $\nu$CAs

In the most general case, the rule allocation changes both in space and in
time. We discuss two special cases of two-rule $\nu$CAs with some systematic
local rule allocation, and demonstrate how this locality causes the $\nu$CA to
be equivalent to a uniform (multi-state) CA, and vice versa.

First, $Z(t)$ may change over time if the local rule depends on the
neighbourhood. However, as an example, suppose rule 153 applies when the
neighbourhood is symmetric, and rule 102 otherwise. In binary code, we write
this as $153=\mathbf{1}0\mathbf{0}11\mathbf{0}0\mathbf{1}_{2}$ and
$102=0\mathbf{1}1\mathbf{00}1\mathbf{1}0_{2}$, where the bold bits indicate
when the rule applies. The effective uniform rule is then simply the
combination of the boldface bits, so $11000011_{2}=195$. This is easily
generalised to CAs with more states and/or a larger neighbourhood.

Second, we can build a simple $\nu$CA with local rule allocation dynamics,
stacking from two rules $\phi$ and $\psi$. Suppose rule $\phi$ applies to
cells $\\{c_{i}|i\in Z(t)\\}$, and rule $\psi$ applies to all others. From
some initial rule allocation $Z(0)$, the set $Z(t)$ is updated according to
some local rule, say another Wolfram rule $\xi$ with

$\displaystyle[\phi_{i}(t+1)=\phi]=\xi([\phi_{i-1}(t)=\phi],[\phi_{i}(t)=\phi],[\phi_{i+1}(t)=\phi]).$
(6.3)

Here $\phi_{i}(t)$ indicates the rule that updates cell $c_{i}$ at time step
$t$, and $[\phi_{i}(t)=\phi]$ outputs $1$ (resp. $0$) when the update rule is
rule $\phi$ (resp. rule $\psi$).

Note, now, that any cell can be in one of four ‘dual’ states, namely
$\\{0,\phi\\},\\{0,\psi\\},\\{1,\phi\\}$ or $\\{1,\psi\\}$, and the dual state
of a cell at the next time step is deterministically and uniformly dictated by
the dual states of its neighbourhood. The dual state’s first element depends
on the first elements of the dual states of the cell’s neighbourhood, as well
as the second element of the dual state of the cell itself. The dual state’s
second element depends only on the second elements of the dual states of the
neighbourhood. This amounts to $256^{3}\sim 10^{7}$ possible rules,
essentially picking a Wolfram rule for $\phi,\psi$, and $\xi$. These rules
form a (tiny) subset of the $\sim 10^{38}$ quaternary $|\mathcal{N}|=3$ local
update rules. That is to say: a binary three-neighbourhood two-rule $\nu$CA
can be mapped to – and therefore simulated by – a quaternary three-
neighbourhood uniform CA.

As an example of such a mapping, consider a binary two-rule $\nu$CA
$\mathcal{C}_{1}$ and a quaternary uniform CA $\mathcal{C}_{2}$, both with
$|\mathcal{N}|=3$. If we consider $\mathcal{C}_{1}$ to have four dual states,
we may perform a mapping (choosing one of $4!$ possibilities) between the
states of both CAs:

$\displaystyle(\\{0,\phi\\},\\{0,\psi\\},\\{1,\phi\\},\\{1,\psi\\})\mapsto(0,1,2,3).$

This implies that a cell in an even state in $\mathcal{C}_{2}$ corresponds to
a cell that obeys rule $\phi$ in $\mathcal{C}_{1}$. A cell in a state smaller
than 2 in $\mathcal{C}_{2}$ corresponds to a cell in state 0 in
$\mathcal{C}_{1}$. These are two independent binary observations (odd/even and
smaller/greater than 2), which always lead to a definite state value for the
cell in the quaternary CA. We show an example of the result from this mapping
in Fig. 6.1.

Figure 6.1: A four-state (quaternary) CA can simulate a $\nu$CA with locally
defined dynamic rule allocation. Here, the cells in a $\nu$CA are evolved
according to either rule $\phi=110$ or rule $\psi=170$. The allocation of
these rules to the cells at a particular step is determined by the initial
rule allocation – in this case periodic with period $T=5$ –, and evolved by
rule $\xi=240$ (left). The resulting $\nu$CA spacetime diagram is shown in the
centre diagram. The righthand spacetime diagram displays the quaternary
uniform CA that simulates this $\nu$CA by means of rule
$326\,159\,115\,819\,648\,357\,517\,613\,529\,732\,932\,608\,160$.

More generally, a $\nu$CA governed by $l$ rules and hosting $k$ states can be
mapped to a uniform $(k\times l)$-nary CA with the same neighbourhood size.
The inverse is generally not true as the rule space cardinality of the former
is much smaller than that of the latter:

$\forall
k,l>1:k^{lk^{|\mathcal{N}|}}l^{l^{|\mathcal{N}|}}\ll(kl)^{(kl)^{|\mathcal{N}|}}.$

This is due to the fact that many quaternary rules are illegal for $\nu$CA
simulation, because the outputs of all $(kl)^{|\mathcal{N}|}$ neighbourhood
configurations must be mutually consistent.

##### Hybrid CAs

Because one of the central CA properties is its locality, CAs that violate
this attribute are sometimes called ‘hybrid CAs’. The local update rule can
generally be written as $\phi=\phi(\tilde{s}(\mathcal{N},t),\theta(i,t))$,
with $\theta$ a time- and space-dependent global parameter. This essentially
allows for an infinite number of rules and is arguably the most general form
of a $\nu$CA. Its merit is however again mostly in applications, as closed
mathematical expressions are now generally infeasible.

###  6.3 Non-uniform CA genotype and phenotype

####  6.3.1 The non-uniform CA genotype

Dennunzio et al. [97] identify three directions in the genotypical
characterisation of $\nu$CAs: (1) the investigation of sensitive dependence on
initial conditions, (2) the generalisation of conditions for dynamical
properties such as number conservation and reversibility, and (3) the
exploration of the set of reachable states, and of the fixed-point sets in
particular. Because many genotypical properties of classical CAs are supported
by the uniform application of a single rule table, many of these are no longer
true for $\nu$CAs in general. Some clever generalisations can be made for
particular $\nu$CAs [95], but these results are difficult to exploit outside
the realm of pure mathematics.

Dependence on initial conditions, which is a measure of chaoticity, has been
studied from a genotypical perspective by Kamilya and Das [158] by quantifying
the information flow through the CA.

Rule table parameters for $\nu$CA may be constructed from the rule table
parameters associated with the rules that make up the $\nu$CA, e.g. by simply
taking the average. However, an approach that depends less on contingent
choices is supported by the observation that the uniform $k$-nary CA that
simulates the $\nu$CA at hand, must also encode its genotype. That is to say:
just look at the rule table of the uniform CA that simulates the $\nu$CA.
Whether or not this approach is helpful, however, depends on whether (1) this
complexity trade-off map between the two CA families exists – which is not
true in general –, and whether (2) the genotype of the $k$-nary CA is known
and sufficiently informative. If these conditions are met, a $\nu$CA can be
associated with all rule table parameters and global properties known to the
$k$-nary CA, independent of the initial configuration. To our knowledge, no
such approach has yet been taken.

Regarding the identification of genotypical dynamical $\nu$CA properties
(Dennunzio et al.’s second research direction), much theoretical work has been
focused on number conservation (e.g. [294]). In particular, Wolnik et al.
[355] recently identified all number-conserving and reversible finite 1-D
$\nu$CAs constructed from Wolfram rules. More generally, Dennunzio et al. [96]
formally investigated properties of $\nu$CAs for different rule allocations,
identifying a number of complexity classes, but also again pinpointing the
many methodological challenges that non-uniformity invokes [96].

Concerning the third research direction, Dennunzio et al.[97] have applied de
Bruijn graphs in formal language theory to identify a number of fixed-point
configurations of the $\nu$CA. Adak et al. [6] developed a construction method
for $\nu$CAs whose fixed-point set has cardinality one, i.e. that have a
static end state. Taking a slightly different perspective, Adak et al. [5]
recently developed an (often efficient) algorithm that decides whether or not
a $\nu$CA configuration can be reached from another one.

####  6.3.2 The non-uniform CA phenotype

Little work has been done on the classification of $\nu$CAs based on their
phenotype. Arguably, this is due to the large number of possibilities –
allocating two rules in a periodic CA of $N$ cells provides $2^{N}/N$ options
–, and due to the unpredictable interference of rules – e.g. two periodic
rules may cooperate, generating a complex pattern. While the latter reason is
indeed a symptom of the theoretical difficulty associated with $\nu$CAs, it is
also an important reason to investigate this model further. After all, it
demonstrates yet again the principle of emergence in (evolving) artificial
life [309].

We argue that computational resources can now accommodate large-scale
simulations that may uncover instructive statistical correlations within the
large set of $\nu$CA possibilities. This is especially the case considering
that almost all local phenotypical properties remain well-defined.
Nonetheless, the amount of research in this direction is limited, and
established results are mostly formulated in terms of equivalent stochastic
CAs. In particular, the aforementioned work by Fatès [108] on diploid CAs in
fact also documents phase transitions in $\nu$CAs with random dynamic rule
allocations, and Roy et al.’s work on temporally stochastic CAs [286]
demonstrates the emergence of unexpected behaviour in purely temporal
$\nu$CAs.

As a closing remark, note that also the Lyapunov exponent remains well-
defined, but that the introduction of non-uniformity opens the possibility of
inspecting a new type of sensitivity: dependence on initial rule allocation.
The initial defect is then represented by breaking uniformity via the
allocation of a different rule to one cell, possibly causing a defect cone in
the resulting spacetime diagram.

###  6.4 Applications of non-uniform CAs

####  6.4.1 Computational advances

In the context of computer science, $\nu$CAs were explored in the context of
tasks such as the majority problem [311]. In particular, Sipper [310] showed
that $\nu$CAs are capable of solving this problem in over 90 percent of the
cases, mainly due to the higher number of design variations. As with the
uniform case [228], evolutionary algorithms can be of great help for
identifying these rules, as well as for constructing a $\nu$CA that performs
simple arithmetic operations [129]. Further, Kumaravel and Meetei [171] used
reversible $\nu$CAs for increasing the complexity (and hence the safety) of
encryption-decryption algorithms. This research was continued more recently by
Mukherjee et al. [236]. A better understanding of the theoretical foundation
is of particular interest for these approaches, and a lot is left to uncover.

####  6.4.2 $\nu$CAs in mathematical modelling

Outside theoretical computer science, $\nu$CAs have been applied to model both
natural and man-made phenomena, such as epidemiology [103], insect movement
[282], and biochemistry [102]. In theoretical biology, Adams [11] again
highlights the importance of randomness in evolution, by means of a purely
temporal $\nu$CA where the local rule is determined by some global property of
the system. Hybrid CAs have been used in wildfire modelling where the global
parameter could be the time-dependent direction of the wind [18], and in
cancer therapy research where the changing nutrients concentration affects the
local transition rule [280]. Another example of a hybrid CA is Vichniac’s
Ising model [336], in which the temperature plays the role of global parameter
that affects transition probabilities.

##  7 Conclusion and outlook

Figure 7.1: We identify five families of CAs, based on their divergence from
the elementary cellular automaton (ECA). Some important identities and trade-
offs between these families are indicated by arrows annotated with the
required change in interpretation. Clockwise, the diagram contains non-uniform
(nuCA), multiple-state (MSCA), extended-neighbourhood (ENCA), asynchronous
(ACA), and stochastic cellular automata (SCA).

We reviewed literature on five families: asynchronous CAs, stochastic CAs,
multi-state CAs, extended-neighbourhood CAs, and non-uniform CAs. Each of
these families is characterised by a distinct departure from the definition of
ECAs, and are interconnected by mathematical identities, shown in Fig. 7.1.
Despite the fact that some CA types and applications were not covered, we
consider this review to be highly comprehensive. This is because we chose to
only leave out particular topics when the relation to ECAs was considered too
remote (e.g. spatially continuous CAs), when the CA was too idiosyncratic to a
particular research field (e.g. quantum CAs), or when applications were not
chiefly of a scientific nature (e.g. CAs in the arts).

This survey disclosed a number of noteworthy patterns and realisations within
the study of CAs. First, we emphasise the conceptual paradox that many CA
families and types are in some sense opposed to the CA philosophy of strict
locality, as often some global or random choice is imposed onto the individual
cells. Second, we observe a trade-off of sorts: increased realism and
applicability almost invariably comes at the cost of decreased mathematical
elegance and methodological generality. Third, the methodological approach to
each CA family brought with it an appreciation for the substantial
mathematical overlap between these families. This clearly allows for an entire
spectrum of approaches to a particular mathematical matter, but also bridges
the gap between various academic branches within this field of research.

Concluding, we perceive the study of CAs as a great scientific opportunity,
both as the object of mathematical inquiry as well as a modelling tool. CA
research has a mature theoretical basis, presents many promising research
avenues, and is studied at a time when computational power allows for thorough
exploration. Non-uniform CAs and network automata in particular are currently
well-positioned for disclosing their properties and merits. This is underlined
by their close relationship to well-documented CA families and their
properties, the many straightforward simulations that can be statistically
described with these properties, and the wide spectrum of applications.

## Acknowledgements

This work has been partially supported by the FWO grant 3G0G0122 with project
title “An analysis of network automata as models for biological and natural
processes”.

## References

  * Abdo et al. [2013] A. A. Abdo, S. Lian, I. A. Ismail, M. Amin, H. Diab, A cryptosystem based on elementary cellular automata, Communications in Nonlinear Science and Numerical Simulation 18 (1) (2013) 136–147, ISSN 1007-5704, doi:https://doi.org/10.1016/j.cnsns.2012.05.023.
  * Abu Dalhoum et al. [2012] A. L. Abu Dalhoum, B. A. Mahafzah, A. A. Awwad, I. Aldamari, A. Ortega, M. Alfonseca, Digital Image Scrambling Using 2D Cellular Automata, IEEE Multimedia 19 (4) (2012) 28–36, ISSN 1070-986X, doi:10.1109/MMUL.2011.54.
  * Aburas et al. [2016] M. M. Aburas, Y. M. Ho, M. F. Ramli, Z. H. Ash’aari, The simulation and prediction of spatio-temporal urban growth trends using cellular automata models: A review, International Journal of Applied Earth Observation and Geoinformation 52 (2016) 380–389, ISSN 0303-2434, doi:10.1016/j.jag.2016.07.007.
  * Adachi et al. [2004] S. Adachi, F. Peper, J. Lee, Computation by asynchronously updating cellular automata, Journal of Statistical Physics 114 (1-2) (2004) 261–289, ISSN 0022-4715, doi:10.1023/B:JOSS.0000003112.54283.ac.
  * Adak et al. [2021] S. Adak, S. Mukherjee, S. Das, Reachability problem in non-uniform cellular automata, Information Sciences 543 (2021) 72–84, ISSN 0020-0255, doi:10.1016/j.ins.2020.07.034.
  * Adak et al. [2017] S. Adak, N. Naskar, P. Maji, S. Das, On Synthesis of Non-Uniform Cellular Automata Having Only Point Attractors, Journal of Cellular Automata 12 (1-2) (2017) 81–100, ISSN 1557-5969.
  * Adamatzky [1994] A. Adamatzky, Hierarchy of fuzzy cellular automata, Fuzzy Sets and Systems 62 (2) (1994) 167–174.
  * Adamatzky [1996] A. Adamatzky, Voronoi-like Partition of Lattice in Cellular Automata, Mathl. Comput. Modelling 23 (4) (1996) 51–66.
  * Adamatzky [2009] A. Adamatzky, Identification of Cellular Automata, in: Encyclopedia of Complexity and Systems Science, Springer New York, 4739–4751, 2009.
  * Adamatzky et al. [2006] A. Adamatzky, A. Wuensche, B. D. Costello, Glider-based computing in reaction-diffusion hexagonal cellular automata, Chaos Solitons & Fractals 27 (2) (2006) 287–295, ISSN 0960-0779, doi:10.1016/j.chaos.2005.03.048.
  * Adams [2022] A. M. Adams, The Effects of Interaction Functions between Two Cellular Automata, Complex Systems 31 (2) (2022) 203–217, doi:10.25088/ComplexSystems.31.2.203.
  * Agapie et al. [2014] A. Agapie, A. Andreica, M. Giuclea, Probabilistic Cellular Automata, Journal of Computational Biology 21 (9) (2014) 699–708, ISSN 1066-5277, doi:10.1089/cmb.2014.0074.
  * Ahmed and Teahan [2020] N. Ahmed, W. Teahan, Using compression to find interesting one-dimensional cellular automata, Complex & Intelligent Systems 6 (1) (2020) 123–146, ISSN 2199-4536, doi:10.1007/s40747-019-00121-7.
  * Akishin et al. [1998] P. G. Akishin, M. V. Altaisky, I. Antoniou, A. D. Budnik, V. V. Ivanov, Simulation of Earthquakes with Cellular Automata, Discrete Dynamics in Nature and Society 2 (4), ISSN 1026-0226.
  * Alarcón et al. [2003] T. Alarcón, H. Byrne, P. Maini, A cellular automaton model for tumour growth in inhomogeneous environment, Journal of Theoretical Biology 225 (2) (2003) 257–274, ISSN 0022-5193, doi:https://doi.org/10.1016/S0022-5193(03)00244-3.
  * Alber et al. [2003] M. Alber, M. Kiskowski, J. Glazier, Y. Jiang, On cellular automaton approaches to modeling biological cells, in: J. Rosenthal, D. Gilliam (Eds.), Mathematical Systems Theory in Biology, Communications, Computation, and Finance, vol. 134 of _IMA Volumes in Mathematics and its Applications_ , Inst Math & Its Appl, ISBN 0-387-40319-1, 1–39, 15th International Symposium on Mathematical Theory of Networks and Systems (MTNS), Univ. Notre Dame, Notre Dame, IN, AUG 12-16, 2002, 2003\.
  * Albert and Barabasi [2000] R. Albert, A. L. Barabasi, Topology of evolving networks: Local events and universality, Physical Review Letters 85 (24) (2000) 5234–5237, ISSN 0031-9007, doi:10.1103/PhysRevLett.85.5234.
  * Alexandridis et al. [2011] A. Alexandridis, L. Russo, D. Vakalis, G. V. Bafas, C. I. Siettos, Wildland fire spread modelling using cellular automata: evolution in large-scale spatially heterogeneous environments under fire suppression tactics, International Journal of Wildland Fire 20 (5) (2011) 633–647.
  * Alonso-Sanz [2003] R. Alonso-Sanz, Reversible cellular automata with memory: two-dimensional patterns from a single site seed, Physica D - Nonlinear Phenomena 175 (1-2) (2003) 1–30, ISSN 0167-2789, doi:10.1016/S0167-2789(02)00693-0.
  * Alonso-Sanz [2008] R. Alonso-Sanz, Cellular automata with memory, vol. 3, Archives contemporaines, 2008.
  * Alonso-Sanz [2009] R. Alonso-Sanz, Cellular Automata with Memory, in: Encyclopedia of Complexity and Systems Science, Springer New York, 823–848, 2009\.
  * Alonso-Sanz [2013] R. Alonso-Sanz, Cellular Automata with Memory and the Density Classification Task, Journal of Cellular Automata 8 (2013) 283–297, ISSN 1557-5969.
  * Alonso-Sanz et al. [2003] R. Alonso-Sanz, M. Martín, R. Kamimura, M. N. Szilagyi, J. R. Weimar, Elementary Cellular Automata with Memory, Complex Systems 14 (2).
  * Andrecut [2000] M. Andrecut, 1/f noise in the “game of life”’, Modern Physics Letters B 14 (2) (2000) 53–57, ISSN 0217-9849, doi:10.1142/S0217984900000094.
  * Aracena et al. [2009] J. Aracena, E. Goles, A. Moreira, L. Salinas, On the robustness of update schedules in Boolean networks, Biosystems 97 (1) (2009) 1–8, ISSN 0303-2647, doi:https://doi.org/10.1016/j.biosystems.2009.03.006.
  * Arrighi [2019] P. Arrighi, An overview of quantum cellular automata, Natural Computing 18 (4) (2019) 885–899, ISSN 1572-9796, doi:10.1007/s11047-019-09762-6.
  * Arrighi et al. [2013] P. Arrighi, N. Schabanel, G. Theyssier, Stochastic Cellular Automata: Correlations, Decidability and Simulations, Fundamenta Informaticae 126 (2-3) (2013) 121–156, ISSN 0169-2968, doi:10.3233/FI-2013-875.
  * Baetens and De Baets [2013] J. Baetens, B. De Baets, Topology-induced phase transitions in totalistic cellular automata, Physica D: Nonlinear Phenomena 249 (2013) 16–24, ISSN 01672789, doi:10.1016/j.physd.2013.01.004.
  * Baetens and De Baets [2010] J. M. Baetens, B. De Baets, Continuous cellular automata on irregular tessellations: Mimicking steady-state heat flow, in: 2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC), 53–59, doi:10.1109/NABIC.2010.5716301, 2010\.
  * Baetens and De Baets [2011] J. M. Baetens, B. De Baets, On the topological sensitivity of cellular automata, Chaos: An Interdisciplinary Journal of Nonlinear Science 21 (2) (2011) 23108, ISSN 1054-1500, doi:10.1063/1.3535581.
  * Baetens and De Baets [2012] J. M. Baetens, B. De Baets, Cellular automata on irregular tessellations, Dynamical Systems-An International Journal 27 (4) (2012) 411–430, ISSN 1468-9367, doi:10.1080/14689367.2012.711300.
  * Baetens and De Baets [2014] J. M. Baetens, B. De Baets, Towards a Comprehensive Understanding of Multi-state Cellular Automata, in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8751, Springer Verlag, 16–24, doi:10.1007/978-3-319-11520-7_3, 2014.
  * Baetens and Gravner [2018] J. M. Baetens, J. Gravner, Introducing Lyapunov profiles of cellular automata, Journal of Cellular Automata 13 (3) (2018) 267–286, ISSN 1557-5969.
  * Baetens et al. [2017] J. M. Baetens, W. Van der Meeren, B. De Baets, On the dynamics of stochastic elementary cellular automata, Journal of Cellular Automata 12 (1-2) (2017) 63–80, ISSN 1557-5969.
  * Baetens et al. [2012] J. M. Baetens, P. Van Der Weeën, B. De Baets, Effect of asynchronous updating on the stability of cellular automata, Chaos, Solitons and Fractals 45 (4) (2012) 383–394, ISSN 09600779, doi:10.1016/j.chaos.2012.01.002.
  * Balzter et al. [1998] H. Balzter, P. Braun, W. Kohler, Cellular automata models for vegetation dynamics, ECOLOGICAL MODELLING 107 (2-3) (1998) 113–125, ISSN 0304-3800, doi:10.1016/S0304-3800(97)00202-0.
  * Bandini et al. [2012] S. Bandini, A. Bonomi, G. Vizzari, An Analysis of Different Types and Effects of Asynchronicity in Cellular Automata Update Schemes, Natural Computing: An International Journal 11 (2) (2012) 277–287, ISSN 1567-7818, doi:10.1007/s11047-012-9310-4.
  * Bartolozzi and Thomas [2004] M. Bartolozzi, A. W. Thomas, Stochastic cellular automata model for stock market dynamics, Physical Review E 69 (4), ISSN 1539-3755, doi:10.1103/PhysRevE.69.046112.
  * Bays [2009] C. Bays, Cellular Automata in Triangular, Pentagonal and Hexagonal Tessellations, in: R. A. Meyers (Ed.), Encyclopedia of Complexity and Systems Science, Springer New York, New York, NY, ISBN 978-0-387-30440-3, 892–900, doi:10.1007/978-0-387-30440-3_58, 2009.
  * Berlekamp et al. [1982] E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, vol. 1, Academic Press London, 1982.
  * Bersini and Detours [1994] H. Bersini, V. Detours, Asynchrony induces stability in cellular automata based models, in: Artificial life IV, MIT Press, MA, 382–387, 1994\.
  * Betel and Flocchini [2011] H. Betel, P. Flocchini, On the Relationship between Fuzzy and Boolean Cellular Automata, Theor. Comput. Sci. 412 (8–10) (2011) 703–713, ISSN 0304-3975, doi:10.1016/j.tcs.2010.11.006.
  * Bezbradica et al. [2014] M. Bezbradica, H. J. Ruskin, M. Crane, Comparative analysis of asynchronous cellular automata in stochastic pharmaceutical modelling, JOURNAL OF COMPUTATIONAL SCIENCE 5 (5) (2014) 834–840, ISSN 1877-7503, doi:10.1016/j.jocs.2014.04.010.
  * Bhattacharjee and Das [2016] K. Bhattacharjee, S. Das, Reversibility of d-state finite cellular automata, Journal of Cellular Automata 11 (2-3) (2016) 213–245.
  * Bhattacharjee et al. [2020] K. Bhattacharjee, N. Naskar, S. Roy, S. Das, A survey of cellular automata: types, dynamics, non-uniformity and applications, Natural Computing 19 (2) (2020) 433–461, ISSN 1572-9796, doi:10.1007/s11047-018-9696-8.
  * Bhattacharjee et al. [2017] K. Bhattacharjee, D. Paul, S. Das, Pseudo-random number generation using a 3-state cellular automaton, International Journal of Modern Physics C 28 (06) (2017) 1750078, ISSN 0129-1831, doi:10.1142/S0129183117500784.
  * Biafore [1994] M. Biafore, Cellular-Automata For Nanometer-Scale Computation, Physica D 70 (4) (1994) 415–433, ISSN 0167-2789, doi:10.1016/0167-2789(94)90075-2.
  * Billings and Yang [2003] S. A. Billings, Y. X. Yang, Identification of probabilistic cellular automata, IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics 33 (2) (2003) 225–236, ISSN 1083-4419, doi:10.1109/TSMCB.2003.810437.
  * Binder [1993] P. M. Binder, A phase diagram for elementary cellular automata, Complex Systems 7 (3) (1993) 241\.
  * Blanchard et al. [2005] F. Blanchard, J. Cervelle, E. Formenti, Some results about the chaotic behavior of cellular automata, Theoretical Computer Science 349 (3) (2005) 318–336, ISSN 0304-3975, doi:https://doi.org/10.1016/j.tcs.2005.06.038.
  * Boccara and Roger [1999] N. Boccara, M. Roger, Totalistic two-dimensional cellular automata exhibiting global periodic behavior, INTERNATIONAL JOURNAL OF MODERN PHYSICS C 10 (6) (1999) 1017–1024, ISSN 0129-1831, doi:%****␣ca-taxonomy-review_elsevier-formatted.bbl␣Line␣425␣****10.1142/S0129183199000814.
  * Boghosian [1999] B. M. Boghosian, Lattice gases and cellular automata, Future Generation Computer Systems 16 (2) (1999) 171–185, ISSN 0167-739X, doi:https://doi.org/10.1016/S0167-739X(99)00045-X.
  * Bonchev et al. [2010] D. Bonchev, S. Thomas, A. Apte, L. B. Kier, Cellular automata modelling of biomolecular networks dynamics, SAR and QSAR in Environmental Research 21 (1-2) (2010) 77–102, ISSN 1062-936X, doi:10.1080/10629360903568580.
  * Bouré et al. [2012] O. Bouré, N. Fatès, V. Chevrier, Probing robustness of cellular automata through variations of asynchronous updating, Natural Computing 11 (4) (2012) 553–564, ISSN 1572-9796, doi:10.1007/s11047-012-9340-y.
  * Buca et al. [2021] B. Buca, K. Klobas, T. Prosen, Rule 54: exactly solvable model of nonequilibrium statistical mechanics, Journal of Statistical Mechanics-Theory and Experiment 2021 (7), ISSN 1742-5468, doi:10.1088/1742-5468/ac096b.
  * Bunimovich [2005] L. A. Bunimovich, Coupled map lattices: at the age of maturity, 2005.
  * Burks [1970] A. W. Burks, Essays on cellular automata, Urbana (Ill.) : University of Illinois press, ISBN 0252000234, 1970.
  * Buschmann et al. [2023] C. Buschmann, H. Böhner, N. Röder, The cost of stabilising the German lapwing population: A bioeconomic study on lapwing population development and distribution using a cellular automaton, Journal for Nature Conservation 71, ISSN 1617-1381, doi:10.1016/j.jnc.2022.126314.
  * Bušić et al. [2013] A. Bušić, J. Mairesse, I. Marcovici, Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling, Advances in Applied Probability 45 (4) (2013) 960–980, ISSN 0001-8678, doi:DOI:10.1239/aap/1386857853.
  * Butler [1974] J. T. Butler, A note on cellular automata simulations, Information and Control 26 (3) (1974) 286–295, ISSN 0019-9958, doi:10.1016/S0019-9958(74)91409-0.
  * Cagigas-Muñiz et al. [2022] D. Cagigas-Muñiz, F. Diaz-del Rio, J. L. Sevillano-Ramos, J.-L. Guisado-Lizar, Efficient simulation execution of cellular automata on GPU, Simulation Modelling Practice and Theory 118 (2022) 102519, ISSN 1569-190X, doi:https://doi.org/10.1016/j.simpat.2022.102519.
  * Caracciolo et al. [2014] D. Caracciolo, L. V. Noto, E. Istanbulluoglu, S. Fatichi, X. C. Zhou, Climate change and Ecotone boundaries: Insights from a cellular automata ecohydrology model in a Mediterranean catchment with topography controlled vegetation patterns, ADVANCES IN WATER RESOURCES 73 (2014) 159–175, ISSN 0309-1708, doi:10.1016/j.advwatres.2014.08.001.
  * Cattaneo et al. [2009] G. Cattaneo, A. Dennunzio, E. Formenti, J. Provillard, Non-Uniform Cellular Automata, in: LATA 2009: Language and Automata Theory and Applications, ISBN 978-3-642-00981-5, 1–12, doi:10.1007/978-3-642-00982-2_26, 2009\.
  * Cattaneo et al. [1997] G. Cattaneo, P. Flocchini, G. Mauri, C. Vogliotti, N. Santoro, Cellular automata in fuzzy backgrounds, Physica D: Nonlinear Phenomena 105 (1) (1997) 105–120, ISSN 0167-2789, doi:https://doi.org/10.1016/S0167-2789(96)00233-3.
  * Cavalcante et al. [2021] A. L. B. Cavalcante, L. P. D. Borges, M. A. D. Lemos, M. M. De Farias, H. S. Carvalho, Modelling the spread of covid-19 in the capital of Brazil using numerical solution and cellular automata, Computational Biology and Chemistry 94, ISSN 1476-9271, doi:10.1016/j.compbiolchem.2021.107554.
  * Celada and Seiden [1992] F. Celada, P. E. Seiden, A Computer-Model of Cellular Interactions in the Immune-System, Immunoloy Today 13 (2) (1992) 56–62, ISSN 0167-5699, doi:10.1016/0167-5699(92)90135-T.
  * Chai et al. [2020] X. Chai, X. Fu, Z. Gan, Y. Zhang, Y. Lu, Y. Chen, An efficient chaos-based image compression and encryption scheme using block compressive sensing and elementary cellular automata, Neural Computing & Applications 32 (9, SI) (2020) 4961–4988, ISSN 0941-0643, doi:10.1007/s00521-018-3913-3.
  * Chakraborty et al. [2022] A. Chakraborty, S. Sikder, H. Omrani, J. Teller, Cellular Automata in Modeling and Predicting Urban Densification: Revisiting the Literature since 1971, Land 11 (7), ISSN 2073-445X, doi:10.3390/land11071113.
  * Chan et al. [1995] T. C. Chan, H. F. Chau, K. S. Cheng, Cellular-Automaton Model For Diffuse and Dissipative Systems, Physical Review E 51 (4) (1995) 3045–3051, ISSN 1063-651X, doi:10.1103/PhysRevE.51.3045.
  * Chopard and Droz [1991] B. Chopard, M. Droz, Cellular automata model for the diffusion equation, Journal of Statistical Physics 64 (3) (1991) 859–892, ISSN 1572-9613, doi:10.1007/BF01048321.
  * Chopard and Droz [1998] B. Chopard, M. Droz, Cellular Automata Modeling of Physical Systems, Collection Alea-Saclay: Monographs and Texts in Statistical Physics, Cambridge University Press, doi:10.1017/CBO9780511549755, 1998.
  * Cirillo et al. [2021] E. N. M. Cirillo, F. R. Nardi, C. Spitoni, Phase transitions in random mixtures of elementary cellular automata, Physica A–Statistical Mechanics and its Applications 573, ISSN 0378-4371, doi:10.1016/j.physa.2021.125942.
  * Clarke et al. [1994] K. C. Clarke, J. A. Brass, P. J. Riggan, A Cellular-Automaton Model of Wildfire Propagation and Extinction, Photogrammetric Engineering and Remote Sensing 60 (11) (1994) 1355–1367, ISSN 0099-1112.
  * Clarke and Gaydor [1998] K. C. Clarke, L. J. Gaydor, Loose-coupling a cellular automaton model and GIS: long-term urban growth prediction for San Francisco and Washington/Baltimore, International Journal of Geographical Information Science 12 (7) (1998) 699–714, ISSN 1365-8816, doi:10.1080/136588198241617, publisher: Taylor & Francis.
  * Clarke et al. [1997] K. C. Clarke, S. Hoppen, L. Gaydos, A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area, Environment and Planning B-Planning & Design 24 (2) (1997) 247–261, ISSN 0265-8135, doi:10.1068/b240247.
  * Cook [2004] M. Cook, Universality in Elementary Cellular Automata, Complex Systems2 15 (2004) 1–40.
  * Corona-Bermúdez et al. [2022] E. Corona-Bermúdez, J. C. Chimal-Eguía, G. Téllez-Castillo, Cryptographic Services Based on Elementary and Chaotic Cellular Automata, Electronics 11 (4), ISSN 2079-9292, doi:10.3390/electronics11040613.
  * Coulthard and Van De Wiel [2006] T. J. Coulthard, M. J. Van De Wiel, A cellular model of river meandering, Earth Surface Processes and Landforms 31 (1) (2006) 123–132, ISSN 0197-9337, doi:10.1002/esp.1315.
  * Courbage and Kamiński [2006] M. Courbage, B. Kamiński, Space-Time Directional Lyapunov Exponents for Cellular Automata, Journal of Statistical Physics 124 (6) (2006) 1499–1509, ISSN 1572-9613, doi:10.1007/s10955-006-9172-1.
  * Coxe and Reiter [2003] A. M. Coxe, C. A. Reiter, Fuzzy hexagonal automata and snowflakes, Computers & Graphics 27 (3) (2003) 447–454.
  * Culik and Kari [1993] K. Culik, J. Kari, Image Compression Using Weighted Finite Automata, Computers & Graphics 17 (3) (1993) 305–313, ISSN 0097-8493, doi:%****␣ca-taxonomy-review_elsevier-formatted.bbl␣Line␣675␣****10.1016/0097-8493(93)90079-O.
  * Culik et al. [1989] K. Culik, J. Pachl, S. Yu, On the Limit Sets of Cellular Automata, SIAM Journal on Computing 18 (4) (1989) 831–842, doi:10.1137/0218057.
  * Culik and Yu [1988] K. Culik, S. Yu, Undecidability of CA classification schemes, Complex Systems 2 (2) (1988) 177–190.
  * da Mata [2020] A. S. da Mata, Complex Networks: a Mini-review, Brazilian Journal of Physics 50 (5) (2020) 658–672, ISSN 1678-4448, doi:10.1007/s13538-020-00772-9.
  * da Silva and Alves Jr [2005] R. da Silva, N. Alves Jr, Dynamic exponents of a probabilistic three-state cellular automaton, Physica A: Statistical Mechanics and its Applications 350 (2-4) (2005) 263–276.
  * Dai et al. [2021] J. D. Dai, C. Zhai, J. L. Ai, J. Y. Ma, J. D. Wang, W. Sun, Modeling the Spread of Epidemics Based on Cellular Automata, Processes 9 (1), ISSN 2227-9717, doi:10.3390/pr9010055.
  * Darabos et al. [2007] C. Darabos, M. Giacobini, M. Tomassini, Performance and robustness of cellular automata computation on irregular networks, Advances in Complex Systems 10 (supp01) (2007) 85–110, doi:10.1142/s0219525907001124.
  * Das et al. [1994] R. Das, M. Mitchell, J. P. Crutchfield, A genetic algorithm discovers particle-based computation in cellular automata, in: Parallel Problem Solving from Nature — PPSN III, Springer Berlin Heidelberg, 344–353, doi:10.1007/3-540-58484-6_278, 1994.
  * Das et al. [2009] S. Das, S. Mukherjee, N. Naskar, B. K. Sikdar, Characterization of Single Cycle CA and its Application in Pattern Classification, Electronic Notes in Theoretical Computer Science 252 (2009) 181–203, ISSN 1571-0661, doi:https://doi.org/10.1016/j.entcs.2009.09.021.
  * de Oliveira et al. [2000] G. M. B. de Oliveira, P. P. Balbi, N. Omar, Guidelines for dynamics-based parameterization of one-dimensional cellular automata rule spaces, Complexity 6 (2) (2000) 63–71, ISSN 1076-2787, doi:10.1002/cplx.1021.
  * del Rey [2015] A. M. del Rey, Mathematical modeling of the propagation of malware: a review, Security and Communications Networks 8 (15) (2015) 2561–2579, ISSN 1939-0114, doi:10.1002/sec.1186.
  * Delacourt and Hellouin de Menibus [2017] M. Delacourt, B. Hellouin de Menibus, Characterisation of Limit Measures of Higher-Dimensional Cellular Automata, Theory of Computing Systems 61 (4) (2017) 1178–1213, ISSN 1433-0490, doi:10.1007/s00224-017-9753-1.
  * Dennunzio et al. [2013a] A. Dennunzio, P. Di Lena, E. Formenti, L. Margara, Periodic Orbits and Dynamical Complexity in Cellular Automata, Fundamenta Informaticae 126 (2013a) 183–199, doi:10.3233/FI-2013-877.
  * Dennunzio et al. [2013b] A. Dennunzio, E. Formenti, L. Manzoni, G. Mauri, m-Asynchronous cellular automata: from fairness to quasi-fairness, Natural Computing 12 (4) (2013b) 561–572, ISSN 1572-9796, doi:10.1007/s11047-013-9386-5.
  * Dennunzio et al. [2012] A. Dennunzio, E. Formenti, J. Provillard, Non-uniform cellular automata: Classes, dynamics, and decidability, Information and Computation 215 (2012) 32–46, ISSN 0890-5401, doi:https://doi.org/10.1016/j.ic.2012.02.008.
  * Dennunzio et al. [2013c] A. Dennunzio, E. Formenti, J. Provillard, Local Rule Distributions, Language Complexity and Non-Uniform Cellular Automata, Theor. Comput. Sci. 504 (2013c) 38–51, ISSN 0304-3975, doi:10.1016/j.tcs.2012.05.013, publisher: Elsevier Science Publishers Ltd. Place: GBR.
  * Dennunzio et al. [2014a] A. Dennunzio, E. Formenti, J. Provillard, Three research directions in non-uniform cellular automata, Theoretical Computer Science 559 (2014a) 73–90, ISSN 0304-3975, doi:https://doi.org/10.1016/j.tcs.2014.06.046.
  * Dennunzio et al. [2014b] A. Dennunzio, E. Formenti, M. Weiss, Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues, Theoretical Computer Science 516 (2014b) 40–59, ISSN 0304-3975, doi:https://doi.org/10.1016/j.tcs.2013.11.005.