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.