# Regional Controllability of Cellular Automata as a SAT Problem

Franco Bagnoli, Sara Dridi, Nazim Fatès

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

## To cite this version:

Franco Bagnoli, Sara Dridi, Nazim Fatès. Regional Controllability of Cellular Automata as a SAT Problem. Natural Computing, In press, 25 (1), pp.2. 10.1007/s11047-025-10061-6. hal-05003164

HAL Id: hal-05003164

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

Submitted on 24 Mar 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Regional Controllability of Cellular Automata as a SAT Problem

Franco Bagnoli* Sara Dridi† Nazim Fatès‡

March 24, 2025

## Abstract

Controllability, one of the fundamental concepts in control theory, consists in guiding a system from an initial state to a desired one within a limited (and possibly minimum) time interval. When the objective is limited to a specific sub-region of the system's domain, the concept is referred to as regional controllability.

We examine this notion in the context of Boolean one-dimensional cellular automata of finite length. Depending on the local evolution rule, we investigate whether it is possible to control the evolution of the system by imposing particular values on the boundary conditions. This approach is related to key dynamical properties of CA, specifically chain transitivity and chain mixing. We show that the control problem can be formulated as a Boolean satisfiability (SAT) problem and can thus be addressed using SAT solvers. We also show how finding shortest paths in the configuration graph allows to determine controllability properties. From our observations we can state that only peripherally-linear rules are fully controllable, while for other rules, the reachability ratio, that is, the fraction of controllable pairs of initial and final configurations, is vanishing when the system size grows.

## 1 Introduction

Control theory is a branch of mathematics and engineering that deals with the behaviour of dynamical systems and how this behaviour can be modified with some influence that takes the form of a feedback. In other words, to control a system means to influence its behaviour so as to steer it to a desired state. Control theory is widely used in large number of fields ranging from aerospace, robotics, electrical engineering to social science.

<footnote>*Department Physics and Astronomy and CSDC, University of Florence, Via G. Sansone, Sesto Fiorentino, 50019, Italy; franco.bagnoli@unifi.it</footnote>

<footnote>†Institute of Optics and Precision Mechanics, University of Setif 1, Algeria; sara.dridi@univ-setif.dz</footnote>

<footnote>‡Université de Lorraine, CNRS, Inria, LORIA, Nancy, 54000, France; nazim.fates@loria.fr</footnote>
Many studies have explored the control of dynamical systems with continuous variables and continuous-time evolution addressing both finite- and infinite-dimensional cases. These systems are typically modelled and analysed using differential equations and partial differential equations [25, 8].

Controllability, introduced by Kalman in 1960, is one of the fundamental concepts in control theory. It explores whether a system can be guided from any initial state to a desired state within a predefined time interval $[0, T]$. Since the, this concept has been extensively studied for finite-dimensional systems [28] and infinite-dimensional systems described by partial differential equations (PDE) [26, 24].

More recently, controllability has been studied in the context of cellular automata (CA – acronym also used to define single cellular automaton), which are considered as potential alternatives to classical models based on partial differential equations, as they can effectively capture non-linear phenomena through simple local rules.

Cellular automata are discrete dynamical systems regarded as the simplest models of spatially extended systems which can offer an effective framework for describing complex phenomena. They consist of three components: a grid of cells, each taking a state from a finite set, a neighbourhood (for each cell) and a local transition function. The CA paradigm has been successfully applied to a wide range of fields, including biology, chemistry, physics, and ecology, as evidenced by an extensive literature on the subject [17, 21, 33]. For a general overview, see the proceedings of the ACRI conference [1].

The focus of this paper is on a specific aspect of controllability, known as regional controllability, where the goal is to achieve a desired objective only on a part of the whole domain by applying actions on its boundaries. Regional controllability of cellular automata focuses on the ability to guide the state of a system toward desired configurations within a specific subregion of the entire domain. This concept was introduced by El Jai and Zerrik in (1993-1995) and well studied in a wide range of works in the context of distributed parameter systems described by partial differential equations. It is particularly relevant for this type of systems to address situations where full domain control is either unachievable or unnecessary, while control within a specific region remains achievable.

When switching from a continuous description (PDE) to a discrete one (coupled maps or CA), we have also to introduce the system size $n$ as a relevant parameter.

In the context of CA, different characterization results have been proposed to extend or substitute the widely used Kalman criterion and the regional controllability problem was analysed with various methods to establish new criteria for the case of cellular automata and discrete complex systems [9].

Our research primarily focused on the regional controllability of Boolean CA, demonstrating its validity through the use of Markov chains and graph theory tools [15, 11, 13]; see Ref. [3] for a general overview.

The problem of regional controllability has been addressed with an approach based on the Kalman condition [14, 16]. For one-dimensional deterministic cellular automata, the problem has been explored using the
concept of Boolean derivatives [6] and the probabilistic case has been investigated with a Markov-chain approach [4, 5]. In a recent work, a novel characterization of controllability and regional controllability based on symbolic dynamics was introduced [10]. This study establishes that the regional controllability for every n (where n is the size of the controlled region) and controllability of cellular automata are equivalent to the topological properties, namely those of chain transitivity and chain mixing.

In another recent work, a preimage algorithm was used to determine whether a desired configuration can be reached from an initial configuration, using a characterization tool known as the controllability tree [12]. This paper builds upon these findings.

In this work, we deepen our exploration of the regional controllability of elementary cellular automata by formulating this problem as a satisfiability problem (SAT). We also provide new techniques such as finding the minimum path in the directed configuration graph.

The structure of the paper is as follows. Section 2 provides an overview of the definitions of elementary cellular automata, introduces the regional controllability problem and the connection between chain transitivity, chain mixing and regional controllability. Section 3 formulates the problem of regional controllability for one-dimensional cellular automata as a SAT problem. Furthermore, this method can also be used to explore key dynamical properties of cellular automata, particularly chain transitivity and chain mixing. Section 4 is devoted to the generation of preimages of a given configuration, given the controls, and in Section 5, we present another technique for CA control, focusing on the process of finding the shortest path in the directed configuration graph, achieved by constructing trees of images and preimages corresponding to the starting and target configurations for all possible control inputs. Finally, conclusions are drawn in Section 6.

# 2 Definitions of the problem and mathematical properties

## 2.1 Elementary Cellular Automata

Elementary cellular automata (ECA – acronym also used to define a single automaton) are discrete dynamical systems for which the state of each cell only takes two values and is determined at each time step by its own state and the state of left and right neighbours. The evolution of the states of all cells occurs in parallel.

We first consider a one-dimensional infinite set of cells. The state of each cell $i \in \mathbb{Z}$ at time $t$ is given by a variable $x_i^t \in \{0, 1\}$. Mathematically, the evolution of the cells is defined in terms of a local function $f\{0, 1\}^3 \to \{0, 1\}$:

$$ \forall i \in \mathbb{Z}, x_i^{t+1} = f(x_{i-1}^t, x_i^t, x_{i+1}^t). $$

For a given time $t$, we denote by $\boldsymbol{x}^t = (x_i^t)_{i \in \mathbb{Z}}$ the sequence of all cell states, i.e., a configuration. In the rest of the paper we consider only finite
configurations since we will focus on a particular set of cells, or a region, not taking into consideration what happens outside it.

<table><caption>Table 1: The look-up table of Rules 150 and 22. $\mathcal{N}$ is the neighbourhood in the base-two representation, $\mathcal{N}^{(10)}$ is the same in then base-ten representation. The column $f^{(150)}$ is the output of Rule 150 and $D_{\mathcal{N}}^{(150)}$ the derivative of the Rule 150 in zero with respect to the ones in the neighbourhood in the base-two representation, same for $f^{(22)}$ and $D^{(22)}$ for Rule 22.</caption><thead><tr><th>$\mathcal{N} = (x_{-1}, x_0, x_1)$</th><th>$\mathcal{N}^{(10)} = 4x_{-1} + 2x_0 + x_1$</th><th>$f^{(150)}(\mathcal{N})$</th><th>$D_{\mathcal{N}}^{(150)}$</th><th>$f^{(22)}(\mathcal{N})$</th><th>$D_{\mathcal{N}}^{(22)}$</th></tr></thead><tbody><tr><td>0, 0, 0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0, 0, 1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0, 1, 0</td><td>2</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0, 1, 1</td><td>3</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1, 0, 0</td><td>4</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1, 0, 1</td><td>5</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1, 1, 0</td><td>6</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1, 1, 1</td><td>7</td><td>1</td><td>0</td><td>0</td><td>1</td></tr></tbody></table>

