arxiv: 2604.10076 · v1 · submitted 2026-04-11 · 🌊 nlin.CG · cs.SY· eess.SY

Recognition: 2 theorem links

· Lean Theorem

General control of linear cellular automata

Franco Bagnoli , Sara Dridi , Bassem Sellami , Amira Mouakher , Samira El Yacoubi

Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:26 UTC · model grok-4.3

classification 🌊 nlin.CG cs.SYeess.SY

keywords cellular automatacontrollabilitylinear systemscontrollability matrixBoolean cellular automatadiscrete controlone-dimensional automatatwo-dimensional automata

0 comments

The pith

Controllability of linear cellular automata holds exactly when a controllability matrix is invertible.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a control theory tailored to linear and affine cellular automata, discrete grid-based systems whose updates can be written as matrix operations. It defines a controllability matrix built from the transition rules and the locations of external inputs, then proves that the automaton can be driven from any initial configuration to any target configuration in finite time if and only if this matrix is invertible. The result supplies an algebraic test that replaces the classical controllability criteria of continuous linear systems, which do not apply directly to these discrete models. The authors illustrate the test on one- and two-dimensional Boolean examples. If the equivalence holds, engineers and modelers gain a practical way to decide whether chosen inputs can steer the entire state space.

Core claim

We develop a general theory for linear (and affine) cellular automata, and apply it to examples of one-dimensional and two-dimensional Boolean cases. We introduce the concept of controllability matrix and show that controllability holds if and only if the controllability matrix is invertible.

What carries the argument

The controllability matrix, formed by stacking the effects of control inputs across successive time steps according to the linear evolution rule, whose invertibility certifies that every state is reachable from every other state.

If this is right

Controllability reduces to a single matrix inversion or rank computation rather than exhaustive search of state trajectories.
The same matrix test applies unchanged to both one-dimensional rings and two-dimensional grids when the rules remain linear.
Affine updates, which include constant terms, are covered by the same construction after a shift of coordinates.
Once the matrix is known to be invertible, explicit sequences of control inputs can be recovered by solving the corresponding linear system.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The matrix criterion could be used to select minimal sets of control sites that still render a given cellular-automaton rule fully controllable.
For large grids the test may be approximated by examining the rank of truncated controllability matrices whose size grows only with the number of control steps rather than the full state space.
The approach suggests a route for extending reachability analysis to other discrete dynamical systems whose evolution is linear over finite alphabets, such as certain finite-state transducers or linear feedback shift registers.

Load-bearing premise

The cellular automata must follow linear or affine update rules that can be expressed with matrix multiplication over a suitable algebraic structure such as a finite field.

What would settle it

Exhibit a linear cellular automaton whose controllability matrix is singular yet every configuration is still reachable from every other in finite time, or whose matrix is invertible yet some target state cannot be reached from a given initial state.

Figures

Figures reproduced from arXiv: 2604.10076 by Amira Mouakher, Bassem Sellami, Franco Bagnoli, Samira El Yacoubi, Sara Dridi.

