One-dimensional cellular automata with a unique active transition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911609169903616 |
|---|---|
| author | Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Baños, Luguis de los Santos |
| author_facet | Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Baños, Luguis de los Santos |
| contents | A one-dimensional cellular automaton $τ: A^\mathbb{Z} \to A^\mathbb{Z}$ is a transformation of the full shift defined via a finite neighborhood $S \subset \mathbb{Z}$ and a local function $μ: A^S \to A$. We study the family of cellular automata whose finite neighborhood $S$ is an interval containing $0$, and there exists a pattern $p \in A^S$ satisfying that $μ(z) = z(0)$ if and only if $z \neq p$; this means that these cellular automata have a unique \emph{active transition}. Despite its simplicity, this family presents interesting and subtle problems, as the behavior of the cellular automaton completely depends on the structure of $p$. We show that every cellular automaton $τ$ with a unique active transition $p \in A^S$ is either idempotent or strictly almost equicontinuous, and we completely characterize each one of these situations in terms of $p$. In essence, the idempotence of $τ$ depends on the existence of a certain subpattern of $p$ with a translational symmetry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03601 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | One-dimensional cellular automata with a unique active transition Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Baños, Luguis de los Santos Cellular Automata and Lattice Gases Formal Languages and Automata Theory Dynamical Systems 37B15, 68Q80 A one-dimensional cellular automaton $τ: A^\mathbb{Z} \to A^\mathbb{Z}$ is a transformation of the full shift defined via a finite neighborhood $S \subset \mathbb{Z}$ and a local function $μ: A^S \to A$. We study the family of cellular automata whose finite neighborhood $S$ is an interval containing $0$, and there exists a pattern $p \in A^S$ satisfying that $μ(z) = z(0)$ if and only if $z \neq p$; this means that these cellular automata have a unique \emph{active transition}. Despite its simplicity, this family presents interesting and subtle problems, as the behavior of the cellular automaton completely depends on the structure of $p$. We show that every cellular automaton $τ$ with a unique active transition $p \in A^S$ is either idempotent or strictly almost equicontinuous, and we completely characterize each one of these situations in terms of $p$. In essence, the idempotence of $τ$ depends on the existence of a certain subpattern of $p$ with a translational symmetry. |
| title | One-dimensional cellular automata with a unique active transition |
| topic | Cellular Automata and Lattice Gases Formal Languages and Automata Theory Dynamical Systems 37B15, 68Q80 |
| url | https://arxiv.org/abs/2411.03601 |