Since there are $2^3 = 8$ different neighbourhood states, there are $2^8 = 256$ different ECA rules. It is usual to associate to each ECA $f$ its decimal code $W$, defined by $W(f) = f(0, 0, 0)2^0 + \dots + f(1, 1, 1)2^7$ [31, 32]. This amounts to writing the digits of the transition table $f(0, 0, 0) \dots f(1, 1, 1)$ and converting the binary number to a decimal number. As an example, Rule 150 corresponds to the array $1, 0, 0, 1, 0, 1, 1, 0$, which is equal to 150 in base ten (see Table 1).

One can apply two symmetries on the rule, the left-right inversion and the one-zero exchange, which gives 88 classes. The rules with smallest decimal code in a class are called *minimal CA* and it is usual to consider only these rules for studying ECA (see the left column of Table 5).

## 2.2 Definition of the regional controllability problem

In our problem, the definition of a regionally-controllable CA will be set for an arbitrary number of cells, with the goal of determining the asymptotic behaviour. For a given number of cells $n$, we will focus on the region represented by the set of $n$ cells indexed from 1 to $n$ and try to control the evolution of this region, without setting in advance the number of steps $T$. We are also interested in looking for the minimal value of $T(\boldsymbol{x}, \boldsymbol{y})$ for a given pair of configurations $(\boldsymbol{x}, \boldsymbol{y})$ and the minimal value for a region size $n$

$$T(n) = \min\{T(\boldsymbol{x}, \boldsymbol{y}) : \boldsymbol{x}, \boldsymbol{y} \in \{0, 1\}^n\},$$

where $\{0, 1\}^n$ denotes the set of finite words (configurations) of length $n$ over $\{0, 1\}$,

Given a number of cells $n$ and two finite sub-configurations $\boldsymbol{x} = (x_1, \dots, x_n)$ and $\boldsymbol{y} = (y_1, \dots, y_n) \in \{0, 1\}^n$, our objective is to determine if there exists an appropriate control sequence on the boundary
<figure><img src="image_3.png" /><figcaption>Figure 1: General view of the regional controllability problem of one-dimensional CA via boundary actions for $n = 6$ controlled cells. The initial and final configurations are respectively in yellow and cyan. Time goes from bottom to top. Colour Online</figcaption></figure>

cells, namely cell 0 and cell $n + 1$, such that the system will evolve from $\boldsymbol{x}$ to $\boldsymbol{y}$ in a finite number of time steps (see Fig. 1 for an illustration).

Mathematically, this amounts to saying that:

A CA is regionally controllable, if there exists $N \in \mathbb{N}^+$ such that for every $n \ge N$ and for every pair of configurations $\boldsymbol{x} = \boldsymbol{x}^0, \boldsymbol{y} \in \{0, 1\}^n$, there exists $T > 0$ and a control vector $\boldsymbol{u} = (u^0, \dots, u^{T-1})$ where $u^t = (x_0^t, x_{n+1}^t)$ such that

$$ \boldsymbol{x}^T = \boldsymbol{y}, $$

that is, $\boldsymbol{y}$ is reachable from $\boldsymbol{x}$ in $T$ steps, with

$$ \forall t \in \{1, \dots, T\}, \forall i \in \{1, \dots, n\}, x_i^{t+1} = f(x_{i-1}^t, x_i^t, x_{i+1}^t). $$

In the case where a rule is not regionally controllable, we are interested in determining the reachability ratio $\rho(n)$, that is, the ratio of controllable pairs of initial and final configurations of size $n$:

$$ \rho(n) = \frac{1}{2^{2n}} \mathrm{card}\{(\boldsymbol{x}, \boldsymbol{y}) \in \{0, 1\}^n \times \{0, 1\}^n : \boldsymbol{y} \text{ is reachable from } \boldsymbol{x}\}. $$
## 2.3 Peripheral linearity: a sufficient condition to be controllable

Let us now examine under which conditions elementary cellular automata can be controlled.

To this end, we introduce the notion of a *derivative* of a Boolean function $f(x, y)$ [29] as:

$$ \frac{\partial f}{\partial x} = f(x \oplus 1, y) \oplus f(x, y), $$

where $\oplus$ stands for the sum modulo two (equivalent to an exclusive OR). This definition obeys many standard properties of derivatives, like the chain rule [2]. It is possible also to define higher-order derivatives.

By means of Boolean derivatives in zero one can obtain the Ring Sum Expansion of a function [30]:

$$ f(x_0, x_1, x_2) = D_0 \oplus D_1x_0 \oplus D_2x_1 \oplus D_4x_2 \oplus D_3x_0x_1 \oplus D_5x_0x_2 \oplus D_6x_1x_2 \oplus D_7x_0x_1x_2, \quad (1) $$

where $D_i$ is the derivative of $f$ with respect to the bits that have value 1 in the binary representation of $i$.

For instance

$$ D_5 = D_{1,0,1} = \frac{\partial^2 f}{\partial x_0 \partial x_2} (0) = f(1, 0, 1) \oplus f(1, 0, 0) \oplus f(0, 0, 1) \oplus f(0, 0, 0). $$

Rules that have all derivatives of order greater than one equal to zero (i.e., $D_3 = D_5 = D_6 = D_7 = 0$) are called *affine*, and linear if $f(0, 0, 0) = 0$. For instance, Rule 150 is a linear rule since it can be written as

$$ f^{(150)}(x_0, x_1, x_2) = x_0 \oplus x_1 \oplus x_2, $$

while Rule 22, although quite similar to Rule 150 (see Table. 1), is not affine:

$$ f^{(22)}(x_0, x_1, x_2) = x_0 \oplus x_1 \oplus x_2 \oplus x_0x_1x_2. $$

The Boolean derivatives in zero and the affinity of all minimal ECA are reported in Table 2 of Ref. [12].

We can now define the property of *linearity with respect to the periphery of the neighbourhood*, which, for ECA, amounts to saying that there exists a function $g$ such that:

$$ f(x_0, x_1, x_2) = x_0 \oplus g(x_1, x_2) \quad \text{or} \quad f(x_0, x_1, x_2) = g(x_0, x_1) \oplus x_2. $$

In terms of Boolean derivatives, a rule is peripherally-linear if $D_1 = 1$ and $D_3 = D_5 = D_7 = 0$ or $D_4 = 1$ and $D_5 = D_6 = D_7 = 0$. In the ECA space, the peripherally-linear rules are Rules 15, 30, 45, 60, 90, 105, 106, 150, 154, and 170.

As shown in Refs. [6, 14], peripherally-linear rules are fully controllable.
## 2.4 Chain transitivity, chain mixing and regional controllability

Let us recall the definitions of $\epsilon$-chains, chain transitivity and chain mixing.

Let $\epsilon > 0$ and let $x, y \in A^Z$ where $A$ is the alphabet. An $\epsilon$-chain ($\epsilon$-pseudo-orbit) from $x$ to $y$ is a finite sequence of configurations $\{x^0, x^1, \dots, x^t\}$ with $x^0 = x$ and $x^T = y$, such that for $T > 0$ and $d(F(x^t), x^{t+1}) < \epsilon$, for $t \in \{0, \dots, T-1\}$, where the distance $d$ is defined as:

$$d(x, y) = 2^{-\min\{|k|:x_k \neq y_k\}}$$

and $F: A^Z \to A^Z$ is the global transition function.

A cellular automaton is chain-transitive if for all $x, y \in A^Z$ and $\epsilon > 0$ there exists an $\epsilon$-chain from $x$ to $y$ [23]. Similarly, a cellular automaton is considered to be chain-mixing if, for any two configurations $x, y \in A^Z$ and $\epsilon > 0$ there exists $T > 0$ such that for all $t \ge T$, there exists an $\epsilon$-chain of length $t$ from $x$ to $y$ [23].

Recall that regional controllability refers to the ability to steer a dynamical system in a specific region from any initial configuration to any desired configuration in that region within a finite time $T$ using appropriate inputs (control). Meanwhile, chain transitivity means that for any two points in the state space, one can find a sequence of pseudo-orbits (arbitrary small jumps) connecting them. The connection between chain transitivity, chain mixing and regional controllability of cellular automata was investigated and a proof has been recently proposed to establish an equivalence between regional controllability for every $n$ (where $n$ is the size of the controlled region), the chain-transitivity and chain-mixing properties of one-dimensional cellular automata [10]. It has been shown that a CA is regionally controllable for every $n$ if and only if it is chain-transitive and chain-mixing.

The link between these concepts can be understood through graph theory, by modelling controlled cellular automata as directed graph, where nodes denotes the finite configurations in $A^n$ and the arcs represent transitions between them, governed by system dynamics or external inputs. In graph terms, the regional controllability concept corresponds to strong connectivity of the state transition graph meaning that any state can be reached from any other state via a directed path between nodes [15, 9]. It has been shown that when this connectivity property is verified for every $n$, it is equivalent to chain transitivity and chain mixing [10]. For a finite cellular automaton the relationship also remains valid.

