# Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence

Souvik Roy, Nazim Fatès, Sukanta Das

► To cite this version:

Souvik Roy, Nazim Fatès, Sukanta Das. Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence. Theoretical Computer Science, 2024, 1011, pp.114721. 10.1016/j.tcs.2024.114721. hal-04456320

HAL Id: hal-04456320

https://inria.hal.science/hal-04456320v1

Submitted on 13 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence

Souvik Roy*

Nazim Fatès†

Sukanta Das‡

February 13, 2024

## Abstract

Reversibility is a well-studied property for deterministic cellular automata but it is only partially explored when randomness appears in the update or in the transitions. Here, we present a detailed study of 21 finite-size elementary cellular automata with a fully asynchronous updating and periodic boundary conditions. We estimate their degree of reversibility by counting the number of recurrent configurations as a function of the size of the automaton (number of cells). We show that these rules exhibit various qualitative behaviours: some rules show a “strong reversibility” with a number of recurrent configurations that grows exponentially, while other rules have a “weak reversibility” with a linear growth. We also analyse the structure of the communication graph and report various scaling relations of the number of recurrent communication classes. We identify the cases where the divisibility of the size by 2 or 3 introduces some discontinuities in the behaviour. This study completes the characterization of the 256 elementary cellular automata with regard to their recurrence properties.

## 1 Introduction

Cellular automata (CA) have gained their notoriety in the scientific landscape thanks to the simplicity of their structure: with a discrete space, time and set of states, the mathematical description of their evolution is simple and yet allows one to obtain a wide range of astonishing behaviours. Their mathematical structure also assumes synchronous transitions, which, in some sense, amounts

<footnote>*School of Engineering and Applied Science, Ahmedabad University, Gujarat, India.
svkr89@gmail.com, souvik.roy@ahduni.edu.in</footnote>

<footnote>†Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France. nazim.fates@loria.fr</footnote>

<footnote>‡Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, West Bengal, India. sukanta@it.iiests.ac.in</footnote>
to the hypothesis that there is a global clock that synchronises the transitions of the cells that compose the automaton. Like any hypothesis in a model, the use of such a global clock is perfectly acceptable and sound, but it can also be enlightening to explore an asynchronous updating scheme, with cells applying their transitions randomly and independently. The last two decades have seen an increase in the interest in the study of asynchronous cellular automata (ACA) with various questions raised about their dynamics and asymptotic behaviour [5, 4, 9].

In the CA literature, *reversibility* has been an important property to characterise the behaviour of a rule. It has been studied in the framework of dynamical systems and the first questions were raised in the 1970's [1, 3, 20, 13] where the concept of *backward determinism* was proposed to capture the notion of reversibility: in a system each configuration should have a unique predecessor, a property which amounts to the injectivity of the global transition function. However, this definition of reversibility cannot be transposed in a straightforward way to asynchronous cellular automata, as the non-determinism of the update implies that a configuration may have different successors and in general *does* have many successors.

Following this remark, in a Markovian setting where the state of the systems at time $t+1$ only depends on its state at time $t$, the notion of reversibility for asynchronous systems was identified with the property of *recurrence*, that is, the possibility to return almost surely an infinite number of times to the initial condition [18]. In other words, the notion of reversibility for asynchronous system captures an “eternal return” phenomenon. So far, only a few results have been obtained on this type of reversibility of asynchronous cellular automata [18, 17, 21, 8, 11]. The work of Sarkar et. al. identified that there are some rules where the system can return back to the initial condition following an independent updating scheme [17]. In a different direction, Wacker and Worsch have explored the possibility of constructing inverse rules for asynchronous automata systems [21]. Recently, Phung established the equivalence between reversibility, stable reversibility, and stable injectivity for asynchronous non-uniform cellular automata [11, 12].

In this article, we consider the case of elementary cellular automata (ECA) under a fully asynchronous updating scheme, that is, when a single cell is selected uniformly at random for update. In a previous work, we have identified that 18 minimal representative ECAs, out of 88, would be recurrent in the sense that they would always return to their initial condition an infinite number of times [18]. This study implied that he other rules are partially or totally irreversible, but the “degree of reversibility” of such systems was not evaluated. We thus now aim at quantifying this degree of reversibility by counting the number of recurrent configurations as a function of the size of the configuration. We are particularly interested in studying 21 minimal ECAs which do not show a reversible dynamics and where the classes of recurrence are not all reduced to a fixed point. In the next section we present the mathematical framework we use and then expose the main result in Section 3. The rules are then examined in order from those with a “strong reversibility” to those showing a “weak reversibil-
ity": in Section 4, we present the “almost recurrent” rules where the maximal number of recurrent configurations scales in $2^n$. In Section 5 follows the analysis of the rules with a scaling in $\lambda^n$ where $\lambda$ is non-trivial. Last, in Section 6 are exposed the rules with a weak reversibility, where the number of recurrent configurations is upper-bounded by a linear function. We then conclude with a few words of perspective (Sec. 7).

## 2 Elementary cellular automata

<table><caption>(a) classical ordering (RMT)</caption><thead><tr><th>(x,y,z)</th><th>000</th><th>001</th><th>010</th><th>011</th><th>100</th><th>101</th><th>110</th><th>111</th></tr></thead><tbody><tr><th>RMT</th><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td></tr><tr><th>t-code</th><td>A</td><td>B</td><td>E</td><td>F</td><td>C</td><td>D</td><td>G</td><td>H</td></tr><tr><th>f(x,y,z)</th><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>f(x,y,z)</th><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr></tbody><tfoot><tr><td colspan="9"></td><td>rule</td></tr><tr><td colspan="9"></td><td>232-DE</td></tr><tr><td colspan="9"></td><td>204-I</td></tr></tfoot></table>

<table><caption>Table 1: Table of transitions and their associated labels with two different presentations (RMT order and transition code order). Examples: look-up tables of ECA 232-DE and ECA 204-I (identity rule).</caption><caption>(b) transition code ordering (A, ..., H)</caption><thead><tr><th>(x,y,z)</th><th>000</th><th>001</th><th>100</th><th>101</th><th>010</th><th>011</th><th>110</th><th>111</th></tr></thead><tbody><tr><th>t-code</th><td>A</td><td>B</td><td>C</td><td>D</td><td>E</td><td>F</td><td>G</td><td>H</td></tr><tr><th>RMT</th><td>0</td><td>1</td><td>4</td><td>5</td><td>2</td><td>3</td><td>6</td><td>7</td></tr><tr><th>f(x,y,z)</th><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>f(x,y,z)</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr></tbody><tfoot><tr><td colspan="9"></td><td>rule</td></tr><tr><td colspan="9"></td><td>232-DE</td></tr><tr><td colspan="9"></td><td>204-I</td></tr></tfoot></table>

