Accepted papers

You can find the accepted extended abstracts and the accepted exploratory papers here. 

Antonio E. Porreca and Marius Rolland
Solving “pseudo-injective” polynomial equations over finite dynamical systems
We consider the semiring of abstract finite dynamical systems up to isomorphism, with the operations of alternative and synchronous execution. We continue searching for efficient algorithms for solving polynomial equations of the form P(X) = B, with a constant side B, with the goal of decomposing complex behaviors into simpler systems. Taking inspiration from the characterization of injective polynomials P over dynamical systems, which is based on a condition on the lengths of limit cycles of their coefficients, we introduce a more general notion of pseudo-injectivity by relaxing this constraint. We prove that the associated equations can be solved efficiently, even in certain cases where the input is encoded in an exponentially more compact way.
 

Tom Favereau and Ville Salo
Descriptive Complexity of Sensitivity of Cellular Automata
We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is Π₂⁰-complete in dimension 1 and Σ₃⁰-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.
 

Benjamin Hellouin de Menibus, Ville Salo and Ilkka Törmä
Symbol Frequencies in Surjective Cellular Automata
We study the behavior of probability measures under iteration of a surjective cellular automaton. We solve the following question in the negative: if the initial measure is ergodic and has full support, do all weak-* limit points of the sequence of measures have full support as well? The initial measure of our solution is not a product measure, and in this case the question remains open. To this end, we present a tool for studying the frequencies of symbols in preimages of surjective cellular automata, and prove some basic results about it. However, we show that by itself it is not enough to solve the stricter question in the positive.
 

Xuan Kien Phung
On Gottschalk's surjunctivity conjecture for non-uniform cellular automata
Gottschalk’s surjunctivity conjecture for a group G states that it is impossible for cellular automata (CA) over the universe G with finite alphabet to produce strict embeddings of the full shift into itself. A group universe G satisfying Gottschalk’s surjunctivity conjecture is called a surjunctive group. The surjunctivity theorem of Gromov and Weiss shows that every sofic group is surjunctive. In this paper, we study the surjunctivity of local perturbations of CA and more generally of non-uniform cellular automata (NUCA) with finite memory and uniformly bounded singularity over surjunctive group universes. In particular, we show that such a NUCA must be invertible whenever it is reversible. We also obtain similar results which extend to the class of NUCA a certain dual surjunctivity theorem of Capobianco, Kari, and Taati for CA.
 

Pacôme Perrotin, Pedro Paulo Balbi and Eurico Ruivo
A sequential solution to the density classification task using an intermediate alphabet
We present a sequential cellular automaton of radius 21 as a solution to the density classification task that makes use of an intermediate alphabet, and converges to a clean fixed point with no remaining auxiliary or intermediate information. We extend this solution to arbitrary finite alphabets and to configurations in higher dimensions.
 

Pablo Concha-Vega and Kévin Perrot
Timed Prediction Problem for Sandpile Models
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the height adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.
 

Jérôme Casse, Irène Marcovici and Maxence Poutrel
Ergodicity of the hard-core PCA with a random walk method
The hard-core probabilistic cellular automaton has attracted a renewed interest in the last few years, thanks to its connection with the study of a combinatorial game on percolation configurations. We provide an alternative proof for the ergodicity of this PCA for a neighbourhood of size 2 and 3, using the notion of decorrelated islands introduced by Casse in 2023, together with some new ideas. This shortens the previous proofs and provides a more intuitive and unified approach.
 

Henryk Fukś
Ternary cellular automata induced by semigroups of order 3 are solvable
The minimal number of inputs in the local function of a non-trivial cellular automaton is two. Such a function can be viewed as as a kind of binary operation. If this operation is associative, it forms, together with the set of states, a semigroup. There are 18 semigroups of order 3 up to equivalence, and they define 18 cellular automata rules with three states. We investigate these rules with respect to solvability and show that all of them are solvable, meaning that the state of a given cell after n iterations can be expressed by an explicit formula. We derive the relevant formulae for all 18 rules using some additional properties possessed by particular semigroups of order 3, such as commutativity and idempotence.
 

Honglu Sun, Maxime Folschette, Morgan Magnin and Elisa Tonello
Conditions for cyclic attractors for a class of discrete n-dimensional repressilators
Repressilators are biological regulatory networks in which components interact only in terms of negative influences. They are of interest in biology, since their oscillatory behavior can inform the design of gene therapies. Although sustained oscillations are ensured in 3-dimensional repressilators, that is, in systems made of 3 genes, they do not always appear in higher dimensions, as their occurrence depends on the topology of the network and on the chosen parameters. Here we focus on discrete models, where the presence of at least one cyclic attractor is required for sustained oscillations. Even in a discrete framework, enumerating and simulating all possible models can quickly become computationally infeasible. In this paper, we provide a sufficient condition for the presence of sustained oscillations for a class of repressilators, based on the structure of their influence graphs. The condition applies in any dimension and independently of the parameters, that is, threshold labeling of the edges. We also study the coexistence of cyclic attractors and fixed points in dimension 4.
 

