Automaticity and invariant measures of linear cellular automata

Abstract

We show that spacetime diagrams of linear cellular automata $\Phi :{\mathbb{F}}_p^{\mathbb{Z}}\to {\mathbb{F}}_p^{\mathbb{Z}}$ with $(-p)$-automatic initial conditions are automatic. This extends existing results on initial conditions which are eventually constant. Each automatic spacetime diagram defines a $(\sigma ,\Phi )$-invariant subset of ${\mathbb{F}}_p^{\mathbb{Z}}$, where $\sigma$ is the left shift map, and if the initial condition is not eventually periodic then this invariant set is nontrivial. For the Ledrappier cellular automaton we construct a family of nontrivial $(\sigma ,\Phi )$-invariant measures on ${\mathbb{F}}_3^{\mathbb{Z}}$. Finally, given a linear cellular automaton $\Phi$, we construct a nontrivial $(\sigma ,\Phi )$-invariant measure on ${\mathbb{F}}_p^{\mathbb{Z}}$ for all but finitely many $p$.

33 pages, 8 figures; fixed some typos

References in corpus (1)

• A characterization of $p$-automatic sequences as columns of linear cellular automata