← 研踪 PaperTrailarXiv:2611.22365 · v1
Strong Transitivity of Group Cellular Automata: Characterization and Decidability
首次提交 2026-11-17 16:20
版本更新 2026-11-17 16:20
雷达观测 2026-11-18 19:42
摘要
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 . 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 we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial of the associated matrix of Laurent polynomials: the automaton is strongly transitive if and only if and no irreducible factor of 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 , we give an explicit decision procedure whose running time is polynomial in the group size , the number of neighbours, and the neighbourhood radius .
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 16:20 · 最新观测版本
Strong Transitivity of Group Cellular Automata: Characterization and Decidability
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 . 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 we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial of the associated matrix of Laurent polynomials: the automaton is strongly transitive if and only if and no irreducible factor of 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 , we give an explicit decision procedure whose running time is polynomial in the group size , the number of neighbours, and the neighbourhood radius .
查看此版本解读 →查看此版本原文 ↗