This means that the value of $\epsilon$ controls the number of cells $n$ that we have in our system and that applying the control sufficiently far from the centre cell (say at distance $n/2$) guarantees that we obtain a valid $\epsilon$-chain. Mathematically, let us consider a configuration $x^t$ and its image $x^{t+1} = F(x^t)$. Applying a control on $x^{t+1}$ on cells $-n/2$ and $n/2$ transforms this configuration into a configuration $y$. It is easy to see that we have $d(F(x^t), y) \le \frac{1}{2^{n/2}}$, which exactly corresponds to the notion of $\epsilon$-chain for $\epsilon = \frac{1}{2^{n/2}}$. In other words, we need to apply the control at a larger distance as the value of $\epsilon$ gets smaller in the $\epsilon$-chain.
<figure><img src="image_4.png" /><figcaption>Figure 2: One step of the generation of the preimages (control tree) of configuration 01 for Rule 150. Since Rule 150 is (doubly) peripherally linear, there is no failures nor additional forking.</figcaption></figure>

According to the equivalence presented in Ref. [10], the methods used to investigate the regional controllability problem can thus also be used to verify the chain transitivity and chain mixing properties.

# 3 Modelling the control problem as a SAT problem

We can now investigate whether the control problem is solvable for non-peripherally linear rules. In this section, we reformulate the regional controllability of cellular automata problem as a SAT problem.

## 3.1 Modelling the problem

Recall that we have $n$ cells in the target region with indices ranging from 1 to $n$, and two external cells with index 0 and $n+1$ as the border controls. In the CA world, $x_i^t \in \{0,1\}$ describe the state of cell $i \in \{1,n\}$ at time $t$ and $x_0^t$ and $x_{n+1}^t$ respectively describe the state of left and right controls at time $t$. To go to the SAT universe, we map each binary value $x_i^t$ to a Boolean value $b_i^t$, with $t \in \mathbb{N}$ and $i \in \{0, ..., n\}$ such that $b_i^t = \mathcal{B}(x_i^t)$, where $\mathcal{B}$ is the function from $\{0,1\}$ to $\{\text{False}, \text{True}\}$ such that $\mathcal{B}(0) = \text{False}$ and $\mathcal{B}(1) = \text{True}$.

Recall that we fix the values $\boldsymbol{x} = (x_1, ..., x_n)$ and that we want to reach $\boldsymbol{y} = (y_1, ..., y_n)$ in $T$ time steps. This is equivalent to saying that there exists two sequences $(\boldsymbol{x}_0^t)_{t \in \{0, ..., T-1\}}$ and $(\boldsymbol{x}_{n+1}^t)_{t \in \{0, ..., T-1\}}$ such that:
<figure><img src="image_5.png" /><figcaption>Figure 3: (left) Modelling of the controllability problem with Rule 30, initial condition 010001, final condition 101010 and $T = 7$ time steps. Time goes from bottom to top. The control variables are shown in green and the controlled variables in pink. The values of two control variables $x_0^7$ and $x_7^7$ are irrelevant and are left in grey. (right) A solution that was found by the SAT solver. White and blue respectively correspond to 0 and 1, which are respectively associated to False (F) and True (T). Color online</figcaption></figure>

$$ \forall t \in \{0, \dots, T-1\}, \forall i \in \{1, \dots, n\}, \quad x_i^{t+1} = f(x_{i-1}^t, x_i^t, x_{i+1}^t). \quad (2) $$

and $x_i^T = y_i$ for all $i \in \{1, \dots, n\}$, that is, $\mathbf{y}$ is reachable from $\mathbf{x}$ in $T$ steps.

We now need to transform this mathematical relationship into a Boolean formula. Such a formula is usually expressed as a combination of variables, or atoms, and operators. A clause is a special case of formula where atoms and their negations are combined using only OR operators, for instance $f(a, b, c) = a \lor \neg b \lor c$. A formula is in conjunctive normal form (CNF) if it is expressed as a conjunction of clauses, for instance: $f(a, b, c, d) = (a \lor \neg b) \land (b \lor \neg c \lor \neg d)$. SAT solvers take a CNF as an input and try to compute an assignment of the variables that makes the formula true, or, when this is not possible, try to find a proof that there is no such assignment.

To encode the CNF that verifies the regional controllability problem, we proceed in two steps (see Fig. 3).

a) For each $i$ and $t$, we encode the condition $x_i^{t+1} = f(x_{i-1}^t, x_i^t, x_{i+1}^t)$ as a CNF composed of eight clauses which use the four variables $b_i^{t+1}$, $b_{i-1}^t$, $b_i^t$, and $b_{i+1}^t$.

Indeed, each neighbourhood state will generate a clause:

$$ (x_{i-1}^t, x_i^t, x_{i+1}^t) = (0, 0, 0) \implies x_i^{t+1} = f(0, 0, 0), $$

$$ (x_{i-1}^t, x_i^t, x_{i+1}^t) = (0, 0, 1) \implies x_i^{t+1} = f(0, 0, 1), \dots, $$

$$ (x_{i-1}^t, x_i^t, x_{i+1}^t) = (1, 1, 1) \implies x_i^{t+1} = f(1, 1, 1). $$
As $A \implies B$ is equivalent to $\neg A \lor B$, the conditions becomes

$$x_{i-1}^t \neq 0 \lor x_i^t \neq 0 \lor x_{i+1}^t \neq 0 \lor x_i^{t+1} = f(0, 0, 0), \dots,$$

that is,

$$x_{i-1}^t = 1 \lor x_i^t = 1 \lor x_{i+1}^t = 1 \lor x_i^{t+1} = f(0, 0, 0), \dots$$

which translates into

$$b_{i-1}^t \lor b_i^t \lor b_{i+1}^t \lor C[b_i^{t+1}, f(0, 0, 0)] \dots,$$

where $C[b, 1] = b$ and $C[b, 0] = \neg b$.

We thus translate the $n \cdot T$ transitions described in Eq. (2) into $8 \cdot n \cdot T$ clauses.

b) In a second step, we encode the initial and final conditions ($b_i^0$) and ($b_i^T$) for $i \in \{1, \dots, n\}$ and let the control variables free of any constraint.

By combining the conditions obtained in step a) and step b), we obtain a CNF formula $\Phi$ with $8nT + 2n$ clauses and such that $\Phi$ is satisfiable if and only if $y$ is reachable from $x$ in $T$ time steps.

## 3.2 Experimental results

We tested the solving abilities of the SAT solvers with the minisat solver [18]. We used a simple script to generate the formula seen above in the form of a CNF expressed in the popular DIMACS format. For a fixed value of $n$ and $T$, we randomly generated a pair of initial and final configurations $x, y \in \{0, 1\}^n$ and asked the solver whether $y$ was reachable from $x$ with a control sequence of length $T$.

Table 2 presents the results for the 88 minimal ECA for the setting $n = 40, T = 100$ and a sample of 100 random pairs of initial and final configurations. The second column ($\tilde{\rho}$) presents the ratio of cases where a solution was found, that is, a rough estimate of the reachability ratio $\rho(n)$. We observe that $\tilde{\rho}$ is either equal to 1 or is rather small (less than 10%). The case where $\tilde{\rho}$ equals one corresponds exactly to the ten peripherally-linear rules 15, 30, 45, 60, 90, 105, 106, 150, 154, and 170. For the other rules, we issue the following conjecture:

*The reachability ratio $\rho(n)$ tends to zero when the number of cells $n$ tends to infinity for all the ECA rules which are not peripherally-linear.*

This conjecture is supported by the data shown on Table 4, where one can clearly see that the estimated reachability ratio $\tilde{\rho}(n)$ rapidly decreases with $n$, and becomes of the order of a percent when $n$ is equal to 50. It is an open question to obtain more precise scaling laws with $n$, and a good estimate of the time needed to reach a configuration from another.