In this work, we consider one-dimensional binary cellular automata with nearest-neighbour interactions, a model commonly known as elementary cellular automata (ECA). We use periodic boundary conditions, which means that the cells are arranged as a ring; the set of cells' indices is denoted by $\mathcal{L} = \mathbb{Z}/n\mathbb{Z}$, where $n$ is the number of cells. Here, we consider only the case $n > 3$ in order to avoid some exceptions. Each cell has a state in $\{0,1\}$. The collection of all states at a given time is called a configuration and the set of configurations is denoted by $\mathcal{E}_n = \{0, 1\}^\mathcal{L}$.

An ECA is defined by a local transition function $f: \{0,1\}^3 \to \{0,1\}$. This function defines how a cell updates its state according to its own state and the state 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 call a transition active if it changes the state of a cell, i.e., $f(x, y, z) \neq y$, otherwise, it is passive.

Here, the system is updated with a fully asynchronous method, that is, at each time step one cell is selected randomly and uniformly for update. The random sequence of cells that are selected for being updated is denoted by $(U_t)_{t \in \mathbb{N}} \in \mathcal{L}^\mathbb{N}$, where $\mathbb{N} = \{0, 1, \dots\}$ is the set of natural numbers. The evolution of the fully asynchronous ECA from an initial condition $x$ is represented by the stochastic process $(x^t)_{t \in \mathbb{N}}$ and defined recursively by: $x^0 = x$ and $x^{t+1} = F(x^t, U_t)$, with:
$$ \forall i \in \mathcal{L}, x_i^{t+1} = \begin{cases} f(x_{i-1}^t, x_i^t, x_{i+1}^t) & \text{if } i = U_t, \\ x_i^t & \text{otherwise.} \end{cases} $$

In some previous works, transitions were called *rule min terms* (RMT) and an RMT $(x, y, z)$ was indexed by its the number $r = 4x + 2y + z$. In this work, we use another code to identify the transitions: each transition is associated with a letter following the mapping shown on Table 1.

We will denote each ECA $f$ with two complementary codes: a) its classical decimal code $W(f) = f(0,0,0) \cdot 2^0 + f(0,0,1) \cdot 2^1 + \dots + f(1,1,1) \cdot 2^7$. and, b) its transition code $T(f)$, which consists of the concatenation of letters in $\{A, \dots, H\}$ which denote the active transitions of $f$ according to the code presented in Table 1. A rule will be denoted by the couple $W(f) - T(f)$. To illustrate this notation, Table 1 shows the look-up table of the majority rule 232-DE, in which the only active transitions are D and E, or, equivalently, RMT 2 and 5. This table also depicts the identity rule 204-I (here, I stands for identity) where there is no active transition.

There are $2^8 = 256$ ECA rules, which can be reduced to 88 equivalence classes if we use the left-right symmetry and the exchange between 0's and 1's. The rules in each class which have the smallest number are called *minimal representative rules*.

The two homogeneous configurations all-0 and all-1 will be denoted by **0** and **1**, respectively. For $n \in 2\mathbb{N}$, we define $\mathbf{01} = (\mathbf{01})^{n/2}$ and $\mathbf{10} = (\mathbf{10})^{n/2}$; and for $n \in 3\mathbb{N}$, let us introduce $\mathbf{100} = (\mathbf{100})^{n/3}$, $\mathbf{010} = (\mathbf{010})^{n/3}$ and $\mathbf{001} = (\mathbf{001})^{n/3}$.

**Definition 1** A configuration $x \in \mathcal{E}_n$ is called a *fixed point* if we have $F(x, u) = x$ for all $u \in \mathcal{L}$, that is, when all the cells of $x$ are passive. We denote by $\mathcal{F}\mathcal{P}_n$ the set of fixed points of an ECA of size $n$.

# 3 Convergence, Recurrence and Main Result

## 3.1 General definitions

The evolution of our system can be described by a Markov chain over $\mathcal{E}_n$. We now define the recurrence properties of our asynchronous cellular automata using the classical tools from Markov chain theory. We aim at separating the *recurrent* configurations from the *transient* ones. Intuitively, a *transient* configuration is such that there exists a particular sequence of updates which brings the system to a configuration from which it will never be possible to return back to the initial configuration ; by contrast, if the system starts from a *recurrent* recurrent configuration, it will return infinitely often to this configuration.

Given two configurations $x, y \in \mathcal{E}_n$, we say that $y$ is a *successor* of $x$ if there exists an update $u \in \mathcal{L}$ such that $F(x, u) = y$. By iterating the successor relation (zero times or more), we obtain the relation *reachable*: for two arbitrary
configurations $x, y \in \mathcal{E}_n$, we say that $y$ is reachable from $x$ if $y$ can be obtained from $x$ by following a sequence of successor relations, that is, for $k \ge 1$, $\exists k \in \mathbb{N}, \exists(x^i)_{i \in \{0, \dots, k\}}$ such that $x^0 = x$, $x^k = y$ and $\forall i \in \{0, \dots, k-1\}, \exists u_i \in L$; $x^{i+1} = F(x^i, u_i)$. By definition every configuration is reachable from itself. A configuration that is not reachable from any other configuration than itself is *isolated*.

We can now define the recurrence property:

**Definition 2** A configuration $x \in \mathcal{E}_n$ is recurrent if for every configuration $y$ that is reachable from $x$, $x$ is also reachable from $y$. A non-recurrent configuration is transient.

**Definition 3** A rule is recurrent for size $n$ if each configuration of $\mathcal{E}_n$ is recurrent. We say that a rule is recurrent if it is recurrent for all the sizes $n > 3$.

More generally, if $y$ is reachable from $x$ and $x$ is reachable from $y$, we say that $x$ and $y$ communicate. Clearly, the relationship “communicate” is an equivalence relation; this relation partitions the set of configurations into communication classes.

Consequently, two major behaviours exist: for transient configurations, the system remains a finite time in its communication class, then “escapes” this class and never returns back to it. By contrast, when the system starts from a recurrent configuration, it remains in its the communication class of this configuration forever; we call such a class a *recurrent communication class*, or *recurrent class* for short. We denote by $\mathcal{C}(n)$ the number of recurrent classes, where $n$ is the ring size.

Our aim is now to determine, given a cellular automaton $f$ and a ring size $n$, the number of recurrent configurations $\mathcal{R}(n)$. In the case where the growth of $\mathcal{R}$ is exponential, we will be particularly interested in finding the *growth factor* of rule, that is, the constant $\gamma$ such that $\mathcal{R}(n) \sim \gamma^n$. In a second step, we will also evaluate the scaling relations that govern $\mathcal{R}(n)$, the number of recurrent classes.

## 3.2 Recurrent Rules

In our previous work [7, 18], we have identified the ECAs which are recurrent (see Theorem 1 below). Here, we have $\mathcal{R}(n) = 2^n$. Moreover, we also identified the number of communication classes $\mathcal{C}(n)$ for these recurrent rules: these results are summarised below.

