Asynchronous Cellular Automata
Latest version View entry history
 2 Citations
 205 Downloads
Keywords
Asynchronous Cellular Automata Synchrony Rate Dennunzio Asynchronous Update Shift RuleGlossary
 Configurations

These objects represent the global state of the cellular automaton under study. The set of configurations is denoted by Q ^{ℒ}, where Q is the set of states of the cells and ℒ is the space of cells. In this text, we mainly consider finite configurations with periodic boundary conditions. In one dimension, we use ℒ = ℤ/nℤ, the class of equivalence of integers modulo n.
 Convergence

When started from a given initial condition, the system evolves until it attains a set of configurations from which it will not escape. It is a difficult problem to know in general what are the properties of these attractive sets and how long it takes for the system to attain them. In this text, we are particularly interested in the case where these sets are limited to a single configuration, that is, when the system converges to a fixed point. Fixed points play a special role in the theory of asynchronous cellular automata because synchronous and (classical) asynchronous models have the same set of fixed points. In some cases, reaching a fixed point can be interpreted as the end of a randomized computation.
 De Bruijn graph (or diagram)

This is an oriented graph which allows one to represent all the overlaps of length n − 1 in words of length n. This graph is used to find some elementary properties of the convergence of asynchronous CA, in particular to determine the set of fixed points of a rule.
 Elementary cellular automata

There are 256 onedimensional binary rules defined with nearestneighbor interactions; an update sets a cell state to a value that depends only on its three inputs – its own state and the states of its left and right neighbors. Using the symmetries that exchange 0 s and 1 s and left and right, these rules reduce to 88 equivalence classes.
 Game of Life

This cellular automaton was invented by Conway in 1970. It is probably the most famous rule, and it has been shown that it can simulate a universal Turing machine. The behavior of this rule shows interesting phenomena when it is updated asynchronously.
 Markov chain

A stochastic process that does not keep memory of the past; the next state of the system depends only on the current state of the system.
 Reversibility

When the system always return to its initial condition, we say that it is reversible or, more properly speaking, that it is recurrent. Various interpretations of the notion of reversibility can be given in the context of probabilistic cellular automata.
 Updating scheme

