On the minimal memory set of cellular automata

Abstract

For a group \(G\) and a finite set \(A\), a cellular automaton (CA) is a transformation \(\tau : A^G \to A^G\) defined via a finite memory set \(S \subseteq G\) and a local map \(\mu : A^S \to 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 \mathcal{P} \vert\) is not a multiple of \(\vert A \vert\), then the minimal memory set is \(S\) or \(S \setminus \{e\}\). Moreover, when \(\vert \mathcal{P} \vert = \vert A \vert\), and the action of \(\mu\) on these patterns is well-behaved, then the minimal memory set is \(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.