**Theorem 1 ([7, 18])** Among the 88 minimal ECA rules, the following 18 rules are recurrent:

<table><tr><td>33-ADEFGH</td><td>35-ABDEFGH</td><td>38-BDFGH</td><td>41-ADEGH</td><td>43-ABDEGH</td></tr><tr><td>46-BDGH</td><td>51-ABCDEFGH</td><td>54-BCDFGH</td><td>57-ACDEGH</td><td>60-CDGH</td></tr><tr><td>62-BCDH</td><td>105-ADEH</td><td>108-DH</td><td>134-BFG</td><td>142-BG</td></tr><tr><td>150-BCFG</td><td>156-CG</td><td>204-I.</td><td></td><td></td></tr></table>
Moreover, the scaling relationship of the number of the communication classes, which are all recurrent classes, are given by:

<table><thead><tr><th>ECAs</th><th>C(n)</th></tr></thead><tbody><tr><td>33, 35, 41, 43, 51, 57</td><td>1</td></tr><tr><td>38, 46, 54, 60, 62</td><td>2</td></tr><tr><td>134, 142, 150</td><td>Linear : { 3 + n/2 if n ∈ 2Z, 2 + ⌊n/2⌋ otherwise.</td></tr><tr><td>105</td><td>Linear : { 2 if n ∈ 2Z + 1, n/2 + 3 if n ∈ 4Z, n/2 otherwise.</td></tr><tr><td>108, 156, 204</td><td>Exponential</td></tr></tbody></table>

### 3.3 The special case of the convergent rules

As a special case where it is relatively easy to evaluate the recurrence properties, there are rules where the fixed points are the only recurrent configurations and where the other configurations are transient.

**Definition 4** A rule is convergent for size n if its recurrent configurations are all fixed points and if all the other configurations are transient. It is convergent if it is convergent for all the sizes n > 3.

The convergent rules were identified in a previous work [19, 8, 6] and we found that there are 50 minimal convergent ECA rules (see Theorem 2 below). We also proposed a recursive procedure, called the fixed point graph, for identifying and counting the number of fixed points of the ECAs [19, 16]. For the convergent rules, all the fixed points form an (isolated) recurrent communication class and we thus have $C(n) = |FP_n|$.

**Theorem 2 ([19, 8])** Among the 88 minimal ECA rules, the following 50 rules are convergent:

<table><tr><td>0-EFGH</td><td>2-BEFGH</td><td>4-FGH</td><td>5-AFGH</td><td>8-EGH</td></tr><tr><td>10-BEGH</td><td>12-GH</td><td>13-AGH</td><td>18-BCEFGH</td><td>24-CEGH</td></tr><tr><td>26-BCEGH</td><td>32-DEFGH</td><td>34-BDEFGH</td><td>36-DFGH</td><td>40-DEGH</td></tr><tr><td>42-BDEGH</td><td>44-DGH</td><td>50-BCDEFGH</td><td>56-CDEGH</td><td>58-BCDEGH</td></tr><tr><td>72-EH</td><td>74-BEH</td><td>76-H</td><td>77-AH</td><td>78-BH</td></tr><tr><td>90-BCEH</td><td>94-BCH</td><td>104-DEH</td><td>106-BDEH</td><td>122-BCDEH</td></tr><tr><td>128-EFG</td><td>130-BEFG</td><td>132-FG</td><td>136-EG</td><td>138-BEG</td></tr><tr><td>140-G</td><td>146-BCEFG</td><td>152-CEG</td><td>154-BCEG</td><td>160-DEFG</td></tr><tr><td>162-BDEFG</td><td>164-DFG</td><td>168-DEG</td><td>170-BDEG</td><td>172-DG</td></tr><tr><td>178-BCDEFG</td><td>184-CDEG</td><td>200-E</td><td>204-I</td><td>232-DE</td></tr></table>

This result allows us to decide the case of many rules: indeed, all these rules but the Identity (ECA 204-I) are non-recurrent. Obviously, we thus have $R(n) = C(n) = |FP_n|$.
Now, our subject of interest is the remaining 21 minimal ECAs. The following theorem depicts the main result.

**Theorem 3 (Main Result)** There are 21 non-recurrent non-convergent minimal ECAs. The number of their recurrent configurations $\mathcal{R}(n)$ and their number of recurrent classes $\mathcal{C}(n)$ verify the relations expressed in Table 2.

<table><caption>Table 2: Synthetic presentation of the number of the different types with the number of their recurrent configurations and recurrent classes.</caption><thead><tr><th>Type</th><th>ECA</th><th>R(n)</th><th>C(n)</th></tr></thead><tbody><tr><td>A1</td><td>3-ABEFGH<br>11-ABEGH<br>19-ABCEFGH<br>25-ACEGH<br>27-ABCEGH</td><td>2<sup>n</sup> - 1</td><td>1</td></tr><tr><td>A2</td><td>37-ADFGH<br>45-ADGH</td><td>2<sup>n</sup> - 1 (n &notin; 3N) or 3 (n &in; 3N)</td><td>1 (n &notin; 3N) or 3 (n &in; 3N)</td></tr><tr><td>B1</td><td>1-AEFGH<br>9-AEGH<br>129-AEFG<br>137-AEG</td><td>~ &phi;<sup>n</sup>,<br>where &phi; is the golden ratio</td><td>1 or 2</td></tr><tr><td>B2</td><td>28-CGH<br>29-ACGH</td><td>~ &lambda;<sup>n</sup>, with &lambda; &approx; 1.52</td><td>~ &mu;<sup>n</sup>, with &mu; &approx; 1.32</td></tr><tr><td>B3</td><td>73-AEH</td><td>~ &lambda;<sup>n</sup>, with &lambda; &approx; 1.84</td><td>~ &mu;<sup>n</sup>, with &mu; &approx; 1.47</td></tr><tr><td>C1</td><td>6-BFGH<br>14-BGH<br>22-BCFGH<br>30-BCGH</td><td>2 (even size) or 2n (odd size)</td><td>2 (even size) or 1 (odd size)</td></tr><tr><td>C2</td><td>7-ABFGH<br>15-ABGH<br>23-ABCFGH</td><td>2 (even size) or 2n (odd size)</td><td>3 (even size) or 2 (odd size)</td></tr></tbody></table>

These results rely on the discussion exposed in the three following sections.

# 4 Quasi-reversible rules

In this section, we present the rules with a growth factor of 2, or for which there exists an exponential growth of $\mathcal{R}(n)$ in $2^n$ when we exclude some particular cases (here, $n \in 3N$). Figures 1 and 3 show typical examples of space-time diagrams produced by these rules. One can observe that for type A1 rules, the system has a highly noisy evolution, with no structure appearing, which easily explains that almost all configurations will be visited. For type A2 rules, one can see that the evolution resembles some noisy arborescent structures which develop on background formed of a repetition of patterns 001. Let us examine these rules formally.

## 4.1 Type A1

**Theorem 4** For the following ECAs 3-ABEFGH, 11-ABEGH, 19-ABCEFGH, 25-ACEGH, 27-ABCEGH the number of recurrent configurations is $\mathcal{R}(n) = 2^n - 1$.
Remark that A, E, G, and H are active for all the rules considered. Moreover, D is passive and B or C is also active for all these rules. The theorem relies on the following properties.

**Proposition 1** *The homogeneous configuration 1 is isolated.*

**Proof:** This is clear since the application of transition D is the only way to reach **1**, but this transition is passive. Moreover, note that since transition H is active, **1** is not reachable from itself in a positive number of steps. □

**Proposition 2** *The configuration 0 is reachable from any configuration.*

**Proof:** This property can be established by observing that for any configuration $x$ different from **0**, it is possible to find an update that will make a **1** disappear. Indeed, for $x = **1**$, transition H applies in all cells. For a configuration $x \neq **1**$, observe that if there is a pattern **11** is present in the configuration, then transitions G is applicable. If $x$ contains no pattern **11** it means that the **1**'s are isolated and transition E can be applied to decrease the number of **1**'s. □

To structure the following proofs, we introduce the notion of a **1-region** (resp. **0-region**): it corresponds to a maximal set of contiguous cells with state **1** (resp. **0**) in a given configuration.

**Proposition 3** *All the configurations different from **1** are reachable from **0**.*

**Proof:** Let us prove that starting from configuration **0**, we can find an update pattern in order to reach a given configuration $x$. Let $i_1, i_2, \dots$ be the positions of the cells which are the left frontiers of a **1-region** in $x$. In other words, for each $i_k$, we have $x_{i_k-1} = 0$ and $x_{i_k} = 1$.

It can be noted that, by definition, the values $i_k$ are separated by at least two (modulo $n$). We can thus update all the cells with index $i_k$ in order to transform them into **1**'s. Note that transition A always applies because we will always find a **0** surrounded by two **0**'s. We thus obtain a configuration $x'$ that has as many **1-regions** as $x$, and each of this **1-region** is of size **1**.

Recall that, transition B or C is active for all the rules considered; without loss of generality, let us assume that transition C is active. In a second step, we can note that for each region, using transition C we can make the **1-region** of $x'$ grow by updating the cells sequentially from left to right in order to make the regions of the current configuration coincide with the regions of $x$. This is done by using transition C only, until we reach $x$ when the last region has been made equal to the last region of $x$.

In the case where transition B is active, the proof is similar by the left-right symmetry. □

As a consequence of Prop. 1, 2, and 3, for all the rules considered in the theorem, we have only a single recurrent communication class ($C(n) = 1$), which consists of all the configurations but **1**, which ends the proof of Theorem 4.
<figure><img src="image_2.png" /><figcaption>Figure 1: Space-time diagrams of ECA 3-ABEFGH and 27-ABCEGH (type A1) for a size $n = 50$. White and blue squares represent cells in states 0 and 1, respectively. Time goes from bottom to top and each line represents the state of the automaton after $n$ random updates. This convention is kept in the rest of the text.</figcaption></figure>
## 4.2 Type A2

**Theorem 5** For the following ECAs 37-ADFGH, 45-ADGH the number of recurrent configurations is:

$$ \mathcal{R}(n) = \begin{cases} 3 & \text{for } n \in 3\mathbb{N} \\ 2^n - 1 & \text{for } n \notin 3\mathbb{N}. \end{cases} $$

This result relies on the following properties, which are all stated for these two rules, where the transitions A, D, G and H are all active.

**Proposition 4** For $n \in 3\mathbb{N}$, 010 is a fixed point, which is reachable from any configuration.

**Proof:** As transition B, C, and E are passive, the cells of 010 are passive and this is a fixed point.

For $n \in 3\mathbb{N}$, let us consider an arbitrary configuration $\alpha$ and show that 010 is reachable from $\alpha$. First, let us show that $\alpha$ can reach a configuration $\beta$ which contains the pattern 010. We make the following disjunction:

a) if $\alpha$ contains 01, then simply remark that $\beta$ either contains 010, and we are done, or it contains 011, in which case we update the third cell in order to make a 010 appear. Indeed, since transitions G and H are both active, the central cell of 11q is active for both $q = 0$ and $q = 1$.

b) if $\alpha$ does not contain 01, then it is either the homogeneous configuration 0, in which case any update creates a pattern 010, or it is the homogeneous configuration 1, in which case two updates separated by two cells, that is, cell $i$ and $i + 2$ for an arbitrary $i \in \mathcal{L}$, makes the 010 pattern appear.