Table 2 also presents the CPU time that is used to compute the presence or the absence of a solution, and the number of restarts, conflicts and decisions that were taken by the SAT solver. These figures are only presented to furnish a rough estimate of the difficulty of analysis that was met for each rule. It should be noted that we did not encounter any case
<table><caption>Table 2: Controllability statistics for the 88 ECA for $n = 40$, $T = 100$ and 100 random pairs of initial and final configurations. columns : $\tilde{\rho}$ is the average reachability ; time is the cumulative CPU time ; R, C, D respectively represent the cumulative number of restarts, conflicts and decisions of the SAT solver.</caption><thead><tr><th>ECA</th><th>ρ̃</th><th>time</th><th>R</th><th>C</th><th>D</th><th>ECA</th><th>ρ̃</th><th>time</th><th>R</th><th>C</th><th>D</th></tr></thead><tbody><tr><td>0</td><td>0.00</td><td>1.874</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0.00</td><td>1.870</td><td>0</td><td>0</td><td>0</td></tr><tr><td>2</td><td>0.00</td><td>1.866</td><td>0</td><td>0</td><td>0</td><td>3</td><td>0.01</td><td>1.838</td><td>1</td><td>0</td><td>1</td></tr><tr><td>4</td><td>0.00</td><td>1.834</td><td>0</td><td>0</td><td>0</td><td>5</td><td>0.00</td><td>1.864</td><td>0</td><td>0</td><td>0</td></tr><tr><td>6</td><td>0.00</td><td>1.922</td><td>0</td><td>0</td><td>0</td><td>7</td><td>0.00</td><td>1.765</td><td>3</td><td>39</td><td>143</td></tr><tr><td>8</td><td>0.00</td><td>1.808</td><td>0</td><td>0</td><td>0</td><td>9</td><td>0.00</td><td>1.942</td><td>0</td><td>0</td><td>0</td></tr><tr><td>10</td><td>0.00</td><td>1.985</td><td>0</td><td>0</td><td>0</td><td>11</td><td>0.00</td><td>1.870</td><td>0</td><td>0</td><td>0</td></tr><tr><td>12</td><td>0.00</td><td>1.757</td><td>0</td><td>0</td><td>0</td><td>13</td><td>0.00</td><td>2.073</td><td>0</td><td>0</td><td>0</td></tr><tr><td>14</td><td>0.01</td><td>1.825</td><td>1</td><td>14</td><td>451</td><td>15</td><td>1.00</td><td>2.190</td><td>100</td><td>0</td><td>100</td></tr><tr><td>18</td><td>0.00</td><td>1.949</td><td>0</td><td>0</td><td>0</td><td>19</td><td>0.00</td><td>1.867</td><td>0</td><td>0</td><td>0</td></tr><tr><td>22</td><td>0.07</td><td>6.727</td><td>929</td><td>281123</td><td>780831</td><td>23</td><td>0.00</td><td>1.852</td><td>0</td><td>0</td><td>0</td></tr><tr><td>24</td><td>0.00</td><td>2.018</td><td>0</td><td>0</td><td>0</td><td>25</td><td>0.00</td><td>2.182</td><td>11</td><td>151</td><td>838</td></tr><tr><td>26</td><td>0.05</td><td>2.085</td><td>42</td><td>4554</td><td>28485</td><td>27</td><td>0.00</td><td>1.916</td><td>0</td><td>0</td><td>0</td></tr><tr><td>28</td><td>0.00</td><td>1.930</td><td>0</td><td>0</td><td>0</td><td>29</td><td>0.00</td><td>2.140</td><td>0</td><td>0</td><td>0</td></tr><tr><td>30</td><td>1.00</td><td>3.158</td><td>100</td><td>0</td><td>100</td><td>32</td><td>0.00</td><td>2.095</td><td>0</td><td>0</td><td>0</td></tr><tr><td>33</td><td>0.00</td><td>2.202</td><td>0</td><td>0</td><td>0</td><td>34</td><td>0.00</td><td>2.008</td><td>0</td><td>0</td><td>0</td></tr><tr><td>35</td><td>0.00</td><td>1.987</td><td>0</td><td>0</td><td>0</td><td>36</td><td>0.00</td><td>2.161</td><td>0</td><td>0</td><td>0</td></tr><tr><td>37</td><td>0.00</td><td>2.142</td><td>23</td><td>163</td><td>495</td><td>38</td><td>0.00</td><td>2.092</td><td>0</td><td>0</td><td>0</td></tr><tr><td>40</td><td>0.00</td><td>2.072</td><td>0</td><td>0</td><td>0</td><td>41</td><td>0.01</td><td>3.488</td><td>221</td><td>72085</td><td>177628</td></tr><tr><td>42</td><td>0.04</td><td>1.937</td><td>4</td><td>0</td><td>4</td><td>43</td><td>0.01</td><td>1.849</td><td>1</td><td>41</td><td>2190</td></tr><tr><td>44</td><td>0.00</td><td>1.795</td><td>0</td><td>0</td><td>0</td><td>45</td><td>1.00</td><td>2.506</td><td>100</td><td>0</td><td>100</td></tr><tr><td>46</td><td>0.00</td><td>1.867</td><td>0</td><td>0</td><td>0</td><td>50</td><td>0.00</td><td>1.923</td><td>0</td><td>0</td><td>0</td></tr><tr><td>51</td><td>0.00</td><td>1.760</td><td>0</td><td>0</td><td>0</td><td>54</td><td>0.00</td><td>1.947</td><td>3</td><td>148</td><td>1023</td></tr><tr><td>56</td><td>0.00</td><td>1.813</td><td>0</td><td>0</td><td>0</td><td>57</td><td>0.00</td><td>1.870</td><td>0</td><td>0</td><td>0</td></tr><tr><td>58</td><td>0.00</td><td>1.898</td><td>0</td><td>0</td><td>0</td><td>60</td><td>1.00</td><td>2.093</td><td>100</td><td>0</td><td>100</td></tr><tr><td>62</td><td>0.00</td><td>2.061</td><td>10</td><td>555</td><td>1883</td><td>72</td><td>0.00</td><td>1.722</td><td>0</td><td>0</td><td>0</td></tr><tr><td>73</td><td>0.00</td><td>1.809</td><td>0</td><td>0</td><td>0</td><td>74</td><td>0.00</td><td>1.866</td><td>3</td><td>18</td><td>37</td></tr><tr><td>76</td><td>0.00</td><td>1.763</td><td>0</td><td>0</td><td>0</td><td>77</td><td>0.00</td><td>1.790</td><td>0</td><td>0</td><td>0</td></tr><tr><td>78</td><td>0.00</td><td>1.759</td><td>0</td><td>0</td><td>0</td><td>90</td><td>1.00</td><td>2.117</td><td>100</td><td>0</td><td>100</td></tr><tr><td>94</td><td>0.00</td><td>1.777</td><td>0</td><td>0</td><td>0</td><td>104</td><td>0.00</td><td>1.811</td><td>0</td><td>0</td><td>0</td></tr><tr><td>105</td><td>1.00</td><td>2.485</td><td>100</td><td>0</td><td>100</td><td>106</td><td>1.00</td><td>2.553</td><td>100</td><td>0</td><td>100</td></tr><tr><td>108</td><td>0.00</td><td>1.914</td><td>0</td><td>0</td><td>0</td><td>110</td><td>0.04</td><td>7.009</td><td>667</td><td>222617</td><td>499441</td></tr><tr><td>122</td><td>0.00</td><td>1.874</td><td>0</td><td>0</td><td>0</td><td>126</td><td>0.03</td><td>3.445</td><td>249</td><td>62888</td><td>183969</td></tr><tr><td>128</td><td>0.00</td><td>1.795</td><td>0</td><td>0</td><td>0</td><td>130</td><td>0.00</td><td>1.864</td><td>0</td><td>0</td><td>0</td></tr><tr><td>132</td><td>0.00</td><td>1.800</td><td>0</td><td>0</td><td>0</td><td>134</td><td>0.00</td><td>1.804</td><td>5</td><td>93</td><td>394</td></tr><tr><td>136</td><td>0.00</td><td>1.852</td><td>0</td><td>0</td><td>0</td><td>138</td><td>0.00</td><td>1.783</td><td>0</td><td>0</td><td>0</td></tr><tr><td>140</td><td>0.00</td><td>1.729</td><td>0</td><td>0</td><td>0</td><td>142</td><td>0.00</td><td>1.776</td><td>0</td><td>0</td><td>0</td></tr><tr><td>146</td><td>0.01</td><td>2.093</td><td>39</td><td>5636</td><td>25835</td><td>150</td><td>1.00</td><td>2.498</td><td>100</td><td>0</td><td>100</td></tr><tr><td>152</td><td>0.00</td><td>1.842</td><td>0</td><td>0</td><td>0</td><td>154</td><td>1.00</td><td>2.608</td><td>100</td><td>0</td><td>100</td></tr><tr><td>156</td><td>0.00</td><td>1.899</td><td>0</td><td>0</td><td>0</td><td>160</td><td>0.00</td><td>1.805</td><td>0</td><td>0</td><td>0</td></tr><tr><td>162</td><td>0.00</td><td>1.907</td><td>0</td><td>0</td><td>0</td><td>164</td><td>0.00</td><td>1.810</td><td>0</td><td>0</td><td>0</td></tr><tr><td>168</td><td>0.00</td><td>1.864</td><td>0</td><td>0</td><td>0</td><td>170</td><td>1.00</td><td>2.095</td><td>100</td><td>0</td><td>100</td></tr><tr><td>172</td><td>0.00</td><td>1.787</td><td>0</td><td>0</td><td>0</td><td>178</td><td>0.00</td><td>1.773</td><td>0</td><td>0</td><td>0</td></tr><tr><td>184</td><td>0.00</td><td>1.765</td><td>0</td><td>0</td><td>0</td><td>200</td><td>0.00</td><td>1.780</td><td>0</td><td>0</td><td>0</td></tr><tr><td>204</td><td>0.00</td><td>1.814</td><td>0</td><td>0</td><td>0</td><td>232</td><td>0.00</td><td>1.832</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