Alonso Castillo-Ramirez, Alejandro Vazquez-Aceves and Angel Zaldivar-Corichi
Categorical products of cellular automata
 We study two categories of cellular automata. First, for any group G, we consider the category CA(G) whose objects are configuration spaces of the form A^G, where A is a set, and whose morphisms are cellular automata of the form τ: A₁^G → A₂^G. We prove that the categorical product of two configuration spaces A₁^G and A₂^G in CA(G) is the configuration space (A₁ × A₂)^G. Then, we consider the category of generalized cellular automata GCA, whose objects are configuration spaces of the form A^G, where A is a set and G is a group, and whose morphisms are ϕ-cellular automata of the form T : A₁^G₁ → A₂^G₂, where ϕ : G₂ → G₁ is a group homomorphism. We prove that a categorical weak product of two configuration spaces A₁^G₁ and A₂^G₂ in GCA is the configuration space (A₁ × A₂)^{G₁ ∗ G₂}, where G₁ ∗ G₂ is the free product of G₁ and G₂ . The previous results allow us to naturally dene the product of two cellular automata in CA(G) and a weak product of two generalized cellular automata in GCA.
 

Luca Mariot and Federico Mazzone
Self-Orthogonal Cellular Automata
It is known that no-boundary Cellular Automata (CA) defined by bipermutive local rules give rise to Latin squares. In this paper, we study under which conditions the Latin square generated by a bipermutive CA is self-orthogonal, i.e. orthogonal to its transpose. We first enumerate all bipermutive CA over the binary alphabet up to diameter d = 6, remarking that only some linear rules give rise to self-orthogonal Latin squares. We then give a full theoretical characterization of self-orthogonal linear CA, by considering the square matrix obtained by stacking the transition matrices of the CA and of its transpose, and determining when it is invertible. Interestingly, the stacked matrix turns out to have a circulant structure, for which there exists an extensive body of results to characterize its invertibility. Further, for the case of the binary alphabet we prove that irreducibility is a sufficient condition for self-orthogonality, and we derive a simpler characterization which boils down to computing the parity of the central coefficients of the local rule.

Jade Angela Hope Audouard and Guillaume Theyssier
On Kurka’s dichotomy for cellular automata on groups
This paper is about topological dynamics of cellular automata on finitely generated groups. We tackle the problem of determining for which group sensitivity to initial conditions is equivalent to the absence of equicontinuity points (so-called Kurka’s dichotomy). We show that the dichotomy holds on any virtually-Z group but not on free groups with 2 or more generators. We also show that if it holds on some group, it must hold on any of its subgroups.
 

Thomas Prévost and Bruno Martin
A 10-bit S-box generated by Feistel construction from cellular automata
We propose a new 10-bit S-box generated from a Feistel construction. The subpermutations are generated by a 5-cell cellular automaton based on a unique well-chosen rule and bijective affine transformations. In particular, the cellular automaton rule is chosen based on empirical tests of its ability to generate good pseudorandom output on a ring cellular automaton. Similarly, Feistel’s network layout is based on empirical data regarding the quality of the output S-box. We perform cryptanalysis of the generated 10-bit S-box, and we find security properties comparable to or sometimes even better than those of the standard AES S-box. We believe that our S-box could be used to replace the 5-bit substitution of ciphers like ASCON.
 

Victor Lutfalla
Sideways on the highways
We present two generalised ants (LLRRRL and LLRLRLL) which admit both highway behaviours and other kinds of emergent behaviours from initially finite configurations. This limits the well known Highway conjecture on Langton’s ant as it shows that a generalised version of this conjecture generically does not hold on generalised ants.
 

Léo Poirier and Guillaume Theyssier
One-dimensional monotone cellular-automata acting on probability measures
In this paper we study the action of monotone Boolean one-dimensional cellular automata on probability measures. We show that any such cellular automaton converges in Cesaro mean towards a computable measure, when initialized on a shift-ergodic full support measure. However, we show that in some cases there is no simple convergence, even when starting from the uniform measure, and that the support of the limit can be uncomputable. We also show that mu-nilpotency is undecidable for monotone Boolean one-dimensional cellular automata.
 

Nazim Fates
A Note on Endogamous Diploid Elementary Cellular Automata
Diploid cellular automata are stochastic mixtures of two local rules: at each time step each cell independently applies one rule with a given probability λ and the other rule with probability 1 - λ . Here, following a proposition by Roy et al., we investigate the subset of the 168 endogamous rules, that is, the diploid rules formed by a rule and one of its symmetric. Even with such a restriction, these diploids have a great diversity of dynamics. We study the cases where the average convergence time has a logarithmic, linear, or quadratic scaling law and show that this characterisation is useful to understand the behaviour of these endogamous rules.
 