In a second step, let us consider the pattern 010xyz in $\beta$ and let us demonstrate that the pattern xyz can be turned into 010. There are eight cases for the value of xyz. Let us denote these cases by (a), (b), ... (h) according to whether transitions A, B, ..., H respectively apply in xyz.

(a) $xyz = 000$: As transition A is active, we simply update the central cell.

(b) $xyz = 001$: This case is more delicate since the central cell is passive. We propose to apply the following sequence of updates:

$$ \begin{array}{l} 010\ 001 \xrightarrow{A} 010\ 101 \xrightarrow{D} 011\ 101 \xrightarrow{D} 011\ 111 \xrightarrow{G} 011\ 110 \xrightarrow{G} 011\ 100 \xrightarrow{G} \\ 011\ 000 \xrightarrow{G} 010\ 000 \xrightarrow{A} 010\ 010. \end{array} $$

(c) $xyz = 100$: Here too, several updates are needed:

$$ 010\ 100 \xrightarrow{D} 011\ 100 \xrightarrow{G} 011\ 000 \xrightarrow{G} 010\ 000 \xrightarrow{A} 010\ 010. $$

(d) $xyz = 101$: As transition D is active, updating the central cell send us to case (h).

(e) $xyz = 010$: The goal is already attained.

(f) $xyz = 011$: As mentioned above, remark that the third cell ($z$) is necessarily active since transitions G and H are active. Updating this cell makes a 010 appear.
<figure><img src="image_3.png" /><figcaption>Figure 2: Transition from different blocks of states xyz to block 010 with active transition A, D, G, and H. White and blue box represent cells in states 0 and 1 respectively.</figcaption></figure>

(g) $xyz = 110$: As transition G is active, updating the central cell sends us back to case (c).

(h) $xyz = 111$: As seen above, the third cell is necessarily active; updating this cell sends us back to case (g).

The various links between cases and the associated transformations are depicted in Figure 2. By iterating this operation, each block of three cells can thus be turned into an **010**, which shows that **010** is reachable from $\beta$, and thus also reachable from $\alpha$. $\square$ We have thus shown that for $n \in 3N$, the only recurrent configurations are the three fixed points **001**, **010** and **100**.

Let us now study the general case when $n \notin 3N$.

**Proposition 5** *The homogeneous configuration 0 is isolated.*

