# Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures

Pedro Paulo Balbi, Enrico Formenti, Kévin Perrot, Sara Riva, Eurico Ruivo

► To cite this version:

Pedro Paulo Balbi, Enrico Formenti, Kévin Perrot, Sara Riva, Eurico Ruivo. Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures. 26th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Aug 2020, Stockholm, Sweden. pp.14-28, 10.1007/978-3-030-61588-8_2. hal-03659470

HAL Id: hal-03659470

https://inria.hal.science/hal-03659470

Submitted on 5 May 2022

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
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Non-maximal sensitivity to synchronism in
periodic elementary cellular automata: exact
asymptotic measures

Pedro Paulo Balbi¹, Enrico Formenti², Kévin Perrot³, Sara Riva², and Eurico L. P. Ruivo¹

¹ Universidade Presbiteriana Mackenzie, FCI, São Paulo, Brazil

² Université Côte d'Azur, CNRS, I3S, France

³ Université publique

**Abstract.** In [10] and [12] the authors showed that elementary cellular automata rules 0, 3, 8, 12, 15, 28, 32, 34, 44, 51, 60, 128, 136, 140, 160, 162, 170, 200 and 204 (and their conjugation, reflection, reflected-conjugation) are not maximum sensitive to synchronism, i.e., they do not have a different dynamics for each (non-equivalent) block-sequential update schedule (defined as ordered partitions of cell positions). In this work we present exact measurements of the sensitivity to synchronism for these rules, as functions of the size. These exhibit a surprising variety of values and associated proof methods, such as the special pairs of rule 128, and the connection to the bissection of Lucas numbers of rule 8.

# 1 Introduction

Cellular automata (CAs) are discrete dynamical systems with respect to time, space and state variables, which have been widely studied both as mathematical and computational objects as well as suitable models for real-world complex systems. The dynamics of a CA is locally-defined: every agent (cell) computes its future state based upon its present state and those of its neighbors, that is, the cells connected to it. In spite of their apparent simplicity, CAs may display non-trivial global emergent behavior, some of them even reaching computational universality [3,7]. Originally, CAs are updated in a synchronous fashion, that is, every cell of the lattice is updated simultaneously. However, over the last decade, asynchronous cellular automata have attracted increasing attention in its associated scientific community. A comprehensive and detailed overview of asynchronous CAs is given in [6]. There are different ways to define asynchronism in CAs, be it deterministically or stochastically. Here, we deal with a deterministic version of asynchronism, known as *block-sequential*, coming from the model of Boolean networks and first characterized for this more general model in [2,1]. Under such an update scheme, the lattice of the CA is partitioned into blocks of cells, each one is assigned a priority of being updated, and this priority ordering is kept fixed throughout the time evolution. For the sake of simplicity, from now on, whenever we refer to *asynchronism*, we will mean *block-sequential*, deterministic asynchronism.
In previous works ([10,12]), the notion of *maximum sensitivity to asynchronism* was established. Basically, a CA rule was said to present maximum sensitivity to asynchronism when, for any two different block-sequential update schedules, the rule would yield different dynamics. Out of the 256 elementary cellular automata rules (ECAs), 200 possess maximum sensitivity to asynchronism, while the remaining 56 rules do not. Therefore, it is natural to try and define a *degree* of sensitivity to asynchronism to the latter.

Here, such a notion of a measure to the sensitivity to asynchronism is presented and general analytical formulas for sensitivities of the non-maximal sensitive rules are provided. The results (to be presented on Table 1 at the end of Section 2) exhibit an interesting range of values requiring the introduction of various techniques, from measures tending to 0 (insensitive rules) to measures tending to 1 (almost max-sensitive), with one rule tending to some surprising constant between 0 and 1.

This paper is organized as follows. In Section 2, fundamental definitions and results on Boolean networks, update digraphs and elementary cellular automata are given. In Section 3, formal expressions for the sensitivity to asynchronism of non-max sensitive ECA rules are provided for configurations of arbitrary size. Finally, concluding remarks are made in Section 4.

For lack of space most of the proofs are omitted, we refer the reader to [4].

## 2 Definitions

Elementary cellular automata will be presented in the more general framework of Boolean automata networks, for which the variation of update schedule benefits from useful considerations already studied in the literature. Figure 1 illustrates the definitions.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Left: interaction digraph $G_6^{\text{ECA}}$ of the ECA rule 128 for $n = 6$, with local functions $f_i(x) = x_{i-1} \wedge x_i \wedge x_{i+1}$ for all $i \in \{0, \dots, 5\}$. Right: update digraph corresponding to the update schedules $\Delta = (\{1, 2, 3\}, \{0, 4\}, \{5\})$ and $\Delta' = (\{1, 2, 3\}, \{0\}, \{4\}, \{5\})$, which are therefore equivalent ($\Delta \equiv \Delta'$). For example, $f^{(\Delta)}(111011) = 110000$ whereas for the synchronous update schedule we have $f^{(\Delta^{\text{sync}})}(111011) = 110001$.</figcaption></figure>
## 2.1 Boolean networks

A Boolean Network (BN) of size $n$ is an arrangement of $n$ finite Boolean automata (or components) interacting each other according to a global rule $f$: $\{0, 1\}^n \to \{0, 1\}^n$ which describes how the global state changes after one time step. Let $\llbracket n \rrbracket = \{0, \dots, n-1\}$. Each automaton is identified with a unique integer $i \in \llbracket n \rrbracket$ and $x_i$ denotes the current state of the automaton $i$. A configuration $x \in \{0, 1\}^n$ is a snapshot of the current state of all automata and represents the global state of the BN.

For convenience, we identify configurations with words on $\{0, 1\}^n$. Hence, for example, $01111$ or $01^4$ both denote the configuration $(0, 1, 1, 1, 1)$. Remark that the global function $f: \{0, 1\}^n \to \{0, 1\}^n$ of a BN of size $n$ induces a set of $n$ local functions $f_i: \{0, 1\}^n \to \{0, 1\}$, one per each component, such that $f(x) = (f_0(x), f_1(x), \dots, f_{n-1}(x))$ for all $x \in \{0, 1\}^n$. This gives a static description of a discrete dynamical system, and it remains to set the order in which components are updated in order to get a dynamics. Before going to update schedules, let us first introduce interaction digraphs.

