A logical approach to locality in pictures languages

摘要

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 ≥ 1 recognized in linear time on nondeterministic cellular automata, a robust complexity class that contains, for d = 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.