License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.274
URN: urn:nbn:de:0030-drops-36783
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3678/
Go to the corresponding LIPIcs Volume Portal

Grandjean, Etienne ; Olive, Frédéric

Descriptive complexity for pictures languages

pdf-format:
24.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{grandjean_et_al:LIPIcs:2012:3678,
  author =	{Etienne Grandjean and Fr{\'e}d{\'e}ric Olive},
  title =	{{Descriptive complexity for pictures languages}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{274--288},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{Patrick C{\'e}gielski and Arnaud Durand},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3678},
  URN =		{urn:nbn:de:0030-drops-36783},
  doi =		{10.4230/LIPIcs.CSL.2012.274},
  annote =	{Keywords: Picture languages, locality and tiling, recognizability, linear time, cellular automata, logical characterizations, second-order logic}
}

Keywords: Picture languages, locality and tiling, recognizability, linear time, cellular automata, logical characterizations, second-order logic
Collection: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue Date: 2012
Date of publication: 03.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI