A logical approach to locality in pictures languages

• The class of recognizable picture languages is characterized by existential monadic second-order logic.
• Logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata.
• This shows the logics involved can be made “local” with respect to the underlying regular structures.
• Hierarchy results among some logical frameworks are deduced from the above.

This paper deals with descriptive complexity of picture languages of any dimension by fragments of existential second-order logic:1) We generalize to any dimension the characterization by Giammarresi et al. (1996) of the class of recognizable picture languages in existential monadic second-order logic.2) We state natural logical characterizations of the class of picture languages of any dimension d≥1d≥1 recognized in linear time on nondeterministic cellular automata, a robust complexity class that contains, for d=1d=1, all the natural NP-complete problems.Our characterizations are essentially deduced from normalization results for first-order and existential second-order logics over pictures.