On the minimal memory set of cellular automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909202845270016 |
|---|---|
| author | Castillo-Ramirez, Alonso Veliz-Quintero, Eduardo |
| author_facet | Castillo-Ramirez, Alonso Veliz-Quintero, Eduardo |
| contents | For a group $G$ and a finite set $A$, a cellular automaton (CA) is a transformation $τ: A^G \to A^G$ defined via a finite memory set $S \subseteq G$ and a local map $μ: 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 $μ$; 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 \geq 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 \geq 3$, and the restriction of $μ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06394 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the minimal memory set of cellular automata Castillo-Ramirez, Alonso Veliz-Quintero, Eduardo Cellular Automata and Lattice Gases Formal Languages and Automata Theory Dynamical Systems 37B15, 68Q80 For a group $G$ and a finite set $A$, a cellular automaton (CA) is a transformation $τ: A^G \to A^G$ defined via a finite memory set $S \subseteq G$ and a local map $μ: 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 $μ$; 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 \geq 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 \geq 3$, and the restriction of $μ$ 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. |
| title | On the minimal memory set of cellular automata |
| topic | Cellular Automata and Lattice Gases Formal Languages and Automata Theory Dynamical Systems 37B15, 68Q80 |
| url | https://arxiv.org/abs/2404.06394 |