where the solver was unable to provide an answer, either positive or negative and that the answer was given quite rapidly (≈ 20 ms per solution on average).

It is also remarkable that among the rules for which the number of restarts is important, one finds the famous Rule 110, which is known to be Turing-universal. Of course, there is no direct correlation between the computational complexity of a rule and the difficulty to decide its controllability, but we can safely state that the rules which exhibit the
<table><caption>Table 4: Estimation of the reachability ratio $\rho(n)$ for values of $n$ ranging from 10 to 50, for Rule 22 and Rule 110 and different values of $T$. Statistics on 100 random pairs of initial and final random configurations.</caption><thead><tr><th></th><th></th><th colspan="5">n</th></tr><tr><th>ECA</th><th>T</th><th>10</th><th>20</th><th>30</th><th>40</th><th>50</th></tr></thead><tbody><tr><td>22</td><td>100</td><td>0.83</td><td>0.38</td><td>0.15</td><td>0.03</td><td>0.01</td></tr><tr><td>22</td><td>200</td><td>0.84</td><td>0.46</td><td>0.11</td><td>0.04</td><td>0.01</td></tr><tr><td>22</td><td>400</td><td>0.89</td><td>0.43</td><td>0.17</td><td>0.03</td><td>0.01</td></tr><tr><td>110</td><td>100</td><td>0.72</td><td>0.38</td><td>0.17</td><td>0.03</td><td>0.01</td></tr><tr><td>110</td><td>200</td><td>0.75</td><td>0.36</td><td>0.15</td><td>0.07</td><td>0.00</td></tr><tr><td>110</td><td>400</td><td>0.75</td><td>0.31</td><td>0.13</td><td>0.06</td><td>0.01</td></tr></tbody></table>

richest panel of behaviours (gliders, collisions generating other gliders, etc.) are among the most difficult ones to analyse by the SAT solvers.

In order to gain insights on the relationships between regional control- lability and the difficulty to find a solution or to prove that there is none, we now explore a technique of tree-building in order to find the shortest paths between two configurations.

## 4 Generating preimages

Let us sketch the idea of generating the preimage $(z_0, z_1, z_2, \dots, z_n, z_{n+1})$ of a given configuration $(x_1, x_2, \dots, x_n)$, for all possible controls $z_0$ and $z_{n+1}$. This method will be exploited in the next section to examine the control tree.

The construction of the preimage is performed one site after the other. We start by inserting the two sites $z_0$ ad $z_1$. Since there are $n+2$ items in the preimage $(z_0, z_1, z_2, \dots, z_n, z_{n+1})$, and only $n$ in $(x_1, x_2, \dots, x_n)$, we have to iterate over all the four values of $z_0$ and $z_1$.

We can then select the value(s) of $z_2$ such that

$$x_1 = f(z_0, z_1, z_2).$$

It may happen that there are no values allowed, just one or two.

In the first case, we abort the reconstruction and pass to the next pair of $z_0$ and $z_1$ values, if available, or declare that there is no preimage. In the second case, we can proceed with the neighbouring site ($z_3$). In the third case, we have to fork the procedure for the two values of $z_2$ and continue to the next site ($z_3$). This procedure continues until we generate $z_{n+1}$.

Instead of scanning the whole look-up table (which can be costly for large neighbourhoods), one can take profit of the ring sum expansion, Eq. (1)

$$x_i = D_0 \oplus D_1 z_{i-1} \oplus D_2 z_i \oplus D_4 z_{i+1} \oplus D_3 z_{i-1} z_i \oplus \\ D_5 z_{i-1} z_{i+1} \oplus D_6 z_i z_{i+1} \oplus D_7 z_{i-1} z_i z_{i+1},$$
<figure><img src="image_6.png" /><figcaption>Figure 4: One step of the generation of the preimages (control tree) of configuration 01 for Rule 22. Since Rule 22 is not peripherally-linear, some configurations do not have preimages and others have more than one preimage.</figcaption></figure>

to calculate directly $z_{i+1}$ knowing $z_{i-1}$ and $z_i$, using the formula:

$$z_{i+1}(D_4 \oplus D_5z_{i-1} \oplus D_6z_i \oplus D_7z_{i-1}z_i) = x_i \oplus D_0 \oplus D_1z_{i-1} \oplus D_2z_i \oplus D_3z_{i-1}z_i,$$

as illustrated in Fig. 4 for Rule 22.

If $D_4 \oplus D_5z_{i-1} \oplus D_6z_i \oplus D_7z_{i-1}z_i = 1$ then $z_{i+1} = x_i \oplus D_0 \oplus D_1z_{i-1} \oplus D_2z_i \oplus D_3z_{i-1}z_i$, otherwise, if $x_i = D_0 \oplus D_1z_{i-1} \oplus D_2z_i \oplus D_3z_{i-1}z_i$, one has to fork for $z_{i-1} = 0, 1$, else the recursion fails.

An example of this procedure is reported in Figure 2 for a peripherally-linear rule (Rule 150) and in Figure 4 for a nonlinear rule (Rule 22).

Let us illustrate in detail the operation: the evolution of a rule which is right-peripheral, i.e.,

$$x' = g(x_{-}, x) \oplus x_{+}$$

can be inverted, giving

$$x_{+} = x' \oplus g(x_{-}, x),$$

and in this case it is evident that the preimage is always unique.

For instance, for Rule 150

$$x' = x_{-} \oplus x \oplus x_{+} \quad \Rightarrow \quad x_{+} = x' \oplus x \oplus x_{-}.$$

On the other side, for nonlinear rules like Rule 22

$$x' = x_{-} \oplus x \oplus x_{+} \oplus x_{-}xx_{+} \quad \Rightarrow \quad x_{+}(1 \oplus x_{-}x) = x' \oplus x_{-} \oplus x_{+},$$
<figure><img src="image_7.png" /><figcaption>Figure 5: The two minimal control paths from configuration 10 to configuration 4 for Rule 30 and $n = 3$. The forward edges are in green and the backward ones in red. The connecting configurations 6 and 7 are marked in blue. To the left the full control graph (controls values are not shown, for each link there could be more than one control possible).</figcaption></figure>

we have three possibilities: if $1 \oplus x_{-}x = 1$; one can obtain $x_{+}$ uniquely, otherwise, either we have zero or two possibilities. In the example of Rule 22, $1 \oplus x_{-}x = 0$ implies $x_{-} = x = 1$ and looking in the Look-up table (Table 1) we can only have $x' = 0$, so, if this is the case, we have either both values $x_{+} = 0$ and $x_{+} = 1$ (if $x' = 0$), or none.

# 5 An alternative approach: Finding the shortest path in the control tree

We present here an alternative method to test the reachability of $\mathbf{y}$ from $\mathbf{x}$: we simultaneously explore both the tree of images starting from $\mathbf{x}$, with all the possible controls, and the tree of preimages starting from $\mathbf{y}$, until these two trees meet in at least one configuration, thus indicating the shortest control that transforms $\mathbf{x}$ into $\mathbf{y}$.

Finding a control $l = (x_0^0, x_0^1, \dots, x_0^{T-1})$ and $r = (x_{n+1}^0, x_{n+1}^1, \dots, x_{n+1}^{T-1})$ driving the system from configuration $\mathbf{x} = \mathbf{x}^0 = (x_1^0, x_2^0, \dots, x_n^0)$ at time $t=0$ to configuration $\mathbf{y} = \mathbf{x}^T = (x_1^T, x_2^T, \dots, x_n^T)$ at time $T$ can be done by looking for the shortest path in the tree generated by all possible pairs of values for the control at each time step, forward in time starting from $\mathbf{x}$, or in the tree of all possible preimages backward in time starting from configuration $\mathbf{y}$.

Going forward in time, each node can in principle generate four branches, for the four possible values of the left-right pair, but it may happen that more than one control pair gives the same configuration. Going backward in time, it may also happen that a given control pair gives no configuration, or, as we have seen, more branches have to be followed while generating preimages.

Depending on the branching of the trees, it may be more efficient to generate more forward or backward levels. However, an acceptable
<figure><img src="image_8.png" /><figcaption>Figure 6: Average number of nodes $N$ visited to determine the absence of a control for the 88 minimal rules, scaled by the total number of configurations ($2^n$) vs. the reachability ratio $\rho$. Peripherally-linear rules have $\rho = 1$ and $N = 0$. Data from Table 5.</figcaption></figure>

