Advertisement
Published in:
30-09-2017
Cellular automata and finite groups
Published in: Natural Computing | Issue 3/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \(\mathrm {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 \(\mathrm {ICA}(G;A)\) of \(\mathrm {CA}(G;A)\). We obtain a decomposition of \(\mathrm {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 \(\mathrm {CA}(G;A)\); in particular, we prove that \(\mathrm {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 \(\mathrm {ICA}(G;A)\) on \(\mathrm {CA}(G;A)\), i.e. the minimal size of a set \(V \subseteq \mathrm {CA}(G;A)\) such that \(\mathrm {CA}(G;A) = \langle \mathrm {ICA}(G;A) \cup V \rangle\).