
arXiv: 2507.09761
We prove that many dynamical properties of group cellular automata (i.e., cellular automata defined on any finite group and with global rule which is an endomorphism), including surjectivity, injectivity, sensitivity to initial conditions, strong transitivity, positive expansivity, and topological entropy, can be decided by decomposing them into a set of much simpler group cellular automata. To be more specific, we provide a novel algorithmic technique allowing one to decompose the group cellular automaton to be studied into a finite number of group cellular automata, some of them defined on abelian groups, while others, if any, defined on products of simple non-abelian isomorphic groups. It is worth noting that the groups resulting from the decomposition only depend on the original group and therefore they are completely independent of both the automaton and the property under investigation. As a result, they do not inherit any aspect of the complexity of the automaton under investigation. We prove that the group cellular automata obtained by the decomposition preserve dynamical properties and turn out to be much easier to analyze if compared to the original cellular automaton. As a consequence of these results, we show that injectivity, surjectivity and sensitivity to initial conditions are decidable properties and that no strongly transitive, and therefore no positively expansive, group cellular automata defined on non-abelian groups exist. Moreover, we prove that the topological entropy of a group cellular automaton can be computed, provided we know how to compute the topological entropy for group cellular automata defined on products of simple non-abelian isomorphic groups and on abelian groups.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Discrete Mathematics, Formal Languages and Automata Theory (cs.FL), Formal Languages and Automata Theory
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Discrete Mathematics, Formal Languages and Automata Theory (cs.FL), Formal Languages and Automata Theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