strategy consists in generating one level at a time for the forward and the backward tree, until the same configuration appears at the end of both, marking a shortest path from $x$ to $y$. This procedure is indicated schematically in Figure 5.

An estimation of the reachability ratio $\rho$ for different lengths and all minimal elementary cellular automaton is reported in Table 5. One can see that peripherally-linear ECA are always fully controllable, while the fraction of controllable pairs for the other ECA diminishes with the length of the configuration, therefore indicating that the boundary control is almost impossible for large lengths for non-peripherally-linear rules. This confirms the observations made in Section 3.2 that for the ECA that are not peripherally-linear, the controllability of randomly chosen pairs tends to zero as the size of the system grows.

This technique can help us compute an estimation of the reachability ratio $\rho(n)$. We can also estimate the average complexity of finding all controls by counting the average number of nodes explored in the control tree before declaring that there is no possible control. This complexity is zero for peripherally-linear rules (since they are always controllable), but also for CA like Rule 0, which have only one possible configuration in their image (all-zero). This also holds for all the rules that have a reachability ratio very near to zero, see Table 5.

In Figure 6 we show that there is a nice relationship between the reachability ratio $\rho$ and the average complexity, scaled by the total number of configurations ($2^n$). This behaviour is reminiscent of the complexity phase transitions of SAT problems [19, 7, 22, 20].
# 6 Conclusions

In control theory, systems are classically defined by a set of differential equations and the control is applied with a feedback system. In this work, we extended this framework by tackling the question of how to control a *spatially-extended discrete dynamical system*, namely an elementary cellular automaton, by changing the state of only two boundary cells at each time step to influence a region of the entire domain.

We showed that the problem could adequately be translated into a Boolean CNF formula and fed to a SAT solver to effectively obtain a solution when the control is indeed possible, or a proof that it is impossible when this the case. From a concrete point of view, the control sequence is obtained rapidly, even for a system of the order of a hundred cells and a few hundred time steps. Interestingly enough, we observed that the difficulty to find a solution was somehow related to the computational complexity of the rules. As an alternative, we showed that one could also search for the shortest path between an initial and a final configuration by progressively extending trees in the directed graph of the transitions between configurations.

From a theoretical point view, we showed the equivalence of regional controllability for every $n$ with being chain-transitive and chain-mixing as presented in Ref. [10].

This means that our techniques may also apply to verify such properties in various other cases. More generally, a logical next step would be to explore how our work extends to cellular automata with higher dimensions, a greater number of states, or even to non-uniform rules (applying different local rules in a SAT solver and in the search of the shortest path can be done directly without any additional effort).

