Definability by Horn Formulas and Linear Time on Cellular Automata
Nicolas Bacquey, Etienne Marc Grandjean, Frédéric Olive · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2017
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.