EUVIMEDEUVIMED entdecken
Crossref

On the order of lazy cellular automata

Edgar Alcalá-Arroyo, Alonso Castillo-Ramirez

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →