We establish an exact logical characterization of linear time complexity of cellular automata of dimension d, for any fixed d: a set of pictures of dimension d belongs to this complexity class iff it is definable in existential second-order logic restricted to monotonic Horn formulas with built-in successor function and d+1 first-order variables. This logical characterization is optimal modulo an open problem in parallel complexity. Furthermore, its proof provides a systematic method for transforming an inductive formula defining some problem into a cellular automaton that computes it in linear time.

This article deals with cellular automata (CA) working over periodic configurations, as opposed to standard CA, where the initial configuration is bounded by persistent symbols. We study the capabilities of language recognition and computation of functions over such automata, as well as the complexity classes they define over languages and functions. We show that these new complexity classes coincide with the standard ones starting from polynomial time. As a by-product, we present a CA that solves a somehow relaxed version of the density classification problem.