The function that decides which cells are updated at each time step. In this text, we focus on probabilistic updating schemes. Our cellular automata are thus particular cases of probabilistic cellular automata or interacting particle systems.
Article Outline
This text is intended as an introduction to the topic of asynchronous cellular automata and is presented as a path. We start from the simple example of the Game of Life and examine what happens to this model when it is made asynchronous (section “Introduction”). We then formulate our definitions and objectives to give a mathematical description of our topic (section “Defining Asynchrony in the Cellular Models”). Our journey starts with the examination of the shift rule with fully asynchronous updating, and from this simple example, we will progressively explore more and more rules and gain insights on the behavior of the simplest rules (section “Convergence Properties of Simple Binary Rules”). As we will meet some obstacles in having a full analytical description of the asynchronous behavior of these rules, we will turn our attention to the descriptions offered by statistical physics and more specifically to the phase transition phenomena that occur in a wide range of rules (section “Phase Transitions Induced by αAsynchronous Updating”). To finish this journey, we will discuss the various problems linked to the question of asynchrony (section “Other Questions Related to the Dynamics”) and present some openings for the readers who wish to go further (section “Openings”).
Definition of the Subject
This article is mainly concerned with asynchronous cellular automata viewed as discrete dynamical systems. The question is to know, given a local rule, how the cellular automaton evolves if this local rule is applied to only a fraction of the cells. We are mainly interested in stochastic systems, that is, we consider that the updating schemes, the functions which select the cells to be updated, are defined with random variables. Even if there exists a wide range of results obtained with numerical simulations, we focus our discussion on the analytical approaches as we believe that the analytical results, although limited to a small class of rules, can serve as a basis for constructing a more general theory. Naturally, this is a partial view on the topic, and there are other approaches to asynchronous cellular automata. In particular, such systems can be viewed as parallel models of computation (see Th. Worsch’s article in this encyclopedia) or as models of reallife systems. Readers who wish to extend their knowledge may refer to our survey paper for a wider scope on this topic (Fatès 2014a).
Introduction
Cellular automata were invented by von Neumann and Ulam in the 1950s to study the problem of making artificial selfreproducing machines (Moore 1962). In order to imitate the behavior of living organisms, the design of such machines involved the use of a grid where the nodes, called the cells, would evolve according to a simple recursive rule. The model employs a unique rule, which is applied to all the cells simultaneously: this rule represents the “physics” of this abstract universe. The rule is said to be local in the sense that each cell can only see some subset of cells located at short distance: these cells form its neighborhood. In von Neumann’s original construction, all the cells are updated at each time step, and this basis has been adopted in the great majority of the cellular automata constructions. This hypothesis of a perfect parallelism is quite practical as it facilitates the mathematical definition of the cellular automaton and its description with simple rules or tables. However, it is a matter of debate to know if such a hypothesis can be “realistic.” The intervention of an external agent that updates all the components simultaneously somehow contradicts the locality of the model. One may legitimately raise what we could call the nochiefconductor objection: “in Nature, there is no global clock to synchronise the transitions of the elements that compose a system, why should there be one in our models?”
However, this objection alone cannot discard the validity of the classical synchronous models. Instead, one may simply affirm that the nochiefconductor objection raises the question of the robustness of cellular automata models. Indeed, at some point, the hypothesis of perfectly synchronous transitions may seem unrealistic, but we cannot know a priori if its use introduces spurious effects. There are some cases where a given behavior of a cellular automaton will only be seen for the synchronous case, and there are also cases where this behavior remains constant when the updating scheme is changed. In essence, without any information on the system, we have no means to tell what are the consequences of choosing one updating scheme or the other.
If we have a robust model, changes in the updating may only perturb slightly the global behavior of a system. On the contrary, if this modification induces a qualitative change on the dynamics, the model will be called structurally unstable or simply sensitive to the perturbations of its updating Scheme. A central question about cellular automata is thus to know how to assess their degree of robustness to the perturbations of their updating. Naturally, the same questions can be raised about the other hypotheses of the model: the homogeneity of the local rule, the regular topology, the discreteness of states, etc. (see, e.g., Problem 11 in Wolfram (1985)).
A First Experiment
The first observation is that the introduction of a small degree of asynchrony does not modify the qualitative behavior of the rule on the short term. However, one can predict that the longterm behavior of the rule will be perturbed because it is no longer possible to observe cycles. For example, the configuration with only three living cells in a row oscillates in the classical Game of life, but these oscillations only exist with a synchronous updating, and the configuration evolves to a totally different pattern when this perfect simultaneity is broken. Another important property to remark is that the new (asynchronous) system has the same fixed points as the original (synchronous) system. In fact, this is a quite general property that does not depend on the local rule. The reason is simple: if a configuration is a fixed point of the synchronous system, it means that all its cells are stable under the application of the local rule. Hence, if we select a subset of cells for an update, this subset will also be stable. Reciprocally, if any choice of cells gives a stable situation, then the whole system is also stable.
The second important observation regards the evolution with α = 0.5: the global behavior of the system is completely overwhelmed! A new stationary behavior appears, and a pattern which resembles a labyrinth forms. This pattern is stable in some parts and unstable in some other parts of the grid. We will not enter here into the details on how this stability can be quantified, but it is sufficient to observe that, in most cases, this pattern remains for a very long time.
Questions
It may be argued that these observations are not that surprising, because if one modifies the basic definitions of a dynamical system, one naturally expects to see effects on its behavior. However, this statement is only partially true, as this type of radical modifications is not observed for all the rules. In fact, as Nakamura has shown, we can always modify a rule in order to make it insensitive to the variations of its updating scheme (Nakamura 1974, 1981). Formally, this amounts to show that any classical deterministic cellular automaton may be simulated by an asynchronous one. By “simulated” we mean that the knowledge of the evolution of the stochastic asynchronous system allows one to know the evolution of the deterministic original rule with a simple transformation (see Th. Worsch’s article). The idea of Nakamura is that each cell should keep three registers: one with its current state, one with its previous state, and one with a counter that tells if its local time is late, in advance or synchronized with the local time of its neighbors. There is of course an overhead in terms of simulation time and number of states which are used, and one may want to reduce this overhead as much as possible (Lee et al. 2004), but the point is that there are asynchronous rules which will evolve as their synchronous deterministic counterparts. As an extreme example, we can also think of the rule where each cell turns to a given state independently of its neighbor: the global evolution is easily predicted.
Partial robustness can also be observed with some simple rules. For example, let us consider the majority rule: cells take the state that is the most present in their neighborhood. Observing this rule on a twodimensional grid with periodic boundary conditions shows that it is robust to the variations of α: roughly speaking, if we start from a uniform random initial condition, for 0.5 < α < 1, the system seems to always stabilize quickly on a fixed point. For smaller values of α, the only noticeable effect is a slowdown of the converge time. However, a modification also exists at the vicinity of α = 1: like for the Game of Life, as soon as a little asynchrony is present, cycles disappear.
These experiments indicate that there is something about asynchronous systems that deserves to be investigated. Since the first numerical simulations (Buvel and Ingerson 1984), a great number of approaches have been adopted to gain insights on asynchronous cellular automata. However, if we want to be convinced that these systems can be studied and understood theoretically, and despite their randomness, we need some analytical tools. The purpose of the lines that follow is to give a few indications on how the question of asynchrony in cellular automata can be dealt with theoretical tools from computer science and probability theory.
Defining Asynchrony in the Cellular Models
Literally, asynchronous is a word derived from the Ancient Greek ἀσυνχρονος, which simply means “not same time”. From this etymology, it follows that we cannot speak of a single model of asynchrony in cellular automata, but there is an infinity of models. In fact, one is allowed to speak of an asynchronous model as soon as there is some perturbation in the updating process of the cells (Note that asynchrony and asynchronism have been both used in the literature in an equivalent way. We will in general use the former for the modification of the updating and use the latter to designate a topic of research.).We voluntarily stay vague at this point in order to stress that one may imagine a great variety of situations where some irregularity occurs on the way the information is processed by the cells. For instance, we may examine what happens if all the transitions do occur at each time step but where the cells receive the state of their neighbors imperfectly.
In this text, we will restrict our scope to the most simple cases of asynchronous updating.
Mathematical Framework
Let ℒ ∈ ℤ^{ d } be the set of cells that compose a ddimensional cellular automaton. The set of states that each cell may hold is Q. The collection of all states at a given time is called a configuration, and the configuration space is thus Q ^{ℒ}.
Let \( \mathcal{N}\in {\left({\mathrm{\mathbb{Z}}}^d\right)}^k \) be the neighborhood of the cellular automaton, that is, for \( \mathcal{N}=\left({n}_1,\dots, {n}_k\right) \), n _{ i } represents the vector between the central cell and its ith neighbor.
The local function of a cellular automaton is a function f: Q ^{ k } → Q which assigns to a cell c ∈ ℒ its new state q′ = f (q _{1},…, q _{ k }), where the tuple (q _{1},…, q _{ k }) represents the state of the neighbors of a cell c.
Now, to define an asynchronous cellular automaton , we need to introduce an updating scheme. Such a function takes the form \( \mathcal{U}:\mathrm{\mathcal{L}}\to \wp \left(\mathrm{\mathcal{L}}\right) \), where \( \wp (S) \) denotes the parts of S, that is, the set of all subsets of S (also denoted by 2^{ S }). For a given time step t ∈ ℕ, the set of cells that are updated at time t is represented by \( \mathcal{U}(t) \).
The type of function \( \mathcal{U} \) defines the type of asynchronism in use. The first issue of distinction is between deterministic and stochastic (or probabilistic) functions. In this text, we will focus on stochastic functions. Indeed, since asynchronism is often thought of as an unpredictable aspect of the system, stochastic systems have been more intensively studied. One finds only a small number of studies which use deterministic systems. Examples of such studies can be found in Cornforth et al. (2005), Schönfisch and de Roos (1999) where the authors have considered, for example, the effects caused by updating cells sequentially from left to right. As one may expect, such approaches often lead to curious phenomena: the information spreads in a nonnatural way because a single sequence of updates from left to right suffices to change the state of the whole system. More interesting are evenodd updating schemes where one updates the even cells and, in the next step, the odd cells. A famous example of such model is the Q2R model (Vichniac 1984): although the local rule of this system is deterministic, using a random initial condition makes it evolve with the same density as the Ising model (see, e.g., Kari and Taati (2015) for a recent development).
In fact, we can remark that in general it is not difficult to transform an asynchronous system into a synchronous one: in many cases, adding more states is sufficient. For example, for the evenodd updating, we may mark the even and odd cells with a flag up and down, respectively, and make this flag “flip” at each time step. Similarly, an ordered updating may be simulated in a synchronous model by moving a token in a given order. However, such direct transformations are not always possible: for example, Vielhaber has proposed an original way of achieving computation universality by selecting the cells to update (Vielhaber 2013), and this construction cannot be transformed into a deterministic cellular automaton by the mere addition of a few internal states.
Randomness in the Updating
In the case where the updating scheme \( \mathcal{U} \) is a random variable, then the evolution of the system is a stochastic process , and if \( \mathcal{U} \) does not depend on time, it is a Markov chain (a memoryless system). In order to be perfectly rigorous in the formal description of the system, advanced tools from probability theory are necessary. A good example on how to properly use these mathematical objects and their properties can be found in a survey by Mairesse and Marcovici (2014). However, for the sake of simplicity, one may still use the usual notations and consider that the sequences (x ^{ t })_{ t ∈ ℕ} are formed by configurations rather than probability distributions.
 αasynchronous updating scheme: let α ∈ (0, 1] be constant called the synchrony rate. Let \( {\left({\mathrm{\mathcal{B}}}_i^t\right)}_{i\in \mathrm{\mathcal{L}},t\in \mathrm{\mathbb{N}}} \) be a sequence of independent and identically distributed Bernoulli random variables of parameter α. The evolution of the system with an αasynchronous updating scheme is then given by:$$ {x}^0=x\, \mathrm{and}\, \forall i\in \mathrm{\mathbb{Z}},{x}_i^{t+1}=\left\{\begin{array}{ll}f\left({x}_{i+{n}_1}^t,\dots, {x}_{i+{n}_k}^t\right)& \mathrm{if}\;{\mathrm{\mathcal{B}}}_i^t=1,\\ {}{x}_c^t& \mathrm{otherwise}.\end{array}\right. $$
 Fully asynchronous updating scheme: in the case where ℒ is finite, let (S _{ t })_{ t ∈ ℕ} be a sequence of independent and identically distributed random variables that select an element uniformly in ℒ. The evolution of the system is given by:$$ {x}^0=x\, \mathrm{and}\, \forall i\in \mathrm{\mathbb{Z}},{x}_i^{t+1}=\left\{\begin{array}{ll}f\left({x}_{i+{n}_1}^t,\dots, {x}_{i+{n}_k}^t\right)& \mathrm{if}\;i={S}_t,\\ {}{x}_c^t& \mathrm{otherwise}.\end{array}\right. $$
Note that in most cases, authors do not use the indices i and t for \( \left({\mathrm{\mathcal{B}}}_i^t\right) \) or (S _{ t }) and simply consider that there is one function that is used at each time step and for each cell.
We do not enter here into the details of how we can generalize these definitions (see, e.g., Dennunzio et al. (2013)). We point the work of Bouré et al. on asynchronous latticegas cellular automata to underline that adding asynchrony to the cellular models which have more structure than the classical ones can be a nontrivial operation if one wants to maintain the properties of these models (e.g., conservation of the number of particles) (Bouré et al. 2013a). Similar difficulties arise when agents can move on the cellular grid, and one needs to define some procedures to solve the conflicts that may occur when several agents want to modify simultaneously the same cell (Belgacem and Fatès 2012; Chevrier and Fatès 2010).
Convergence Properties of Simple Binary Rules
We have seen that a central question in the study of asynchronous cellular automata was to determine their convergence properties. In particular one may wonder, given a simple binary rule, what we can predict about its possible behavior. Is it converging to a given fixed point? In which time in average? And if so, what kind of “trajectory” the system will follow to attain a stable state (if any)? The lines that follow aim at presenting the mathematical tools to answer these questions.
Expected Convergence Time to a Fixed Point
Recall that one major modification caused by the transformation of a cellular automaton from synchronous to asynchronous updating is the removal of cycles: cycles are replaced by some attractive sets of configurations (see below for a more precise description). Let us examine this property on a simple case. We work on a finite onedimensional system and denote the set of cells by ℒ = ℤ/nℤ, where n is the number of cells. We employ a fully asynchronous updating scheme described by a sequence of independent and identically distributed random variables (S _{ t }) which are uniform on ℒ (one cell is selected at each time step). The local rule depends only on the state of the cell itself and its left and right neighbors; we have \( \mathcal{N} \) = {−1, 0, 1}. Recall that for an initial condition x ∈ Q ^{ℒ}, the evolution of the system is thus described by (x ^{ t })_{ t ∈ ℕ} such that x ^{0} = x and x ^{ t + 1} = F (x ^{ t }) such that \( \forall i\in \mathrm{\mathcal{L}},{x}_i^{t+1}=f\left({x}_{i1}^t,{x}_i^t,{x}_{i+1}^t\right) \) if i = S _{ t } and \( {x}_i^{t+1}={x}_i^t \) otherwise.
To evaluate the converge time of given rule, we proceed as in the theory of computation and define the “time complexity” of this rule as the function which estimates the amount of time taken by the “most expensive” computation of size n (see Th. Worsch’s article in this encyclopedia). Let ℱ denote the set of fixed points of a rule, and let T (x) denote the random variable which represents the time needed to attain a fixed point: T (x) = {min t: x ^{ t } ∈ ℱ}. In order to have a fair comparison with the synchronous update, we consider that one time step corresponds to n updates, and we introduce the rescaled time τ (x) = T (x)/n. The “complexity measure” of a rule is then given by the worst expected convergence time (WECT): \( W\; ECT(n)=\max \left\{\mathbb{E}\left\{\tau (x)\right\};x\in {Q}^{\mathrm{\mathcal{L}}}\right\} \).
Two Notations for ECAs
Notation by transitions. Left, table of transitions and their associated labels. Right, symmetries of the ECA space (see text for explanations)
A  B  C  D 

000  001  100  101 
010  011  110  111 
E  F  G  H 
For example, let us consider the XOR rule f(x, y, z) = x ⊕ y ⊕ z, where ⊕ denotes the usual XOR operator. The decimal code associated to this rule is 150. The active transitions of this rule are 001 → 1 (B), 100 → 1 (C), 011 → 0 (F), and 110 → 0 (G). The four other transitions are passive, that is, they do not change the state of the central cell. We thus obtain the new code: BCFG.
Left, summary of the effect of each transition on a fully asynchronous ECA. Right, summary of the combinations of two (active or inactive) transitions
A  Stability of 0regions  
B  B 01frontiers move left  No A+ no H doubly quiescent rule 
C  10frontiers move right  
D  Absorption of 0regions  B+ F random walk of the 01frontiers 
E  Absorption of 1regions  
F  01frontiers move right  C + G random walk of the 10frontiers 
G  10frontiers move left  
H  Stability of 1regions 
If a rule does not have A (resp. H) in its code, the size of a 0region (resp. a 1region) may increase or decrease by 1, but this region cannot be broken.
Transitions B and F control the movements of the 01frontiers: B (resp. F) moves this frontier to the left (resp. to the right). If both transitions are present, the 01frontier performs a nonbiased random walk.
Similarly, transitions C and G control the movements of the 10frontiers.
Transition D (resp. E) controls the fusion of 1regions (resp. 0regions): the absence of D (resp. E) implies that the 0regions (resp. 1regions) cannot disappear.
These properties are summed up on Table 2, left.
A Starting Example
The solution of this system is T _{ i } = i(n − i)/2ε. Since ε = 1/n, we can write ∀i ∈ {0,…, n}, T _{ i } ≤ n ^{3}/8; in other words, for the configurations with only two zones, the average number of updates needed to attain a fixed point is at most cubic in n.
Martingales
How can we deal with the other configurations? If we start from a configuration x with k 1regions and k > 1, the probability to increase or decrease by 1 the number of 1 s is kϵ. The evolution of the system can no longer be described by the Markov chain in Fig. 4. Indeed, the value ϵ needs to be replaced by ϵ′ = kϵ, but, as k is not constant, this process is no longer a Markov chain. As seen in Fig. 4, the frontiers of the regions will perform random walks until a region disappears, which will make ϵ′ decrease again and so on until we reach one of the two fixed points. In order to determine the convergence time τ (x), one could estimate the average “living time” of a configuration with kregions. However, this is a difficult problem because this living time strongly depends on the size of each region.
It is easier to note that the process (X _{ t }) defined with X _{ t } = x ^{ t }  _{1} is a martingale, that is, a stochastic process whose average value is constant over time. The theory of martingales allows us to find the probability p _{1}(x) to reach the fixed point 1 from x and the average time of convergence \( \mathbb{E}\left\{\tau (x)\right\} \). For the sake of brevity, we skip the details of the mathematical treatments and write down directly the results that are exposed in Fatès et al. (2006a): (a) the probability of reaching the fixed point 1 is still equal to the initial density, p _{ 1 }(x) = x _{1}/n, and (b) the rescaled average time also scales quadratically with \( n:\mathbb{E}\left\{\tau (x)\right\}\le {\leftx\right}_1\left(n{\leftx\right}_1\right)/2 \).
We thus have an upper bound on the WECT which is WECT (n) ≤ n ^{2}/8, and, considering the initial condition x = 0^{ n/2}1^{ n/2}, we obtain the lower bound WECT (n) ≥ n ^{2}/8. We can thus write WECT (n) = \( \mathcal{O} \)(n ^{2}) where \( \mathcal{O} \) expresses the equivalence up to a constant. We thus say that the shift has a quadratic convergence time or, for short, that it is quadratic.
A Relationship with Computational Problems
In fact, since the convergence of the asynchronous shift depends on the initial density, one may consider this process as a particular kind of decentralized computation. For the sake of brevity, we will not develop this point here, but we simply indicate to the readers interested by this issue that similar stochastic rules have been used to solve the density classification problem (see, e.g., (de Oliveira 2014; Fatès 2013b; Fukś 2002) and de Oliveira’s article in this encyclopedia).
From the Shift to Other Quadratic Rules
We now examine step by step how to generalize the example of the asynchronous shift given above to a wider class of rules.
With the decomposition described above, we can readily deduce that the Markov chain described for counting the number of 1 s for the shift rule (BDEG) also applies for rule CG, for which the 10frontier performs a nonbiased random walk and for rule BCDEFG, for which the two frontiers perform a random walk.
In a second time, we can ask what happens if we change the code of these rules by removing the transition D of their code, that is, we set 101 → 0 and make the transition D inactive. This transformation implies that the 0regions can no longer disappear, while the 1regions may disappear if an isolated 1 is updated (010 → 0). As a consequence, the fixed point 1 is no longer reachable, and the system will almost surely converge to the fixed point 0 for an initial condition different from 1. The system will thus most of the time behave as a regular martingale, but sometimes it will “bounce” on an isolated 0. Is the average convergence time still quadratic? The answer is positive: even though the behavior cannot be described (simply) by a martingale, it is possible to “save” the previous results and still obtain a quadratic scaling of the WECT. Interested readers may refer to our study on fully asynchronous doubly quiescent (A quiescent state is a state q such that the local rule f obeys f(q,…, q) = q.) rules for the mathematical details (Fatès et al. 2006a).
Functions with a Potential
Interestingly, a similar type of convergence can also be obtained by adding an active transition to the shift rule. For example, let us consider ECA BDEFG (162). Its evolution is shown in Fig. 6. One should observe that the 01frontiers perform a nonbiased random walk, while the 10frontier tends to move to the left. This means that the 1regions have a tendency to decrease, but their evolution is no longer monotonous as in the case of rule DEG. It can be shown that if we take back the function ϕ(x) = x _{1} + x _{01} and X _{ t } = ϕ(x ^{ t }), then (X _{ t }) is a supermartingale, that is, its average value decreases in average. This property and other conditions ensuring that it cannot stay too “static” imply that its convergence time scales linearly with the ring size n (Fatès et al. 2006a). Indeed, for any configuration that is not a fixed point, the quantity \( \mathbb{E}\left\{{X}^{t+1}{X}^t\left{x}^t\right.\right\} \) is negative. The same method can be applied for showing the convergence in linear time for the rule 130:BEFG.
Nonpolynomial Types of Convergence.
The rules 200:E and 232:DE have a logarithmic WECT. This can be shown with the same techniques as for the convergence of the couponcollector process (Fatès et al. 2006a).
The rule 154:BCEG has an exponential WECT. This comes from a kind of paradox: the rule has a tendency to increase the number of 1 s, but its only fixed point 1 is not reachable. The only way it can converge is by reaching the fixed point 0, a phenomenon that is very unlikely.
The rules 134:BFG, 142:BG, 156:CG, and 150:BCFG are nonconverging. This is because in all these rules, transitions D and E are inactive and, at the same time, the frontiers are not static.
Other Elementary Rules
The question of classifying the other ECA rules, where no state or only one state is quiescent, is still open. Some conjectures have been stated from experimental observations, but they still deserve an indepth analysis (Fatès 2013a). In particular, there are currently only partial results for all the rules which are conjectured to converge “very rapidly,” that is, in logarithmic time (Fatès 2014b).
From Fully Asynchronous to αAsynchronous Updating
The authors developed an interesting analytical framework (potential functions, masks, etc.) and succeeded in giving bounds on the convergence of 19 (minimal) doubly quiescent rules, leaving the question open for five other rules. The various rules show different kinds of scaling relations of the WECT, depending on α and n. If we consider the dependence on n only, the families of functions are the same as those obtained for fully asynchronous dynamics, that is, logarithmic, linear, quadratic, exponential, and infinite. However, there are rules whose type of converge varies from the fully asynchronous updating to αasynchronous updating. For example, rule 152:CEG, which is quadratic with a fully asynchronous updating (see above), becomes linear for αasynchronous updating. Two rules, namely, ECA 146:BCEFG and 178:BCDEFG, were conjectured to display a phase transition: their type of converge may change from polynomial to exponential depending on whether the α is greater or lower than a particular critical value. This property was partially proved by Regnault in a thorough study of ECA 178, where the polynomial and exponential convergence times were formally obtained for extrema values of the synchrony rate (Regnault 2013). Ramos and Leite recently studied a generalization of this model where the asynchronous case appears as a special case of the family of probabilistic cellular automata that are studied (Ramos and Leite 2017).
TwoDimensional Rules
The study of the convergence properties of simple twodimensional rules has been carried out for the socalled totalistic cellular automata , where the local rule only depends on the number of 1 s in the neighborhood (Fatès and Gerin 2009). For the von Neumann neighborhood (the cell and its four nearest neighbors), there are 2^{6} such rules. Their WECT were also analyzed for the fully asynchronous updating, and all rules but one was found to fall into the previous classes of convergence. One remarkable exception was given by the epidemic rule, where a 0 turns into a 1 if it has a 1 in its neighborhood and then will always remain a 1. This rule has a WECT which scales as \( \varTheta \left(\sqrt{n}\right). \) Even though this scaling property can be intuitively understood from the dynamics of the rule, which merely amounts to “contaminating” neighboring cells, proving the class of convergence was a difficult task. It is only recently that a proof has been proposed by Gerin, who succeeded in applying subtle combinatorial arguments to obtain upper and lower bounds on the time of convergence (Gerin 2017).
The minority rule received a special attention. Indeed, when updated asynchronously, it has the ability to create patterns which can take the form of checkerboard or stripes. The behavior of this rule with an asynchronous updating was analyzed in the case of von Neumann and Moore neighborhood (the cell and its eight nearest neighbors) (Regnault et al. 2009, 2010). Regnault et al. noticed that the convergence to the fixed point was not uniform: the process can be separated in two phases – first the “energy” decreases rapidly, and then the system stays in a lowenergy state where it will progressively approach the fixed point by moving the unstable patterns, thanks to the random fluctuations. It is an open question to know to which extent this type of behavior can be found in other contexts, e.g., latticegas cellular automata (Bouré et al. 2013b).
The convergence properties can thus be determined quite precisely but only for a family of simple binary cellular automata rules. It is an open problem to find such analytical tools. As far as the αasynchronous updating is concerned, the results are even more restricted. As we will see in the following, this is not so surprising because the behavior of some rules sometimes requires the introduction of tools from advanced statistical physics.
Phase Transitions Induced by αAsynchronous Updating
The Game of Life
We propose to come back to the phenomenon observed in Fig. 1 (see p. 4). Blok and Bergersen were the first authors to give a precise explanation of the change of behavior in the Game of Life, the phenomenon that was described in the introductory part of this article. They identified the existence of a secondorder phase transitio n (Informally, in statistical physics, phase transitions are defined by the existence of a discontinuity in the values taken by a macroscopic parameter, called the order parameter, when system is submitted to a continuous variation of a control parameter. Firstorder transitions are those for which the discontinuity appears directly on the order parameter, while secondorder phase transitions (or continuous phase transitions) are those where the derivative of the order parameter is infinite.) which separates two qualitatively different behaviors: a highdensity steady state with vertical and horizontal stripes and lowdensity steady state with avalanches (Blok and Bergersen 1999). They measured the critical value of the synchrony rate at α _{ c } ≈ 0.906 and showed that near the critical point, the stationary density d _{ ∞ } obeyed a power law of the form d _{ ∞ } ∼ (α − αc)^{ β }. It is well known in the field of statistical physics that the values taken by the power laws are not arbitrary and that various systems of unrelated fields may display the same critical exponents (see F. Bagnoli’s article in this encyclopedia). The class of systems which share the same values of exponents is called a universality class, and in the case of the Game of Life, Blok and Bergersen found that its phase transition was likely to belong to the universality class of directed percolation (also called oriented percolation or Reggeon field theory).
These measures were later confirmed by a set of more precise experiments (Fatès 2010), and the critical value of the synchrony rate was measured at α _{ c } ≈ 0.911. Moreover, for the Game of Life, the critical phenomenon was shown to be robust to the introduction of a small degree of irregularity in the grid. This phase transition was also observed for other lifelike rules (Fatès 2010).
Elementary Cellular Automata
Critical synchrony rates for the ECA with a phase transition
ECA  6  18  26  38  50  58  106  134  146  178 

α _{ c }  0.283  0.714  0.475  0.041  0.628  0.340  0.815  0.082  0.675  0.410 
Other Questions Related to the Dynamics
In order to broaden our view of asynchronous cellular automata, we now briefly mention some other problems which have been studied with analytical tools.
Reversibility
The question of reversibility amounts to knowing if it is always possible to “go back in time” and to knowing if any configuration has a unique predecessor. This question is undecidable in general, but there are some sets of rules for which one can tell whether a rule is reversible or not (see Morita (2008) for a survey on this question). In the context of random asynchronous updating, the question cannot be transposed in a direct way because the evolution of the system is not one to one (otherwise we would have a deterministic system).
To date, two different approaches have been considered for finite systems. Wacker and Worsch proposed to examine the transition graph of the Markov chain of the asynchronous system (Wacker and Worsch 2013). A rule is said to be phasespace invertible if there exists another rule – possibly itself – whose transition graph is the “inverse” of the graph of the original rule. By “inverse” it is meant that the directions of the transitions are reversed. In other words, the probabilities to go from x to y are identical if one permutes x and y. Interestingly, the authors show that the property of being phasespace invertible is decidable for onedimensional fully asynchronous cellular automata.
Wolfram codes and transition codes of the 16 recurrent rules (From Fatès et al. (2017)). The two separate rules are recurrent for n ≠ 3
35:ABDEFGH  38:BDFGH  43:ABDEGH  46:BDGH 
51:ABCDEFGH  54:BCDFGH  57:ACDEGH  60:CDGH 
62:BCDGH  105:ADEH  108:DH  134:BFG 
142:BG  150:BCFG  156:CG  204:I 
33:ADEFGH  41:ADEGH 
These results are encouraging, and it is rather pleasant to note that contrarily to the problem of convergence seen above, deciding the recurrence properties of an ECA can be achieved. It is thus interesting to see to which extent these results apply to a broader class of systems, including infinitesize systems.
Coalescence
Rouquier and Morvan have studied experimentally this phenomenon for the 88 ECA with αasynchronous updating (Rouquier and Morvan 2009). They discovered an unexpected richness of behavior: some rules coalesce rapidly and others slowly, some never coalesce, some even display phase transitions, etc. Insights have been given by Francès de Mas on this question, and a classification of the convergence time has been given from both the observation of spacetime diagrams and an analysis of the behavior (de Mas 2017). It is still an open question to provide a complete mathematical analysis of these systems and to issue a proof that coalescence can indeed happen in a linear time with respect to the ring size.
Other Problems
There are many other problems which have led to various interesting experimental or theoretical works. For instance, Gacs (2001) and then MacAuley and Mortveit (2010, 2013; Macauley et al. 2008) have provided a deep analysis on the independence of the trajectories of an asynchronous with regard to the updating sequence. Chassaing and Gerin analyzed the scaling relationships that would lead to an infinitesize continuous framework (Chassaing and Gerin 2007). This framework is also analyzed in detail by Dennunzio et al., who examined how the theory of measure can be applied to onedimensional systems defined on an infinite line (Dennunzio et al. 2013, 2017).
As an example of a possible application of the use of these dynamical systems, we mention the work of Das et al., who proposed to use such models for pattern classification (Sethi et al. 2016), and the work of Takada et al., who designed asynchronous selfreproducing loops (Takada et al. 2007a). These are only some entry point to the literature on this topic, and we refer again to our survey paper for a wider scope (Fatès 2014a).
Openings
We have seen that the randomness involved in the asynchronous updating create an amazing source of new questions on cellular automata. After more than two decades of continued efforts, this topic shows signs of maturity, and although it remains in large part a terra incognita, there are some insights on how asynchronous cellular automata can be studied with a theoretical point of view. A set of analytical tools are now available, and when the analysis fails to answer all the questions, one can carry out numerical simulations. Readers should now be convinced that asynchronous cellular automata are by no means some “exotic” mathematical objects but constitute a thriving field of research. The elements we presented here are only a small part of this field and should be completed by a more extensive bibliographical work. Before closing this text, we want to present a few questions that are currently investigated.
Defining Asynchrony
As mentioned in the introduction, asynchrony is a concept that can be defined with a great variety of forms. For example, the notion of αasynchronous updating scheme needs to be generalized to go beyond the simple homogeneous finite case. This has led to propose the use of some measuretheoretic tools to define masynchronous cellular automata to include the cases of nonhomogeneous probabilities of updating, infinitesimal ones, etc. (Dennunzio et al. 2012, 2013).
To complete this point, let us underline that Bouré et al. have proposed to examine the case where the randomness occurs not on the moments of updating but on the possibility to miss the information from one or several neighbors (Bouré et al. 2012). Interestingly, the study of these new updating schemes, named β and γasynchronous updating schemes, shows that their behavior partially overlaps with αasynchronous systems but also reveals some novel and unexpected behaviors (e.g., other rules show a phase transitions).
Asynchronous Models
The theoretical results obtained so far do not tell us what is a good model of asynchrony in general. Since cellular automata are defined with a discrete of time and space, it is not straightforward to decide a priori to use a synchronous updating, or a fully asynchronous one, or a partially synchronous one. In fact, the most reasonable position would be to test various updating schemes on a rule and to examine if it is robust or sensitive to these modifications. Although this critical attitude has been quite rare so far, a good example of such a study has been provided by Grilo and Correia, who made a systematic study of the effects of the updating in the spatially extended evolutionary games. This question rose after the criticisms made by Huberman and Glance (1993) to the model proposed by Nowak and May (1992). We think that exploring more systematically these issues on realworld models could help us understand to which extent the simplifications operated in a model are justified or are a potential source of artifacts (see Fatès (2014a) for other examples).
Experimental Approaches and Theoretical Questions
The questions of how to measure the behavior of asynchronous systems are of course primordial. Among the various approaches, let us mention that Silva and Correia have shown the importance of taking into account the timerescaling effects when using experiments (Silva and Correia 2013). Louis has underlined that the efficiency of a simulation may greatly vary depending on the different regimes that may occur in a simulation (Louis 2015). Recently, Bolt et al. have raised the problem of identification: if one is given spacetime diagrams with missing parts, how can one find the rule which generated this piece of information? (Bolt et al. 2016). (See also A. Adamatzky’s article in this encyclopedia for the general problem of identification.)
New Models of Computation
As mentioned earlier, it is no surprise if the computing abilities of general asynchronous cellular automata are the same as those of their deterministic counterparts. However, as shown by various authors, the question becomes much more delicate if one asks how to simulate an asynchronous system by another asynchronous system or if one wants to design asynchronous systems which hold good computing abilities and use a limited number of states (Takada et al. 2007b; Worsch 2013).
On the technological side, let us mention the work of Silva et al. on modeling the interactions between (static) robots which need to be synchronized (Silva et al. 2015). Lee, Peper, and their collaborators aimed at developing asynchronous circuits which are designed with simple local rules (Peper et al. 2003). Such Brownian cellular automata (Lee and Peper 2008) exploit the inherent fluctuations of the particles to perform asynchronous computations (Lee et al. 2016b; Peper et al. 2010). They represent a potential source of major technical innovations, in particular with the possibility of implementing such circuits with DNA reactiondiffusion systems (Yamashita et al. 2017) or single electron tunneling techniques (Lee et al. 2016a).
CrossReferences
Bibliography
 Belgacem S, Fatès N (2012) Robustness of multiagent models: the example of collaboration between turmites with synchronous and asynchronous updating. Complex Syst 21(3):165–182MathSciNetzbMATHGoogle Scholar
 Blok HJ, Bergersen B (1999) Synchronous versus asynchronous updating in the “game of life”. Phys Rev E 59:3876–3879ADSCrossRefGoogle Scholar
 Bolt W, Wolnik B, Baetens JM, De Baets B (2016) On the identification of αasynchronous cellular automata in the case of partial observations with spatially separated gaps. In: De Tré G, Grzegorzewski P, Kacprzyk J, Owsinski JW, Penczek W, Zadrozny S (eds) Challenging problems and solutions in intelligent systems. Springer, pp 23–36Google Scholar
 Bouré O, Fatès N, Chevrier V (2012) Probing robustness of cellular automata through variations of asynchronous updating. Nat Comput 11:553–564MathSciNetCrossRefzbMATHGoogle Scholar
 Bouré O, Fatès N, Chevrier V (2013a) First steps on asynchronous latticegas models with an application to a swarming rule. Nat Comput 12(4):551–560MathSciNetCrossRefzbMATHGoogle Scholar
 Bouré O, Fatès N, Chevrier V (2013b) A robustness approach to study metastable behaviours in a latticegas model of swarming. In: Kari J, Kutrib M, Malcher A (eds) Proceedings of automata’13, volume 8155 of lecture notes in computer science. Springer, Gießen, Germany, pp 84–97Google Scholar
 Buvel RL, Ingerson TE (1984) Structure in asynchronous cellular automata. Physica D 1:59–68MathSciNetGoogle Scholar
 Chassaing P, Gerin L (2007) Asynchronous cellular automata and brownian motion. In: DMTCS proceedings of AofA’07, volume AH. Juan les Pins, France, pp 385–402Google Scholar
 Chevrier V, Fatès N (2010) How important are updating schemes in multiagent systems? An illustration on a multiturmite model. In: Proceedings of AAMAS ‘10. International Foundation for Autonomous Agents and Multiagent Systems, Richland, pp 533–540Google Scholar
 Cornforth D, Green DG, Newth D (2005) Ordered asynchronous processes in multiagent systems. Physica D 204(1–2):70–82ADSMathSciNetCrossRefGoogle Scholar
 de Mas JF (2017) Coalescence in fully asynchronous elementary cellular automata. Technical report, HAL preprint hal01627454Google Scholar
 de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385MathSciNetzbMATHGoogle Scholar
 Dennunzio A, Formenti E, Manzoni L (2012) Computing issues of asynchronous CA. Fundamenta Informaticae 120(2):165–180MathSciNetzbMATHGoogle Scholar
 Dennunzio A, Formenti E, Manzoni L, Mauri G (2013) masynchronous cellular automata: from fairness to quasifairness. Nat Comput 12(4):561–572MathSciNetCrossRefzbMATHGoogle Scholar
 Dennunzio A, Formenti E, Manzoni L, Mauri G, Porreca AE (2017) Computational complexity of finite asynchronous cellular automata. Theor Comput Sci 664:131–143MathSciNetCrossRefzbMATHGoogle Scholar
 Fatès N (2009) Asynchronism induces second order phase transitions in elementary cellular automata. J Cell Autom 4(1):21–38MathSciNetzbMATHGoogle Scholar
 Fatès N (2010) Does life resist asynchrony? In: Adamatzky A (ed) Game of life cellular automata. Springer, London, pp 257–274CrossRefGoogle Scholar
 Fatès N (2013a) A note on the classification of the most simple asynchronous cellular automata. In: Kari J, Kutrib M, Malcher A (eds) Proceedings of automata’13, volume 8155 of lecture notes in computer science. Springer, Netherlands, pp 31–45. https://doi.org/10.1007/s1104701393892
 Fatès N (2013b) Stochastic cellular automata solutions to the density classification problem – when randomness helps computing. Theory Comput Syst 53(2):223–242MathSciNetCrossRefzbMATHGoogle Scholar
 Fatès N (2014a) A guided tour of asynchronous cellular automata. J Cell Autom 9(5–6):387–416MathSciNetzbMATHGoogle Scholar
 Fatès N (2014b) Quick convergence to a fixed point: a note on asynchronous elementary cellular automata. In: Was J, Sirakoulis GC, Bandini S (eds) Proceedings of ACRI’14, volume 8751 of lecture notes in computer science. Krakow, Poland, Springer, pp 586–595Google Scholar
 Fatès N, Gerin L (2009) Examples of fast and slow convergence of 2D asynchronous cellular systems. Old City Publishing. J Cell Autom 4(4):323–337. http://www.oldcitypublishing.com/journals/jcahome/
 Fatès N, Morvan M (2005) An experimental study of robustness to asynchronism for elementary cellular automata. Complex Syst 16:1–27MathSciNetzbMATHGoogle Scholar
 Fatès N, Morvan M, Schabanel N, Thierry E (2006a) Fully asynchronous behavior of doublequiescent elementary cellular automata. Theor Comput Sci 362:1–16MathSciNetCrossRefzbMATHGoogle Scholar
 Fatès N, Regnault D, Schabanel N, Thierry E (2006b) Asynchronous behavior of doublequiescent elementary cellular automata. In: Correa JR, Hevia A, Kiwi MA (eds) Proceedings of LATIN 2006, volume 3887 of lecture notes in computer science. Valdivia, Chile, Springer, pp 455–466Google Scholar
 Fatès N, Sethi B, Das S (2017) On the reversibility of ecas with fully asynchronous updating: the recurrence point of view. To appear in a monography edited by Andrew Adamatzky – Preprint available on the HAL server, id: hal01571847Google Scholar
 Fukś H (2002) Nondeterministic density classification with diffusive probabilistic cellular automata. Phys Rev E 66(6):066106ADSCrossRefGoogle Scholar
 Fukś H, Fatès N (2015) Local structure approximation as a predictor of secondorder phase transitions in asynchronous cellular automata. Nat Comput 14(4):507–522MathSciNetCrossRefGoogle Scholar
 Gács P (2001) Deterministic computations whose history is independent of the order of asynchronous updating. Technical report – arXiv:cs/0101026Google Scholar
 Gerin L (2017) Epidemic automaton and the eden model: various aspects of robustness. Text to appear in a monography on probabilistic cellular automata. SpringerGoogle Scholar
 Huberman BA, Glance N (1993) Evolutionary games and computer simulations. Proc Natl Acad Sci U S A 90:7716–7718ADSCrossRefzbMATHGoogle Scholar
 Kari J, Taati S (2015) Statistical mechanics of surjective cellular automata. J Stat Phys 160(5):1198–1243ADSMathSciNetCrossRefzbMATHGoogle Scholar
 Lee J, Peper F (2008) On brownian cellular automata. In: Adamatzky A, AlonsoSanz R, Lawniczak AT, Martínez GJ, Morita K, Worsch T (eds) Proceedings of automata 2008. Luniver Press, Frome, pp 278–291Google Scholar
 Lee J, Adachi S, Peper F, Morita K (2004) Asynchronous game of life. Phys D 194(3–4):369–384MathSciNetCrossRefzbMATHGoogle Scholar
 Lee J, Peper F, Cotofana SD, Naruse M, Ohtsu M, Kawazoe T, Takahashi Y, Shimokawa T, Kish LB, Kubota T (2016a) Brownian circuits: designs. Int J Unconv Comput 12(5–6):341–362Google Scholar
 Lee J, Peper F, Leibnitz K, Ping G (2016b) Characterization of random fluctuationbased computation in cellular automata. Inf Sci 352–353:150–166CrossRefGoogle Scholar
 Louis PY (2015) Supercritical probabilistic cellular automata: how effective is the synchronous updating? Nat Comput 14(4):523–534MathSciNetCrossRefGoogle Scholar
 Macauley M, Mortveit HS (2010) Coxeter groups and asynchronous cellular automata. In: Bandini S, Manzoni S, Umeo H, Vizzari G (eds) Proceedings of ACRI’10, volume 6350 of lecture notes in computer science. Springer, Ascoli Piceno, Italy, pp 409–418Google Scholar
 Macauley M, Mortveit HS (2013) An atlas of limit set dynamics for asynchronous elementary cellular automata. Theor Comput Sci 504:26–37. Discrete mathematical structures: from dynamics to complexityMathSciNetCrossRefzbMATHGoogle Scholar
 Macauley M, McCammond J, Mortveit HS (2008) Order independence in asynchronous cellular automata. J Cell Autom 3(1):37–56MathSciNetzbMATHGoogle Scholar
 Mairesse J, Marcovici I (2014) Around probabilistic cellular automata. Theor Comput Sci 559:42–72. Nonuniform cellular automataMathSciNetCrossRefzbMATHGoogle Scholar
 Moore EF (1962) Machine models of selfreproduction. Proc Symp Appl Math 14:17–33. (Reprinted in Essays on cellular automata, Burks AW (ed), University of Illinois Press, 1970)CrossRefzbMATHGoogle Scholar
 Morita K (2008) Reversible computing and cellular automata – a survey. Theor Comput Sci 395(1):101–131MathSciNetCrossRefzbMATHGoogle Scholar
 Nakamura K (1974) Asynchronous cellular automata and their computational ability. Syst Comput Controls 5(5):58–66MathSciNetGoogle Scholar
 Nakamura K (1981) Synchronous to asynchronous transformation of polyautomata. J Comput Syst Sci 23(1):22–37MathSciNetCrossRefzbMATHGoogle Scholar
 Nowak MA, May RM (1992) Evolutionary games and spatial chaos. Nature 359:826–829ADSCrossRefGoogle Scholar
 Peper F, Lee J, Adachi S, Mashiko S (2003) Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers? Nanotechnology 14(4):469ADSCrossRefGoogle Scholar
 Peper F, Lee J, Isokawa T (2010) Brownian cellular automata. J Cell Autom 5(3):185–206MathSciNetzbMATHGoogle Scholar
 Ramos AD, Leite A (2017) Convergence time and phase transition in a nonmonotonic family of probabilistic cellular automata. J Stat Phys 168(3):573–594ADSMathSciNetCrossRefzbMATHGoogle Scholar
 Regnault D (2013) Proof of a phase transition in probabilistic cellular automata. In: Béal MP and Carton O (eds) Proceedings of developments in language theory, volume 7907 of lecture notes in computer science. Springer, MarnelaVallée, France, pp 433–444Google Scholar
 Regnault D, Schabanel N, Thierry E (2009) Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority. Theor Comput Sci 410(47–49):4844–4855MathSciNetCrossRefzbMATHGoogle Scholar
 Regnault D, Schabanel N, Thierry E (2010) On the analysis of “simple” 2d stochastic cellular automata. Discrete Math Theor Comput Sci 12(2):263–294MathSciNetzbMATHGoogle Scholar
 Rouquier JB, Morvan M (2009) Coalescing cellular automata: synchronization by common random source for asynchronous updating. J Cell Autom 4(1):55–78MathSciNetzbMATHGoogle Scholar
 Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. Biosystems 51:123–143CrossRefGoogle Scholar
 Sethi B, Fatès N, Das S (2014) Reversibility of elementary cellular automata under fully asynchronous update. In: Gopal TV, Agrawal M, Li A, Cooper B (eds) Proceedings of TAMC’14, volume 8402 of lecture notes in computer science. Springer, Chennai, India, pp 39–49Google Scholar
 Sethi B, Roy S, Das S (2016) Asynchronous cellular automata and pattern classification. Complexity 21:370–386ADSMathSciNetCrossRefGoogle Scholar
 Silva F, Correia L (2013) An experimental study of noise and asynchrony in elementary cellular automata with sampling compensation. Nat Comput 12(4):573–588MathSciNetCrossRefGoogle Scholar
 Silva F, Correia L, Christensen AL (2015) Modelling synchronisation in multirobot systems with cellular automata: analysis of update methods and topology perturbations. In: Sirakoulis GC, Adamatzky A (eds) Robots and lattice automata, volume 13 of emergence, complexity and computation. Springer International Publishing, Springer. pp 267–293Google Scholar
 Takada Y, Isokawa T, Peper F, Matsui N (2007a) Asynchronous selfreproducing loops with arbitration capability. Phys D Nonlinear Phenom 227(1):26–35ADSMathSciNetCrossRefzbMATHGoogle Scholar
 Takada Y, Isokawa T, Peper F, Matsui N (2007b) Asynchronous selfreproducing loops with arbitration capability. Phys D 227(1):26–35MathSciNetCrossRefzbMATHGoogle Scholar
 Vichniac GY (1984) Simulating physics with cellular automata. Phys D Nonlinear Phenom 10(1):96–116ADSMathSciNetCrossRefzbMATHGoogle Scholar
 Vielhaber M (2013) Computation of functions on n bits by asynchronous clocking of cellular automata. Nat Comput 12(3):307–322MathSciNetCrossRefzbMATHGoogle Scholar
 Wacker S, Worsch T (2013) On completeness and decidability of phase space invertible asynchronous cellular automata. Fundam Informaticae 126(2–3):157–181MathSciNetzbMATHGoogle Scholar
 Wolfram S (1985) Twenty problems in the theory of cellular automata. Phys Scr T9:170ADSMathSciNetCrossRefzbMATHGoogle Scholar
 Worsch T (2013) Towards intrinsically universal asynchronous CA. Nat Comput 12(4):539–550MathSciNetCrossRefzbMATHGoogle Scholar
 Yamashita T, Isokawa T, Peper F, Kawamata I, Hagiya M (2017) Turingcompleteness of asynchronous noncamouflage cellular automata. In: Dennunzio A, Formenti E, Manzoni L, Porreca AE (eds) Proceedings of AUTOMATA 2017, volume 10248 of lecture notes in computer science. Springer, Milan, Italy, pp 187–199Google Scholar