CS Paper Radar

Topological Entropy of Group Cellular Automata is Effectively Computable

Niccolò Castronuovo, Alberto Dennunzio, Jarkko Kari, Luciano Margara

cs.CC math.DS ·submitted 2026-11-12 12:58 UTC · v1
theory

Abstract

Topological entropy is a fundamental invariant of dynamical systems, quantifying their complexity. For cellular automata, however, determining topological entropy is generally algorithmically intractable. We study group cellular automata, namely cellular automata over a finite group alphabet whose global map is a group endomorphism. In dimension one, we decompose topological entropy into two one-sided components describing information propagating from the left and from the right in space--time. We introduce finite families of left and right traces and prove that the entropy is the sum of their growth rates. Hence, the entropy is completely determined by the growth rate of a fixed-width family of space--time patterns. This reduction from arbitrarily large windows to uniformly bounded width yields an effective procedure for computing the entropy. In particular, the entropy of every one-dimensional group cellular automaton is the logarithm of a positive integer. Using Pontryagin duality and the Bridge Theorem between topological and algebraic entropy, we also derive an explicit formula for linear cellular automata over $(\mathbb{Z}/p\mathbb{Z})^n$ in terms of their characteristic polynomial. Moreover, in every dimension $D\geq 2$, a group cellular automaton is either equicontinuous with zero entropy or sensitive to initial conditions with infinite entropy. Combined with decidability of equicontinuity, this implies that topological entropy is effectively computable from the local rule in every dimension. Thus, group cellular automata form a natural nontrivial class in which algebraic structure restores computability of topological entropy.

Closest papers

Nearest neighbours by meaning across the whole index.

Spatiotemporal Dynamics of Conway's Game of Life in the Entropy--Complexity Plane

cs.IT nlin.CD ·2026-10-21 ·Lucas Malacarne Astore, Alejandro C. Frery, Petrônio Cândido de Lima e Silva, Frederico Gadelha Guimarães
similarity 0.63
Abstract

We investigate the dynamics of Conway's Game of Life (GoL) through the lens of Ordinal Pattern analysis. Each GoL generation is transformed into a one-dimensional time series, from which ordinal patterns are extracted to characterize its underlying dynamics. The resulting ordinal distributions are then represented in the Entropy--Statistical Complexity ($H \times C$) plane, enabling a quantitative analysis of the system's evolution. We evaluate different encoding strategies, including patch sizes and linearization methods, and assess their impact on the resulting $H \times C$ trajectories. Finally, we characterize the emergent dynamics in terms of convergence behavior, trajectory patterns, and statistical complexity, showing how the proposed entropy--complexity framework provides insights into the dynamics of cellular automata.

0.26

Strong Transitivity of Group Cellular Automata: Characterization and Decidability

cs.DM cs.FLmath.DS ·2026-11-17 ·Niccolò Castronuovo, Alberto Dennunzio, Luciano Margara
theory similarity 0.63
Abstract

A discrete-time dynamical system is strongly transitive if every point can be reached, in finitely many steps, from every non-empty open set. We study this property for group cellular automata, \ie cellular automata over a finite group alphabet whose global map is a group endomorphism, in every dimension $d\geq1$. We prove that no group cellular automaton over a non-abelian group is strongly transitive, and we develop a decomposition of group cellular automata over abelian groups, via quotients by power subgroups, which preserves strong transitivity. For linear cellular automata over $(\mathbb Z/p\mathbb Z)^n$ we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial $χ_A$ of the associated matrix $A$ of Laurent polynomials: the automaton is strongly transitive if and only if $\det(A)\neq0$ and no irreducible factor of $χ_A$ has an invertible constant term. Combining these results, we obtain that strong transitivity is decidable for group cellular automata in every dimension. For every fixed dimension $d$, we give an explicit decision procedure whose running time is polynomial in the group size $N$, the number $k$ of neighbours, and the neighbourhood radius $\varrho$.

