Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 17 Septembre 2019

Communication complexity tools on recognizable picture languages

par Véronique Terrier (GREYC,Caen)

Introduced by D. Giammarresi and A. Restivo, the class of recognizable picture languages, REC, is the natural counterpart of regular languages for two-dimensional settings. Characterized in several different ways, this class has been shown to be robust. But things become more complex and many properties proved in the one-dimensional case, are no longer true. Notably, REC is not closed under complement and, in addition, the non-deterministic, unambiguous and deterministic versions are no more equivalent in REC.

In this talk, we will focus on the class REC and its unambiguous version UREC, along with their corresponding complements co-REC and co-UREC. We will show that the sets REC ∩ co-REC and UREC ∪ co-UREC are different. For that, we will use communication complexity results to identify a candidate with a significant gap between unambiguous and co-unambiguous communication complexities on one side and non-deterministic and co-non-deterministic complexities on the other side. Then we adjust it to get a language belonging to both REC and co-REC but not belonging either in UREC nor in co-UREC.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30