  Descriptive complexity may be useful to design programs in a natural
declarative way. This is important for parallel computation models such as
cellular automata, because designing parallel programs is considered difficult.
Our paper establishes logical characterizations of the three classical
complexity classes that model minimal time, called real-time, of
one-dimensional cellular automata according to their canonical variants. Our
logics are natural restrictions of the existential second-order Horn logic.
They correspond to the three ways of deciding a language on a square grid
circuit of side n according to the three canonical placements of an input word
of length n on the grid. Our key tool is a normalization method that transforms
a formula into an equivalent formula that literally mimics a grid circuit.