0.34

Functorial Analysis of Group-Alphabet Cellular Automata

cs.FL math.GRmath.COmath.CT+1 ·2026-10-29 ·François Huard, Nathan Dion Larivière
similarity 0.60
Abstract

Let $G$ be a group and let $n\in\mathbb N$. We consider one-dimensional cellular automata of length $n$ over the alphabet $G$, with periodic boundary conditions and with local rules $φ$ given by words. We construct a functor $F$ from $\mathbf{Grp}$, the category of groups (or any similar algebraic structure), to the category of pointed digraphs, and show its faithfulness. We introduce the image category $\mathcal C_{n,φ}$ of state transition graphs of all such group-alphabet cellular automata, and show $F$ is an equivalence onto this category. Consequently we investigate the translation of categorical structures in $\mathbf{Grp}$ in terms of automata, and give examples of how standard methods of homological algebra may now be applied to automata. Additionally, a graph-theoretical construction of the product in $\mathcal C_{n,φ}$ is given, together with a formula for cycle lengths and multiplicities in this product. When $G$ is abelian, further structural properties of state transition graphs follow, and we contrast these results with non-abelian counterexamples.

0.19

Locally eventually onto cellular automata

cs.FL cs.DMmath.COmath.DS+1 ·2026-10-23 ·Jan Kristian Haugland, Nadia S. Larsen, Tron Omland, Henrikke G. Rustad
similarity 0.60
Abstract · 29 pages

We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is locally eventually onto. In this setting, openness is equivalent to being n-to-1 for some n and therefore implies surjectivity. Bipermutive cellular automata are known to be locally eventually onto, while open cellular automata that are neither bipermutive nor bijective appear to have received less attention. Building on Sutner's work with de Bruijn graphs, we describe a method for deciding openness and at the same time determining n. We then introduce the notion of block-regularity of local rules as a generalization of bipermutivity and prove that it implies openness. We further identify two conditions that, together with block-regularity, ensure that every nonempty cylinder set is mapped onto the whole configuration space after a finite number of iterations, and hence that the cellular automaton is locally eventually onto. The appendix provides the algorithms that check these finite criteria and then presents examples of locally eventually onto, non-bipermutive cellular automata for small diameters.

0.27

A characterization of the reversibility of linear cellular automata

cs.FL math.GRmath.DS ·2026-08-20 ·Alonso Castillo-Ramirez
theoryunusual similarity 0.52
Abstract · 10 pages

Let $G$ be a group, let $\mathbb{K}$ be a field, and let $V$ be a $\mathbb{K}$-vector space. We prove that there exists a bijective linear cellular automaton $V^G\to V^G$ whose inverse is not a cellular automaton if and only if $G$ is not locally finite and $\dim_{\mathbb{K}}V \geq |\mathbb{K}|^{\aleph_0}$. In particular, $|\mathbb{K}|^{\aleph_0}$ is the exact dimension threshold for non-reversibility. This answers an open problem proposed by T. Ceccherini-Silberstein and M. Coornaert.

0.30

A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry

cs.CC math.COcs.FLcs.LO ·2026-09-04 ·Jineon Baek, Byung-Hak Hwang, Joonhyun La, Hongseok Yang
theorycode/data similarity 0.51
Abstract · 76 pages, Lean formalisation available at https://github.com/hongseok-yang/automata-catalan-symmetry-release

