On the order of lazy cellular automata
Theoretical Computer Science · 2026-06 · 1076 · 115965
DOI: 10.1016/j.tcs.2026.115965 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-06. Verfasst von Edgar Alcalá-Arroyo und 1 weiteren Autor:innen. Die Arbeit nennt 13 Literaturangaben. Gefördert von: Université de Lille, Secretariat of Science Humanities Technology and Innovation.
Abstract (Originalsprache)
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 $\tau : A^G \to A^G$, defined as the cardinality of the set $\{ \tau^k : k \in \mathbb{N} \}$. In particular, we establish a general upper bound for the order of $\tau$ in terms of the fibers of $p$, and we prove that this bound is attained when $p$ is a quasi-constant pattern.
Förderung
- Université de Lille
- Secretariat of Science Humanities Technology and Innovation
Zitieren
APA
Alcalá-Arroyo, E., & Castillo-Ramirez, A. (2026). On the order of lazy cellular automata. Theoretical Computer Science, 1076, 115965. https://doi.org/10.1016/j.tcs.2026.115965
Vancouver
Alcalá-Arroyo E, Castillo-Ramirez A. On the order of lazy cellular automata. Theoretical Computer Science. 2026;1076:115965. doi:10.1016/j.tcs.2026.115965
BibTeX
@article{AlcalArroyo2026,
author = {Alcalá-Arroyo, Edgar and Castillo-Ramirez, Alonso},
title = {On the order of lazy cellular automata},
journal = {Theoretical Computer Science},
year = {2026},
volume = {1076},
pages = {115965},
doi = {10.1016/j.tcs.2026.115965}
}
EUVIMED