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

الأصل · EN

We show that a sequence over a finite field Fq 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 Fq. As a consequence, the subshift generated by a length-p substitution can be realized as a topological factor of a linear cellular automaton.