Automaticity of double sequences generated by one-dimensional linear cellular automata (Q1389657)

A sequence \(n\mapsto u(n)\) of elements of a finite set is said to be \(k\)-automatic, if restricting the domain to congruence classes modulo powers of \(k\) yield only finitely many subsequences. The authors consider double (i.e., spatio-temporal) sequences generated by linear one-dimensional cellular automata over a modular domain, to which the notion of automaticity is readily generalized. The authors characterize completely the automatic sequences, proving (among other things) that a sequence is \(k\)-automatic if and only if \(R(X^k)=R(X)^k\), where \(R(X)\) is some power of the generating polynomial of the automaton.