This is clear since the application of $E$ is the only way to reach **0**, but this transition is passive. Moreover, since transition **A** is active, **0** is not reachable from itself in a positive number of steps.

**Proposition 6** *For $n \notin 3N$, the configuration 1 is reachable from any configuration.*

**Proof:** This property can be established by observing that for any configuration $x$ different from **1**, it is possible to find an update pattern that will increase the number of **1's**.

The increase in the number of **1's** is immediate if $x$ contains a pattern **000** or **101**, that is, if transitions **A** or **D** can be applied.

Let us assume that this is not the case, that is, $x$ contains no **0** surrounded by two **0's** (**000**) and no isolated **0** (**101**). Note that $x$ necessarily contains a pattern **00**; otherwise all the **0's** of $x$ would be isolated, which would contradict the previous hypothesis.

Let us assume that $x$ contains the pattern **11**. Since $x \neq 1$, it also necessarily contains the pattern **110**, and also the pattern **1100**, as the last **0** cannot be
<figure><img src="image_4.png" /><figcaption>Figure 3: Space-time diagrams of ECA 37-ADFGH (type A2) (a) left: $n = 21$, in this example the system reaches a fixed point; (b) right: $n = 20$ in this case, all the configurations except **0** are recurrent.</figcaption></figure>

isolated (101). In this case, remark that we can apply transition G on the second cell, and then transition A on the third cell, and then transition D on the second cell, which gives a pattern 1110 and adds a 1 to the configuration.

The last case to consider is when $x$ contains none of the patterns 000, 101, or 11. Remark that each 00 is necessarily followed by a 1, and that each 001 is necessarily followed by another 001 pattern (because the last 1 can only be followed by 00). This leads to a contradiction with $n \notin 3N$. Indeed, if $x$ is of the form $x = (100)^k\alpha$, then $\alpha = 0$ and $\alpha = 1$ are both impossible because $x$ would contain 000 or 11; and if $x = (100)^k0\beta$ then, again, the two possibilities for $\beta$ lead to a contradiction. This ends the proof of the proposition.

□

**Proposition 7** For $n \notin 3N$, any configuration different from **0** is reachable from **1**.

This property is the symmetric of Prop. 3 by the conjugation operation, i.e., exchanging **0**'s and **1**'s. Here, note that transitions G and H are active.

We can now notice that all the configurations but **0** communicate with configuration **1**. This implies that all the configurations of $E_n\setminus\{0\}$ are recurrent. We thus have $\mathcal{R}(n) = 2^n - 1$ for $n \notin 3N$.

Following the discussion above, $\mathcal{C}(n) = 1$ when $n \notin 3N$. On the other hand, $\mathcal{C}(n) = |\mathbb{F}| = 3$ when $n \in 3N$. The ring size thus introduces a huge discrepancy,
<figure><img src="image_5.png" /><figcaption>Figure 4: Space-time diagrams of ECA 9-AEGH and 137-AEG (type B1).</figcaption></figure>

with two qualitatively different behaviours of the system.

# 5 Rules with a Non-trivial Exponential Number of Recurrent Configurations

In this section, we present the rules which display an exponential number of recurrent configurations, but with an irrational non-trivial growth factor. Figures 4 and 6 display examples of typical space-time diagrams produced by such rules: for type B1, the evolution is noisy and shows no stable part (pairs 11 are avoided). For types B2 and B3, it can be seen that the dynamics of such rules results from the combination of two effects: the creation of stable zones in configuration (stripes in the space-time diagram) and a noisy evolution in the interval between such zones (Fig. 6).

## 5.1 Type B1

**Theorem 6** For the following ACAs: 1-AEFGH, 9-AEGH, 110-BDH, and 126-BCDH, the number of recurrent configurations is $\mathbb{R}(n) \sim \phi^n$, where $\phi$ is the golden ratio.

Let us denote by $\rho$ the set of (circular) configurations which do not contain the pattern 11.
**Proposition 8** For the rules 1-AEFGH and 9-AEGH, respectively, 129-AEFG and 137-AEG, the set of recurrent configurations is $\wp$, and respectively, $\wp \cup \{\mathbf{1}\}$.

**Proof:** In order to prove the proposition above, we proceed in three steps.

(a) Let us show that for 1-AEFGH and 9-AEGH, $\mathbf{0}$ is reachable from any configuration and for 129-AEFG and 137-AEG, $\mathbf{0}$ is reachable from any configuration different from 1.

To see why, simply observe that from any configuration $x \notin \{\mathbf{0}, \mathbf{1}\}$, it is possible to find an update that will make a 1 disappear. Indeed, observe that there exists a cell $i \in \mathcal{L}$, such that $x_i = 1$ and $x_{i+1} = 0$. Such a cell $i$ is active, as either transition E or transition G will be active on it. For the rules 1-AEFGH and 9-AEGH, $\mathbf{0}$ is also reachable from 1, as this configuration is unstable, while for rules 129-AEFG and 137-AEG, it is a fixed point, and thus a recurrent configuration, as transition H is passive.

(b) In a second step, remark that any configuration of $\wp$ can be attained from $\mathbf{0}$. Indeed, we can sequentially update the cells in which we want the 1's to appear: transition A is always active in such cells as they are necessarily a $\mathbf{0}$ surrounded by two $\mathbf{0}$'s.

(c) A configuration of $\varepsilon_n \setminus \wp$ cannot be attained from $\mathbf{0}$. This third property results from the fact that a pair 11 cannot appear by updating a configuration that does not contain it. Indeed, there are only three possibilities to make a 11 appear: $101 \to 111$, $001 \to 011$, or $100 \to 110$, but the three transitions that would respectively apply, namely D, B, and C, are passive. $\square$

To establish Theorem 6, we simply need to count the size of $\wp$. Writing $s_n = \text{card } \wp(n)$, we have: $s_{n+1} = s_n + s_{n-1}$ with $s_2 = 3$ and $s_3 = 4$. This series is called the Lucas series and it is the sequence A000032 in the On-Line Encyclopedia of Integer Sequences (OEIS). We have: $s_n = \phi^n + (-\phi)^{-n}$, where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio.

Note that the result directly applies to minimum representative rules 110-BDH, and 126-BCDH, as they are equivalent to the rules 129-AEFG and 137-AEG by conjugation.

Also note that we have only one recurrent class ($C(n) = 1$) for 1-AEFGH and 9-AEGH, and two recurrent classes for 110-BDH and 126-BCDH ($C(n) = 2$). The communication graph of 9-AEGH is shown on Figure 5 for a size $n = 6$.

## 5.2 Type B2

**Theorem 7** For the following ECAs 28-CGH, 29-ACGH the number of recurrent configurations verifies $\mathbb{R}(n) \sim \lambda^n$, where $\lambda \approx 1.52$.

This result relies on the following property.

**Proposition 9** For the rules 28-CGH, 29-ACGH, a configuration which contains the pattern 111, 1100, or 1000 is transient.

