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

Abstract

We show that a sequence over a finite field ${\mathbb{F}}_q$ of characteristic $p$ is $p$-automatic if and only if it occurs as a column of the spacetime diagram, with eventually periodic initial conditions, of a linear cellular automaton with memory over ${\mathbb{F}}_q$. As a consequence, the subshift generated by a length-$p$ substitution can be realized as a topological factor of a linear cellular automaton.

19 pages, 6 figures; final version

Cited by in corpus (2)

• Construction of Minkowski Sums by Cellular Automata
• Automaticity and invariant measures of linear cellular automata