A generalization of cellular automata over groups

Abstract

Let G be a group and let A be a finite set with at least two elements. A cellular automaton (CA) over A^G is a function $\tau :A^G\to A^G$ defined via a finite memory set $S\subseteq G$ and a local function $\mu :A^S\to A$. The goal of this paper is to introduce the definition of a generalized cellular automaton (GCA) $\tau :A^G\to A^H$, where H is another arbitrary group, via a group homomorphism $\varphi :H\to G$. Our definition preserves the essence of CA, as we prove analogous versions of three key results in the theory of CA: a generalized Curtis-Hedlund Theorem for GCA, a Theorem of Composition for GCA, and a Theorem of Invertibility for GCA. When G = H, we prove that the group of invertible GCA over A^G is isomorphic to a semidirect product of $\text{Aut}{(G)}^{\text{op}}$ and the group of invertible CA. Finally, we apply our results to study automorphisms of the monoid $\text{CA}(G;A)$ consisting of all CA over A^G . In particular, we show that every $\varphi \in \text{Aut}(G)$ defines an automorphism of $\text{CA}(G;A)$ via conjugation by the invertible GCA defined by $\varphi$, and that, when G is abelian, $\text{Aut}(G)$ is embedded in the outer automorphism group of $\text{CA}(G;A)$.

Communicated by Pedro Garcia-Sanchez

Keywords:

• Cellular automata
• Curtis-Hedlund theorem
• monoid of cellular automata
• outer automorphism group

2020 Mathematics Subject Classification:

• 37B15
• 68Q80

Additional information

Funding

The first author was supported by a CONACYT Basic Science Grant (No. A1-S-8013). The second and third authors were supported by CONACYT National Posgraduate Scholarships.