On Finite Monoids of Cellular Automata

Abstract

For any group $G$ and set $A$, a cellular automaton over $G$ and $A$ is a transformation $\tau :A^G\to A^G$ defined via a finite neighborhood $S\subseteq G$ (called a memory set of $\tau$) and a local function $\mu :A^S\to A$. In this paper, we assume that $G$ and $A$ are both finite and study various algebraic properties of the finite monoid $\text{CA}(G,A)$ consisting of all cellular automata over $G$ and $A$. Let $\text{ICA}(G;A)$ be the group of invertible cellular automata over $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 $\text{ICA}(G;A)$ in terms of direct and wreath products. In the second part, 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 $G$ is finite abelian, we determine the minimal size of a set $V\subseteq \text{CA}(G;A)$ such that $\text{CA}(G;A)=⟨\text{ICA}(G;A)\cup V⟩$.

12 pages

References in corpus (2)

• The rank of the semigroup of transformations stabilising a partition of a finite set
• Ranks of finite semigroups of one-dimensional cellular automata

Cited by in corpus (5)

• Cellular Automata and Finite Groups
• Elementary, Finite and Linear vN-Regular Cellular Automata
• Some Algebraic Properties Of Linear Synchronous Cellular Automata
• Generating infinite monoids of cellular automata
• On the minimal number of generators of endomorphism monoids of full shifts