Algebraic combinatorics often seeks bijections that explain identities between distributions object by object. Encoding combinatorial objects as words lets automata theory study such a bijection as a word-to-word computation and measure its memory, input access, and control of output order. This refines existence questions by asking which computational mechanisms a bijection requires. We develop this viewpoint for Dyck paths. Our motivating example is the $q,t$-Catalan polynomial. Let $D_n$ be the set of Dyck paths of semilength $n$, let $D=\bigcup_{n\ge 0}D_n$, and let $area, dinv, bounce \colon D\to\mathbb{N}$ be the standard statistics. Then, \[ C_n(q,t)=\sum_{P\in D_n}q^{area(P)}t^{bounce(P)} =\sum_{P\in D_n}q^{dinv(P)}t^{area(P)}. \] Haglund's zeta map $ζ\colon D\to D$ gives a bijective proof: it preserves semilength and sends $(dinv,area)$ to $(area,bounce)$. By contrast, the full symmetry $C_n(q,t)=C_n(t,q)$ still lacks a direct explanation: no explicit, uniform, semilength-preserving bijection is known that swaps area and dinv on every Dyck path. Polyregular maps from automata theory provide a natural computational starting point, but we prove that neither $ζ$ nor the classical height-sweep bijection witnessing Narayana symmetry is polyregular. The missing mechanism is global ordering by numerical levels whose range grows with the input. We call this a \emph{rank sort} and introduce \emph{weighted-rank polyregular maps} (WRP), extending polyregular maps by one such sort and containing both bijections. Nevertheless, WRP is a proper subclass of deterministic logspace. We prove that $ζ^{-1}$ lies outside WRP and that no WRP map can realise a semilength-preserving area-dinv swap. Thus the rank-sorting strategy behind $ζ$ cannot be extended within WRP to exchange the two statistics.

0.43

Conjugacy problems in higher-dimensional Thompson groups

cs.FL math.GRmath.DS ·2026-10-08 ·Ville Salo
theory similarity 0.51
Abstract · 17 pages

We prove that topological conjugacy of elements of the Brin--Thompson group $nV$ is undecidable for every $n\geq2$. From a Turing machine $T$, the reduction produces two elements of $nV$, which are conjugate by an involution in $nV$ if $T$ halts on the empty tape. If $T$ does not halt on the empty tape, the topological dynamics of the two group elements are distinguished by their visits to minimal subsystems of the set of (germ-)aperiodic points. In these groups, and any finitely-generated supergroups inside the homeomorphism group of Cantor space, we also obtain undecidability of the Whitehead problem (the problem of being in the same automorphism orbit), and undecidability of group-theoretic conjugacy.

0.28

Rule-table structure of life-like cellular automata: activity, asymmetry, sensitivity, and the propagation storage factorisation

cs.LG q-bio.PE ·2026-11-07 ·Yair Cohen
unusual similarity 0.50
Abstract

What structure on the rule space of a cellular-automaton family exposes which rules can support which behaviours? For the 262,144 life-like rules -- the two-dimensional outer-totalistic family containing Conway's Game of Life -- the standard coordinate, Langton's activity parameter, is long known to be too coarse. I organise the family by three symmetry-derived rule-table coordinates: an unweighted activity, a birth-survival asymmetry (odd under the swap of birth and survival), and the Vichniac-Binder Boolean-derivative sensitivity in closed form, whose centre-bit component vanishes exactly on the centre-blind (B=S) submanifold. The cardinality coordinates lambda, delta are necessary but never sufficient to certify behaviour; the centre-bit sensitivity labels the B=S submanifold on which the paper's one exact exclusion holds. Combined with an exhaustive enumeration of every rule's compact gliders, still lifes and oscillators (three-by-three seed, period at most sixteen), they expose a hierarchical factorisation: the birth condition is a narrow gate deciding whether anything can propagate, the survival condition tunes storage, and every compact-glider-supporting rule is birth-light and survival-rich. One exclusion is exact: no B=S rule supports a compact glider at that footprint, proven by exhaustive enumeration and closing only for compact-footprint patterns -- 36 B=S rules ship at four-by-four seed and 40 at five-by-five. Two dynamical results frame the whole: glider-capable rules that random sampling never expresses show that capability is certifiable from the table while its expression is only estimable from dynamics; and every uncatalogued rule producing a richly Life-like ecology turns out to be a Conway or HighLife variant on the neighbour counts its trajectories actually visit.

0.26