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 11-dimensional spacetimes to 4-dimensional 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 shift-invariant and positive rate probabilistic cellular automata (PCA) on rooted d-regular 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 space-time 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 non-ergodicity of our PCA on d-ary 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 one-dimensional nonequilibrium interacting particle systems are capable of displaying phase transitions and, as a by-product, 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 four-state cellular automaton with three absorbing states---only 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 ergodic-nonergodic 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 many-body 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 birth-and-death chains and Galton-Watson 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 stack-sortable 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 Moore-Myhill Garden of Eden theorem.

Motivated by multi-hop communication in unreliable wireless networks, we present a percolation theory for time-varying 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 multi-hop paths on an effective two-state Markov process. We show analytically how this Markov process converges towards a memory-less 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 cyber-physical systems such as self-organized 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 real-life phenomena. Classically, CAs are uniform. However, non-uniformity 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 non-uniformity in CAs and especially to non-uniform elementary CAs, which have been very useful in solving several real-life 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 short-time 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 long-term persistence of infection. Further we demonstrate that when the range of influence of an infected individual is wider, one obtains lower persistent infection. This counter-intuitive observation can also be understood through the relation of synchronization to infection burn-out.

The method of choice to study one-dimensional 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 short-term 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 "freezing-order". 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 freezing-order (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 non--redundant 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 finite-size effects in the geometric Galton-Watson branching process. This is possible because of an exact mapping between one-dimensional random walks and geometric branching processes, known as the Harris walk. In this way, first-passage 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 non-percolating trees. In fact, both systems display a second-order 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 finite-size scaling laws.

Gauge-invariance is a fundamental concept in physics---known 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 step-by-step 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, fault-tolerant (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 non-deterministic 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 parameter-free model-based 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, space-time 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 statistical-oriented techniques that otherwise would lack model inference capabilities.

We study the asymptotic behaviour of symbolic computing systems, notably one-dimensional 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 ultra-discretization 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 ultra-discretization. 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 Nagel-Schreckenberg 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 finite-size 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 (p-p_{c})^{\alpha}$, whereas on quasiperiod lattices it follows a logarithmic law as $v \sim \ln(p-p_{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 single-lane 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 finite-difference approximation of this acoustic-type 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 three-dimensional extension of LtL. In this paper, we show a radius-4 three-dimensional LtL rule is a candidate for weakly universal one.