2026-07-22T19:10:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3678 2024-03-06T10:34:21Z ddc:004 open_access

Descriptive complexity for pictures languages Grandjean, Etienne Olive, Frédéric Picture languages locality and tiling recognizability linear time cellular automata logical characterizations second-order logic This paper deals with logical characterizations of picture languages of any dimension by syntactical fragments of existential second-order logic. Two classical classes of picture languages are studied: - the class of "recognizable" picture languages, i.e. projections of languages defined by local constraints (or tilings): it is known as the most robust class extending the class of regular languages to any dimension; - the class of picture languages recognized on "nondeterministic cellular automata in linear time" : cellular automata are the simplest and most natural model of parallel computation and linear time is the minimal time-bounded class allowing synchronization of nondeterministic cellular automata. We uniformly generalize to any dimension the characterization by Giammarresi et al. (1996) 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Etienne Grandjean and Frédéric Olive 2012 Is Part Of LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2012.274 urn:nbn:de:0030-drops-36783 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.274 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode