Nazim Fatès
email: nazim.fates@inria.fr

A tutorial on Elementary cellular automata with fully asynchronous updating -General properties and convergence dynamics

We present a picture of the convergence properties of the 256 Elementary Cellular Automata under the fully asynchronous updating, that is, when only one cell is updated at each time step. We regroup here the results which have been presented in different articles and expose a full analysis of the behaviour of finite systems with periodic boundary conditions. Our classification relies on the scaling properties of the average convergence time to a fixed point. We observe that different scaling laws can be found, which fall in one of the following classes: logarithmic, linear, quadratic, exponential and non-converging. The techniques for quantifying this behaviour rely mainly on Markov chain theory and martingales. Most behaviours can be studied analytically but there are still many rules for which obtaining a formal characterisation of their convergence properties is still an open problem.

Introduction

Synchronous and asynchronous cellular automata have been a central topic in the study of complex systems. Their analysis covers various fields such as computability [START_REF] Kari | Theory of cellular automata: A survey[END_REF][START_REF] Kutrib | Cellular automata: Descriptional complexity and decidability[END_REF][START_REF] Worsch | Intrinsically?) universal asynchronous CA[END_REF], dynamical systems [SS12, BVdWDB12, DFM12, SFD14], modelling of biological phenomena [START_REF] Deutsch | Cellular Automaton Modeling of Biological Pattern Formation Characterization, Applications, and Analysis[END_REF], etc. Synchronous models are praised for their capacity to generate complex behaviour from simple local rules with only a few states. At the same time, they are criticised for their lack of realism and the fact that their components, the cells, are updated all together in a perfect synchrony. Asynchronous models offer a greater range of possibilities but this freedom brings out new questions: to date, selecting a particular model of updating is more a matter of taste than a question of science, and no one really knows what effects a change in the updating may produce at a global scale... The question of knowing which part of the behaviour is due to the local rule and which part is due to the updating method is a fundamental question (see Ref. [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF] and references therein). However, it is only in the last decade that asynchronous cellular automata have emerged as a research topic per se. In 2014, we gave a panoramic view of the various research directions which appeared [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF] and recently, we presented an introductory article to this field [START_REF] Fatès | Asynchronous Cellular Automata[END_REF]. Our objective here is to expose the state of the art on what is known about the behaviour of the simplest asynchronous cellular automata. We do not aim at presenting novelties but rather gathering results which has been dispersed in a series of articles dealing with this question.

We present a study on the 256 Elementary Cellular Automata, that is, one-dimensional binary rules with nearest-neighbour interaction. We consider these models with the fully asynchronous updating scheme, that is, when only one cell is updated at each time step, chosen uniformly at random. We are mainly interested in describing if the convergence to a fixed point happens, and what is the average time it takes to converge. More precisely, we want to know how the time needed to attain a fixed point scales with the size of the automaton. Indeed, we claim that the convergence time to a fixed point is a good approach to understand the behaviour of the rules. Of course, this approach will only give us a partial view on these mathematical objects but, as we will see, it is a source of beautiful questions and a good starting point to understand the dynamics of probabilistic complex systems.

Definitions 2.1 Elementary cellular automata

An Elementary Cellular Automaton (ECA) is a one-dimensional binary CA with nearest-neighbour interactions. We here tackle the finite case where cells are arranged in a ring and we denote by L = Z/nZ the set of n cells; we take n ≥ 3 in order to avoid some exceptions due to the cases where we would have only one or two cells.

The state of the automaton at a given time is called a configuration; the set of configurations of size n is denoted by

E n = {0, 1} L .
The evolution of an ECA is governed by its local function f : {0, 1} 3 → {0, 1}. This function defines how a cell updates its state according to its own state and the states of its left and right neighbours.

A transition is a relation between a triplet (x, y, z) and the value f (x, y, z). We say that a transition is active if its application changes the state of a cell, that is, if f (x, y, z) = y, otherwise it is passive. By extension, for a given configuration x, a cell i ∈ L is called active if the transition that applies in i is active, that is, if f (x i-1 , x i , x i+1 ) = x i .

We now define our stochastic dynamical system. We denote by (U t ) t∈N ∈ L N the random sequence of cells that are selected for being updated, that is, where the local function will be applied. The evolution of the fully asynchronous ECA from an initial condition x is represented by the stochastic process (x t ) t∈N and defined recursively by: x 0 = x and x t+1 = F (x t , U t ), with:

∀i ∈ L, x t+1 i = f (x t i-1 , x t i , x t i+1 ) if i = U t x t i otherwise.
(1)

We now specify (U t ): it is the realisation of a sequence of independent random uniform updates in L. As this updating method is fixed, we will make a small abuse of notation and simply write F (x) for the random variable that describes the configuration obtained by a uniform random update on x.

A configuration x ∈ E n is called a fixed point if we always have F (x) = x, that is, when all the cells of x are in a passive state. We denote by FP the set of fixed points. Since fixed points are defined as the configurations which contain no active cell, this property is independent of the updating scheme, which implies that both the synchronous and asynchronous updating methods induce the same set of fixed points.

Starting from a configuration x, the convergence time T (x) is the random variable that corresponds to the time required to reach a fixed point: T (x) = min{t ∈ N, x t ∈ FP}. If the sequence (x t ), which implicitly depends on the sequence of updates (U t ), does not lead to a fixed point, then T (x) is infinite for this sequence of updates. For a fixed ring size n, we define

τ (n) = 1 n max x∈En E{T (x)}.
This time-rescaling operation allows us to compare "fairly" the synchronous and asynchronous updating; one can also note that the dynamics of the system would be very similar if the cell updates would occur in a continuous time according to an independent Poisson process of rate 1 (see [START_REF] Silva | An experimental study of noise and asynchrony in elementary cellular automata with sampling compensation[END_REF][START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF] for more discussions on time rescaling).

Our objective is to find the different qualitative behaviours that are possible for τ (n). More precisely, we want to sort out the 256 ECAs according to the scaling law this function obeys. We will use the usual notations and write τ (n) ∈ O(φ(n)) to say that φ asymptotically bounds τ from above up to a constant, and τ (n) ∈ Θ(φ(n)) to say that φ asymptotically bounds τ from below and from above, up to a constant.

Since the rescaled worst expect convergence time τ will be our main parameter, in what follows, we will simply call it convergence time for short. We will show that when the convergence time is defined, it can be either logarithmic, linear, quadratic or exponential. When τ (n) is not defined for an infinite number of values n, we will say that the rule under study is non-converging.

Elementary mechanics of asynchronous ECAs

Following a convention introduced by Wolfram, it is common to identify each ECA f by a decimal code W (f ) which consists in converting the sequence of bits formed by the values of f to a decimal number:

W (f ) = f (0, 0, 0) • 2 0 + f (0, 0, 1) • 2 1 + • • • + f (1, 1, 1) • 2 7 .
We now introduce another notation of ECA rules, the transitions code, consists in identifying an ECA rule f with a word formed of labels from {A, B, . . . , H}, where each label identifies an active transition. The mapping between labels and transition is given in Table 1.

For example, 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 transitions code: BCFG.

One important fact about ECAs is that their global properties are not affected by the reflection symmetry, which consists in exchanging left and right directions, and by the conjugation symmetry, which consist in permuting the 0's and 1's. For example, if for a given size a rule converges to the fixed point "all-zero" in T time steps, then its conjugate will converge to "all-one" in T time steps too. This means that if we know the dynamics of a rule f , we can immediately deduce the behaviour of the rules obtained with these two symmetries. Note that since a rule may be its own symmetric, the equivalence classes are formed of 1,2 or 4 different rules and we can partition the space of the 256 rules into 88 non-equivalent classes. For the sake of simplicity, we will from now on restrict our examination to the Note that with the transitions code of a rule, we can easily deduce the symmetric rules: to obtain the reflected rule, we only need to exchange the labels B and C (that is, to replace B by C and vice-versa), and exchange F and G. To obtain the conjugate rule, we need to exchange the labels A and H, B and G, C and F, D and E, respectively (see Tab. 1-right).

