8-10 juin 2026 Lyon (France)
Recognizable picture languages
Andrei Romashchenko  1, @  , Pascal Vanier, Antonin Callard, Véronique Terrier, @
1 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier  (LIRMM)
Université Montpellier II - Sciences et techniques, CNRS : UMR5506
CC 477, 161 rue Ada, 34095 Montpellier Cedex 5 -  France

We discuss classes of recognizable two-dimensional picture languages under ambiguous and unambiguous recognition. We focus on the classes REC (the class of picture languages recognized by tiling systems) and UREC (the class of picture languages recognized by unambiguous tiling systems). We explain how allowing ambiguity increases the expressive power of tiling systems (Véronique Terrier, 2019). We also show that coUREC is not included in REC (recent joint work with A. Collard, V. Terrier, and P. Vanier). These results reveal subtle connections between recognizable picture languages and communication complexity.



  • Poster
Chargement... Chargement...