On the order of lazy cellular automata
By: Edgar Alcalá-Arroyo, Alonso Castillo-Ramirez
Potential Business Impact:
Makes simple computer rules behave in predictable ways.
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 $p$ and $a$, and we prove that this bound is attained when $p$ is a quasi-constant pattern.
Similar Papers
On the order of lazy cellular automata
Formal Languages and Automata Theory
Makes simple computer rules work in predictable ways.
Atomic Gliders and CA as Language Generators (Extended Version)
Formal Languages and Automata Theory
Makes simple computer rules create complex patterns.
Combinatorial Designs and Cellular Automata: A Survey
Combinatorics
Makes secret codes harder to break.