We also observed that in the ECA that are not peripherally-linear, the probability to reach a final configuration from an initial configuration vanishes when the system's size grows and when the configurations are chosen randomly. It would be interesting to prove this property formally. In fact, a more precise description would quantify how the size of the communication classes of the transition graph scale as a function of the system's size. The techniques that were applied for fully asynchronous ECA [27] may also apply here and the use of SAT solvers may be of great help to derive such formal proofs of reachability.
<table><caption>Table 5: Numerical estimation $\tilde{\rho}$ of the reachability ratio and number N of nodes to be visited to check for the absence of control for all minimal ECA R and various configuration sizes n. The data are obtained sampling over $10^4$ random pairs of configurations.</caption><thead><tr><th rowspan="2">R</th><th colspan="2">n = 9</th><th colspan="2">n = 11</th><th colspan="2">n = 13</th><th colspan="2">n = 15</th></tr><tr><th>ρ̃</th><th>N</th><th>ρ̃</th><th>N</th><th>ρ̃</th><th>N</th><th>ρ̃</th><th>N</th></tr></thead><tbody><tr><td>0</td><td>0.002</td><td>0.9956</td><td>0.0011</td><td>0.9985</td><td>0</td><td>0.9997</td><td>0</td><td>0.9999</td></tr><tr><td>1</td><td>0.0112</td><td>9.8817</td><td>0.0021</td><td>10.2039</td><td>0.0005</td><td>10.2994</td><td>0.0003</td><td>9.1978</td></tr><tr><td>2</td><td>0.0801</td><td>37.6393</td><td>0.0426</td><td>84.2125</td><td>0.0208</td><td>185.0444</td><td>0.0137</td><td>400.4257</td></tr><tr><td>3</td><td>0.3936</td><td>121.053</td><td>0.2907</td><td>436.7135</td><td>0.2303</td><td>1459.9432</td><td>0.1783</td><td>4800.218</td></tr><tr><td>4</td><td>0.0026</td><td>2.5131</td><td>0.0007</td><td>2.7917</td><td>0.0002</td><td>2.7316</td><td>0.0001</td><td>3.3823</td></tr><tr><td>5</td><td>0.0132</td><td>12.9694</td><td>0.0031</td><td>14.1058</td><td>0.0006</td><td>13.7366</td><td>0</td><td>14.5212</td></tr><tr><td>6</td><td>0.3918</td><td>124.9131</td><td>0.2638</td><td>401.5478</td><td>0.1666</td><td>1172.6215</td><td>0.107</td><td>3171.2119</td></tr><tr><td>7</td><td>0.2093</td><td>90.0002</td><td>0.1223</td><td>226.8278</td><td>0.0655</td><td>552.3652</td><td>0.0417</td><td>1302.8289</td></tr><tr><td>8</td><td>0.0035</td><td>3.6936</td><td>0.0013</td><td>4.0129</td><td>0.0003</td><td>4.1582</td><td>0</td><td>4.4093</td></tr><tr><td>9</td><td>0.3893</td><td>122.727</td><td>0.2378</td><td>376.5136</td><td>0.141</td><td>978.621</td><td>0.0774</td><td>2346.7942</td></tr><tr><td>10</td><td>0.195</td><td>83.5645</td><td>0.1316</td><td>236.9626</td><td>0.0902</td><td>649.5169</td><td>0.0507</td><td>1775.1363</td></tr><tr><td>11</td><td>0.327</td><td>112.401</td><td>0.2183</td><td>349.5516</td><td>0.1468</td><td>1011.7967</td><td>0.0917</td><td>2837.0574</td></tr><tr><td>12</td><td>0.003</td><td>2.6059</td><td>0.0007</td><td>2.7152</td><td>0.0004</td><td>2.8586</td><td>0</td><td>3.0346</td></tr><tr><td>13</td><td>0.0156</td><td>14.6131</td><td>0.0038</td><td>17.273</td><td>0.0014</td><td>19.732</td><td>0.0004</td><td>20.4391</td></tr><tr><td>14</td><td>0.4133</td><td>123.18</td><td>0.2794</td><td>423.1061</td><td>0.1938</td><td>1293.3974</td><td>0.1304</td><td>3763.2499</td></tr><tr><td>15</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>18</td><td>0.4262</td><td>125.7239</td><td>0.3267</td><td>443.4179</td><td>0.234</td><td>1497.6062</td><td>0.1713</td><td>4780.7041</td></tr><tr><td>19</td><td>0.0083</td><td>7.4527</td><td>0.0018</td><td>7.93</td><td>0.0004</td><td>7.9429</td><td>0.0002</td><td>8.3817</td></tr><tr><td>22</td><td>0.8586</td><td>62.3896</td><td>0.7928</td><td>333.8604</td><td>0.7057</td><td>1692.3004</td><td>0.6131</td><td>7699.2784</td></tr><tr><td>23</td><td>0.0126</td><td>12.1348</td><td>0.0031</td><td>13.4406</td><td>0.0008</td><td>14.4739</td><td>0.0005</td><td>14.9865</td></tr><tr><td>24</td><td>0.0911</td><td>43.8604</td><td>0.0515</td><td>97.4022</td><td>0.0257</td><td>213.4277</td><td>0.0142</td><td>461.6439</td></tr><tr><td>25</td><td>0.7168</td><td>103.373</td><td>0.5606</td><td>502.6101</td><td>0.4128</td><td>1971.0832</td><td>0.2882</td><td>6698.8188</td></tr><tr><td>26</td><td>0.7686</td><td>90.9939</td><td>0.6906</td><td>438.8354</td><td>0.6189</td><td>1900.8206</td><td>0.5183</td><td>8258.4423</td></tr><tr><td>27</td><td>0.5841</td><td>126.0192</td><td>0.4693</td><td>501.9368</td><td>0.3645</td><td>1862.9912</td><td>0.2838</td><td>6487.5229</td></tr><tr><td>28</td><td>0.0235</td><td>20.7356</td><td>0.0058</td><td>26.5314</td><td>0.0024</td><td>29.8961</td><td>0.0003</td><td>34.9573</td></tr><tr><td>29</td><td>0.0156</td><td>13.5261</td><td>0.0039</td><td>14.127</td><td>0.0013</td><td>14.6097</td><td>0.0002</td><td>14.692</td></tr><tr><td>30</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>32</td><td>0.0062</td><td>5.1255</td><td>0.0029</td><td>5.1161</td><td>0.0003</td><td>5.5633</td><td>0</td><td>5.319</td></tr><tr><td>33</td><td>0.0447</td><td>40.8937</td><td>0.0128</td><td>47.7303</td><td>0.0028</td><td>50.5435</td><td>0.001</td><td>50.9947</td></tr><tr><td>34</td><td>0.1698</td><td>73.7404</td><td>0.1125</td><td>206.6842</td><td>0.0776</td><td>562.5955</td><td>0.0541</td><td>1510.5548</td></tr><tr><td>35</td><td>0.5773</td><td>124.4786</td><td>0.4492</td><td>509.7556</td><td>0.3446</td><td>1888.0347</td><td>0.2731</td><td>6487.2539</td></tr><tr><td>36</td><td>0.0064</td><td>6.3585</td><td>0.0022</td><td>7.1627</td><td>0.0005</td><td>7.0318</td><td>0.0003</td><td>7.1574</td></tr><tr><td>37</td><td>0.9829</td><td>8.5978</td><td>0.8781</td><td>220.7768</td><td>0.7562</td><td>1512.4127</td><td>0.5589</td><td>8097.3136</td></tr><tr><td>38</td><td>0.3943</td><td>121.9057</td><td>0.2901</td><td>410.0903</td><td>0.2061</td><td>1316.2389</td><td>0.1464</td><td>4065.0292</td></tr><tr><td>40</td><td>0.2021</td><td>17.7929</td><td>0.0063</td><td>20.9039</td><td>0.0011</td><td>21.9891</td><td>0.0003</td><td>28.0374</td></tr><tr><td>41</td><td>0.8068</td><td>79.0688</td><td>0.6983</td><td>437.369</td><td>0.6055</td><td>1966.9365</td><td>0.5038</td><td>8234.82</td></tr><tr><td>42</td><td>0.5302</td><td>128.4775</td><td>0.4543</td><td>505.6233</td><td>0.3875</td><td>1920.5669</td><td>0.323</td><td>7182.0698</td></tr><tr><td>43</td><td>0.6385</td><td>118.688</td><td>0.506</td><td>503.6215</td><td>0.37</td><td>1943.5089</td><td>0.2789</td><td>6608.7907</td></tr><tr><td>44</td><td>0.0145</td><td>13.4614</td><td>0.0037</td><td>15.1588</td><td>0.0014</td><td>15.5487</td><td>0.0002</td><td>16.7039</td></tr><tr><td>45</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>46</td><td>0.1373</td><td>60.7865</td><td>0.0762</td><td>138.4218</td><td>0.0383</td><td>307.8265</td><td>0.0203</td><td>671.4806</td></tr><tr><td>50</td><td>0.0126</td><td>12.9995</td><td>0.0046</td><td>14.382</td><td>0.0009</td><td>15.2791</td><td>0.0003</td><td>16.3391</td></tr><tr><td>51</td><td>0.004</td><td>1.992</td><td>0.0009</td><td>1.9982</td><td>0.0003</td><td>1.9994</td><td>0</td><td>2</td></tr><tr><td>54</td><td>0.5991</td><td>123.0332</td><td>0.4806</td><td>512.1205</td><td>0.3817</td><td>1928.2614</td><td>0.2934</td><td>6796.8576</td></tr><tr><td>56</td><td>0.3266</td><td>110.1283</td><td>0.2159</td><td>345.4543</td><td>0.1452</td><td>1004.3413</td><td>0.1011</td><td>2798.7363</td></tr><tr><td>57</td><td>0.1427</td><td>66.3875</td><td>0.0595</td><td>138.6571</td><td>0.0368</td><td>269.1887</td><td>0.0166</td><td>522.0983</td></tr><tr><td>58</td><td>0.2261</td><td>91.8859</td><td>0.1241</td><td>227.1284</td><td>0.0685</td><td>522.7471</td><td>0.0352</td><td>1159.563</td></tr><tr><td>60</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>62</td><td>0.6806</td><td>115.2031</td><td>0.3775</td><td>511.3079</td><td>0.2104</td><td>1427.2255</td><td>0.1077</td><td>3330.3698</td></tr><tr><td>72</td><td>0.0059</td><td>6.6752</td><td>0.0014</td><td>7.1114</td><td>0.0004</td><td>7.5419</td><td>0.0001</td><td>8.7902</td></tr><tr><td>73</td><td>0.4241</td><td>153.995</td><td>0.2697</td><td>539.3759</td><td>0.1559</td><td>1611.5</td><td>0.0902</td><td>4281.3997</td></tr><tr><td>74</td><td>0.6732</td><td>112.9072</td><td>0.5043</td><td>513.9198</td><td>0.3615</td><td>1857.4982</td><td>0.2324</td><td>6055.0327</td></tr><tr><td>76</td><td>0.0027</td><td>1.9973</td><td>0.0008</td><td>2.1884</td><td>0.0003</td><td>2.3443</td><td>0</td><td>2.4521</td></tr><tr><td>77</td><td>0.0076</td><td>7.4463</td><td>0.0024</td><td>8.0492</td><td>0.0006</td><td>8.4614</td><td>0.0002</td><td>9.1361</td></tr><tr><td>78</td><td>0.0212</td><td>17.3528</td><td>0.0051</td><td>20.4336</td><td>0.002</td><td>23.2771</td><td>0.0005</td><td>24.8262</td></tr><tr><td>90</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>94</td><td>0.2209</td><td>119.264</td><td>0.1172</td><td>304.6733</td><td>0.0527</td><td>682.9739</td><td>0.0266</td><td>1295.4297</td></tr><tr><td>104</td><td>0.0594</td><td>47.047</td><td>0.016</td><td>62.2863</td><td>0.0051</td><td>73.0639</td><td>0.0012</td><td>74.4246</td></tr><tr><td>105</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>106</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>108</td><td>0.0133</td><td>11.6458</td><td>0.0033</td><td>12.9831</td><td>0.0014</td><td>14.3384</td><td>0.0001</td><td>15.3613</td></tr><tr><td>110</td><td>0.7892</td><td>85.207</td><td>0.7088</td><td>422.3375</td><td>0.6229</td><td>1918.6175</td><td>0.5404</td><td>8131.7471</td></tr><tr><td>122</td><td>0.7727</td><td>90.6083</td><td>0.6454</td><td>467.5212</td><td>0.515</td><td>2016.0089</td><td>0.3819</td><td>7780.4991</td></tr><tr><td>126</td><td>0.3602</td><td>115.4745</td><td>0.2572</td><td>389.2605</td><td>0.1823</td><td>1232.7578</td><td>0.1309</td><td>3752.0127</td></tr><tr><td>128</td><td>0.0042</td><td>4.767</td><td>0.0014</td><td>5.1223</td><td>0.0004</td><td>5.3654</td><td>0.0001</td><td>5.8271</td></tr><tr><td>130</td><td>0.0865</td><td>41.9356</td><td>0.0468</td><td>89.3382</td><td>0.0231</td><td>190.9837</td><td>0.0128</td><td>407.73</td></tr><tr><td>132</td><td>0.0086</td><td>7.517</td><td>0.0021</td><td>8.0448</td><td>0.0008</td><td>8.9295</td><td>0.0002</td><td>9.4588</td></tr><tr><td>134</td><td>0.4792</td><td>127.2468</td><td>0.3204</td><td>448.0948</td><td>0.2053</td><td>1372.3773</td><td>0.1371</td><td>3794.8008</td></tr><tr><td>136</td><td>0.0081</td><td>6.9283</td><td>0.0023</td><td>7.6935</td><td>0.001</td><td>9.3916</td><td>0.0001</td><td>8.8709</td></tr><tr><td>138</td><td>0.3932</td><td>121.1175</td><td>0.3025</td><td>429.4487</td><td>0.232</td><td>1456.7279</td><td>0.1803</td><td>4788.5434</td></tr><tr><td>140</td><td>0.0065</td><td>5.4538</td><td>0.0014</td><td>6.5541</td><td>0.0004</td><td>7.4921</td><td>0.0002</td><td>8.3589</td></tr><tr><td>142</td><td>0.6478</td><td>115.6484</td><td>0.4983</td><td>511.3795</td><td>0.376</td><td>1925.1316</td><td>0.2793</td><td>6605.3952</td></tr><tr><td>146</td><td>0.4318</td><td>126.3201</td><td>0.3181</td><td>451.5111</td><td>0.2391</td><td>1490.3106</td><td>0.1689</td><td>4798.1028</td></tr><tr><td>150</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><td>152</td><td>0.1055</td><td>57.6982</td><td>0.0559</td><td>126.3235</td><td>0.0308</td><td>271.1771</td><td>0.0155</td><td>580.6825</td></tr><tr><td>154</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>156</td><td>0.02</td><td>18.6955</td><td>0.0066</td><td>23.3457</td><td>0.0024</td><td>27.5274</td><td>0.0004</td><td>31.1357</td></tr><tr><td>160</td><td>0.019</td><td>14.9671</td><td>0.005</td><td>16.1459</td><td>0.0014</td><td>17.7011</td><td>0.0003</td><td>20.3167</td></tr></tbody></table>
<table><tr><td>162</td><td>0.1731</td><td>76.9699</td><td>0.1151</td><td>210.7525</td><td>0.0764</td><td>568.7733</td><td>0.0534</td><td>1517.3141</td></tr><tr><td>164</td><td>0.1176</td><td>64.8285</td><td>0.0527</td><td>130.9186</td><td>0.0232</td><td>228.8644</td><td>0.0075</td><td>371.3313</td></tr><tr><td>168</td><td>0.0949</td><td>67.665</td><td>0.0405</td><td>135.6538</td><td>0.0168</td><td>258.6673</td><td>0.0085</td><td>440.1266</td></tr><tr><td>170</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>172</td><td>0.0485</td><td>37.6656</td><td>0.0175</td><td>63.234</td><td>0.0068</td><td>99.9733</td><td>0.0026</td><td>151.9821</td></tr><tr><td>178</td><td>0.0135</td><td>11.9561</td><td>0.0034</td><td>13.2167</td><td>0.0016</td><td>14.1006</td><td>0.0001</td><td>13.7332</td></tr><tr><td>184</td><td>0.5655</td><td>126.3228</td><td>0.4373</td><td>500.8263</td><td>0.334</td><td>1775.3973</td><td>0.2422</td><td>5955.3257</td></tr><tr><td>200</td><td>0.0031</td><td>2.3074</td><td>0.0003</td><td>2.4128</td><td>0.0001</td><td>2.5936</td><td>0.0001</td><td>2.9415</td></tr><tr><td>204</td><td>0.002</td><td>0</td><td>0.0005</td><td>0</td><td>0.0004</td><td>0</td><td>0</td><td>0</td></tr><tr><td>232</td><td>0.0079</td><td>7.309</td><td>0.0024</td><td>8.2605</td><td>0.0007</td><td>8.5996</td><td>0.0001</td><td>8.5114</td></tr></table>

