Classes de sous-shifts définis par des formules logiques

Une configuration est un coloriage du plan Z². Habituellement, les ensembles de configurations étudiés sont ceux définis par un ensemble de motifs “interdits” n’apparaissant dans aucune des configurations de l’ensemble. De tels ensembles sont appelés sous-shifts. Dans ce séminaire, on définit les ensembles de configurations grâce à la logique Monadique du Second Ordre (MSO), et on s’intéressera à la complexité de savoir si une formule MSO définit un sous-shift. On s’intéressera également à la complexité de ces ensembles.