On the order of lazy cellular automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910151094566912 |
|---|---|
| author | Alcalá-Arroyo, Edgar Castillo-Ramirez, Alonso |
| author_facet | Alcalá-Arroyo, Edgar Castillo-Ramirez, Alonso |
| contents | We study the most elementary family of cellular automata defined over an arbitrary group universe $G$ and an alphabet $A$: the lazy cellular automata, which act as the identity on configurations in $A^G$, except when they read a unique active transition $p \in A^S$, in which case they write a fixed symbol $a \in A$. As expected, the dynamical behavior of lazy cellular automata is relatively simple, yet subtle questions arise since they completely depend on the choice of $p$ and $a$. In this paper, we investigate the order of a lazy cellular automaton $τ: A^G \to A^G$, defined as the cardinality of the set $\{ τ^k : k \in \mathbb{N} \}$. In particular, we establish a general upper bound for the order of $τ$ in terms of the fibers of $p$, and we prove that this bound is attained when $p$ is a quasi-constant pattern. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_14841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the order of lazy cellular automata Alcalá-Arroyo, Edgar Castillo-Ramirez, Alonso Formal Languages and Automata Theory Dynamical Systems Group Theory Cellular Automata and Lattice Gases We study the most elementary family of cellular automata defined over an arbitrary group universe $G$ and an alphabet $A$: the lazy cellular automata, which act as the identity on configurations in $A^G$, except when they read a unique active transition $p \in A^S$, in which case they write a fixed symbol $a \in A$. As expected, the dynamical behavior of lazy cellular automata is relatively simple, yet subtle questions arise since they completely depend on the choice of $p$ and $a$. In this paper, we investigate the order of a lazy cellular automaton $τ: A^G \to A^G$, defined as the cardinality of the set $\{ τ^k : k \in \mathbb{N} \}$. In particular, we establish a general upper bound for the order of $τ$ in terms of the fibers of $p$, and we prove that this bound is attained when $p$ is a quasi-constant pattern. |
| title | On the order of lazy cellular automata |
| topic | Formal Languages and Automata Theory Dynamical Systems Group Theory Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2510.14841 |