**Proof:** Remark that, C, G, and H are active for the two rules considered.
<figure><img src="image_6.png" /><figcaption>Figure 5: Communication graph for ECA 9-AEGH. An arrow between two configurations indicates a potential transition of the system. Self-loops are removed for the sake of clarity. Note that recurrent states are the configurations which do not contain two consecutive 1's.</figcaption></figure>
(a) Let us assume that a configuration $x$ contains a 111. One can see easily that since transition H is active, its application will increase the number of 1-regions, however, this number can never decrease as the transitions D and E are passive. It will thus not be possible to reach $x$ again.

(b) If a configuration contains a 1100, then by applying transition C we create a pattern 111, which amounts to the previous case.

(c) Similarly, if a configuration contains a 1000, then by applying the transition C twice, we reach a configuration with a 111. □

**Proposition 10** For the rules 28-CGH, 29-ACGH, the configurations which do not contain any of the patterns 111, 000, or 1100 are recurrent.

**Proof:** It can be observed that if a configuration $x$ does not contain one of the three patterns 111, 000, or 1100, then it can be decomposed into a sequence of parts where each part is itself a sequence of length-2 patterns 10 followed by a sequence of 100 or 110 length-3 patterns. In other words, we can write:

$$x = (01)^{i_1}(0q_11)^{j_1} \dots (01)^{i_k}(0q_k1)^{j_k},$$

where $i_1, j_1, \dots, i_k, j_k$ are arbitrary positive integers, $k$ is a non-negative integer, and where $q_1, \dots, q_k$ are arbitrary (binary) states.

In such a configuration $x$, one can see that the only active cells are those where the transition C ($q_i = 0$) or transition G ($q_i = 1$) apply. However, this transformation only changes the state $q_i$, keeping the updated cell active and not creating or removing any other neighbouring active cell. As a consequence, if a configuration $y$ can be reached from $x$ then $x$ can also be reached from $y$, which implies that $x$ is recurrent. The communication class of a configuration $x = (01)^{i_1}(0q_11)^{j_1} \dots (01)^{i_k}(0q_k1)^{j_k}$ is thus formed by the set of size $2^k$ configurations:

$$C_x = \{(01)^{i_1}(0q_11)^{j_1} \dots (01)^{i_k}(0q_k1)^{j_k}; (q_1, \dots, q_k) \in \{0, 1\}^k\}.$$

<figure><img src="image_7.png" /></figure>

Remark, that the homogeneous configuration 0 is a special case:

* For 28-CGH, transition A is passive, therefore, 0 is a fixed point, and as transition E is passive, this is an isolated fixed point, which implies that it is a recurrent configuration.

* For 29-ACGH, 0 is transient because transition A is active, which implies that a pattern 1000 can be created; in other words, it can reach a transient configuration and is therefore transient itself (see above Prop. 9).

To count the recurrent configurations, remark that a configuration is recurrent if it avoids the pattern 111, 000, and 1100. Let $s_n$ be the number of such configurations of size $n$; we have $s_n = s_{n-2} + 2s_{n-3}$ with $s_1 = 0, s_2 = 2, s_3 = 6$ [10]. The first elements of the sequence are 0, 2, 6, 2, 10, 14, 14, 34, 42. The
sequence has index A072328 in the On-Line Encyclopedia of Integer Sequences (OEIS) and we have $s_n \sim \lambda^n$, where $\lambda \approx 1.52$ is the real root of $P(x) = x^3 - x - 2$.

On the other hand, the number of recurrent classes equals the number of partitions of $n$ into blocks of length 2 (pattern 10) and length 3 (patterns 100 and 110). The number of recurrent classes $\mathcal{C}(n)$ thus follows the recurrence equation $\mathcal{C}(n) = \mathcal{C}(n-2) + \mathcal{C}(n-3)$ and it has the index A182097 in the OEIS. We have $\mathcal{C}(n) \sim \mu^n$ with $\mu \approx 1.32$, which is the real root of $P(x) = x^3 - x - 1$.

## 5.3 Type B3

**Theorem 8** For the ECA 73-AEH, the number of recurrent configurations verifies $\mathcal{R}(n) \sim \lambda^n$, where $\lambda \approx 1.84$.

This result relies on the following property.

**Proposition 11** For the rule 73-AEH, a configuration which contains the pattern 111 is transient.

**Proof:** Let us assume that a configuration $x$ contains a 111. One can see easily that since transition H is active, from $x$, one can reach a configuration $y$ which does not contain any 111. Then, remark that from $y$, we can only increase the number of 1's by using active transition A. However, this creates isolated 1's and can never produce a 111 pattern (since B, C and D are passive). Therefore, it will not be possible to reach $x$ again. □

**Proposition 12** For the rule 73-AEH, a configuration which does not contain the pattern 111 is recurrent.

**Proof:** It can be observed that if a configuration $x$ does not contain the pattern 111, then either it is the all-zero configuration 0 or all the 1's it contains are isolated or grouped by two. Formally, up to a given number of shifts, we can write:

$$x = (0110)w_1(0110)w_2\dots(0110)w_k,$$

where $w_1, \dots, w_k$ are words where all the 1's are isolated (they do not contain 11).

In such a configuration, the patterns with 0110 are static, as transitions B, C, D, F and G are passive. Inside the words $w_i$, only A and E apply, and these two transitions imply direct reversibility: if $x$ can reach $y$ by updating a given cell, then $y$ can reach $x$ by updating the same cell. So if $x$ can reach $y'$ with a given sequence of updates, $y'$ can reach $x$ by applying this sequence in reverse order, which implies that $x$ is recurrent. □

To establish Theorem 8, we simply need to count $s_n$, the number of configurations of size $n$ which do not contain the pattern 111. By applying classical combinatorial techniques, we have: $s_{n+1} = s_n + s_{n-1} + s_{n-2}$ with $s_1 = 1$, $s_2 = 3$, $s_3 = 7$ [10]. This sequence has the index A001644 in the OEIS; its first elements are 1, 3, 7, 11, 21, 39, 71 and we have $s_n \sim \lambda^n$, where $\lambda \approx 1.84$ is the real root of the polynomial $P(x) = x^3 - x^2 - x - 1$.
<figure><img src="image_8.png" /><figcaption>Figure 6: Space-time diagrams of ECA 28-CGH (type B2) and ECA 73-AEH (type B3).</figcaption></figure>
To count the number of recurrent classes, simply remark that every configuration $x$ that has the form $x = (0110)w_1(0110)w_2... (0110)w_k$ described above communicates with a configuration $r(x) = (0110)0^{|w_1|}(0110)0^{|w_2|}... (0110)0^{|w_k|}$, where $|w|$ denotes the length of a word $w$. The number of recurrent classes $\mathcal{C}(n)$ is thus formed by the number of circular words which avoid the patterns $010$ and $111$. Indeed, such configurations correspond to all the possible forms for $r(x)$. The same enumeration techniques lead to the following recurrence equation $\mathcal{C}(n) = \mathcal{C}(n-2) + \mathcal{C}(n-3)$, which implies that $\mathcal{C}(n) \sim \mu^n$, where $\mu \approx 1.47$ is the unique real root of $P(x) = x^3 - x^2 - 1$. This corresponds to the A001609 sequence in the OEIS and its first elements are 1, 1, 4, 5, 6, 10, 15, 21, 31.

