Computer Science – Logic in Computer Science
Scientific paper
2012-01-27
Computer Science
Logic in Computer Science
33 pages - Submited to Lics 2012
Scientific paper
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. \cite{GRST96} of the class of \emph{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 characterizations of complexity classes of cellular automata. Our characterizations are essentially deduced from normalization results we prove for first-order and existential 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.
Grandjean Etienne
Olive Frédéric
Richard Gaétan
No associations
LandOfFree
Descriptive complexity for pictures languages (extended abstract) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Descriptive complexity for pictures languages (extended abstract), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Descriptive complexity for pictures languages (extended abstract) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-345426