On Finite Monoids of Cellular Automata

Abstract : For any group G and set A, a cellular automaton over G and A is a transformation $\mathrm{\tau <!--\; \tau \; -->}:A^G\to <!--\; \to \; -->A^G$ defined via a finite neighbourhood $S\subseteq <!--\; \subseteq \; -->G$ (called a memory set of $\mathrm{\tau <!--\; \tau \; -->}$) and a local function $\mathrm{\mu <!--\; \mu \; -->}:A^S\to <!--\; \to \; -->A$. In this paper, we assume that G and A are both finite and study various algebraic properties of the finite monoid $\mathrm{C}\mathrm{A}(G,A)$ consisting of all cellular automata over G and A. Let $\mathrm{I}\mathrm{C}\mathrm{A}(G;A)$G and A. In the first part, using information on the conjugacy classes of subgroups of G, we give a detailed description of the structure of $\mathrm{I}\mathrm{C}\mathrm{A}(G;A)$ in terms of direct and wreath products. In the second part, we study generating sets of $\mathrm{C}\mathrm{A}(G;A)$. In particular, we prove that $\mathrm{C}\mathrm{A}(G,A)$ cannot be generated by cellular automata with small memory set, and, when G is finite abelian, we determine the minimal size of a set $V\subseteq <!--\; \subseteq \; -->\mathrm{C}\mathrm{A}(G;A)$ such that $\mathrm{C}\mathrm{A}(G;A)=⟨<!--\; ⟨\; -->\mathrm{I}\mathrm{C}\mathrm{A}(G;A)\cup <!--\; \cup \; -->V⟩<!--\; ⟩\; -->$.