
Complex systems may morph between structures with different dimensionality
and degrees of freedom. As a tool for their modelling, nonlinear embeddings are
introduced that encompass objects with different dimensionality as a continuous
parameter $\kappa \in \mathbb{R}$ is being varied, thus allowing the
unification of vectors, matrices and tensors in single mathematical structures.
This technique is applied to construct warped models in the passage from
supergravity in 10 or 11dimensional spacetimes to 4dimensional ones. We also
show how nonlinear embeddings can be used to connect cellular automata (CAs) to
coupled map lattices (CMLs) and to nonlinear partial differential equations,
deriving a class of nonlinear diffusion equations. Finally, by means of
nonlinear embeddings we introduce CA connections, a class of CMLs that connect
any two arbitrary CAs in the limits $\kappa \to 0$ and $\kappa \to \infty$ of
the embedding.

In this article we study a class of shiftinvariant and positive rate
probabilistic cellular automata (PCA) on rooted dregular trees $\mathbb{T}^d$.
In a first result we extend the results of [10] on trees, namely we prove
that to every stationary measure $\nu$ of the PCA we can associate a spacetime
Gibbs measure $\mu_{\nu}$ on
$\mathbb{Z} \times \mathbb{T}^d$. Under certain assumptions on the dynamics
the converse is also true.
A second result concerns proving sufficient conditions for ergodicity and
nonergodicity of our PCA on dary trees for $d\in \{ 1,2,3\}$ and
characterizing the invariant product Bernoulli measures.

Almost four decades ago, Gacs, Kurdyumov, and Levin introduced three
different cellular automata to investigate whether onedimensional
nonequilibrium interacting particle systems are capable of displaying phase
transitions and, as a byproduct, introduced the density classification problem
(the ability to classify arrays of symbols according to their initial density)
in the cellular automata literature. Their model II became a well known model
in theoretical computer science and statistical mechanics. The other two
models, however, did not receive much attention. Here we characterize the
density classification performance of Gacs, Kurdyumov, and Levin's model IV, a
fourstate cellular automaton with three absorbing statesonly two of which
are attractive, by numerical simulations. We show that model IV compares
well with its sibling model II in the density classification task: the
additional states slow down the convergence to the majority state but confer a
slight advantage in classification performance. We also show that,
unexpectedly, initial states diluted in one of the nonclassifiable states are
more easily classified. The performance of model IV under the influence of
noise was also investigated and we found signs of an ergodicnonergodic phase
transition at some small finite positive level of noise, although the evidences
are not entirely conclusive. We set an upper bound on the critical point for
the transition, if any.

We introduce a novel method of quantum emulation of a classical reversible
cellular automaton. By applying this method to a chaotic cellular automaton,
the obtained quantum manybody system thermalizes while all the energy
eigenstates and eigenvalues are solvable. These explicit solutions allow us to
verify the validity of some scenarios of thermalization to this system. We find
that two leading scenarios, the eigenstate thermalization hypothesis scenario
and the large effective dimension scenario, do not explain thermalization in
this model.

In this paper, we consider the soliton cellular automaton introduced in
[Takahashi 1990] with a random initial configuration. We give multiple
constructions of a Young diagram describing various statistics of the system in
terms of familiar objects like birthanddeath chains and GaltonWatson
forests. Using these ideas, we establish limit theorems showing that if the
first $n$ boxes are occupied independently with probability $p\in(0,1)$, then
the number of solitons is of order $n$ for all $p$, and the length of the
longest soliton is of order $\log n$ for $p<1/2$, order $\sqrt{n}$ for $p=1/2$,
and order $n$ for $p>1/2$. Additionally, we uncover a condensation phenomenon
in the supercritical regime: For each fixed $j\geq 1$, the top $j$ soliton
lengths have the same order as the longest for $p\leq 1/2$, whereas all but the
longest have order at most $\log n$ for $p>1/2$. As an application, we obtain
scaling limits for the lengths of the $k^{\text{th}}$ longest increasing and
decreasing subsequences in a random stacksortable permutation of length $n$ in
terms of random walks and Brownian excursions.

We review topics in the theory of cellular automata and dynamical systems
that are related to the MooreMyhill Garden of Eden theorem.

Motivated by multihop communication in unreliable wireless networks, we
present a percolation theory for timevarying networks. We develop a
renormalization group theory for a prototypical network on a regular grid,
where individual links switch stochastically between active and inactive
states. The question whether a given source node can communicate with a
destination node along paths of active links is equivalent to a percolation
problem. Our theory maps the temporal existence of multihop paths on an
effective twostate Markov process. We show analytically how this Markov
process converges towards a memoryless Bernoulli process as the hop distance
between source and destination node increases. Our work extends classical
percolation theory to the dynamic case and elucidates temporal correlations of
message losses. Quantification of temporal correlations has implications for
the design of wireless communication and control protocols, e.g. in
cyberphysical systems such as selforganized swarms of drones or smart traffic
networks.