Firas Ben Ramdhane
On surjectivity and dynamical properties of dill maps
In this paper, we study certain dynamical properties of dill maps, a class of functions introduced in [9] that generalizes both cellular automata and substitutions. In particular, we prove that surjective uniform dill maps are precisely the surjective cellular automata. We also establish a sufficient condition for a dill map to be equicontinuous.
 

Louis Paletta, Mazyar Mirrahimi, Anthony Leverrier and Christophe Vuillot
High-performance local automaton decoders for defect matching in 1D
Local automaton decoders offer a promising path toward real-time quantum error correction by replacing centralized classical decoding, with inherent hardware constraints, by a natively parallel and streamlined architecture from a simple local transition rule. We propose two new types of local decoders for the quantum repetition code in one dimension. The signal-rule decoders interpret odd parities between neighboring qubits as defects, attracted to each other via the exchange of classical point-like excitations, represented by a few bits of local memory. We prove the existence of a threshold in the code-capacity model and present numerical evidence of exponential logical error suppression under a phenomenological noise model, with data and measurement errors at each error correction cycle. Compared to previously known local decoders that suffer from sub-optimal threshold and scaling, our construction significantly narrows the gap with global decoders for practical system sizes and error rates. Implementation requirements can be further reduced by eliminating the need for local classical memories, with a new rule defined on two rows of qubits. This shearing-rule works well at relevant system sizes but is without a threshold. When combined with biased-noise qubits, such as cat qubits, these decoders enable a fully local
quantum memory in one dimension.
 

Van-Giang Trinh, Samuel Pastva, Jordan Rozum, Kyu Hyong Park and Réka Albert
On the number of asynchronous attractors in AND-NOT Boolean networks
Boolean Networks (BNs) are a mathematical formalism that has applications in various areas of science and engineering, and especially in systems biology. Due to the noisy nature and incomplete characterization of biological systems, a stochastic asynchronous update scheme is often more appropriate than the deterministic synchronous one. AND-NOT BNs, whose logic functions are the conjunction of literals, are an important subclass of BNs because of their structural simplicity and usefulness in analyzing biological systems. In this paper, we derive one upper bound for the number of asynchronous attractors in an AND-NOT BN based on the notion of dominating sets. This finding has useful implications for not only BN research, but also symbolic AI research.

Edgar Alcalá-Arroyo and Alonso Castillo-Ramirez
Dynamical behavior of cellular automata with a unique quasi-constant active transition
Let G be a group and let A be a set with at least two elements. A cellular automaton (CA) τ : A^G → A^G has a unique active transition if the identity e of G is in the local neighborhood S of τ and there exists a pattern p ∈ A^S such that μ(p) ≠ p(e) and μ(z) = z(e) for all z ∈ A^S\{p}, where μ : A^S → A is the local defining map of τ. We study CA with a unique active transition p ∈ A^S that is quasi-constant i.e., p is not constant but there exists an r ∈ S such that p restricted to S\{r} is constant. We extend the idempotency characterization obtained in [1] by completely describing the dynamical behavior of such CA.
 

Michiel Rollier, Lucas Caldeira de Oliveira, Odemir Bruno and Jan Baetens
Impact maximisation: a network automaton perspective
The emergent structures of complex systems in nature and society often appear to be robust: small changes to initial conditions generally do not qualitatively affect the global behaviour. However, such (in)sensitivities to initial conditions are far from being fully understood. Exposing and mapping sensitivities in complex systems is a crucial step towards better understanding and designing robust dynamical models — or towards exploiting a targeted disturbance that is capable of tipping the scale. We explore fundamental answers to a highly stylised form of difficult questions such as those posed above. We do so by studying the dynamical processes of cellular automata (CAs), which serve as a computational laboratory for the formal study of emergence [8]. In particular, we investigate so-called life-like network automata (LLNAs): models proposed by Miranda et al. [4] in the context of pattern recognition [9], in which the famous Game of Life [3] is generalised onto a network topology [5].
 

Nassima Ait Sadi and Nazim Fates
A partial cellular automaton solution for self-stabilisation of 3-colourings
We present a cellular automaton that partially solves the problem of self-stabilisation of 3-colourings. Indeed, this case is known to be difficult and finding a full or partial solution is still an open problem [2]. Our rule follows a directional correction process and corrects almost all the cases. There are however some specific configurations for which the correction process is not finite and for which the errors are sent at infinity.
 

Dominik Falkiewicz, Barbara Wolnik, Witold Bołt and Adam Rutkowski
New perspective on the number-conserving cellular automata
Cellular automata with particle-like behavior offer intuitive models for physical processes such as fluid or granular flow. Although such dynamical systems are known to successfully capture particle dynamics, the complete enumeration of all such cellular automata for two-dimensional Moore neighborhoods remains unresolved. In this paper, we propose a novel framework that simplifies their structural analysis, enabling for the first time a systematic enumeration of such cellular automata, and offering a clear physical interpretation in terms of particle movement rules reminiscent of traffic dynamics.