# 6 Weakly reversible rules

In this section, we present the rules where the reversibility is weak (type C1 and C2). For such rules, the maximal number of recurrent configurations is a linear function. Figure 7 presents a typical example of such evolution: for rule 15-ABGH, one can see that the system is attracted towards one of the two fixed points **01** or **10**, and that in the case of an odd size, this fixed point is not reachable from other configurations, which creates a remaining default which travels right and periodically loops.

**Theorem 9** For the following ECAs 6-BFGH, 7-ABFGH, 14-BGH, 15-ABGH, 22-BCFGH, 23-ABCFGH, 30-BCGH, the number of recurrent configurations is:

$$ \mathcal{R}(n) = \begin{cases} 2 & \text{for } n \in 2\mathbb{N}, \\ 2n & \text{for } n \in 2\mathbb{N} + 1. \end{cases} $$

We remark that for $n \in 2\mathbb{N}$, **01** and **10** are fixed points, since transitions D and E are passive. We also note they are the configurations with a maximal number of 1-regions.

Let us denote by $\eta$ the set of configurations which are equivalent either to $001(01)^{\frac{n-3}{2}}$ or to $011(01)^{\frac{n-3}{2}}$, up to shifts. We remark that for an odd size ($n \in 2\mathbb{N}+1$), $\eta$ is the set of configurations with a maximal number of 1-regions.

Theorem 9 relies on the following property.

**Proposition 13** If $x \neq 0$ is a configuration with $k$ 1-regions, where $k$ is not maximal, then there exists a configuration $y$ with $(k+1)$ 1-regions which is reachable from $x$.

**Proof:**

Let us examine a configuration $x \neq 0$ where the number of 1-regions $k$ is not maximal, that is, with have $k < \lfloor \frac{n}{2} \rfloor$. (An example of such a configuration is 0011010101.)

Remark that B, G and H are active for all the rules considered.

If $x$ contains the pattern 111, then we can directly apply H to increase the number of 1-regions.
<figure><img src="image_9.png" /><figcaption>Figure 7: Space-time diagrams of ECA 15-ABGH (type C2): (a) $n = 20$, the system evolves to a fixed point; (b) $n = 21$ the system converges to a set of recurrent configurations (see text).</figcaption></figure>

If $x$ contains the pattern `0001`, observe that we can apply the transition `B` twice to create a pattern `111`, and we are sent to the previous case.

In the case where $x$ does neither contain `0001` nor `111`, then it necessarily contains the pattern `0011` (otherwise it would have a maximal number of 1-regions). We can thus apply the active transition `G` to obtain a configuration which contains the pattern `0001`, which sends us to the previous case. $\square$

Moreover, if transition `A` is passive, then `0` is an *isolated fixed point*, as transition `E` is passive. It is thus a recurrent configuration. If `A` is active, then `0` is not recurrent: it communicates with the pattern `0001`, and this case has been discussed above.

Let us now examine the case with an odd size.

**Proposition 14** For $n \in 2\mathbb{N}+1$, let $\eta$ be the set of configurations with $k = \lfloor \frac{n}{2} \rfloor$ 1-region. Any configuration of $\eta$ is reachable from any configuration of $\eta$.

**Proof:**

Let $x_i$ be a configuration of $\eta$ which is equivalent by shifts to `001(01)^(n-3)/2` and where $i$ indicates the position of `001`. Similarly, we define $y_i$ as the configuration which is equivalent by shifts to `011(01)^(n-3)/2` and where $i$ indicates the position of `011`.

Let us denote by $x \to y$, the fact that $y$ is reachable from $x$.
<table><caption>Table 3: Sequence of updates showing the communication between the configurations of $\eta$. See the text for the definitions of $x_i$ and $y_i$.</caption><thead><tr><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>(x<sub>1</sub>)</td><td>001010101<br>cbededede</td><td>→</td><td>(y<sub>1</sub>)</td><td>011010101<br>dfgdedede</td><td>→</td><td>(x<sub>3</sub>)</td><td>010010101<br>decbedede</td><td>→</td><td>(y<sub>3</sub>)</td><td>010110101<br>dedfgdede</td><td>→</td></tr><tr><td>(x<sub>5</sub>)</td><td>010100101<br>dedebede</td><td>→</td><td>(y<sub>5</sub>)</td><td>010101101<br>dededfgde</td><td>→</td><td>(x<sub>7</sub>)</td><td>010101001<br>dededecbe</td><td>→</td><td>(y<sub>7</sub>)</td><td>010101011<br>dedededfg</td><td>→</td></tr><tr><td>(x<sub>9</sub>)</td><td>010101010<br>bededede</td><td>→</td><td>(y<sub>9</sub>)</td><td>110101010<br>fgdeded</td><td>→</td><td>(x<sub>2</sub>)</td><td>100101010<br>ecbeded</td><td>→</td><td>(y<sub>2</sub>)</td><td>101101010<br>edfgdeded</td><td>→</td></tr><tr><td>(x<sub>4</sub>)</td><td>101001010<br>edecbeded</td><td>→</td><td>(y<sub>4</sub>)</td><td>101011010<br>ededfgded</td><td>→</td><td>(x<sub>6</sub>)</td><td>101010010<br>ededdecbed</td><td>→</td><td>(y<sub>6</sub>)</td><td>101010110<br>edededfgd</td><td>→</td></tr><tr><td>(x<sub>8</sub>)</td><td>101010100<br>edededdec</td><td>→</td><td>(y<sub>8</sub>)</td><td>101010101<br>gdedededf</td><td>→</td><td>(x<sub>1</sub>)</td><td>001010101<br>cbededede</td><td>→</td><td></td><td></td><td></td></tr></tbody></table>

Let us take a configuration $x_i \in \eta$ and show that: (a) $x_i \to y_i$; (b) $x_i \to x_{i+2}$. (Recall that the indices of the cells are taken modulo $n$.)

We advise the readers to follow the text below with an eye on Table 3. Also note that according to the hypotheses of Theorem 9, transitions B and G are active for all the rules considered.

(a) The property $x_i \to y_i$ is obtained with transition B, which allows us to transform a 001 into a 011.

(b) The property $y_i \to x_{i+2}$ is obtained with transition G, which allows us to transform a 011 into a 001. Observe that the pattern 001 has moved two cells to the right.

As the cells are disposed on a ring, all the configurations of $\eta$ communicate.