References

[1] Acri: International conference on cellular automata for research and industry. Lecture Notes in Computer Science LNCS 2493, 3305, 4173, 5191, 6350, 7495, 8751, 9863, 11115, 12599, 13402, 14978, https://link.springer.com/conference/acri, 2002-2024. [Online; accessed 3-March-2025].

[2] Franco Bagnoli. Boolean derivatives and computation of cellular automata. *International Journal of Modern Physics C*, 3(02):307-320, 1992.

[3] Franco Bagnoli. *Synchronization and Control of Cellular Automata*. Springer International Publishing, Cham, Switzerland, March 2025.

[4] Franco Bagnoli, Sara Dridi, Samira El Yacoubi, and Raúl Rechtman. Regional control of probabilistic cellular automata. In *International Conference on Cellular Automata*, pages 243-254. Springer, 2018.

[5] Franco Bagnoli, Sara Dridi, Samira El Yacoubi, and Raul Rechtman. Optimal and suboptimal regional control of probabilistic cellular automata. *Natural Computing*, 18(4):845-853, 2019.

[6] Franco Bagnoli, Samira El Yacoubi, and Raúl Rechtman. Toward a boundary regional control problem for boolean cellular automata. *Natural Computing*, 17(3):479-486, 2018.

[7] Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Where the really hard problems are. In *Proceedings of the 12th International Joint Conference on Artificial Intelligence - Volume 1*, IJCAI'91, page 331-337, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc.

[8] Ruth F Curtain and Hans Zwart. *An introduction to infinite-dimensional linear systems theory*, volume 21. Springer Science & Business Media, New York, USA, 2012.

[9] Sara Dridi. *Recent advances in regional controllability of cellular automata*. PhD thesis, Perpignan, 2019.

[10] Sara Dridi. New characterization of regional controllability and controllability of deterministic cellular automata via topological and symbolic dynamics notions. *arXiv preprint arXiv:2501.02622*, 2025.

[11] Sara Dridi, Franco Bagnoli, and Samira El Yacoubi. Markov chains approach for regional controllability of deterministic cellular automata, via boundary actions. *Journal of Cellular Automata*, 14, 2019.
[12] Sara Dridi, Franco Bagnoli, and Samira El Yacoubi. *Regional Controllability of Cellular Automata Through Preimages*, page 22–33. Springer Nature Switzerland, Cham, Switzerland, 2024.

[13] Sara Dridi, Samira El Yacoubi, and Franco Bagnoli. *Boundary regional controllability of linear Boolean cellular automata using Markov chain*, pages 37–48. Springer International Publishing, Cham, Switzerland, 2020.

[14] Sara Dridi, Samira El Yacoubi, and Franco Bagnoli. *Kalman condition and new algorithm approach for regional controllability of peripherally-linear elementary cellular automata via boundary actions*. *J. Cell. Autom.*, 16(3-4):173–195, 2022.

[15] Sara Dridi, Samira El Yacoubi, Franco Bagnoli, and Allyx Fontaine. *A graph theory approach for regional controllability of boolean cellular automata*. *International Journal of Parallel, Emergent and Distributed Systems*, pages 1–15, 2019.

[16] Samira El Yacoubi, Théo Plénet, Sara Dridi, Franco Bagnoli, Laurent Lefèvre, and Clément Raïevsky. *Some control and observation issues in cellular automata*. *Complex Systems*, 30(3):391–413, 2021.

[17] G Bard Ermentrout and Leah Edelstein-Keshet. *Cellular automata approaches to biological modeling*. *Journal of Theoretical Biology*, 160(1):97–133, 1993.

[18] Niklas Eén and Niklas Sörensson. *The minisat solver page*. http://minisat.se/, 2003. [Online; accessed 16-March-2025].

[19] Brian Hayes. *Computing science: Can't get no satisfaction*. *American scientist*, 85(2):108–112, 1997.

[20] Tad Hogg, Bernardo A. Huberman, and Colin Williams. *Frontiers in problem solving: Phase transitions and complexity*, 1996.

[21] Lemont B Kier, Paul G Seybold, and Chao-Kun Cheng. *Cellular automata modeling of chemical systems*. Springer, Dordrecht, Netherlands, 2005.

[22] Scott Kirkpatrick and Bart Selman. *Critical behavior in the satisfiability of random boolean expressions*. *Science*, 264(5163):1297–1301, May 1994.

[23] Petr Kurka. *Topological and symbolic dynamics*. Société mathématique de France, Paris, France, 2003.

[24] Jacques-Louis Lions. *Controlabilité exacte des systèmes distribués: remarques sur la théorie générale et les applications*. In *Analysis and Optimization of Systems: Proceedings of the Seventh International Conference on Analysis and Optimization of Systems, Antibes, June 25-27, 1986*, pages 3–14. Springer, 1986.

[25] Jacques-Louis Lions. *Exact controllability for distributed systems. some trends and some problems*. In *Applied and industrial mathematics*, pages 59–84. 1991.

[26] Jacques-Louis Lions and Pierre Lelong. *Contrôle optimal de systèmes gouvernés par des équations aux dérivées partielles*. Collection "Études mathématiques". Dunod, Paris, France, 1968.
[27] Souvik Roy, Nazim Fatès, and Sukanta Das. Reversibility of Elementary Cellular Automata with fully asynchronous updating: An analysis of the rules with partial recurrence. *Theoretical Computer Science*, 1011:114721, 2024.

[28] Eduardo D Sontag. *Mathematical Control Theory: Deterministic Finite Dimensional Systems*, volume 6. Springer Science & Business Media, New York, USA, 2013.

[29] Gérard Y. Vichniac. Boolean derivatives on cellular automata. *Physica D: Nonlinear Phenomena*, 45(1-3):63-74, 1990.

[30] Ingo Wegener. *The complexity of Boolean functions*. Applicable Theory in Computer Science. Vieweg & Teubner, Wiesbaden, Germany, 1987.

[31] Stephen Wolfram. Statistical mechanics of cellular automata. *Reviews of modern physics*, 55(3):601, 1983.

[32] Stephen Wolfram. *A New Kind of Science*. Wolfram Media, Cham-paign, IL, 2002.

[33] X Xiao, S Shao, Y Ding, Z Huang, X Chen, and K-C Chou. Using cellular automata to generate image representation for biological sequences. *Amino acids*, 28:29-35, 2005.