Current browse context:
nlin.CG
Change to browse by:
References & Citations
Nonlinear Sciences > Cellular Automata and Lattice Gases
Title: On the minimal memory set of cellular automata
(Submitted on 9 Apr 2024)
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.
Submission history
From: Alonso Castillo-Ramirez [view email][v1] Tue, 9 Apr 2024 15:36:16 GMT (10kb)
Link back to: arXiv, form interface, contact.