**Figure 1.** Figure 1: The adjacency matrix of a 16-sites one-dimensional elementary cellular automaton of 16 sites with (a) fixed or (b) periodic boundary conditions (indexed using the hexadecimal representation of indices). Yellow squares correspond to aij = 1 and black squares to aij = 0. (a) (b) [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 2.** Figure 2: The adjacency matrix of a two-dimensional cellular automaton of 4 × 4 sites with von Neumann neighborhood and (a) fixed or (b) periodic boundary conditions. Yellow squares correspond to aij = 1 and black squares to aij = 0. In general, the global function F is defined by means of a local function fi , which may depend on the site index i (inhomogeneous automata). For instance, for fixed boundary conditions… view at source ↗

**Figure 3.** Figure 3: The evolution of an initial perturbation at time t = 0 on site (0, 0) (red circle) for a linear rule and von Neumann neighborhood, zero boundary conditions. (a) t = 1, (b) t = 2, (c) t = 3, (d) t = 4, after which the patterns (c) and (d) repeat themselves. Color code: black=0, green = 1. controls, but for T = 3, c0(0) s0(0) s1(0) s2(0) s3(0) c1(0) c0(1) s0(1) s1(1) s2(1) s3(1) c1(1) c0(2) s0(2) s1(2) s2(2)… view at source ↗

**Figure 4.** Figure 4: The evolution of an initial perturbation at t = 0 on site (0, 1) (red circle) for a linear rule and von Neumann neighborhood, zero boundary conditions. (a) t = 1, (b) t = 2, (c) t = 3, (d) t = 4, after which the patterns (c) and (d) repeat themselves. Color code: black=0, green = 1. The control matrix is C =   0 1 1 0 1 0 1 0 0 0 0 0   and we get   c0(0) c0(1) c0(2)   =   0 0 1 0 0 1 0 0 1 1 … view at source ↗

**Figure 5.** Figure 5: An example of application of the control in the two-dimensional Von Neumann linear rule with fixed boundaries, where we want to flip cell D (13) at time T = 3. top row: the configuration before applying the control, bottom row: after applying the control, i.e., with cell state flipped. Time is from left to right. The activation times of controls are marked in yellow. (a) (b) (c) (d) [PITH_FULL_IMAGE:figur… view at source ↗

**Figure 6.** Figure 6: (a) The initial configuration at T = 0. (b) The configuration at time T = 4 without controls. (c) The desired configuration. (d) The control sites (red circles) with the corresponding activation times in yellow. And finally a real control experiment. Let us start from configuration with sites 5,6 and 9 on, [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗

read the original abstract

In mathematics and engineering, control theory is concerned with the analysis of dynamical systems through the application of suitable control inputs. One of the prominent problems in control theory is controllability which concerns the ability to determine whether there exists a control input that can steer a dynamical system from an initial state to a desired final state within a finite time horizon. There is a general theory for controlling linear or linearizable system, but it cannot be applied to discrete systems like cellular automata, which is the problem of that we address in this paper. We develop a general theory for linear (and affine) cellular automata, and apply it to examples of one-dimensional and two-dimensional Boolean cases. We introduce the concept of controllability matrix and show that controllability holds if and only if the controllability matrix is invertible.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper adapts the standard Kalman controllability test to linear cellular automata by building global A and B matrices from local rules, then verifies the invertibility condition on small Boolean examples.

read the letter

The paper's central point is that you can test controllability of a linear cellular automaton by checking if a controllability matrix is invertible, just like in ordinary linear systems. They show this by defining the right global matrices for the CA update rule. They do a good job making the connection explicit. The construction of the controllability matrix from the local CA rule and the placement of controls is worked out for one- and two-dimensional grids. The Boolean examples they include are small but sufficient to illustrate that the test gives the expected answer: the system is controllable when the matrix has full rank. The main soft spot is that this is a straightforward application of the Kalman rank condition once the system is written in matrix form. The paper does not introduce new mathematics beyond that representation step. It also sticks to finite grids and field operations, without discussing how the approach scales or what changes if the state space is larger or the rules are more complex. A reader who studies control of discrete or grid-based systems will find this useful as a worked example. It is not groundbreaking, but it fills in the details for cellular automata specifically. The paper deserves to go through peer review. The authors have done the basic work of setting up the framework and checking it on examples, so referees can focus on whether the construction is general enough and whether more applications or proofs are needed.

Referee Report

0 major / 3 minor

Summary. The manuscript develops a general theory for controllability of linear and affine cellular automata. It defines a controllability matrix and proves that controllability holds if and only if this matrix is invertible. The approach is illustrated with explicit constructions and verification on one-dimensional and two-dimensional Boolean cellular automata.

Significance. If the derivations hold, the work supplies a direct, matrix-based test for controllability in linear cellular automata by constructing the global state-transition matrix A and input matrix B from the local CA rule, thereby recovering the classical Kalman rank condition in this discrete setting. The Boolean examples provide concrete verification that the resulting controllability matrix is invertible for the chosen control configurations. This adaptation may be useful for analyzing steering problems in finite-grid discrete systems, though the core equivalence is a standard result once the linear representation is established.

minor comments (3)

The abstract states the main theorem but supplies no proof outline or key assumptions on the state space and control action; a one-sentence indication of the linear representation x_{t+1}=A x_t + B u_t would improve clarity for readers outside control theory.
The manuscript should explicitly reference the classical Kalman controllability criterion and the rank condition to situate the contribution and avoid any appearance of reinventing the linear-algebraic test.
Notation for the controllability matrix (e.g., its explicit block form in terms of A and B) should be introduced with a numbered equation in the main text rather than only in the examples.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report, so we have no point-by-point responses to address. We are pleased that the adaptation of the controllability test to cellular automata is viewed as potentially useful.

Circularity Check

0 steps flagged

No circularity: standard Kalman condition applied after explicit (A,B) construction from CA rules

full rationale

The paper maps linear/affine CA rules to a global linear system x_{t+1}=A x_t + B u_t over a finite vector space, then defines the controllability matrix in the classical form and states the equivalence to controllability. This equivalence is the known Kalman rank condition for finite-dimensional linear systems, which the abstract treats as pre-existing general theory rather than deriving it from the paper's own data, parameters, or self-citations. No self-definitional loop, fitted-input-as-prediction, or load-bearing self-citation appears; the contribution is the CA-specific (A,B) construction and example verification, which remains independent of the controllability theorem itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The approach rests on standard linear algebra applied to discrete systems plus the new controllability matrix; no free parameters or invented physical entities are mentioned.

axioms (1)

domain assumption Linear cellular automata can be represented as linear transformations over appropriate algebraic structures such as finite fields.
Required to define the controllability matrix and apply invertibility criteria.

invented entities (1)

Controllability matrix for cellular automata no independent evidence
purpose: To test whether a linear cellular automaton can be driven from any initial state to any target state.
Newly introduced concept whose properties are asserted to determine controllability.

pith-pipeline@v0.9.0 · 5445 in / 1260 out tokens · 43070 ms · 2026-05-10T16:26:26.559951+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean bool_absolute_floor echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

The Jacobian Jij = ∂s′i/∂sj … in case of linear rules ∂si(T)/∂sj(0)=(J^T)ij

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 9 canonical work pages

[1]

Jacques Louis Lions.Optimal control of systems governed by partial dif- ferential equations. Vol. 170. Springer, 1971

1971
[2]

Exact Controllability, Stabilization and Perturbations for Dis- tributed Systems

J. L. Lions. “Exact Controllability, Stabilization and Perturbations for Dis- tributed Systems”. In:SIAM Review30.1 (Mar. 1988), pp. 1–68.issn: 1095-7200.doi:10.1137/1030001.url:http://dx.doi.org/10.1137/ 1030001

work page doi:10.1137/1030001.url:http://dx.doi.org/10.1137/ 1988
[3]

Eduardo D Sontag.Mathematical Control Theory: Deterministic Finite Dimensional Systems. Vol. 6. New York, USA: Springer Science & Business Media, 2013.doi:10.1007/978-1-4612-0577-7

work page doi:10.1007/978-1-4612-0577-7 2013
[4]

A New Approach to Linear Filtering and Prediction Prob- lems

R. E. Kalman. “A New Approach to Linear Filtering and Prediction Prob- lems”. In:Journal of Basic Engineering82.1 (Mar. 1960), pp. 35–45.issn: 0021-9223.doi:10 . 1115 / 1 . 3662552.url:http : / / dx . doi . org / 10 . 1115/1.3662552

1960
[5]

Markov Chains Ap- proach for Regional Controllability of Deterministic Cellular Automata, via Boundary Actions

Sara Dridi, Franco Bagnoli, and Samira El Yacoubi. “Markov Chains Ap- proach for Regional Controllability of Deterministic Cellular Automata, via Boundary Actions.” In:Journal of Cellular Automata14 (2019)

2019
[6]

Recent advances in regional controllability of cellular au- tomata

Sara Dridi. “Recent advances in regional controllability of cellular au- tomata”. PhD thesis. Perpignan, 2019

2019
[7]

A graph theory approach for regional controllability of Boolean cellular automata

Sara Dridi et al. “A graph theory approach for regional controllability of Boolean cellular automata”. In:International Journal of Parallel, Emer- gent and Distributed Systems(2019), pp. 1–15.doi:10.1080/17445760. 2019.1608442. General control of linear cellular automata 15

work page doi:10.1080/17445760 2019
[8]

Kalman Condition and New Algorithm Approach for Regional Controllability of Peripherally- linear Elementary Cellular Automata via Boundary Actions

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.” In:J. Cell. Autom.16.3-4 (2022), pp. 173–195

2022
[9]

Towardabound- ary regional control problem for Boolean cellular automata

FrancoBagnoli,SamiraElYacoubi,andRaúlRechtman.“Towardabound- ary regional control problem for Boolean cellular automata”. In:Natural Computing17.3 (2018), pp. 479–486.doi:10.1007/s11047-017-9626-1

work page doi:10.1007/s11047-017-9626-1 2018
[10]

Regional control of probabilistic cellular automata

Franco Bagnoli et al. “Regional control of probabilistic cellular automata”. In:International Conference on Cellular Automata. Springer. New York, USA, 2018, pp. 243–254.doi:10.1007/978-3-319-99813-8_22

work page doi:10.1007/978-3-319-99813-8_22 2018
[11]

Optimal and suboptimal regional control of prob- abilistic cellular automata

Franco Bagnoli et al. “Optimal and suboptimal regional control of prob- abilistic cellular automata”. In:Natural Computing18.4 (2019), pp. 845– 853.doi:10.1007/s11047-019-09763-5

work page doi:10.1007/s11047-019-09763-5 2019
[12]

Molloy and B

Franco Bagnoli, Michele Baia, and Tommaso Matteuzzi. “Effects of a Van- ishing Noise on Elementary Cellular Automata Phase-Space Structure”. In:Cellular Automata. New York, USA: Springer Nature, 2024, pp. 45– 57.isbn: 9783031715525.doi:10.1007/978- 3- 031- 71552- 5_5.url: http://dx.doi.org/10.1007/978-3-031-71552-5_5

work page doi:10.1007/978- 2024
[13]

Boundary regional controllability of linear boolean cellular automata using markov chain

Sara Dridi, Samira El Yacoubi, and Franco Bagnoli. “Boundary regional controllability of linear boolean cellular automata using markov chain”. In:Recent advances in modeling, analysis and systems control: theoretical aspects and applications. Springer, 2019, pp. 37–48

2019
[14]

Con- trolled cellular automata

Achilles Beros, Monique Chyba, and Oleksandr Markovichenko. “Con- trolled cellular automata”. In:Networks and Heterogeneous Media14.1 (2019), pp. 1–22. [15]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://...

2019
[15]

Phys Nonlinear Phenom 65(1-2):117-134

Gérard Y. Vichniac. “Boolean derivatives on cellular automata”. In:Phys- ica D: Nonlinear Phenomena45.1–3 (1990), pp. 63–74.issn: 0167-2789. doi:10.1016/0167- 2789(90)90174- n.url:http://dx.doi.org/10. 1016/0167-2789(90)90174-N

work page doi:10.1016/0167- 1990
[16]

Booleanderivativesandcomputationofcellularautomata

FrancoBagnoli.“Booleanderivativesandcomputationofcellularautomata”. In:International Journal of Modern Physics C3.02 (1992), pp. 307–320. doi:10.1142/S0129183192000257

work page doi:10.1142/s0129183192000257 1992