Also note that since transitions D and E are passive, the number of 1-regions cannot decrease.

For $n \in 2\mathbb{N} + 1$, the recurrent configurations are the members of the set $\eta$, which are $2n$. When $n$ is even, the only recurrent configurations are the two fixed points **01** and **10**. $\square$

According to the discussion above, for ECAs 7-ABFGH, 15-ABGH, and 23-ABCFGH, as transition A is active, we have only one recurrent class ($C(n) = 1$) when $n$ is odd and two recurrent classes ($C(n) = |\mathbb{F}| = 2$) when $n$ is even. Moreover, when A is passive, as a special case, the configuration **0** creates an additional isolated recurrent class. Therefore, for the ECAs 6-BFGH, 14-BGH, 22-BCFGH, 30-BCGH, we have $C(n) = 2$ when $n$ is odd and $C(n) = 3$ when $n$ is even.

# 7 Conclusion

To sum up, with this last series of results, the situation of the 256 ECA is now fully covered with regard to their main properties of recurrence. We extended the techniques presented for recurrent systems [19, 8, 7, 18] to the case where the recurrence was only partial. We fully characterised the 21 remaining non-recurrent non-convergent ECA rules, counting their number of recurrent configurations and number of recurrent classes.

Taking the scaling laws of the number of recurrent configuration as a criterion, we distinguished three main types of behaviour linked to the partial
recurrence: (a) almost recurrent rules with a maximal number of recurrent con-
figurations that scales in 2ⁿ; (b) partially recurrent rules with a scaling in λⁿ
where λ is non-trivial, and (c) weakly reversible rules, where the number recur-
rent configurations is upper-bounded by a linear function.

Among the different cases, some remarkable behaviours emerged; for in-
stance, rules of type A2 and type C showed a convergent dynamics when the
ring size is divisible by three and two, respectively. We also noted that four rules
(type B1) showed a scaling relation with the golden ratio as a growth factor,
while other type-B rules displayed a growth factor which is the solution of a
polynomial of order 3.

Moreover, we studied the structure of the communication graph and esti-
mated the number of recurrent classes, which also allowed us to exhibit various
scaling relations. We found that some rules had a constant number of recurrent
classes while other rules, such as ECA 28-CGH, 29-ACGH, and 73-AEH this number
grows exponentially.

Natural extensions of this work on the effects of asynchronism and the re-
versibility property raise the following questions:

* What can be said for larger class of rules? For instance, for radius-2 rules, ternary systems, two-dimensional rules, etc.

* In a previous work [15], we explored the structure of the communication classes of the recurrent rules and examined if all the configurations of the communication class were “equally exposed” in the sense that they would have equal frequencies of apparition in the recurrent set. Can we conduct a similar analysis of the “exposition” characteristics for the recurrent classes of the 21 non-convergent non-recurrent rules?

* What can be said about the extension of these results to other asyn-
chronous updating schemes, for instance α-, β- or γ-asynchronism [2], or
delay-sensitive [14] updating schemes?

References

[1] S. Amoroso and Y.N. Patt. Decision procedures for surjectivity and injec-
tivity of parallel maps for tessellation structures. *Journal of Computer and
System Sciences*, 6(5):448–464, 1972.

[2] Olivier Bouré, Nazim Fatès, and Vincent Chevrier. Probing robustness of cellular automata through variations of asynchronous updating. *Natural Computing*, 11(4):553–564, 2012.

[3] Sukanta Das and Biplab K. Sikdar. Characterization of 1-d periodic boundary reversible ca. *Electronic Notes in Theoretical Computer Science*, 252:205–227, 2009.
[4] Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Giancarlo Mauri, and Antonio E. Porreca. Computational complexity of finite asynchronous cellular automata. *Theoretical Computer Science*, 664:131–143, 2017.

[5] Nazim Fatès. A guided tour of asynchronous cellular automata. *Journal of Cellular Automata*, 9(5-6):387–416, 2014.

[6] Nazim Fatès. A tutorial on elementary cellular automata with fully asynchronous updating -general properties and convergence dynamics. *Natural Computing*, 19:179–197, 03 2020.

[7] Nazim Fatès, Biswanath Sethi, and Sukanta Das. *On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View*, pages 313–332. Springer International Publishing, Cham, 2018.

[8] Nazim Fatès, Éric Thierry, Michel Morvan, and Nicolas Schabanel. Fully asynchronous behavior of double-quiescent elementary cellular automata. *Theoretical Computer Science*, 362(1):1–16, 2006.

[9] Qin Lei, Tao Li, Jia Lee, Wen-Li Xu, and Ferdinand Peper. Asynchronous communicating cellular automata: Formalization, robustness and equivalence. *Information Sciences*, 587:335–353, 2022.

[10] Matthew Macauley, Jon McCammond, and Henning S Mortveit. Dynamics groups of asynchronous cellular automata. *Journal of Algebraic Combinatorics*, 33(1):11–35, 2011.

[11] Xuan Kien Phung. On reversible asynchronous non-uniform cellular automata. *arXiv preprint arXiv:2201.13283*, 2022.

[12] Xuan Kien Phung. On invertible and stably reversible non-uniform cellular automata. *Theoretical Computer Science*, 940:43–59, 2023.

[13] D. Richardson. Tessellations with local transformations. *Journal of Computer and System Sciences*, 6(5):373–388, 1972.

[14] Souvik Roy. A study on delay-sensitive cellular automata. *Physica A: Statistical Mechanics and its Applications*, 515:600–616, 2019.

[15] Souvik Roy and Sukanta Das. Asynchronous cellular automata that hide some of the configurations during evolution. *International Journal of Modern Physics C*, 32(04):2150054, 2021.

[16] Souvik Roy and Sukanta Das. Clouds in the basins of fully asynchronous cellular automata. *Advances in Complex Systems*, 25(08):2250013, 2022.

[17] Anindita Sarkar, Anindita Mukherjee, and Sukanta Das. Reversibility in asynchronous cellular automata. *Complex Systems*, 21(1):72–84, 2012.
[18] Biswanath Sethi, Nazim Fatès, and Sukanta Das. Reversibility of elementary cellular automata under fully asynchronous update. In T. V. Gopal, Manindra Agrawal, Angsheng Li, and S. Barry Cooper, editors, *Theory and Applications of Models of Computation*, pages 39–49, Cham, 2014. Springer International Publishing.

[19] Biswanath Sethi, Souvik Roy, and Sukanta Das. Asynchronous cellular automata and pattern classification. *Complexity*, 21(S1):370–386, 2016.

[20] Tommaso Toffoli. Computation and construction universality of reversible cellular automata. *Journal of Computer and System Sciences*, 15(2):213–231, 1977.

[21] Simon Wacker and Thomas Worsch. On completeness and decidability of phase space invertible asynchronous cellular automata. *Fundamenta Informaticae*, 126(2-3):157–181, 2013.