Descriptive complexity for pictures languages (Extended abstract)

This paper deals with descriptive complexity of picture languages of any dimension by syntactical fragments of existential second-order logic. • We uniformly generalize to any dimension the characterization by Giammarresi et al. [GRST96] of the class of recognizable picture languages in existential monadic second-order logic. • We state several logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata of any dimension. They are the first machine-independent char-acterizations of complexity classes of cellular automata. Our characterizations are essentially deduced from normalization results we prove for first-order and exis-tential second-order logics over pictures. They are obtained in a general and uniform framework that allows to extend them to other "regular " structures. Finally, we describe some hierarchy results that show the optimality of our logical characterizations and delineate their limits