Basic mechanics

The important point is that in the case of fully asynchronous updating, the notation by transitions allows us to decompose the behaviour of the local rule according to some "basic mechanics" laws. For a given configuration, we call a q-region a maximal set of contiguous cells in state q and frontiers the cells which are at the border of two regions. These laws can be formulated as follows:

• If transition A (resp. H) is passive, the size of a 0-region (resp. a 1-region) may increase or decrease by 1 but this region cannot be broken.

• Transitions B and F control the movements of the 01-frontiers: B (resp. F) moves this frontier to the left (resp. to the right). If both transitions are active, the 01-frontier performs an unbiased random walk.

• Similarly, transitions C and G control the movements of the 10-frontiers.

• Transition D controls the fusion of 1-regions: the absence of D implies that the 0-regions cannot disappear. Similarly, the 1-regions can only disappear if E is active.

These properties are summed up on Tab. 2. We suggest to the readers to keep these rules carefully in mind and, if possible, to always have a copy of Table 1 before them. Indeed, the great majority of the proofs will rely on these elements. Let us also stress that these properties are only valid when two neighbouring cells cannot be updated simultaneously, which is the case here.

A rule for which the two states are quiescent (A and H are not active) is said to be doubly quiescent. For such rules, using the "basic mechanics" laws stated above to deduce to global behaviour of the rule can be done without too much difficulty. However, when one of the two states or both states are not quiescent, things become more complicated and require a particular analysis. We now present some simple additional tools that will help us relate the local properties of a rule and its global behaviour.

de Bruijn graphs

The transitions code presented on Table 1 is defined by a mapping t : Q 3 → {a, . . . , h} such that t(0, 0, 0) = a, t(0, 0, 1) = b, .... This mapping can be used to produce a complementary useful view on configurations by transforming a configuration x ∈ Q L into a configuration x ∈ {a, . . . , h} L , that we can call the t-image of x, obtained by assigning to each cell a label a, b, ... if the transition A, B, ... applies on it (independently of whether or not this transition is active). For simplicity we write x t = x to denote that x = t(x) is the t-image of x.

This transformation can be done directly but it is also interesting to consider the de Bruijn graph, which allows one to do this transformation by reading one symbol at time, from left to right, and by following the edge with the label that was read (see Fig. 1-right). This graph is useful for determining various properties of cellular automata. In particular, since we are on Z/nZ, the fixed points of a rule are the configurations for which a circuit in the de Bruijn graph does not go through any node with an active transition. Since we are mainly interested in the convergence of asynchronous cellular automata to fixed points, this observation on the de Bruijn graph will be helpful to study the structure of the global Markov chain that defines the dynamics, more specifically in Sec. 7 where properties of non-convergence will be established.

For a particular configuration x ∈ E n , we denote by a(x), . . . , h(x) the number of occurrences of the labels a, . . . , h in x, the t-image of x . Note that in most cases, we will omit the argument x for the functions a, . . . , h since it will be implicitly given by the context. For a pattern P ∈ Q * , we denote by |x| P the number of occurrences of the pattern P in the configuration x.

From the de Bruijn graph, one can deduce the following simple, but fundamental, equalities, which hold for any configuration x ∈ E n :

b = c, f = g, |x| 01 = b + d = c + d = e + f = e + g = |x| 10 .
(2)

The rewriting table

We remark that in t-images of configurations, when an active cell is updated, three cells modify their labels: the updated cell, but also its left and right neighbours (see Fig. 1-left). In order to find out all the transformations that can occur when a cell is updated, we thus need to consider all the possible 32 triplets of t-labels. These transitions are represented on Table 3; we call this table the rewriting table. The triplets correspond to the sequences of five cell states (α, x, y, z, β) ∈ {0, 1} 5 ordered with the following presentation: each column corresponds to a fixed value of (x, y, z), the first to fourth rows correspond to the "border" values (α, β) equal to (0, 0), (0, 1), (1, 0) and (1, 1), respectively. Note that the only columns to take into account are those which correspond to an active transition. For instance, if we take the majority rule 232-DE, only the eight transitions of columns D and E will be useful to consider.

Potentials

In all this text, we will make an intensive use of functions that map configurations to the set of natural numbers N = {0, 1, 2, . . . }. Borrowing the term from the field of physics, we will call these functions potentials. Indeed, they will be used to measure the "distance" of configurations to a fixed point. Definition 1. A potential W : E n → N is p-linear if it is a linear combination of the number of labels of a given configuration with positive integer coefficients, that is, if it can be written:

W (x) = ω a a(x) + • • • + ω h h(x) with ω a , . . . , ω h ∈ N.
Before presenting concrete cases of potentials, we introduce some useful definitions.

Definition 2. W is balanced if for any configuration the difference of potential produced by the update of a cell is only a function of the label of this cell.

Lemma 1. If W is a p-linear potential such that:

ω a + ω d = ω b + ω c and ω e + ω h = ω f + ω g , then W is balanced.
Proof. First, let us note that if the CA rule is the identity rule 204-I, that is, if no transition is active, then any potential is balanced. Let us assume that transition A is active and examine the first column of Table 3. Let us denote by δ 1 a , δ 2 a , δ 3 a and δ 4 a the difference of potential produced by an update of the central cell of the respective configurations 00000

δ 2 a = 2ω a + ω b -(ω b + ω e + ω d ), δ 3 a = ω c + 2ω a -(ω d + ω e + ω c ), and δ 4 a = ω c + ω a + ω b -(2ω d + ω e )
. Now, the property that the difference of potential depends only on the update of a-and thus not on the first and last cell state of the patternreads:

δ 1 a = δ 2 a = δ 3 a = δ 4 a .
It is then easy to verify that these equalities are equivalent to ω a + ω d = ω b + ω c . In the same way, the four rows of the second column of Table 3 give us:

δ 1 b = δ 2 b = δ 3 b = δ 4 b .
ω e + ω h = ω f + ω g .
When a potential is balanced, we denote by δ t the decrease of potential created by an update of a cell having a label t.

Recall that F (x) denotes the random variable that represents the evolution of the system from a configuration x. We denote by ∆W (x) = W (F (x)) -W (x) the random variable that represents the change of potential in x. Furthermore, we denote by E∆W (x) the expected change of potential in x. For instance, if x has a unique active cell, which produces a change of potential of -1 when it is updated, then we have E∆W (x) = -1/n. Indeed, there are n -1 cells which produce a change of zero and one cell that produces a decrease of 1. We will make an intensive use of this notation in the parts that follow and we will often rather write n • E∆W (x) = -1 in order to preferably manipulate integers.

Before tackling more intricate questions, let us first establish a simple fact: if a rule has a p-linear potential that can decrease for any configuration which is not a fixed point, then the hitting time to a fixed point is almost surely finite. Recall that (x t ) denotes the sequence of random configurations that models the evolution of the system; we state that: Lemma 2. If a rule f has a p-linear potential W , such that for every ring size n ≥ 3, there exists > 0 such that : ∀x ∈ E n Pr{∆W (x) < 0} ≥ , then for all x ∈ E n , the random variable T (x) = min{t ∈ N : W (x t ) = 0} is almost surely finite.

All the elements are now in place to discover the diversity of behaviours of the asynchronous Elementary Cellular Automata. We will group the rules by their class of convergence, starting from the linear class (Sec. 3). We will then examine the quadratic class (Sec. 4), before going to the nonpolynomial types of convergence: the logarithmic (Sec. 5) and exponential (Sec. 6) classes. Last, we will end with the class of non-converging rules (Sec. 7) and then say a few words about the perspectives opened by the current state of the art.

Rules with a linear convergence time

The class of rules with a linear convergence is a good starting point to present the various analysis techniques that we will use. To have an insight of typical behaviour of this type, readers can have a look at the rules marked "LIN" in Table 10 (p. 28). This type of convergence corresponds to an intuitive behaviour: when a system is attracted towards a fixed point, if we double the size of the ring, we will also double the time needed to attain a fixed point. However, as we will see, this behaviour only concerns 13 rules out of 88 and even in this case, obtaining an analytical proof is not always straightforward.

The following lemma captures the idea that despite a random updating of a system, there exists a potential which decreases regularly on average. Lemma 3. If an ECA f admits a p-linear potential W such that, for n large enough:

(a) ∀x ∈ E n , W (x) = 0 =⇒ x ∈ FP and (b) ∀x / ∈ FP, n • E∆W (x) ≤ -1, then the convergence time of f is at most linear, that is, τ (n) ∈ O(n).
Proof. For a given configuration x ∈ E n , let (x t ) be the sequence of random configurations obtained by the evolution of the cellular automaton f on x. Let (X t ) denote the process obtained by looking at the potential of the configurations, that is, (X t ) is the sequence of random variables that are defined with ∀t ∈ N,

X t = W (x t ) if x t / ∈ FP and X t = 0 if x t ∈ FP.
Forcing the potential to be null when we have reached a fixed point is a "trick" that simplifies the analysis.

We now introduce the process

Y t = X t + εt with ε = 1/n and show that it is a supermartingale, that is E{Y t+1 -Y t | F t } ≤ 0.
Here and in the lines that follow, F t denotes a filtration adapted to (x t ), that is, a mathematical object that can be seen as the information gained by observing the evolution of the system until time t. We have:

E{Y t+1 -Y t | F t } = E{X t+1 + (t + 1) -X t -t | F t } = E{X t+1 -X t | F t } + = E∆W (x t ) + ≤ 0.
Let T denote the time when the process (X t ) hits the value 0; this corresponds to the time to converge to a fixed point. According to Lemma 2, T is almost surely finite. Using Doob's optional sampling theorem, we have:

E{Y T } ≤ E{Y 0 }. We write: E{Y 0 } = E{X 0 } = W (x)
, and by definition, we also have

E{Y T } = E{X T + .T } = E{T } and X T = 0. This yields: E{T } ≤ W (x)/ .
From this result, we can note that, since W scales linearly with n and since = 1/n, E{T } scales quadratically with n. The rescaled convergence time thus scales linearly with the ring size n.

Theorem 1 (linear convergence). The rules 128-EFG, 130-BEFG, 132-FG, 136-EG, 140-G, 160-DEFG, 162-BDEFG, 164-DFG, 168-DEG, 172-DG have a linear convergence time; that is, for these rules: τ (n) = Θ(n).

Proof. We proceed in two steps: first, we exhibit p-linear potentials that fulfil (by construction) condition (a) of Lemma 3. We show that they also verify condition (b); this will give us an upper bound on the convergence time. In a second step, we will give lower bounds on τ (n) by calculating the convergence of one particular configuration.

Upper bounds. First, for the four rules 128-EFG, 132-FG, 136-EG and 140-G, it is sufficient to take the number of 1's as a potential: W (x) = |x| 1 , that is, W = e + f + g + h. Indeed, any update of an active cell removes a 1 and there is no way of creating 1's. This reads: x / ∈ FP =⇒ n•E∆W (x) ≤ -1. If we turn our attention to the four rules 160-DEFG, 164-DFG, 168-DEG and 172-DG, we observe that they also decrease the number of 1's, unless the transition D is applied. We note that in all these rules, it is impossible to create a d because transitions A, B, C and H are all passive (see Tab. 3). Moreover each time an active 0-cell is updated (a d), |x| 1 increases by 1 but 2d(x) decreases by 2, which also results in a net decrease of the potential. We thus take W (x) = 2d(x) + |x| 1 as a p-linear potential, that is: W = 2d + e + f + g + h. It verifies the two conditions of Lemma 3.

The case of 130-BEFG and 162-BDEFG is slightly more complex as the evolution is no longer monotonous: the 01-frontier performs an unbiased random walk. For these two rules, a potential function can be nevertheless constructed simply by observing that the number of regions can only decrease with time (see Sec. 2.3). We thus take

W (x) = |x| 1 + |x| 01 , that is, W = b + d + e + f + g + h. 0 1 2 n -1 n 1 2ε 1 -2ε ... 2ε 1 -2ε ε 1 -ε 1
Figure 2: Representation of the Markov chain that describes the evolution of rule 128-EFG from a configuration 1 i 0 n-i . The number of 1's, i, corresponds to the label of the states of the Markov chain.

For rule 130-BEFG, for all the configurations x / ∈ FP, we have: e). The first term corresponds to the variation of the number of 1's and the second term to the variation in the number of regions. We also have b + d = e + f (see Sec. 2.4), which implies:

n • E∆W (x) = (b -e -f -g) + (-
n • E∆W (x) = -e -g -d.
Then it can be noted that if x is not a fixed point, it contains a pattern 01, and we thus have e + g > 0, which implies n.E∆W (x) ≤ -1. The potential W thus verifies the two conditions of Lemma 3. The same proof applies for rule 162-BDEFG.

Lower bounds. To establish a lower bound on the convergence time, first let us consider the particular initial condition x = 001 n-2 . Since all the rules considered are doubly quiescent, we can infer that if x t is not a fixed point it is a two-region configuration, that is, up to a given number of shifts, x t has the form 1 i 0 n-i with i ∈ {1, . . . , n -1}.

Let us consider the four rules 128-EFG and 132-FG, 136-EG, 140-G and the four other rules 160-DEFG, 164-DFG, 168-DEG, 172-DG. It can be noted that the evolution of these rules is monotonous, that is, the number of 1's can only decrease. Indeed, the transition D is never applied as a 0 cannot become isolated; moreover, the size of the 1-regions decreases by 1 when transitions F or G are applied (if they are active). At each time step, the probability to decrease by 1 the number of 1's is thus 1/n or 2/n, which gives an average time to decrease by 1 of n or n/2. Summing up n -2 such operations gives us a quadratic number of steps in n, that is, a linear rescaled convergence time. This evolution can be represented by a Markov chain: see Fig. 2 for the case of 128-EFG.

Although 130-BEFG is not monotonous, giving a lower bound for this rule is not difficult since the fixed point 1 = 1 L is not reachable. This rule can thus only converge to 0, and more slowly than rule 128-EFG since the transition B increases the number of 1's.

The case is more delicate with 162-BDEFG. The fixed point 1 is now reachable since transition D is active. Simulations show that the system has a clear tendency to be attracted to 0: intuitively if we look at a 1-region of length greater than 1, it can decrease from its both sides (as F and G) are active but it can only increase from one side (with B). One can thus guess that the probability to attain 1 becomes exponentially small when n increases. However, this probability cannot be directly neglected and we thus need to call to the step-forward method to solve exactly the system of equations that gives the convergence time (see Ref. [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF] for details). Let us denote by T i the average time needed to converge to a fixed point from the configuration 1 i 0 n-i . By definition, we have T 0 = 0, T n = 0 and, taking ε = 1/n, we write:

T 1 = 1 + T 0 +(1 -2 )T 1 + T 2 ∀i ∈ {2, . . . , n -1}, T i = 1 +2 T i-1 +(1 -3 )T i + T i+1
The solution of this system has the form 1 κ(n) , where κ(n) has a linear term in n and a term with a negative exponential in n. This gives us a convergence time which varies quadratically with n, that is, a rescaled convergence time which is linear in n. It can be noted that this system ). The time goes from bottom to top ; white and blue colours represent states 0 and 1, respectively. The time scale is rescaled by a factor 1/n, that is, the states are represented after n independent updates. This convention is kept in all the following space-time diagrams.

= 2a + 2b + h. B C H abe 4 eca 2 fhg 1 bfg 2 fgc 0 ede 0 ∆W -2 ∆W -2 ∆W -1 abf 4 ecb 2 fhh 2 bfh 3 fgd 0 edf 0 ∆W -1 ∆W -2 ∆W -2 cbe 2 gca 2 hhg 2 dfg 0 hgc 1 gde 0 ∆W -2 ∆W -1 ∆W -2 cbf 2 gcb 2 hhh 3 dfh 1 hgd 1 gdf 0 ∆W -1 ∆W -1 ∆W -3
is very close to the famous Gambler's ruin problem with a biased coin: a player that initially has i points has a probability p to win one point and a probability q = 1p to loose one point. The game ends when the players are ruined or when they reach N points, which corresponds to the bank's ruin. The only difference with our system is that in our case, there is a probability 1 -3 (or 1 -2 for one case) not to move.

Theorem 2. The rules 78-BH and 94-BCH have a linear convergence time.

Proof. For these two rules, we take W = 2a + b + c + h = 2a + 2b + h. The form of the potential reflects the fact that the 0-regions have a tendency to be "eaten" and the fact that b's, c's and h's are active (see Fig. 3). One can then verify that the difference in potential of the triplets rewriting table (Sec. 2.5) are all negative: see Table 4. This yields: ∀x / ∈ FP, n • E∆W x ≤ -1. As the definition of W includes the number of b's, c's and h's, we have W (x) = 0 =⇒ x ∈ FP. The potential W verifies the two conditions of Lemma 3.

For obtaining a lower bound, let us start with rule 78-BH and examine the evolution of the configuration which contains only one 1. It can be seen that for this configuration only transition B can be applied and we obtain a configuration with two adjacent 1's after n steps in average (as the probability of the event is 1/n). In fact, if the configuration contains at least three 0's in the configuration, each time that a b is updated, it creates another b. The last b disappears when the configuration obtained no longer contains any 00 pattern. So it is necessary to perform an order of n steps, each of which has an average time of 1/n, which gives a quadratic number of steps in n and a linear rescaled convergence time. Note that in between the 00 patterns, the transition H applies but does not create any 00 pattern nor does it erase any B (see Fig. 3).

The same argument applies for rule 94-BCH, with the only difference being that the convergence time is halved since the pattern extends in both directions.

Conjecture 1. The rule 74-BEH has a convergence time which is at least linear.

This rule has a fascinating behaviour. Empirically, one can observe that when started from a random uniform initial condition, the rule has a tendency to converge very rapidly. However, it is possible to build configurations for which the convergence seems (at least) linear. For instance, for k > 0, consider the initial condition 001(011) k : a "cascade" propagates from right to left and makes the system progressively converge to 0 = 0 L (see Fig. 3). We could not find any suitable potential to study this rule.

It is an open question to find a precise characterisation of its convergence dynamics.

Rules with a quadratic convergence time

In this section, we will examine the rules for which the convergence time varies quadratically with the ring size n. For the ECAs, this type of convergence is always obtained with three ingredients: (a) the rule is doubly quiescent (that is, A and H are passive), which ensures the stability of the regions; (b) one of their frontiers or both frontiers perform an unbiased random walk; (c) one type of region or both types of regions have the possibility to disappear (that is, D or E is active). To have an insight into a typical behaviour of this type, readers can have a look at the rules marked "QUAD" in Table 10 (p. 28).

Lemma 4. If an ECA f admits a p-linear potential W ∈ {0, . . . , n} such that:

(a) x ∈ FP ⇐⇒ W (x) = 0 or W (x) = n, (b) ∀x ∈ E n , E∆W (x) = 0, and (c) ∀x / ∈ FP, Pr{W (F (x)) = W (x)} ≥ 1 n , then the convergence time of f is at most quadratic, that is, τ (n) ∈ O(n 2 ).
Proof. For a given configuration x ∈ E n , let (x t ) be the sequence of random configurations obtained by the evolution of the cellular automaton f . Let (X t ) denote the process obtained by looking at the potential of the configurations, that is, (X t ) is the sequence of random variables that are defined with ∀t ∈ N, X t = W (x t ).

First, we have that (X t ) is a martingale. Indeed, for x t / ∈ FP, condition (b) yields: E{X t+1 -X t | F t } = E∆W (x) = 0 and by definition this property is also valid for x t ∈ FP. Let T be the hitting time of (X t ) to zero or n; this corresponds to the number of steps for the convergence to a fixed point. According to Lemma 2, T is almost surely finite. On the one hand, we use Doob's optional sampling theorem: E{X T } = E{X 0 } = W (x), where x is the initial condition. On the other hand, we have E{X T } = p 0 • 0 + p n • n, where p 0 = E{X T = 0} and p n = E{X T = n} respectively represent the probability that the process stops on 0 or n. This gives us: p n = W (x)/n. In words, if we think of W (x) as the number of 1's, this means that the probability that system converges by hitting the upper limit is equal to the initial density of 1's.

0 1 2 n -1 n 1 ε 1 -2ε • • • ε 1 -2ε ε 1 -2ε ε • • • ε ε 1
Figure 4: Representation of the Markov chain that describes the evolution of the shift rule 170-BDEG from a configuration 1 i 0 n-i . The number of 1's, i, corresponds to the label of the states of the Markov chain.

Let us perform a martingale analysis a second time with the process

Y t = ε.t -X 2
t , where ε = 1/n. Let us show that (Y t ) is a supermartingale:

E{Y t+1 -Y t | F t } = E{ε(t + 1) -X 2 t+1 -εt + X 2 t | F t } = E{-(X 2 t+1 -X 2 t ) + ε | F t } = -E{(X t+1 -X t ) 2 | F t } -2X t E{X t+1 -X t | F t } + ε ≤ 0.
Indeed, condition (a) gives us E{X t+1 -X t | F t } = 0 and, from condition (c), we have: E{

(X t+1 -X t ) 2 | F t } ≥ ε.
Once again, using Doob's optional sampling theorem, we have : E{Y T } ≤ E{Y 0 }. In order to express E{Y T } as a function of the expected value of T , we write: E{Y T } = εE{T } -E{X 2 T }. We can then use our previous calculations and write:

E{X 2 T } = p 0 • 0 2 + p n • n 2 = nW (x).
Putting together these elements yields: εE{T } -nW (x) ≤ -W (x) 2 and we finally obtain:

E{T } ≤ W (x) (n -W (x)) ε .
As we have 1/ε = n, and since the quantity W (x) n -W (x) is upperbounded by n 2 /4, we have at most a cubic number of time steps for the convergence to a fixed point, which corresponds, as expected, to a quadratic rescaled convergence time.

Theorem 3. The rules 170-BDEG, 184-CDEG have a quadratic convergence time.

Proof. Note that rule 170-BDEG corresponds to the shift and rule 184-CDEG is the well-known "Traffic rule", so called because it has the remarkable property to conserve the number of 1's (in a synchronous dynamics) and that these 1's can be seen as cars trying to move whenever they find an empty space. We can observe experimentally that for both rules, the density fluctuates but its average remains stable, that is, there is no general tendency to increase or decrease; we thus take W (x) = |x| 1 as a potential. It is easy to verify that this potential fulfils the conditions (a), (b) and (c) of Lemma 4.

In order to obtain a lower bound, for a given n, we take k = n/2 and consider the initial condition x = 1 k 0 n-k . As in the previous case, since we have a doubly-quiescent rule, the evolution of the rules is contained in the set of configurations {1 i 0 n-i , i ∈ {0, . . . , n}} and their translations. We project the evolution of the system on a process that counts the number of 1's: X t = |x t | 1 . The process (X t ) is a Markov chain; let's denote again by T k the average number of steps for reaching one of the two absorbing states 0 or 1. It can be noted that the process corresponds to a Gambler's ruin problem where one needs to wait n time steps in average between successive rounds of play (see Fig. 4). By using the step-forward method, we obtain T k = n(nk)/ε with ε = 1/n, which gives us a cubic number of steps and, as expected, a convergence time that varies quadratically with the ring size n. The proof of this result was established in Ref. [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF]. Unfortunately, we could not find a p-linear potential that could be used to obtain this result directly. Instead, it was necessary to consider the number of 1's and to add 1 or -1 to this quantity each time a transition D or E was respectively applied. This Deus ex machina is necessary to compensate the fact that if a configuration contains an isolated 0 or an isolated 1, the probabilities to add a 1 or to remove a 1 are no longer constant. Finding a more elegant way to describe the dynamics of this rule is an open question.

Theorem 5. The rules 138-BEG, 146-BCEFG, 152-CEG have a quadratic convergence time.

For the sake of brevity, we will here describe these three behaviours only informally. Let us note that they only differ from the three previous rules in having D passive. A difference of behaviour with the previous rules will occur only when an isolated 0 is updated (D is not applied). This means that the 0-regions cannot disappear and creates a "bouncing" effect when two 1-regions meet. The fixed point 1 is thus unreachable and the process can only converge to the fixed point 0 by making 1-regions disappear with the application of transition E. The remarkable fact is, however, that this effect does not change qualitatively the convergence time. Indeed, let us consider a fictional random-walk process (X t ) which evolves in discrete steps in {0, . . . , 2n} with the initial condition X 0 = n. At each time step, we have X t+1 = X t if X t = 0 or X t = 2n and X t+1 = X t + R t otherwise, with R t = 1 with probability 1/2 and R t = -1 with probability -1/2. The process X t is a regular unbiased random walk in {0, . . . , 2n}. It thus converges in a time proportional to the square of 2n. Now, let us consider the process Y t = |X t -n|. It takes its value in {0, . . . , n} and has the same "bouncing" property as discussed above. However, one immediately sees that the two processes have the same convergence time. This idea can be similarly applied to our rules to show that their convergence time is quadratic. Readers wishing to have more details on these techniques may look at Ref. [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF].

Logarithmic convergence of ECAs

We now reach a more complex case, the class of rules with logarithmic convergence, that is, for which τ (n) = Θ(log n). Surprisingly enough, this class is potentially formed of no less than 22 rules.

Identification of the rules of this class

Before tackling the analysis, let us simply observe the space-time diagram of the various rules with a rapid convergence in Figure 5. To list all the behaviours of this kind of the ECAs, one may examine by eye all the spacetime diagrams of the 88 ECAs and select those which appear to converge rapidly to a fixed point [START_REF] Fatès | A note on the classification of the most simple asynchronous cellular automata[END_REF]. In Table 5, we give a list of such candidate rules, based on whether the system has a tendency to converge to the homogeneous fixed point 0 (RCH) or to a non-homogeneous one (RCN). It can be seen that the common property of the various behaviours observed is the presence of fragmentation processes: the larger 1-regions clearly have a tendency to break into smaller pieces and the smaller regions have a tendency to vanish.

Let us now try to go from empirical observations to more analytical arguments.

A lemma for a lower bound

Our first goal is to establish a lower bound on the convergence time: the following lemma tells us that, whatever the behaviour of a rule, its convergence time cannot be more rapid than logarithmic.

Lemma 5. Apart from the identity rule, the convergence time of all the rules is at least logarithmic in the size of the automaton. Proof. To see why, let t be one active transition of the rule and let the pattern π t ∈ {0, 1} 3 be the sequence of 3 states that generates t. For instance, for the majority rule DE, if we choose transition t = E, we have π t = 010. The configuration x obtained by repeating k times the pattern π t has a length n = 3k and we call targets the k cells at the centre of each pattern (that is, with an index i such that i mod 3 = 1).

These targets are active and a necessary condition for the convergence of the system is that they are all stabilised (i.e. made passive). Clearly, the updating of a target cannot stabilise another target and a target is stabilised either if it is updated, or if its right or left neighbour is updated. The stabilisation time of the targets thus gives a lower bound of the convergence time. The process of updating k elements with a random uniform sampling of the elements corresponds to a coupon collector process: take k elements that are randomly and uniformly selected at each time step, the average time needed to select each element at least once is equivalent to k log k for a large k. This result can be easily obtained with the analysis of the Markov chain depicted on Fig. 6. Recall that the convergence time τ (n) corresponds to the number of times steps divided by n; τ (n) is thus lower-bounded by

f (n) ≤ τ (n) with f (n) ∼ 1 n k log k ∼ 1 3 log n for a large n. 0 1 2 n -2 n -1 n 1 1 - 1 -2 2 ... 2 1 -2 1 - 1
Figure 6: Representation of the Markov chain that describes a coupon collector process.

Lemma for an upper bound

In a second step, let us use again the idea of comparing our asynchronous cellular automata to a coupon collector process, this time to establish an upper bound. Lemma 6. If for a rule f different from the identity, there exist a positive integer m and a p-linear potential W such that for every ring size n ∈ N:

(a) W (x) = 0 =⇒ x ∈ FP, and
(b) ∀x / ∈ FP, n • E∆W (x) ≤ - W (x) m ,
then f has a logarithmic convergence time:

τ (n) ∈ Θ(log(n)).
Proof. Let W be a p-linear potential that satisfies the two conditions (a) and (b). Recall that (x t ) denotes the sequence of random configurations obtained from an initial condition x. Let (X t ) denote the sequence of potentials defined with:

∀t ∈ T, X t = W (x t ) if x t ∈ FP, 0 otherwise.
Remark that as W is a p-linear potential, (X t ) is a integer-valued process in {0, . . . , M W • n}, where M W is the greatest of the eight coefficients that define the potential W (see Def. 1 above). Let T be random variable defined as T = min{t ∈ N; x t ∈ FP}; this corresponds to the hitting time to a fixed point.

Condition (b) gives:

n • E{X t+1 -X t | F t } ≤ - X t m ,
and for t < T , the contrapositive of (a) reads X t = W (x t ) > 0 for t < T . We can thus write:

E{ X t+1 X t | F t } ≤ 1 - 1 mn . (3)
Let us now introduce the variable δ = 1-1/mn. We have δ ∈ (0, 1) and this variable can be seen as a "damping factor" of the process: 1/mn represents the fraction of the potential that is lost in average at each time step.

In order to build a martingale, we would like to multiply the value of X t by δ -1 at each time step. However, there is a problem when X t = 0: the result of X t multiplied by any quantity will also be zero... This is why we introduce the following process. Assuming T > 1, we set:

∀t ∈ N, Y t = X t • (1/δ) t for t < T -1 X T -1 • (1/δ) T -1 for t ≥ T -1.
In other words, we "freeze" the value of X t that is taken into account in the definition of (Y t ) one step before the hitting time.

Let us show that it is indeed a supermartingale. For t < T -1, we have X t > 0 and:

E{Y t+1 -Y t | F t } = E{X t+1 • (1/δ) t+1 -X t • (1/δ) t | F t } = X t δ t+1 E{ X t+1 X t -δ | F t } ≤ 0 from Eq. (3). For t ≥ T -1, we have Y t = Y T -1 , which ensures the validity of the supermartingale inequality (E{Y t+1 -Y t | F t } ≤ 0).
Given that T is almost surely finite (by Lemma 2), and given that (Y t ) is non-negative, we apply Doob's optional sampling theorem for non negative supermartingales:

E{Y T } ≤ Y 0 . We also have Y 0 = X 0 ≤ M W • n.
Remembering the definition of (Y t ), we write:

E{Y T } = E{X T -1 (1/δ) T -1 } ≥ δE{(1/δ) T }, since X T -1 ≥ 1.
By remarking that the function x → (1/δ) x is a convex function, the application of Jensen's inequality reads: E{(1/δ) T } ≥ (1/δ) E{T } , which yields:

δ(1/δ) E{T } ≤ E{Y T } ≤ M w • n.
Taking the logarithm of this expression gives: log δ + E{T } log(1/δ) ≤ log M W + log n, and:

E{T } ≤ log n + o(log n) log(1/δ) ,
where o(f (n)) is one of the Landau notations, and denotes a function that is negligible as compared to f for a large n. Now, simply remark that since δ = 1 -1/mn, log(1/δ) is equivalent to mn for a large n. The inequality on T reads:

E{T } ≤ mn log n + o(n log n),
that is, in terms of rescaled convergence time:

τ (n) = O(log n).
Let us now examine the different ways to find a potential for showing that a rule has a logarithmic convergence time.

Rules with a strictly decreasing activity

We say that a rule has a strictly decreasing activity if the number of active cells decreases each time an active cell is updated. As an example, consider the case of ECA 76-H. This rule has only one active transition and: a) only cells with label h are active and b) an h that is updated is turned into a d and c) no h can be created by updating an h. Theorem 6. The rules 0-EFGH, 4-FGH, 12-GH, 76-H, 77-AH, 200-E, 232-DE have a strictly decreasing activity. Their convergence time is logarithmic.

Proof. There are two methods to verify that a rule has a strictly decreasing activity. The first method is to consider the number of active cells and to examine exhaustively the difference of potential of the triplets of the rewriting table (Sec. 2.5 and the example of Tab. 4). If for every transition of the rewriting table, the transformation shows a strict decrease in the number of active cells, then the rule has a strictly decreasing activity. The second method is to analyse the possible values of the local transition rule (see Ref. [START_REF] Fatès | Quick convergence to a fixed point: A note on asynchronous elementary cellular automata[END_REF]).

For all these rules, we take a potential function which counts the number of active cells. For instance, rule 4-FGH would be associated with the following potential: W = f + g + h. It can then be verified that this potential fulfils the conditions of Lemma 6 but in fact here the coupon collector argument directly applies and gives us a logarithmic convergence time.

Rules with a monotonous potential

How can we find a potential for the rules for which counting the number of active cells is not sufficient? As an illustration, let us turn our attention to the rule EH. By examining the difference of active cells in the two columns which correspond to E and H in the rewriting table (Table 3), it can be seen that this rule has an "almost" strictly decreasing activity: there is only one entry (H1) where there is no decrease, it corresponds to the case where an h produces two e's. We can thus count one h as three e's. In this case, this transition would still continue to decrease the number of "weighted" active cells. Let us make this simple idea more formal. We say that a local rule f has a monotonous potential W if for any transformation that results from the application of the global rule, the potential strictly decreases, that is, if ∀x ∈ E n , ∀i ∈ A(x) ⊆ L, W (F (x, i)) -W (x) < 0, where A(x) denotes the set of active cells of x.

Theorem 7. The rules 5-AFGH, 8-EGH, 13-AGH, 72-EH admit a monotonous potential; their convergence time is logarithmic.

Proof. Case of 8-EGH. We take W = e + 2g + h. This potential verifies the conditions of Lemma 6. Indeed, it is balanced with:

δ E = δ G = δ H = -1.
We thus have for x / ∈ FP:

n • E∆W (x) = -e -g -h = - 1 2 (e + 2g + h) - 1 2 (e + h) ≤ - 1 2 W (x).
The same proof applies for 72-EH and the potential function W = e+3h, which gives: ∀x / ∈ FP, E∆W (x) ≤ -1 3n W (x). Similarly, in the case of 5-AFGH, we take W = a + f + g + 2h = a + 2g + 2h. The potential is not balanced but the differences of potential of the triplets of rewriting table are all negative (as in Tab. 4). More precisely, the potential decreases by at least 1, when transitions A, F, or G are applied and decreases by 4 when H is applied. We thus have for x / ∈ FP:

E∆W (x) ≤ 1 n (-a -f -g -4h) ≤ - 1 n (a + f + g + 2h) ≤ - 1 n W (x).
The conditions of Lemma 6 are thus verified. The same proof applies for 13-AGH.

Rules with an average decrease of potential

To close, this section, we now present the rules for which the decrease of potential only happens on average. Theorem 8. The convergence time of rules 2-BEFGH, 32-DEFGH, 34-BDEFGH, 40-DEGH is logarithmic.

Proof. The same techniques as above can be applied to rule BEFGH. Let us take the potential W = 3e + 5f + 2h. It is balanced and we have δ B = 2, δ E = -3, δ F = δ G = -2 and δ H = -1. For x / ∈ FP, this yields:

n • E∆W (x) = 2b -3e -2f -2g -h = (2b -2e -2f ) -e -2g -h ≤ -e -2g -h ≤ 1 3 (-3e -6f -3h) ≤ - 1 3 W (x),
which results from the simple relations b ≤ e + f and f = g. Here, we also need to verify what happens when W (x) cancels. We have W (x) = 0 =⇒ h = 0, e = 0 and f = 0 which also implies g = 0, that is, |x| 1 = 0 and x = 0 ∈ FP. The conditions of application of Lemma 6 are thus all valid. This potential function can also be used for the three other rules. We only need to adapt our proof by taking into account δ D = 1 and by using again b+d = e+f to derive an inequality of the type E∆W (x) ≤ -1 mn W (x) with a specific value of m for each case. For these rules too, we have that W (x) = 0 implies e = f = g = h = 0, which implies x = 0 ∈ FP. This is an open problem. The general idea is to find a good method to quantify the fragmentation phenomena that occur in the evolution of all these cellular automata. To this end, using potential functions defined with subwords of length greater than 3 is a possible approach. Such techniques have been used by Regnault in his study of phase transitions in asynchronous cellular automata [START_REF] Regnault | Proof of a phase transition in probabilistic cellular automata[END_REF] and it is quite clear that they could be applied to analyse some, if not all, of the rules listed above.

Remaining rules

Rules with an exponential convergence

We now come to examine a few rules which have a peculiar behaviour: although there exists a fixed point which can always be reached, there is no tendency of the system to be attracted to this fixed point. This results in a convergence that is exponential in the ring size. In the lines that follow, we will briefly give some elements to explain this behaviour.

Theorem 9. The rule 154-BCEG has an exponential convergence time. Sketch. Since the readers are now more familiar with the use of martingales and Markov-chain analysis, we feel that it is better not to give all the details but rather to sketch the main ideas that we need.

First, let us pay attention to Fig. 7. We observe that the rule has a clear tendency to increase the number of 1's. The problem-if we may say so-is that only the fixed point 0 is reachable, the other fixed point 1 cannot be attained as transition D is not active.

To obtain a lower bound on the convergence time, let us again consider the initial condition x = 1 n 0. Because the rule is doubly quiescent, the system can evolve by reaching only configurations of the form 1 i 0 n-i , up to shifts. It is sufficient to count the number of 1's to fully describe the dynamics: the process X t = |x t | 1 is a Markov chain. Denoting by T i the average time needed to hit the value 0, and using the step-forward method, 0

1 2 n -2 n -1 n 1 ε 1 -ε 2ε 1 -3ε • • • 2ε 1 -3ε 2ε 1 -3ε ε • • • ε ε 1
Figure 8: Representation of the Markov chain that describes the evolution of rule 154-BCEG from a configuration 1 i 0 n-i . The number of 1's, i, corresponds to the label of the states of the Markov chain.

we obtain the following system of equations:

T 0 = 0 T i = 1 + εT i-1 + (1 -3ε)T i + 2εT i+1 for i ∈ {1, . . . , n -2} T n-1 = 1 + εT n-2 + (1 -ε)T n-1 .
This is a system of second-order linear recurrence equations, which is nonhomogeneous with a constant term. As for rule 130-BEFG, its solution gives a formula with exponentials, which resembles the solutions to the Gambler's ruin problem with a biased coin (see Ref. [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF]). After simplification, we obtain T i ∼ n.2 n (independent of i). This gives us a rescaled convergence time which is exponential:

τ (n) ∈ O(2 n ).
Conjecture 3. The rules 90-BCEH and 122-BCDEH have an exponential convergence time.

First, it can be observed that for these two rules, 0 is a fixed point for any value of n. For n = 3k, the configuration x F = (101) k t = (gdf) k is also a fixed point. To prove that the convergence is at least exponential, one could show that 0 is reachable from any configuration that is different from x F . In a second step, it is necessary to obtain an upper bound on the time needed to reach the absorbing state 0. Unfortunately, we currently do not have the adequate analytical tools to establish such a proof. It is thus an open problem to develop the appropriate lemma to better understand the rules which converge with an exponential time. In some sense, these rules can be said to be metastable: they spend a long time in a state that is away from the "minimal energy" state, and they suddenly freeze when an unlikely combination of updates makes them fall into the absorbing state... (see e.g. Ref. [START_REF] Emilio | Basic Ideas to Approach Metastability in Probabilistic Cellular Automata[END_REF] for an overview of the notion of metastability in probabilistic cellular automata).

Non-converging rules

We now come to the end of our tour of asynchronous Elementary Cellular Automata. We examine all the rules for which a convergence to a fixed point cannot be guaranteed: the value of τ (n) may be undefined for any n or for a infinite set of values of n. Contrary to the previous classes, the class of non-converging rules does not correspond to a typical behaviour. We choose to present separately the various arguments that can be given for showing that a rule is non-converging. This, in some sense, provides a subdivision of this class.

Theorem 10. The 38 rules listed in Table 6 are non-converging. This result will be established by a series of propositions which follows. Note that some rules will appear more than once as various arguments can be given in order to show their membership to the non-converging class. Proof. In order to admit a fixed point on a circular configuration, there must be a possibility to make a cycle in the de Bruijn graph without having any active transition (see the de Bruijn graph Sec. 2.4). Consequently, a rule possesses no fixed point if its transitions code contains at least one letter in each of these sets of letters: {A}, {H}, {D,E}, {B,C,E}, {D,F,G}, {B,C,F,G}. Indeed, "parsing" a configuration corresponds to making a circuit in this graph and these sets correspond to all the elementary cycles one can have by making a circuit in this graph. Any other cycle can be decomposed into such elementary cycles. The rules given above are precisely those which satisfy these constraints.

Rules with an unreachable fixed point

A second obvious reason for being non-convergent is to have a unique fixed point... which cannot be reached from other configurations.

Proposition 2. For the following rules, 0 is the only fixed point and it is not reachable from any other configuration than itself: 38-BDFGH, 46-BDGH, 54-BCDFGH, 60-CDGH, 62-BCDGH, 110-BDH and 126-BCDH.

Proof. The fact that 0 is the only fixed point is clear: the transitions code of these rules does not contain A and it has at least one active transition in the sets {H}, {D,E}, {B,C,E}, {D,F,G}, {B,C,F,G}, which guarantees that no other fixed point can exist (see the de Bruijn graph Sec. 2.4). Moreover, as E is not active, the configuration 0 cannot be reached (the last 1 cannot disappear).

Recurrent sets of configurations for any size

Recall that the evolution of our system is a finite-state Markov chain: the conditional probability to be in a given configuration at time t + 1 given the entire history of the process depends only on the configuration at time t. We can thus divide the configurations of E n into two main classes: the recurrent configurations and the transient configurations. The recurrent configurations are the initial configurations to which the system returns infinitely to them. The transient configurations are those which are visited almost surely only a finite number of times, after which the system enters in another set of configurations and will never return to the initial condition.

In our case, we only need to remark that if a rule always admits a recurrent configuration which is not a fixed point, then it is non-converging. The different other configurations that a recurrent configuration reaches before returning to itself forms a recurrent set and it is necessarily formed of other recurrent configurations.

Proposition 3. The rules 28-CGH, 29-ACGH, 73-AEH, and 108-DH have non fixed-point recurrent sets for an infinite number of sizes n.

Proof. For the rules 28-CGH and 29-ACGH, let us take k > 0 and consider the two configurations x = 001(01) k and y = 101(01) k . These two configurations form a recurrent set: x and y contain only one active cell (the leftmost); each time x is updated on this cell, it becomes y and vice-versa. See Tab. 7 and 9 in the Appendix for a typical evolution of these rules.

For rule 73-AEH, we take k > 0 and consider the two configurations x = (0011) k 00011 and y = (0011) k 01011. These two configurations contain only one active cell and form a recurrent set, transforming into each other when transitions A and E are applied in x and y, respectively.

For rule 108-DH and an arbitrary k > 0, we take x = 1010 k and y = 1110 k . As in the previous cases, only D and H may be applied on x and y to transform one configuration into the other; these two configurations thus form a recurrent set of size 2.

Recurrent sets of configurations for some sizes

We now look at the rules which have a natural tendency to produce stripes. They have the particularity to converge only for some given values of the ring size n [SRD18].

Proposition 4. The rules 6-BFGH, 7-ABFGH, 14-BGH, 15-ABGH, 22-BCFGH, 23-ABCFGH, 30-BCGH are non-converging.

Proof. For all these rules and for an arbitrary k > 0, let us examine the configuration x = 001(01) k . This configuration contains only one active cell and can only evolve to y = 011(01) k when transition B is applied. Now, configuration y has two active cells and can either come back to x or evolve to z = 01001(01) k-1 , that is, to a shift of x. The rotations of x and y thus form a recurrent set. Since there is an infinity of sizes for which such recurrent sets exist, the rules are non-converging. • For rules 37-ADFGH and 45-ADGH, for n = 3k, the configuration (001

) k t = (bec)
k and its translations are the only fixed points.

• For rules 7-ABFGH, 15-ABGH, 23-ABCFGH and 29-ACGH, for n = 2k, the configuration (01) k t = (de) k and its translation are the two only fixed points.

We believe that the convergence of these rules to their fixed point can only happen in quadratic time. This conjecture is supported by empirical observations: the convergence happens when frontiers between regular patterns meet and merge.

In the examples above, we presented some particular configurations which form a recurrent set. Remarkably, there are some rules for which this behaviour is always verified: the system has the property of "eternal return" to its initial condition. These rules are called recurrent and we end this part by giving their list. Of course, all these rules except the identity rule (204-I) are nonconverging. Interestingly enough, if one counts the number of communication classes, that is, the maximal recurrent sets, as a function of the ring size, one finds again a great variety of results. This suggests that the class of non-converging rules should be studied with more precise criteria and that for these rules, we need to understand the communication graph, that is, the graph where links between configurations model the possibility to go from one configuration to the other in one step. We refer to a recent work on this topic for a more detailed analysis [START_REF] Fatès | On the reversibility of ECAs with fully asynchronous updating: The recurrence point of view[END_REF].

Conclusion

This tutorial has presented a panorama of the behaviours of the 256 Elementary Cellular Automata with a fully asynchronous updating. The results are summarised in Tables 7, 8, 9 and 10 (pp. 25-28). Our approach was to focus on the convergence time to a fixed point: the different classes are coherent and show that members of the same class share some common feature. For the logarithmic class a fragmentation process is at play, the rules have a tendency to cut the regions into smaller pieces and then to make them disappear. For the linear class, there are regions (or patterns) which have some stability and for which the frontiers have a tendency to move in a particular direction. The same phenomenon occurs for the quadratic class, except that the frontiers between regions perform unbiased random walks, in other words, they have no preferred direction of propagation. We also have examples of rules which can be said to be metastable: they can remain a long time in an unstable stable until they hit a fixed point by pure chance. Last, the category of non-converging rules is much less homogeneous and it is an open problem to give a finer analysis of this class.

There are various directions in which this research can be extended. First, the problem of classifying the convergence time with the α-asynchronous updating scheme, where each cell is updated with probability α at each time step is much more complex [START_REF] Fatès | Asynchronous behavior of double-quiescent elementary cellular automata[END_REF][START_REF] Taggi | Convergence Time of Probabilistic Cellular Automata on the Torus[END_REF]. One can also wonder what happens in two dimensions: here too, the analysis can be much more delicate, as shown by the study on the asynchronous minority rule [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority[END_REF][START_REF] Rouquier | Stochastic minority on graphs[END_REF] or on some simple state-spreading rules [START_REF] Fatès | Examples of fast and slow convergence of 2D asynchronous cellular systems[END_REF][START_REF] Gerin | Epidemic Automaton and the Eden Model: Various Aspects of Robustness[END_REF]. As far as multi-state cellular automata are concerned, this case has not been tackled to our knowledge and it would be interesting to see if new classes of convergence emerge.

In fact, one of the main lessons one can draw from this study is that it is neither easier nor more difficult to predict the evolution of asynchronous cellular automata than their synchronous counterparts. For some rules, such as ECA 110-BDH, the synchronous behaviour is complex but the asynchronous behaviour has nothing remarkable. For other rules, the synchronous dynamics is well understood but with an asynchronous updating the evolution can be amazingly complex (e.g. 50-BCDEFGH, 74-BEH or 105-ADEH). In some sense, asynchrony can be taken as a way to reveal of a different type of complexity, which is yet to be understood.

Table 7: Characteristics of the ECA with only 0 as a quiescent state (Wolfram code even and smaller than 32). The first and second columns present space-time diagrams which are obtained with a random initial condition and with the two-region configuration 0 n/4 1 n/2 0 n/4 , respectively. The two next columns present the decimal code (Wcode) and the transitions code (Tcode). The four other columns present the features that give us the "mechanics laws" expressed in Sec. 2.3: The left arrow ←, the right arrow →, and the double arrow ↔, represent the possible movements of the 01-or 10-frontiers, that is, respectively, a movement to the left, right or a nonbiased random walk (two active transitions). The symbol * q * is used to denote that the q-regions can disappear and the symbol ]q[ denotes the fact that q-regions cannot disappear. Recall that the time is rescaled by a factor 1/n.

Figure 1 :

 1 Figure 1: (left): Example of two binary configurations and their images by the transition code. The upper configuration is obtained by updating the lower configuration on the cell indicated with an arrow. (right): de Bruijn graph with the correspondence between binary sequences of length 3 and transitions A, . . . , H. The labels on the edges show the next letter that is given in input when reading a binary sequence from left to right.

=

  cab. The first row concerns the transformation aaa → bec, which gives us: δ 1 a = 3ω a -(ω bω eω c ). Similarly, the second, third and fourth row give us:

  These equalities are equivalent to : ω a +ω d = ω b +ω c and ω e +ω h = ω f +ω g . The former equality is obtained with the equation δ 2 b = δ 4 b and the latter equality with δ 1 b = δ 2 b . The same argument applies for the five other transitions : C, D, E, F and G. The case of transition H is symmetric to the case of A: the property of balancedness for this column is equivalent to

Figure 3 :

 3 Figure 3: Space-time diagram of fully asynchronous dynamics for n = 33. (left): rule 74-BEH with the initial condition 000(011) 10 . (right): rule78-BH with the initial condition (0 27 )1(0 5). The time goes from bottom to top ; white and blue colours represent states 0 and 1, respectively. The time scale is rescaled by a factor 1/n, that is, the states are represented after n independent updates. This convention is kept in all the following space-time diagrams.

Figure 5 :

 5 Figure 5: Examples of space-time diagrams of the RCH (top) and RCN (bottom) rules for a ring size n = 50 and n = 100 (for 26-BCEGH).

Figure 7 :

 7 Figure 7: Space-time diagram of fully asynchronous dynamics for rule 154-BCEG with a random initial condition.

Conjecture 2 .

 2 The following rules have a logarithmic convergence time 10-BEGH, 18-BCEFGH, 24-CEGH, 26-BCEGH, 36-DFGH, 42-BDEGH, 44-DGH, 50-BCDEFGH, 56-CDEGH, 58-BCDEGH, 104-DEH, 106-BDEH.

Proposition 5 .

 5 For n ∈ 4N, the rule 105-ADEH has only one fixed point, up to translations. For n / ∈ 4N, this rule has no fixed point. For n ∈ 3N, the rule 37-ADFGH and 45-ADGH have only one fixed point, up to translations. For n / ∈ 3N, these rules have no fixed point. For n ∈ 2N, the rule 7-ABFGH, 15-ABGH, 23-ABCFGH and 29-ACGH have only one fixed point, up to translations. For n / ∈ 2N, these rules have no fixed point. Proof. It is clear by examining the transitions codes of these rules that: • For rule 105-ADEH and n = 4k, the configuration (0110) k t = (bfgc) k and its translations are the only fixed points.

Theorem 11 .

 11 The following rules are recurrent for all values of n: 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. The rules 33-ADEFGH and 41-ADEGH are recurrent for n = 3.

  Characteristics of the ECA with no quiescent state (odd Wolfram codeCharacteristics of the ECA with two quiescent states (Wolfram code even and greater than 128

Table 1 :

 1 Notation by transitions. left: table of transitions and their associated labels. right: symmetries of the ECA space (see text for explanations).

	A 000 001 100 101 B C D	A	B	C reflexion	D	conjugation
	010 011 110 111 E F G H	H	G	r+c	F	E
	the rescaled worst expected convergence time as:

Table 2 :

 2 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	unstability of 0-regions
	B	01-frontiers move left
	C	10-frontiers move right
	D	absorption of 0-regions
	E	absorption of 1-regions
	F	01-frontiers move right
	G	10-frontiers move left
	H	unstability of 1-regions

C+ G

random walk of the 10-frontiers 88 so-called minimal representative rules, that is, we will consider for each equivalence class the rule which has the smallest decimal code.

Table 3 :

 3 Table of the 32 possible re-writing triplets in t-images.

	The col-

Table 4 :

 4 Example of the differences of potentials for rule 94 -BCH and a p-linear potential W

Table 5 :

 5 List of the candidates rules in the RCH (top) and RCN (bottom) classes.

		0-EFGH	2-BEFGH	8-EGH	10-BEGH
		18-BCEFGH 24-CEGH	26-BCEGH	32-DEFGH
	RCH	34-BDEFGH 40-DEGH	42-BDEGH	50-
					BCDEFGH
		56-CDEGH	58-BCDEGH 106-BDEH
		4-FGH	5-AFGH	12-GH	13-AGH
	RCN	36-DFGH	44-DGH	72-EH	76-H
		77-AH	104-DEH	200-E	232-DE
	Theorem 4. The rule 178-BCDEFG has a quadratic convergence time.

Table 6 :

 6 List of the non-converging rulesObviously, the first reason why a rule could be non-converging to a fixed point is... if it does not have a fixed point.

	1-AEFGH	3-ABEFGH	6-BFGH	7-ABFGH	9-AEGH	11-ABEGH
	14-BGH	15-ABGH	19-ABCEFGH 22-BCFGH	23-ABCFGH 25-ACEGH
	27-ABCEGH	28-CGH	29-ACGH	30-BCGH	33-ADEFGH 35-ABDEFGH
	37-ADFGH	38-BDFGH	41-ADEGH	43-ABDEGH 45-ADGH	46-BDGH
	51-ABCDEFGH 54-BCDFGH 57-ACDEGH	60-CDGH	62-BCDGH	73-AEH
	105-ADEH	108-DH	110-BDH	126-BCDH	134-BFG	142-BG
	150-BCFG	156-CG
	7.1 Non-existence of fixed points
	Proposition 1. The following rules admit no fixed point: 1-AEFGH, 3-
	ABEFGH, 9-AEGH, 11-ABEGH, 19-ABCEFGH, 25-ACEGH, 27-ABCEGH, 33-ADEFGH,
	35-ABDEFGH, 41-ADEGH, 43-ABDEGH, 51-ABCDEFGH, 57-ACDEGH. They are thus
	non-converging.

Acknowledgements

The author is sincerely grateful for the time and attention of the two anonymous referees. Their remarks considerably helped to improve the presentation of this article.