On the Minimal Memory Set of Cellular Automata

For a group G and a finite set A, a cellular automaton (CA) is a transformation \(\tau : A^G \rightarrow A^G\) defined via a finite memory set \(S \subseteq G\) and a local map \(\mu : A^S \rightarrow A\) . Although memory sets are not unique, every CA admits a unique minimal memory set, which consists on all the essential elements of S that affect the behavior of the local map. In this paper, we study the links between the minimal memory set and the generating patterns \(\mathcal {P}\) of \(\mu \) ; these are the patterns in \(A^S\) that are not fixed when the cellular automaton is applied. In particular, we show that when \(\vert S \vert \ge 2\) and \(\vert \mathcal {P} \vert \) is not a multiple of \(\vert A \vert \) , then the minimal memory set must be S itself. Moreover, when \(\vert \mathcal {P} \vert = \vert A \vert \) , \(\vert S \vert \ge 3\) , and the restriction of \(\mu \) to these patterns is well-behaved, then the minimal memory set must be S or \(S \setminus \{s\}\) , for some \(s \in S \setminus \{e\}\) . These are some of the first general theoretical results on the minimal memory set of a cellular automaton.