Cellular automata (CAs) are dynamical systems which exhibit complex global
behavior from simple local interaction and computation. Since the inception of
cellular automaton (CA) by von Neumann in 1950s, it has attracted the attention
of several researchers over various backgrounds and fields for modelling
different physical, natural as well as reallife phenomena. Classically, CAs
are uniform. However, nonuniformity has also been introduced in update
pattern, lattice structure, neighborhood dependency and local rule. In this
survey, we tour to the various types of CAs introduced till date, the different
characterization tools, the global behaviors of CAs, like universality,
reversibility, dynamics etc. Special attention is given to nonuniformity in
CAs and especially to nonuniform elementary CAs, which have been very useful
in solving several reallife problems.

We explore the emergence of persistent infection in a closed region where the
disease progression of the individuals is given by the SIRS model, with an
individual becoming infected on contact with another infected individual within
a given range. We focus on the role of synchronization in the persistence of
contagion. Our key result is that higher degree of synchronization, both
globally in the population and locally in the neighborhoods, hinders
persistence of infection. Importantly, we find that early shorttime asynchrony
appears to be a consistent precursor to future persistence of infection, and
can potentially provide valuable early warnings for sustained contagion in a
population patch. Thus transient synchronization can help anticipate the
longterm persistence of infection. Further we demonstrate that when the range
of influence of an infected individual is wider, one obtains lower persistent
infection. This counterintuitive observation can also be understood through
the relation of synchronization to infection burnout.

The method of choice to study onedimensional strongly interacting many body
quantum systems is based on matrix product states and operators. Such method
allows to explore the most relevant, and numerically manageable, portion of an
exponentially large space. It also allows to describe accurately correlations
between distant parts of a system, an important ingredient to account for the
context in machine learning tasks. Here we introduce a machine learning model
in which matrix product operators are trained to implement sequence to sequence
prediction, i.e. given a sequence at a time step, it allows one to predict the
next sequence. We then apply our algorithm to cellular automata (for which we
show exact analytical solutions in terms of matrix product operators), and to
nonlinear coupled maps. We show advantages of the proposed algorithm when
compared to conditional random fields and bidirectional long shortterm memory
neural network. To highlight the flexibility of the algorithm, we also show
that it can readily perform classification tasks.

Cellular Automata have been used since their introduction as a discrete tool
of modelization. In many of the physical processes one may modelize thus (such
as bootstrap percolation, forest fire or epidemic propagation models, life
without death, etc), each local change is irreversible. The class of freezing
Cellular Automata (FCA) captures this feature. In a freezing cellular automaton
the states are ordered and the cells can only decrease their state according to
this "freezingorder". We investigate the dynamics of such systems through the
questions of simulation and universality in this class: is there a Freezing
Cellular Automaton (FCA) that is able to simulate any Freezing Cellular
Automata, i.e. an intrinsically universal FCA? We show that the answer to that
question is sensitive to both the number of changes cells are allowed to make,
and geometric features of the space. In dimension 1, there is no universal FCA.
In dimension 2, if either the number of changes is at least 2, or the
neighborhood is Moore, then there are universal FCA. On the other hand, there
is no universal FCA with one change and Von Neumann neighborhood. We also show
that monotonicity of the local rule with respect to the freezingorder (a
common feature of bootstrap percolation) is also an obstacle to universality.

We present modeling strategies that describe the motion and interaction of
groups of pedestrians in obscured spaces. We start off with an approach based
on balance equations in terms of measures and then we exploit the descriptive
power of a probabilistic cellular automaton model. Based on a variation of the
simple symmetric random walk on the square lattice, we test the interplay
between population size and an interpersonal attraction parameter for the
evacuation of confined and darkened spaces. We argue that information overload
and coordination costs associated with information processing in small groups
are two key processes that influence the evacuation rate. Our results show that
substantial computational resources are necessary to compensate for incomplete
information  the more individuals in (information processing) groups the
higher the exit rate for low population size. For simple social systems, it is
likely that the individual representations are not redundant and large group
sizes ensure that this nonredundant information is actually available to a
substantial number of individuals. For complex social systems information
redundancy makes information evaluation and transfer inefficient and, as such,
group size becomes a drawback rather than a benefit. The effect of group sizes
on outgoing fluxes, evacuation times and wall effects are carefully studied
with a Monte Carlo framework accounting also for the presence of an internal
obstacle.

