Cellular Automata and Finite Groups

Abstract

For a finite group $G$ and a finite set $A$, we study various algebraic aspects of cellular automata over the configuration space $A^G$. In this situation, the set $\text{CA}(G;A)$ of all cellular automata over $A^G$ is a finite monoid whose basic algebraic properties had remained unknown. First, we investigate the structure of the group of units $\text{ICA}(G;A)$ of $\text{CA}(G;A)$. We obtain a decomposition of $\text{ICA}(G;A)$ into a direct product of wreath products of groups that depends on the numbers ${\alpha }_{[H]}$ of periodic configurations for conjugacy classes $[H]$ of subgroups of $G$. We show how the numbers ${\alpha }_{[H]}$ may be computed using the Möbius function of the subgroup lattice of $G$, and we use this to improve the lower bound recently found by Gao, Jackson and Seward on the number of aperiodic configurations of $A^G$. Furthermore, we study generating sets of $\text{CA}(G;A)$; in particular, we prove that $\text{CA}(G;A)$ cannot be generated by cellular automata with small memory set, and, when all subgroups of $G$ are normal, we determine the relative rank of $\text{ICA}(G;A)$ on $\text{CA}(G;A)$, i.e. the minimal size of a set $V\subseteq \text{CA}(G;A)$ such that $\text{CA}(G;A)=⟨\text{ICA}(G;A)\cup V⟩$.

To appear in Natural Computing, Special Issue Automata 2016. Extended version of arXiv:1601.05694

References in corpus (3)

• The rank of the semigroup of transformations stabilising a partition of a finite set
• On Finite Monoids of Cellular Automata
• Ranks of finite semigroups of one-dimensional cellular automata

Cited by in corpus (7)

• Elementary, Finite and Linear vN-Regular Cellular Automata
• Generating infinite monoids of cellular automata
• On the minimal number of generators of endomorphism monoids of full shifts
• The number of configurations in the full shift with a given least period
• The relative rank of the endomorphism monoid of a finite $G$-set
• The Möbius function of $\mathrm{PSL}(3,2^p)$ for any prime $p$
• Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and Enumeration