CS Paper Radar

A characterization of the reversibility of linear cellular automata

Alonso Castillo-Ramirez

cs.FL math.GRmath.DS ·submitted 2026-08-20 22:40 UTC · v2
theoryunusual

Abstract

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.

Comment
10 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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.62
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

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.59
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

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.55
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

Conjugacy problems in higher-dimensional Thompson groups

cs.FL math.GRmath.DS ·2026-10-08 ·Ville Salo
theory similarity 0.53
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

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.53
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

Topological Entropy of Group Cellular Automata is Effectively Computable

cs.CC math.DS ·2026-11-12 ·Niccolò Castronuovo, Alberto Dennunzio, Jarkko Kari, Luciano Margara
theory similarity 0.52
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.

0.22

Boxes in Infinite Words: Complexity, Automata, and Point Modules

cs.FL math.LOmath.RA ·2026-11-16 ·Jason Bell
theory similarity 0.52
Abstract · 23 pages

Motivated by the geometry of point modules over monomial algebras, we introduce a box-counting function associated to a right-infinite word over a finite alphabet. An extendable box is a family of finite words obtained by choosing letters independently at each position, subject to the condition that all choices admit a common infinite right continuation in the associated subshift. We prove several results for these functions for words of linearly bounded complexity. For $k$-automatic words, we show using techniques from first-order logic that the total box-counting function is $k$-regular. Finally, we apply our results to prove eventual affine growth of the number of positive-dimensional irreducible components in finite projections of point-module spaces associated to semiprime monomial algebras of at most quadratic growth.

0.35

A $G$-Invariant Erdős--Hanani Theorem with Applications to Optical Orthogonal and Constant-Weight Codes

cs.IT math.CO ·2026-10-07 ·Yeow Meng Chee
theory similarity 0.51
Abstract · 16 pages, 1 table

Let $k>t\ge 2$ be fixed integers, and let $G$ be a permutation group on a set of $v$ points. A $G$-invariant packing is free if every block has $|G|$ distinct images under $G$. We give two conditions on $G$ under which, as $v\to\infty$, there is a free $G$-invariant $t$-$(v,k,1)$ packing with $(1-o(1))\binom{v}{t}/\binom{k}{t}$ blocks. This is a $G$-invariant form of the Erdős--Hanani theorem on asymptotically optimal packings. For semiregular groups $G$, packings with these properties exist if and only if all but $o(v^t)$ of the $t$-subsets of points have trivial setwise stabiliser. This property is satisfied by every semiregular group for $t\ge 3$, and by every cyclic semiregular group for $t=2$. As a consequence, the Johnson bound is asymptotically attained at all lengths by optical orthogonal codes of constant weight $w$ and constant correlation $λ$ with $w\geλ+2$, by their multidimensional and signature pattern versions, and by cyclic and quasi-cyclic constant-weight codes. The same method gives a form of the theorem for group divisible packings that are invariant under a cyclic group. This determines the asymptotic maximum size of two-dimensional optical orthogonal codes with at most one pulse per wavelength.

0.28