We show that a cellular automaton on a mixing subshift of finite type is a
Von Neumann regular element in the semigroup of cellular automata if and only
if it is split epic onto its image in the category of sofic shifts and block
maps. It follows from [S.T\"orm\"a, 2015] that Von Neumann regularity is
decidable condition, and we decide it for all elementary CA.

We revisit the problem of Brownian diffusion with drift in order to study
finitesize effects in the geometric GaltonWatson branching process. This is
possible because of an exact mapping between onedimensional random walks and
geometric branching processes, known as the Harris walk. In this way,
firstpassage times of Brownian particles are equivalent to sizes of trees in
the branching process (up to a factor of proportionality). Brownian particles
that reach a distant boundary correspond to percolating trees, and those that
do not correspond to nonpercolating trees. In fact, both systems display a
secondorder phase transition between "insulating" and "conducting" phases,
controlled by the drift velocity in the Brownian system. In the limit of large
system size, we obtain exact expressions for the Laplace transforms of the
probability distributions and their first and second moments. These quantities
are also shown to obey finitesize scaling laws.

Gaugeinvariance is a fundamental concept in physicsknown to provide the
mathematical justification for all four fundamental forces. In this paper, we
provide discrete counterparts to the main gauge theoretical concepts, directly
in terms of Cellular Automata. More precisely, we describe a stepbystep
gauging procedure to enforce local symmetries upon a given Cellular Automaton.
We apply it to a simple Reversible Cellular Automaton for concreteness. From a
Computer Science perspective, discretized gauge theories may be applied to
numerical analysis, quantum simulation, faulttolerant (quantum) computation.
From a mathematical perspective, discreteness provides a simple yet rigorous
route straight to the core concepts.

Without loss of generalisation to other systems, including possibly
nondeterministic ones, we demonstrate the application of methods drawn from
algorithmic information dynamics to the characterisation and classification of
emergent and persistent patterns, motifs and colliding particles in Conway's
Game of Life (GoL), a cellular automaton serving as a case study illustrating
the way in which such ideas can be applied to a typical discrete dynamical
system. We explore the issue of local observations of closed systems whose
orbits may appear open because of inaccessibility to the global rules governing
the overall system. We also investigate aspects of symmetry related to
complexity in the distribution of patterns that occur with high frequency in
GoL (which we thus call motifs) and analyse the distribution of these motifs
with a view to tracking the changes in their algorithmic probability over time.
We demonstrate how the tools introduced are an alternative to other computable
measures that are unable to capture changes in emergent structures in evolving
complex systems that are often too small or too subtle to be properly
characterised by methods such as lossless compression and Shannon entropy.

Complex data is usually produced by interacting sources with different
mechanisms. Here we introduce a parameterfree modelbased approach, based upon
the seminal concept of Algorithmic Probability, that decomposes an observation
and signal into its most likely algorithmic generative sources. Our methods use
a causal calculus to infer model representations. We demonstrate the method
ability to distinguish interacting mechanisms and deconvolve them, regardless
of whether the objects produce strings, spacetime evolution diagrams, images
or networks. We numerically test and evaluate our causal separation methods and
find that it can disentangle examples of observations from discrete dynamical
systems, and complex networks. We think that these causal separating techniques
can contribute to tackle the challenge of causation for estimations of better
rooted probability distributions thereby complementing more limited
statisticaloriented techniques that otherwise would lack model inference
capabilities.

We study the asymptotic behaviour of symbolic computing systems, notably
onedimensional cellular automata (CA), in order to ascertain whether and at
what rate the number of complex versus simple rules dominate the rule space for
increasing neighbourhood range and number of symbols (or colours), and how
different behaviour is distributed in the spaces of different cellular automata
formalisms. Using two different measures, Shannon's block entropy and
Kolmogorov complexity, the latter approximated by two different methods
(lossless compressibility and block decomposition), we arrive at the same trend
of larger complex behavioural fractions. We also advance a notion of asymptotic
and limit behaviour for individual rules, both over initial conditions and
runtimes, and we provide a formalisation of Wolfram's classification as a limit
function in terms of Kolmogorov complexity.

In this article, I propose a systematic method for the inverse
ultradiscretization of cell automata using a functionally complete operation.
We derive difference equations for the 256 kinds of elementary cellular
automata(ECA) introduced Wolfram\cite{wolfram} by the proposed means of the
inverse ultradiscretization. We show that the behaviors of ECAs can be
completely reproduced by numerically solving the obtained difference equations.

We present a diagrammatic method to build up sophisticated cellular automata
(CAs) as models of complex physical systems. The diagrams complement the
mathematical approach to CA modeling, whose details are also presented here,
and allow CAs in rule space to be classified according to their hierarchy of
layers. Since the method is valid for any discrete operator and only depends on
the alphabet size, the resulting conclusions, of general validity, apply to CAs
in any dimension or order in time, arbitrary neighborhood ranges and topology.
We provide several examples of the method, illustrating how it can be applied
to the mathematical modeling of the emergence of order out of disorder.
Specifically, we show how the the majority CA rule can be used as a building
block to construct more complex cellular automata in which separate domains
(with substructures having different dynamical properties) are able to emerge
out of disorder and coexist in a stable manner.

This paper considers a single link with traffic light boundary conditions at
both ends, and investigates the traffic evolution over time with various signal
and system configurations. A hydrodynamic model and a modified stochastic
domain wall theory are proposed to describe the local density variation. The
NagelSchreckenberg model (NaSch), an agent based stochastic model, is used as
a benchmark. The hydrodynamic model provides good approximations over short
time scales. The domain wall model is found to reproduce the time evolution of
local densities, in good agreement with the NaSch simulations for both short
and long time scales. A systematic investigation of the impact of network
parameters, including system sizes, cycle lengths, phase splits and signal
offsets, on traffic flows suggests that the stationary flow is dominated by the
boundary with the smaller split. Nevertheless, the signal offset plays an
important role in determining the flow. Analytical expressions of the flow in
relation to those parameters are obtained for the deterministic domain wall
model and match the deterministic NaSch simulations. The analytic results agree
qualitatively with the general stochastic models. When the cycle is
sufficiently short, the stationary state is governed by effective inflow and
outflow rates, and the density profile is approximately linear and independent
of time.

In this paper we perform numerical simulations to study Kauffman cellular
automata (KCA) on quasiperiod lattices. In particular, we investigate phase
transition, magnetic entropy and propagation speed of the damage on these
lattices. Both the critical threshold parameter $p_{c}$ and the critical
exponents are estimated with good precision. In order to investigate the
increase of statistical fluctuations and the onset of chaos in the critical
region of the model, we have also defined a magnetic entropy to these systems.
It is seen that the magnetic entropy behaves in a different way when one passes
from the frozen regime ($p<p_{c}$) to the chaotic regime ($p>p_{c}$). For a
further analysis, the robustness of the propagation of failures is checked by
introducing a quenched site dilution probability $q$ on the lattices. It is
seen that the damage spreading is quite sensitive when a small fraction of the
lattice sites are disconnected. A finitesize scaling analysis is employed to
estimate the critical exponents. From these numerical estimates, we claim that
on both pure ($q=0$) and diluted ($q=0.05$) quasiperiodic lattices, the KCA
model belongs to the same universality class than on square lattices.
Furthermore, with the aim of comparing the dynamical behavior between periodic
and quasiperiodic systems, the propagation speed of the damage is also
calculated for the square lattice assuming the same conditions. It is found
that on square lattices the propagation speed of the damage obeys a power law
as $v\sim (pp_{c})^{\alpha}$, whereas on quasiperiod lattices it follows a
logarithmic law as $v \sim \ln(pp_{c})^\alpha$.

Lagging or halted traffic is bothersome. As such, it is desirable to have a
model that can begin to determine the efficiency of various traffic
standardizations. Our model intended to create a multifaceted realistic
simulation of traffic flow while considering several factors. These factors
included: passing conventions, e.g., right except to pass (REP) rule, system
perturbation caused by insertion of an accident into the system, accessible
number of lanes available with the REP, various human factors such as variation
of individual maximum speed and likelihood to pass. A succession of models were
created from a variation on an existing singlelane traffic model and adding
extra dimensionality to the lattice to include multiple lanes, passing
conventions, stochastic elements for individuality, and queuing rules to
movement algorithms. We found that the REP is an effective means of increasing
the critical density that a system can support. Eliminating human factors and
thereby automating the system, results in a 160% increase in the sustainable
critical density of the system. The number of lanes increases the critical
density of the system, but the maximum efficiency of the speed distribution
remains the same. Excluding system automation, the optimal speed distribution
for drivers maximal speed was found to be Beta(5,5). Accidents in stable
systems can cause small local jams without causing global jams.

We consider the D1Q3 lattice Boltzmann scheme with an acoustic scale for the
simulation of diffusive processes. When the mesh is refined while holding the
diffusivity constant, we first obtain asymptotic convergence. When the mesh
size tends to zero, however, this convergence breaks down in a curious fashion,
and we observe qualitative discrepancies from analytical solutions of the heat
equation. In this work, a new asymptotic analysis is derived to explain this
phenomenon using the Taylor expansion method, and a partial differential
equation of acoustic type is obtained in the asymptotic limit. We show that the
error between the D1Q3 numerical solution and a finitedifference approximation
of this acoustictype partial differential equation tends to zero in the
asymptotic limit. In addition, a wave vector analysis of this asymptotic regime
demonstrates that the dispersion equation has nontrivial complex eigenvalues, a
sign of underlying propagation phenomena, and a portent of the unusual
convergence properties mentioned above.

Larger than Life cellular automaton (LtL) is a class of cellular automata and
is a generalization of the game of Life by extending its neighborhood radius.
We have studied the threedimensional extension of LtL. In this paper, we show
a radius4 threedimensional LtL rule is a candidate for weakly universal one.