A characterization of \(p\)-automatic sequences as columns of linear cellular automata (Q477771): Difference between revisions

The sequence of values seen in a given cell of a cellular automaton under iteration gives a column sequence in the spacetime diagram of the orbit of some initial configuration. Asking which sequences from a finite alphabet arise in this way is a natural question. Without further constraints it is clear that any sequence does; here the authors consider the problem of characterizing those sequences that arise in this way for a spatially periodic initial configuration in the cellular automaton. The main result here is that a sequence of elements of a finite field \(\mathbb{F}_{p^r}\) of characteristic \(p\) is \(p\)-automatic if and only if it is a column of a linear cellular automaton with memory over \(\mathbb{F}_q\) whose initial conditions are spatially eventually periodic in both directions. The method of proof is constructive in both directions. This shows, for example, that the subshift generated by a substitution of length \(p\) has a realization as a topological factor of a linear cellular automaton.