The component $i$ influences the component $j$ if $\exists x \in \{0, 1\}^n: f_j(x) \neq f_j(\bar{x}^i)$, where $\bar{x}^i$ is the configuration obtained from $x$ by flipping the state of component $i$. Note that in literature one may also consider positive and negative influences, but they will not be useful for the present study. The interaction digraph $G_f = (V, A)$ of a BN $f$ represents the effective dependencies among its set of components $V = \llbracket n \rrbracket$ and $A = \{(i, j) | i$ influences $j\}$. It will turn out to be pertinent to consider $\tilde{G}_f = (V, A)$, obtained from $G_f$ by removing the loops (arcs of the form $(i, i)$).

For $n \in \mathbb{N}$, denote $\mathcal{P}_n$ the set of ordered partitions of $\llbracket n \rrbracket$ and $|f|$ the size of a BN $f$. A block-sequential update schedule $\Delta = (\Delta_1, \dots, \Delta_k)$ is an element of $\mathcal{P}_{|f|}$. It defines the following dynamics $f^{(\Delta)}: \{0, 1\}^n \to \{0, 1\}^n$,

$$f^{(\Delta)} = f^{(\Delta_k)} \circ \dots \circ f^{(\Delta_2)} \circ f^{(\Delta_1)} \quad \text{with} \quad f^{(\Delta_j)}(x)_i = \begin{cases} f_i(x) & \text{if } i \in \Delta_j, \\ x_i & \text{if } i \notin \Delta_j. \end{cases}$$

In words, the components are updated in the order given by $\Delta$: sequentially part after part, and in parallel within each part. The parallel or synchronous update schedule is $\Delta^{\text{sync}} = (\llbracket n \rrbracket)$ and we have $f^{(\Delta^{\text{sync}})} = f$. In this article, since only block-sequential update schedules are considered, they are simply called update schedule for short. They are

- “fair” in the sense that all components are updated the exact same number of times,

- “periodic” in the sense that the same ordered partition is repeated.

Given a BN $f$ of size $n$ and an update schedule $\Delta$, the transition digraph $D_{f(\Delta)} = (V, A)$ is such that $V = \{0, 1\}^n$ and $A = \{(x, f^{(\Delta)}(x)) | x \in \{0, 1\}^n\}$. It describes the dynamics of $f$ under the update schedule $\Delta$. The set of all possible dynamics of the BN $f$, at the basis of the measure of sensitivity to synchronism, is then defined as $\mathcal{D}(f) = \{D_{f(\Delta)} | \Delta \in \mathcal{P}_{|f|}\}$.
## 2.2 Update digraphs and equivalent update schedules

For a given BN, some update schedules always give the same dynamics. Indeed, if, for example, two components do not influence each other, their order of updating has no effect on the dynamics (see Example 1 for a detailed example). In [2], the notion of update digraph has been introduced in order to study update schedules.

Given a BN $f$ with loopless interaction digraph $\hat{G}_f = (V, A)$ and an update schedule $\Delta \in \mathcal{P}_n$, define $lab_\Delta : A \to \{\oplus, \ominus\}$ as

$$ \forall (i, j) \in A : lab_{\Delta}((i, j)) = \begin{cases} \oplus & \text{if } i \in \Delta_a, j \in \Delta_b \text{ with } 1 \le b \le a \le k, \\ \ominus & \text{if } i \in \Delta_a, j \in \Delta_b \text{ with } 1 \le a < b \le k. \end{cases} $$

The update digraph $U_{f(\Delta)}$ of the BN $f$ for the update schedule $\Delta \in \mathcal{P}_n$ is the loopless interaction digraph decorated with $lab_\Delta$, i.e., $U_{f(\Delta)} = (V, A, lab_\Delta)$. Note that loops are removed because they bring no meaningful information: indeed, an edge $(i, i)$ would always be labeled $\oplus$. Now we have that, if two update schedules define the same update digraph then they also define the same dynamics.

**Theorem 1 ([2]).** Given a BN $f$ and two update schedules $\Delta, \Delta'$, if $lab_\Delta = lab_{\Delta'}$ then $D_{f(\Delta)} = D_{f(\Delta')}$.

A very important remark is that not all labelings correspond to valid update digraphs, in the sense that there are update schedules giving these labelings. For example, if two arcs $(i, j)$ and $(j, i)$ belong to the interaction digraph and are both labeled $\ominus$, it would mean that $i$ is updated prior to $j$ and $j$ is updated prior to $i$, which is contradictory. Fortunately, there is a nice characterisation of valid update digraphs.

**Theorem 2 ([1]).** Given $f$ with $\hat{G}_f = (V, A)$, the label function $lab : A \to \{\oplus, \ominus\}$ is valid if and only if there is no cycle $(i_0, i_1, \dots, i_k)$, with $i_0 = i_k$ and $k > 0$, such that

$$ - \forall 0 \le j < k : ((i_j, i_{j+1}) \in A \land lab((i_j, i_{j+1})) = \oplus) \lor ((i_{j+1}, i_j) \in A \land lab((i_{j+1}, i_j)) = \ominus), $$

$$ - \exists 0 \le i < k : lab((i_{j+1}, i_j)) = \ominus. $$

In words, Theorem 2 states that a labeling is valid if and only if the multi-digraph where the labeling is unchanged but the orientation of arcs labeled $\ominus$ is reversed, does not contain a cycle with at least one arc label $\ominus$ (forbidden cycle). According to Theorem 1, update digraphs define equivalence classes of update schedules: $\Delta \equiv \Delta'$ if and only if $lab_\Delta = lab_{\Delta'}$. Given a BN $f$, the set of equivalence classes of update schedules is therefore defined as $\mathcal{U}(f) = \{U_{f(\Delta)} | \Delta \in \mathcal{P}_{|f|}\}$.

## 2.3 Sensitivity to synchronism

The sensitivity to synchronism $\mu_s(f)$ of a BN $f$ quantifies the proportion of distinct dynamics w.r.t non-equivalent update schedules. The idea is that when two
or more update schedules are equivalent then $\mu_s(f)$ decreases, while it increase when distinct update schedules bring to different dynamics. More formally, given a BN $f$ we define

$$ \mu_s(f) = \frac{|\mathcal{D}(f)|}{|\mathcal{U}(f)|}. $$

Obviously, it holds that $\frac{1}{|\mathcal{U}(f)|} \le \mu_s(f) \le 1$, and a BN $f$ is as much sensible to synchronism as it has different dynamics when the update schedule varies. The extreme cases are a BN $f$ with $\mu_s(f) = \frac{1}{|\mathcal{U}(f)|}$ that has always the same dynamics $D_{f(\Delta)}$ for any update schedule $\Delta$, and a BN $f$ with $\mu_s(f) = 1$ which has a different dynamics for different update schedules (for each $\Delta \ne \Delta'$ it holds that $D_{f(\Delta)} \ne D_{f(\Delta')}$). A BN $f$ is max-sensitive to synchronism iff $\mu_s(f) = 1$. Note that a BN $f$ is max-sensitive if and only if

$$ \forall \Delta \in \mathcal{P}_{|f|} \forall \Delta' \in \mathcal{P}_{|f|} (\Delta \neq \Delta') \Rightarrow \exists x \in \{0, 1\}^n \exists i \in \llbracket n \rrbracket f^{(\Delta)}(x)_i \neq f^{(\Delta')}(x)_i. \quad (1) $$

## 2.4 Elementary cellular automata

In this study we investigate the sensitivity to synchronism of elementary cellular automata (ECA) over periodic configurations. Indeed, they are a subclass of BN in which all components (also called cells in this context) have the same local rule, as follows. Given a size $n$, the ECA of local function $h: \{0, 1\}^3 \to \{0, 1\}$ is the BN $f$ such that $\forall i \in \llbracket n \rrbracket: f_i(x) = h(x_{i-1}, x_i, x_{i+1})$, where components are taken modulo $n$ (this will be the case throughout all the paper without explicit mention). We use Wolfram numbers [13] to designate each of the 256 ECA local rule $h: \{0, 1\}^3 \to \{0, 1\}$ as the number

$$ w(h) = \sum_{(x_1, x_2, x_3) \in \{0, 1\}^3} h(x_1, x_2, x_3) 2^{2^2 x_1 + 2^1 x_2 + 2^0 x_3}. $$

Given a Boolean function $h: \{0, 1\}^3 \to \{0, 1\}$, consider the following transformations over local rules: $\tau_i(h)(x, y, z) = h(x, y, z)$, $\tau_r(h)(x, y, z) = h(z, y, x)$, $\tau_n(h)(x, y, z) = 1-h(1-z, 1-y, 1-x)$ and $\tau_{rn}(h)(x, y, z) = 1-h(1-z, 1-y, 1-x)$ for all $x, y, z \in \{0, 1\}$. In our context, they preserve the sensitivity to synchronism. For this reason we consider only 88 ECA rules up to $\tau_i$, $\tau_r$, $\tau_n$ and $\tau_{rn}$.

The definitions of Subsection 2.3 are applied to ECA rules as follows. Given a size $n$, the ECA interaction digraph of size $n$ $G_n^{\text{ECA}} = (V, A)$ is such that $V = \llbracket n \rrbracket$ and $A = \{(i+1, i), (i, i+1) \mid i \in \llbracket n \rrbracket\}$.

In [10,12], it is proved that $|\mathcal{U}^{\text{ECA}}(n)| = 3^n - 2^{n+1} + 2$, where $\mathcal{U}^{\text{ECA}}(n)$ is the set of valid labelings of $G_n^{\text{ECA}}$. The sensitivity to synchronism of ECAs is measured relatively to the family of ECAs, and therefore relatively to this count of valid labelings of $G_n^{\text{ECA}}$, even for rules where some arcs do not correspond to effective influences (one may think of rule 0). Except from this subtlety, the measure is correctly defined by considering, for an ECA rule number $\alpha$ and a size $n$, that $h_{\alpha}: \{0, 1\}^3 \to \{0, 1\}$ is its local rule, and that $f_{\alpha,n}: \{0, 1\}^n \to \{0, 1\}^n$ is
its global function on periodic configurations of size $n$, $\forall x \in \{0, 1\}^n f_{\alpha,n}(x)_i = h_{\alpha}(x_{i-1}, x_i, x_{i+1})$. Then, the sensitivity to synchronism of ECA rule number $\alpha$ is given by

$$ \mu_s(f_{\alpha,n}) = \frac{|\mathcal{D}(f_{\alpha,n})|}{3^n - 2^{n+1} + 2} $$

A rule $\alpha$ is ultimately max-sensitive to synchronism when $\lim_{n \to +\infty} \mu_s(f_{\alpha,n}) = 1$. The following result provides a first overview of sensitivity to synchronism.

**Theorem 3 ([10,12]).** For any size $n \ge 7$, the nineteen ECA rules 0, 3, 8, 12, 15, 28, 32, 34, 44, 51, 60, 128, 136, 140, 160, 162, 170, 200 and 204 are not max-sensitive to synchronism. The remaining sixty nine other rules are max-sensitive to synchronism.

Theorem 3 gives a precise measure of sensitivity for the sixty nine maximum sensitive rules, for which $\mu_s(f_{\alpha,n}) = 1$ for all $n \ge 7$, but for the nineteen that are not maximum sensitive it only informs that $\mu_s(f_{\alpha,n}) < 1$ for all $n \ge 7$. In the rest of this paper we study the precise dependency on $n$ of $\mu_s(f_{\alpha,n})$ for these rules, filling the huge gap between $\frac{1}{3^n - 2^{n+1} + 2}$ and $\frac{3^n - 2^{n+1} + 1}{3^n - 2^{n+1} + 2}$. This will offer a finer view on the sensitivity to synchronism of ECA. The results are summarized in Table 1.

<table><caption>**Table 1.** The rules are divided into four classes ($\phi$ is the golden ratio).</caption><thead><tr><th>Class</th><th>Rules (α)</th><th>Sections</th><th>Sensitivity (μ<sub>s</sub>(f<sub>α,n</sub>))</th></tr></thead><tbody><tr><td>I</td><td>0, 51, 200, 204</td><td>3.1</td><td>1 / (3<sup>n</sup> - 2<sup>n+1</sup> + 2) for any n ≥ 3</td></tr><tr><td>II</td><td>3, 12, 15, 34, 60, 136, 170<br>28, 32, 44, 140</td><td>3.2</td><td>2<sup>n</sup> - 1 / (3<sup>n</sup> - 2<sup>n+1</sup> + 2) for any n ≥ 4</td></tr><tr><td>III</td><td>8</td><td>3.3</td><td>φ<sup>2n</sup> + φ<sup>-2n</sup> - 2<sup>n</sup> / (3<sup>n</sup> - 2<sup>n+1</sup> + 2) for any n ≥ 5</td></tr><tr><td>IV</td><td>128, 160, 162</td><td>3.4</td><td>3<sup>n</sup> - 2<sup>n+1</sup> - cn + 2 / (3<sup>n</sup> - 2<sup>n+1</sup> + 2) for any n ≥ 5</td></tr></tbody></table>

## 3 Theoretical measures of sensitivity to synchronism

This section contains the main results of the paper, regarding the dependency on $n$ of $\mu_s(f_{\alpha,n})$ for ECA rules that are not max-sensitive to synchronism. As illustrated in Table 1, the ECA rules can be divided into four classes according to their sensitivity functions. Each class will require specific proof techniques but all of them have interaction digraphs as a common denominator.

As a starting point, one can consider the case of ECA rules have an interaction digraph which is a proper subgraph of $G_n^{\text{ECA}}$. Indeed, when considering them as BN many distinct update schedules give the same labelings and hence, by Theorem 1 and the definition of $\mu_s(f_{\alpha,n})$, they cannot be max-sensitive. This is the case of the following set of ECA rules $S = \{0, 3, 12, 15, 34, 51, 60, 136, 170, 204\}$. Indeed, denoting $G_{f_{\alpha,n}} = ([n], A_{f_{\alpha,n}})$ the interaction digraph of ECA rule $\alpha$ of size $n$ for $\alpha \in S$, one finds $\forall n \ge 3$ and $\forall i \in [n]$:
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 2. Illustration of the chain of influences for some update schedule Δ.</figcaption></figure>

Let us now introduce some useful results and notations that will be widely used in the sequel. Given an update schedule Δ, in order to study the chain of influences involved in the computation of the image at cell $i \in \llbracket n \rrbracket$, define

$$ 
\begin{aligned}
\overleftarrow{\mathbf{d}}_{\Delta}(i) &= \max \{ k \in \mathbb{N} \mid \forall j \in \mathbb{N} : 0 < j < k \implies \mathrm{lab}_{\Delta}((i-j, i-j+1)) = \ominus \} \\
\overrightarrow{\mathbf{d}}_{\Delta}(i) &= \max \{ k \in \mathbb{N} \mid \forall j \in \mathbb{N} : 0 < j < k \implies \mathrm{lab}_{\Delta}((i+j, i+j-1)) = \ominus \}.
\end{aligned}
$$

These quantities are well defined because $k=1$ is always a possible value, and moreover, if $\overleftarrow{\mathbf{d}}_{\Delta}(i)$ or $\overrightarrow{\mathbf{d}}_{\Delta}(i)$ is greater than $n$, then there is a forbidden cycle in the update digraph of schedule $\Delta$ (Theorem 2). Note that for any $\Delta \in \mathcal{P}_n$, $\mathrm{lab}_{\Delta}((i - \overleftarrow{\mathbf{d}}_{\Delta}(i), i - \overleftarrow{\mathbf{d}}_{\Delta}(i) + 1)) = \oplus$ and $\mathrm{lab}_{\Delta}((i + \overrightarrow{\mathbf{d}}_{\Delta}(i), i + \overrightarrow{\mathbf{d}}_{\Delta}(i) - 1)) = \oplus$. See Figure 2 for an illustration. The purpose of these quantities is that it holds for any $x \in \{0, 1\}^n$,

$$ f_{\alpha}^{(\Delta)}(x)_i = r_{\alpha}(\underbrace{\overbrace{\overbrace{\dots, x_{i-1}, x_i}^{r_{\alpha}(x_i, x_{i+1}, \dots)}}}_{\dots}, x_i, \dots) \qquad (2) $$

i.e., the quantities $\overleftarrow{\mathbf{d}}_{\Delta}(i)$ and $\overrightarrow{\mathbf{d}}_{\Delta}(i)$ are the lengths of the chain of influences at cell $i$ for the update schedule $\Delta$, on both sides of the interaction digraph. If the chains of influences at some cell $i$ are identical for two update schedules, then the images at $i$ we be identical for any configuration, as stated in the following lemma.

**Lemma 1.** For any ECA rule $\alpha$, any $n \in \mathbb{N}$, any $\Delta, \Delta' \in \mathcal{P}_n$ and any $i \in \llbracket n \rrbracket$, it holds that

$$ \overleftarrow{\mathbf{d}}_{\Delta}(i) = \overleftarrow{\mathbf{d}}_{\Delta'}(i) \wedge \overrightarrow{\mathbf{d}}_{\Delta}(i) = \overrightarrow{\mathbf{d}}_{\Delta'}(i) \text{ implies } \forall x \in \{0, 1\}^n f_{\alpha,n}^{(\Delta)}(x)_i = f_{\alpha,n}^{(\Delta')}(x)_i. $$

*Proof.* This is a direct consequence of Equation 2, because the nesting of local rules for $\Delta$ and $\Delta'$ are identical at cell $i$. $\square$
For any rule $\alpha$, size $n$, and update schedules $\Delta, \Delta' \in \mathcal{P}_n$, it holds that

$$ \forall i \in \llbracket n \rrbracket : \overleftarrow{d}_{\Delta}(i) = \overleftarrow{d}_{\Delta'}(i) \wedge \overrightarrow{d}_{\Delta}(i) = \overrightarrow{d}_{\Delta'}(i) \iff \Delta \equiv \Delta' \quad (3) $$

and this implies $D_{f_{\alpha,n}^{(\Delta)}} = D_{f_{\alpha,n}^{(\Delta')}}$. Remark that it is possible that $\overleftarrow{d}_{\Delta}(i) + \overrightarrow{d}_{\Delta}(i) \ge n$, in which case the image at cell $i$ depends on the whole configuration. Moreover the previous inequality may be strict, meaning that the dependencies on both sides may overlap for some cell. This will be a key in computing the dependency on $n$ of the sensitivity to synchronism for rule 128 for example. Let $d_{\Delta}(i) = \{j \le i | i - j \le \overleftarrow{d}_{\Delta}(i)\} \cup \{j \ge i | j - i \le \overrightarrow{d}_{\Delta}(i)\}$ be the set of cells that $i$ depends on under update schedule $\Delta \in \mathcal{P}_n$. When $d_{\Delta}(i) \ne \llbracket n \rrbracket$ then cell $i$ does not depend on the whole configuration, and $d_{\Delta}(i)$ describes precisely $\Delta$, as stated in the following lemma.

**Lemma 2.** For any $\Delta, \Delta' \in \mathcal{P}_n$, it holds that $\forall i \in \llbracket n \rrbracket \ d_{\Delta}(i) = d_{\Delta'}(i) \ne \llbracket n \rrbracket$ implies $\Delta \equiv \Delta'$.

*Proof.* If $d_{\Delta}(i) \ne \llbracket n \rrbracket$ then $\overleftarrow{d}_{\Delta}(i)$ and $\overrightarrow{d}_{\Delta}(i)$ do not overlap. Moreover, remark that $\overleftarrow{d}_{\Delta}(i)$ and $\overrightarrow{d}_{\Delta}(i)$ can be deduced from $d_{\Delta}(i)$. Indeed, $\overleftarrow{d}_{\Delta}(i) = \max\{j | \forall k \in \llbracket j \rrbracket, i - j + k \in d_{\Delta}(i)\}$ and $\overrightarrow{d}_{\Delta}(i) = \max\{j | \forall k \in \llbracket j \rrbracket, i + j - k \in d_{\Delta}(i)\}$. The result follows since knowing $\overleftarrow{d}_{\Delta}(i)$ and $\overrightarrow{d}_{\Delta}(i)$ for all $i \in \llbracket n \rrbracket$ allows to completely reconstruct $\mathrm{lab}_{\Delta}$, which would be the same as $\mathrm{lab}_{\Delta'}$ if $d_{\Delta}(i) = d_{\Delta'}(i)$ for all $i \in \llbracket n \rrbracket$ (Formula 3). $\square$

## 3.1 Class I: Insensitive rules

This class contains the simplest dynamics with sensitivity function $\frac{1}{3^n - 2^{n+1} + 2}$.

**Theorem 4.** $\mu_s(f_{0,n}) = \frac{1}{3^n - 2^{n+1} + 2}$ for any $n \ge 1$ and for $\alpha \in \{0, 51, 204\}$.

*Proof.* The result for ECA rule 0 is obvious since $\forall n \ge 1 : \forall x \in \{0, 1\}^n : f_{0,n}(x) = 0^n$. The ECA Rule 51 is based on the boolean function $r_{51}(x_{i-1}, x_i, x_{i-1}) = \neg x_i$ and ECA rule 204 is the identity. Therefore, similarly to ECA rule 0, for any $n$ their interaction digraph has no arcs. Hence, there is only one equivalence class of update digraph, and one dynamics. $\square$

The ECA rule 200 also belongs to Class I and it is based on the following local function $r_{200}(x_1, x_2, x_3) = x_2 \wedge (x_1 \vee x_3)$. Indeed, it is almost equal to the identity (ECA rule 204), except for $r_{200}(0, 1, 0) = 0$. It turns out that, even if its interaction digraph has all of the $2n$ arcs, this rule produces always the same dynamics, regardless of the update schedule.

**Theorem 5.** $\mu_s(f_{200,n}) = \frac{1}{3^n - 2^{n+1} + 2}$ for any $n \ge 1$.

*Proof.* We prove that $f_{200,n}^{(\Delta)}(x) = f_{200,n}^{(\Delta^{\text{sync}})}(x)$ for any configuration $x \in \{0, 1\}^n$ and for any update schedule $\Delta \in \mathcal{P}_n$. For any $i \in \llbracket n \rrbracket$ such that $x_i = 0$, the ECA rule 200 is the identity, therefore it does not depend on the states of its neighbors
which may have been updated before itself, i.e., $f_{200,n}^{(\Delta)}(x)_i = 0 = f_{200,n}^{(\Delta_{sync})}(x)_i$.
Moreover, for any $i \in \mathbb{N}$ such that $x_i = 1$, if its two neighbors $x_{i-1}$ and $x_{i+1}$ are
both in state 0 then they will remain in state 0 and $f_{200,n}^{(\Delta)}(x)_i = 0 = f_{200,n}^{(\Delta_{sync})}(x)_i$;
otherwise, the ECA 200 is the identity map and the two neighbors of cell $i$ also
apply the identity, thus again $f_{200,n}^{(\Delta)}(x)_i = 1 = f_{200,n}^{(\Delta_{sync})}(x)_i$. $\square$

**3.2 Class II: Low sensitivity rules**

This class contains rules whose sensitivity function equals $\frac{2^n-1}{3^n-2^{n+1}+2}$. This is a
very interesting class that demands the development of specific arguments and
tools. However, the starting point is always the interaction digraph.

**One-way ECAs.** The following result counts the number of equivalence classes of update schedules for ECA rules $\alpha$ having only arcs of the form $(i, i+1)$, or only arcs of the form $(i+1, i)$ in their interaction digraph $G_{f_{\alpha,n}}$.

**Lemma 3.** For the ECA rules $\alpha \in \{3, 12, 15, 34, 60, 136, 170\}$, it holds that
$|\mathcal{U}(f_{\alpha,n})| \le 2^n - 1$.

*Proof.* The interaction digraph of these rules is the directed cycle on $n$ vertices (with $n$ arcs). There can be only a forbidden cycle of length $n$ in the case that all arcs are labeled $\ominus$ (see Theorem 2). Except for the all $\oplus$ labeling (which is valid), any other labeling prevents the formation of an invalid cycle, since the orientation of at least one arc is unchanged (labeled $\oplus$), and the orientation of at least one arc is reversed (labeled $\ominus$). $\square$

In the sequence, we are going to exploit Lemma 3 to obtain one of the main
results of this section. The ECA rule 170, which is based on the following Boolean
function: $r_{170}(x_{i-1}, x_i, x_{i+1}) = x_{i+1}$, shows the pathway.

**Theorem 6.** $\mu_s(f_{170,n}) = \frac{2^n-1}{3^n-2^{n+1}+2}$ for any $n \ge 2$.

*Proof.* Let $f = f_{170,n}$ and $n \ge 2$. By definition, one finds that for any two non-
equivalent update schedules $\Delta \not= \Delta'$ it holds that $\exists i_0 \in \mathbb{N} \ lab_{\Delta}((i_0+1, i_0)) = \oplus$
and $lab_{\Delta'}((i_0+1, i_0)) = \ominus$. Furthermore, since having $lab_{\Delta'}((i+1, i)) = \ominus$ for
all $i \in \mathbb{N}$ creates an invalid cycle of length $n$, there exists a minimal $\ell \ge 1$ such
that $lab_{\Delta'}((i_0 + \ell + 1, i_0 + \ell)) = \oplus$ (this requires $n > 1$). A part of the update
digraph corresponding to $\Delta'$ is pictured below.

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

By definition of the labels and the minimality of $\ell$ we have that for all $0 \le k < \ell$
it holds that $f^{(\Delta')}(x)_{i_0+k} = x_{i_0+\ell+1}$. Since for the update schedule $\Delta$ we have
$f^{(\Delta)}(x)_{i_0} = x_{i_0+1}$, it is always possible to construct a configuration $x$ with
$x_{i_0+1} \ne x_{i_0+\ell+1}$ such that the two dynamics differ, i.e., $f^{(\Delta)}(x)_{i_0} \ne f^{(\Delta')}(x)_{i_0}$.
The result holds by Formula 1. $\square$

Generalizing the idea behind the construction used for ECA rule 170 one may
prove that ECA rules 3, 12, 15, 34, 60, 136 have identical sensitivity function.
**Exploiting patterns in the update digraph.** We are now going to develop a proof technique which characterizes the number of non-equivalent update schedules according to the presence of specific patterns in their interaction digraph. This will concern ECA rules 28, 32, 44 and 140. When $n$ is clear from the context, we will simply denote $f_\alpha$ instead of $f_{\alpha,n}$ with $\alpha \in \{28, 32, 44, 140\}$. We present ECA rule 32 which is based on the Boolean function $r_{32}(x_1, x_2, x_3) = x_1 \wedge \neg x_2 \wedge x_3$, the reasoning for rules 28, 44 and 140 are analogous.

**Lemma 4.** Fix $n \in \mathbb{N}$. For any update schedule $\Delta \in \mathcal{P}_n$, for any configuration $x \in \{0,1\}^n$ and for any $i \in \llbracket n \rrbracket$, the following holds: $f_{32}^{(\Delta)}(x)_i = 1$ iff $\mathrm{lab}_\Delta((i+1, i)) = \mathrm{lab}_\Delta((i-1, i)) = \oplus$ and $(x_{i-1}, x_i, x_{i+1}) = (1, 0, 1)$.

**Corollary 1.** Fix $n \in \mathbb{N}$. For any update schedule $\Delta \in \mathcal{P}_n$, for any configuration $x \in \{0,1\}^n$ and $i \in \llbracket n \rrbracket$, if $\mathrm{lab}_\Delta((i-1, i)) = \ominus$ or $\mathrm{lab}_\Delta((i+1, i)) = \ominus$, then $f_{32}^{(\Delta)}(x)_i = 0$.

**Lemma 5.** For any $n \in \mathbb{N}$, consider $\Delta, \Delta' \in \mathcal{P}_n$. Then, $D_{f_{32,n}^{(\Delta)}} \neq D_{f_{32,n}^{(\Delta')}}$ if and only if there exists $i \in \llbracket n \rrbracket$ such that one of the following holds:

1. $\mathrm{lab}_\Delta((i+1, i)) = \mathrm{lab}_\Delta((i-1, i)) = \oplus$ and either $\mathrm{lab}_{\Delta'}((i+1, i)) = \ominus$ or $\mathrm{lab}_{\Delta'}((i-1, i)) = \ominus$;

2. $\mathrm{lab}_{\Delta'}((i+1, i)) = \mathrm{lab}_{\Delta'}((i-1, i)) = \oplus$ and either $\mathrm{lab}_{\Delta}((i+1, i)) = \ominus$ or $\mathrm{lab}_{\Delta}((i-1, i)) = \ominus$.

**Theorem 7.** $\mu_s(f_{\alpha,n}) = \frac{2^n-1}{3^{n-2^{n+1}+2}}$ for any $n > 3$ and for all ECA rules $\alpha \in \{28, 32, 44, 140\}$.

*Proof.* Given a configuration of length $n > 3$, the patterns in Lemma 4 may be present in $k$ cells out of $n$ with $1 \le k \le n$ (it must be present in at least one cell because otherwise we would have a $\ominus$ cycle). Therefore, there are $\sum_{k=1}^n \binom{n}{i} = 2^n - 1$ different dynamics. The proof for the ECA rules 28, 44, 140 is similar. $\square$

### 3.3 Class III: Medium sensitivity rules

This subsection is concerned uniquely with ECA Rule 8 which is based on the following Boolean function $r_8(x_1, x_2, x_3) = \neg x_1 \wedge x_2 \wedge x_3$. As will be seen, finding the expression of sensitivity function for this rule is somewhat peculiar and requires to develop specific techniques. The sensitivity function obtained tends to $\frac{1+\phi}{3}$, where $\phi$ is the golden ratio.

**Remark 1.** For any $x_1, x_3 \in \{0,1\}$, it holds that $r_8(x_1, 0, x_3) = 0$. Hence, for any update schedule a cell that is in state 0 will remain in state 0 forever.

We will first see in Lemma 6 that as soon as two update schedules differ on the labeling of an arc $(i, i-1)$, then the two dynamics are different. Then, given two update schedules $\Delta, \Delta'$ such that $\mathrm{lab}_\Delta((i, i-1)) = \mathrm{lab}_{\Delta'}((i, i-1))$ for all $i \in \llbracket n \rrbracket$, Lemmas 7 and 8 will respectively give sufficient and necessary conditions for the equality of the two dynamics.
**Lemma 6.** Consider two update schedules $\Delta, \Delta' \in \mathcal{P}_n$ for $n \ge 3$. If there exists $i \in [n]$ such that $lab_\Delta((i, i-1)) \neq lab_{\Delta'}((i, i-1))$, then $D_{f_{8,n}^{(\Delta)}} \neq D_{f_{8,n}^{(\Delta')}}$.

Now consider two update schedules $\Delta, \Delta'$ whose labelings are equal on all counter-clockwise arcs (i.e., of the form $(i, i-1)$). Lemma 7 states that, if $\Delta$ and $\Delta'$ differ only on one arc $(i-1, i)$ such that $lab_\Delta((i+1, i)) = lab_{\Delta'}((i+1, i)) = \emptyset$, then the two dynamics are identical. By transitivity, if there are more differences but only on arcs of this form, then the dynamics are also identical.

**Lemma 7.** Suppose $\Delta$ and $\Delta'$ are two update schedules over a configuration of length $n \ge 3$ and there is $i \in [n]$ such that

$$-lab_\Delta((i+1, i)) = lab_{\Delta'}((i+1, i)) = \emptyset;$$

$$-lab_\Delta((i-1, i)) \neq lab_{\Delta'}((i-1, i));$$

$$-lab_\Delta((j_1, j_2)) = lab_{\Delta'}((j_1, j_2)), \text{ for all } (j_1, j_2) \neq (i-1, i).$$

$$\text{Then } D_{f_{8,n}^{(\Delta)}} = D_{f_{8,n}^{(\Delta')}}.$$

Lemma 8 states that, as soon as $\Delta$ and $\Delta'$ differ on arcs of the form $(i-1, i)$ such that $lab_\Delta((i+1, i)) = lab_{\Delta'}((i+1, i)) = \emptyset$, then the two dynamics are different (remark that in this case we must have $lab_\Delta((i, i-1)) = lab_{\Delta'}((i, i-1)) = \emptyset$, otherwise one of $\Delta$ or $\Delta'$ has an invalid cycle of length two between the nodes $i-1$ and $i$). This lemma can be applied if at least one cell of the configuration contains the pattern.

**Lemma 8.** For $n \ge 5$, consider two update schedules $\Delta, \Delta' \in \mathcal{P}_n$. If there exists (at least one cell) $i \in [n]$ such that

$$-lab_\Delta((i+1, i)) = lab_{\Delta'}((i+1, i)) = \emptyset;$$

$$-lab_\Delta((i-1, i)) \neq lab_{\Delta'}((i-1, i));$$

$$-lab_\Delta((j, j-1)) = lab_{\Delta'}((j, j-1)), \text{ for all } j \in [n];$$

$$\text{then } D_{f_{8,n}^{(\Delta)}} \neq D_{f_{8,n}^{(\Delta')}}.$$

Lemmas 6, 7 and 8 characterize completely for rule 8 the cases when two update schedules $\Delta, \Delta'$ lead to the same dynamics (i.e., $D(f_{8,n}^{(\Delta)}) = D(f_{8,n}^{(\Delta')})$, or different dynamics (i.e., $D(f_{8,n}^{(\Delta)}) \neq D(f_{8,n}^{(\Delta')})$). Indeed, Lemma 6 shows that counting $|D(f_{8,n})|$ can be partitioned according to the word given by $lab_\Delta((i, i-1))$ for $i \in [n]$, and then for each labeling of the $n$ arcs of the form $(i, i-1)$, Lemmas 7 and 8 provide a way of counting the number of dynamics.

**Theorem 8.** $\mu_s(f_{8,n}) = \frac{\phi^{2n}+\phi^{-2n}-2^n}{3^n-2^{n+1}+2}$ for any $n \ge 5$, with $\phi = \frac{1+\sqrt{5}}{2}$.

## 3.4 Class IV: Almost max-sensitive rules

This last class contains three ECA rules, namely 128, 160 and 162, for which the sensitivity function tends to 1. The study of sensitivity to synchronism for these rules is based on the characterization of pairs of update schedule leading to the same dynamics. A pair of update schedules $\Delta, \Delta' \in \mathcal{P}_n$ is special for rule $\alpha$ if
$\Delta \not\equiv \Delta'$ but $D_{f_{\alpha,n}}^{(\Delta)} = D_{f_{\alpha,n}}^{(\Delta')}$. We will count the special pairs for rules 128 (the reasoning for 160 and 162 is similar). Given an update schedule $\Delta \in \mathcal{P}_n$, define the left rotation $\sigma(\Delta)$ and the left/right exchange $\rho(\Delta)$, such that, $\forall i \in \llbracket n \rrbracket$ it holds that $\mathrm{lab}_{\sigma(\Delta)}((i,j)) = \mathrm{lab}_{\Delta}((i+1,j+1))$ and $\mathrm{lab}_{\rho(\Delta)}((i,j)) = \mathrm{lab}_{\Delta}((j,i))$. It is clear that if a pair of update schedules $\Delta, \Delta' \in \mathcal{P}_n$ is special then $\sigma(\Delta), \sigma(\Delta')$ is also special. Furthermore, when rule $\alpha$ is left/right symmetric (meaning that $\forall x_1, x_2, x_3 \in \{0, 1\}$ we have $r_\alpha(x_1, x_2, x_3) = r_\alpha(x_3, x_2, x_1)$, which is the case of rules 128 and 162, but not 160) then $\rho(\Delta), \rho(\Delta')$ is also special. We say that special pairs in a set $S$ are disjoint when no update schedule belongs to more than one pair i.e., if three update schedules $\Delta, \Delta', \Delta'' \in S$ are such that both $(\Delta, \Delta')$ and $(\Delta, \Delta'')$ are special pairs then $\Delta' = \Delta''$. When it is clear from the context, we will omit to mention the rule relative to which some pairs are special.

**ECA rule 128.** The Boolean function associated with the ECA rule 128 is $r_{128}(x_1, x_2, x_3) = x_1 \land x_2 \land x_3$. Its simple definition will allow us to better illustrate the role played by special pairs. When $\mathbf{d}_{\Delta}(i) = \llbracket n \rrbracket$ for some cell $i$, the only possibility to get $f_{128}^{(\Delta)}(x)_i = 1$ is $x = 1^n$. However for $x = 1^n$ we have $f_{128}^{(\Delta)}(x)_i = 1$ for any $\Delta$. The previous remark combined with an observation in the spirit of Lemma 2, gives the next characterization. Let us introduce the notation $\mathbf{d}_{\Delta} = \mathbf{d}_{\Delta'}$ for cases in which $\mathbf{d}_{\Delta}(i) = \mathbf{d}_{\Delta'}(i)$ holds in every cell $i \in \llbracket n \rrbracket$.

**Lemma 9.** For any $n \in \mathbb{N}$, choose $\Delta, \Delta' \in \mathcal{P}_n$ such that $\Delta \not\equiv \Delta'$. Then, $\mathbf{d}_{\Delta} = \mathbf{d}_{\Delta'}$ if and only if $D_{f_{128,n}}^{(\Delta)} = D_{f_{128,n}}^{(\Delta')}$.

Lemma 9 characterizes exactly the pairs of non-equivalent update schedules for which the dynamics of rule 128 differ, i.e., the set of special pairs for rule 128, which are the set pairs $\Delta, \Delta' \in \mathcal{P}_n$ such that $\Delta \not\equiv \Delta'$ but $\mathbf{d}_{\Delta} = \mathbf{d}_{\Delta'}$. Computing $\mu_s(f_{128,n})$ is now the combinatorial problem of computing the number of possible $\mathbf{d}_{\Delta}$ for $\Delta \in \mathcal{P}_n$. However, remark that Lemma 9 does not hold for all rules, since some of them are max-sensitive, even though there exists $\Delta \not\equiv \Delta'$ with $\mathbf{d}_{\Delta}(i) = \mathbf{d}_{\Delta'}(i)$ for all $i \in \llbracket n \rrbracket$.

We prove that for any $n > 6$, there exist $10n$ disjoint special pairs of schedules of size $n$ (Lemma 12). We first state that special pairs differ in the labeling of exactly one arc (Lemma 11), then establish the existence of $10n$ special pairs of schedules of size $n$ (which come down to five cases up to rotation and left/right exchange) and finally prove that these pairs are disjoint. This gives Theorem 9. These developments make heavy use of the following lemma (see Figure 3).

<figure><img src="image_7.png" /><figcaption>**Fig. 3.** Illustration of Lemma 10, with $\Delta$ in blue and $\Delta'$ in red: hypothesis on the labelings of arc (1,0) imply many $\ominus$ (resp. $\oplus$) labels on arcs of the form $(j,j+1)$ (resp. $(j+1,j)$), for $\Delta$.</figcaption></figure>
**Lemma 10.** For any $n \ge 4$, consider a special pair $\Delta, \Delta' \in \mathcal{P}_n$ for rule 128 s. t. $\mathrm{lab}_\Delta((i+1,i)) = \oplus$ and $\mathrm{lab}_{\Delta'}((i+1,i)) = \ominus$ for some $i \in \lfloor n \rfloor$. For all $j \in \lfloor n \rfloor \setminus \{i, i+1, i+2\}$, it holds that $\mathrm{lab}_\Delta((j,j+1)) = \ominus$ and $\mathrm{lab}_\Delta((j+1,j)) = \oplus$.

**Lemma 11.** For any $n > 6$, if $\Delta, \Delta' \in \mathcal{P}_n$ is a special pair for rule 128, then $\Delta$ and $\Delta'$ differ on the labeling of exactly one arc.

**Lemma 12.** For any $n > 6$, there exist $10n$ disjoint special pairs of size $n$ for rule 128.

As a consequence of Lemma 12 we have $|\{d_\Delta | \Delta \in \mathcal{P}_n\}| = 3^n - 2^{n+1} - 10n + 2$ for any $n > 6$, and the result follows from Lemma 9. For the ECA rule 160 (resp., 162) the number of special pairs is $12n$ (resp., $n$).

**Theorem 9.** $\mu_s(f_{\alpha,n}) = \frac{3^n - 2^{n+1} - c_\alpha n + 2}{3^n - 2^{n+1} + 2}$ for any $n > 6$ and $\alpha \in \{128, 160, 162\}$, with $c_{128} = 10$, $c_{160} = 12$ and $c_{162} = 1$.

# 4 Conclusion and perspectives

Asynchrony highly impacts the dynamics of CAs and new original dynamical behaviors are introduced. In this new model, the dynamics become dependent from the update schedule of cells. However, not all schedules produce original dynamics. For this reason, a measure to quantify the sensitivity of ECA w.r.t to changes of the update schedule has been introduced in [12]. All ECA rules were then classified into two classes: max-sensitive and non-max sensitive.

This paper provides a finer study of the sensitivity measure w.r.t the size of the configurations. Indeed, we found that there are four classes (see Table 1). In particular, it is interesting to remark that the asymptotic behavior is not dichotomic, i.e., the sensitivity function does not always either go to 0 or to 1 when the size of configurations grows. The ECA rule 8 when considered as a classical ECA (i.e., when all cells are updated synchronously) has a very simple dynamical behavior but its asynchronous version has a sensitivity to asynchronism function which tends to $\frac{1+\phi}{3}$ when $n$ tends to infinity ($\phi$ being the golden ratio). Remark that in the classical case, the limit set of the ECA rule 8 is the same as ECA rule 0 after just two steps. It would be interesting to understand which are the relations between the limit set (both in the classical and in the asynchronous cases) and the sensitivity to asynchronism. Indeed, remark that in our study the sensitivity is defined on one step of the dynamics. It would be interesting to compare how changes the sensitivity function of an ECA when the limit set is considered. This idea has been investigated in works on block-invariance [8,9], with the difference that it concentrates only on the set of configurations in attractors, and discards the transitions within these sets.

Remark also that this study focus on block-sequential updating schemes. However, block-parallel update schedules are gaining growing interest [5]. It is a promising research direction to investigate how the sensitivity functions change when block-parallel schedules are considered. Another interesting research direction would consider the generalization of our study to arbitrary CA in order to
verify if a finer grained set of classes appear or not. Maybe, the set of possible
functions is tightly related to the structure of the neighborhood. Finally, another
possible generalization would consider infinite configurations in the spirit of [11].
However, it seems much more difficult to come out with precise asymptotic re-
sults in this last case.

**Acknowledgments.** The work of KP was funded mainly by his salary as a French State agent, affiliated to Aix-Marseille Univ, Univ. de Toulon, CNRS, LIS, France, and to Univ. Côte d'Azur, CNRS, I3S, France, and secondarily by ANR-18-CE40-0002 FANs project, ECOS-Sud C16E01 project, STIC AmSud CoDANet 19-STIC-03 (Campus France 43478PD) project. P.P.B. thanks the Brazilian agencies CAPES and CNPq for the projects CAPES 88881.197456/2018-01, CAPES-Mackenzie PrInt project 88887.310281/2018-00 and CNPq-PQ 305199/2019-6.

References

1. Julio Aracena, Eric Fanchon, Marco Montalva, and Mathilde Noual. Combina-
torics on update digraphs in boolean networks. *Discrete Applied Mathematics*,
159(6):401–409, 2011.

2. Julio Aracena, Eric Goles, Andrès Moreira, and Lilian Salinas. On the robustness of update schedules in boolean networks. *Biosystems*, 97:1–8, 2009.

3. Matthew Cook. Universality in elementary cellular automata. *Complex Systems*, 15(1):1–40, 2004.

4. Pedro PB de Oliveira, Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico LP Ruivo. Non-maximal sensitivity to synchronism in periodic elementary cellular automata: exact asymptotic measures. *Preprint on arXiv:2004.07128*, 2020.

5. Jacques Demongeot and Sylvain Sené. About block-parallel boolean networks: a position paper. *Nat. Comput.*, 19(1):5–13, 2020.

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

7. Martin Gardner. Mathematical games: The fantastic combinations of John Con-
way's new solitaire game "Life". *Scientific American*, 223(4):120–123, 1970.

8. Eric Goles, Marco Montalva-Medel, Stéphanie Maclean, and Henning S. Mortveit. Block invariance in a family of elementary cellular automata. *J. Cellular Automata*, 13(1-2):15–32, 2018.

9. Eric Goles Chacc, Marco Montalva-Medel, Henning S. Mortveit, and Salvador Ramírez-Flandes. Block invariance in elementary cellular automata. *J. Cellular Automata*, 10(1-2):119–135, 2015.

10. Kevin Perrot, Marco Montalva-Medel, Pedro Paulo Balbi de Oliveira, and Eurico L. P. Ruivo. Maximum sensitivity to update schedule of elementary cellular automata over periodic configurations. *Natural Computing*, 2019.

11. Eurico L. P. Ruivo, Pedro Paulo Balbi de Oliveira, Marco Montalva-Medel, and Kevin Perrot. Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations. *Information and Computation*, 2019. to appear.

12. Eurico L. P. Ruivo, Marco Montalva-Medel, Pedro Paulo Balbi de Oliveira, and Kevin Perrot. Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates. *Chaos, Solitons & Fractals*, 113:209–220, 2018.

13. Stephen Wolfram. *A New Kind of Science*. Wolfram Media, 2002.