Sous-shifts et logique monadique du second ordre


Guillaume Theyssier, LAMA. 23 avril 2009 10:15 limd 2:00:00
Abstract:

Les mots (finis ou pas, en dimension 1 ou supérieure) peuvent être vus comme des modèles de formules de la logique monadique du second ordre (MSO), une formule définissant alors un langage. Cette approche a été suivie avec succès en dimension 1 par Büchi et Elgot dans les années 60 : les langages ainsi définis sont exactement les langages rationnels. De plus toute formule MSO est dans ce contexte équivalente à une formule EMSO (quantification existentielle au second ordre suivie d'une formule au premier ordre).
Plus récemment, Giammarresi, Restivo, Seibert et Thomas ont reconsidéré ces résultats dans le cas des figures'', c'est à dire des mots bidimensionnels finis avec bords marqués : cette fois les formules EMSO définissent exactement les langagessofiques'' (projections de langages locaux), mais elles ne suffisent plus à capturer tous les langages définissable par une formule MSO.
L'objectif de cet exposé est de développer cette approche, en dimension 2, pour les sous-shifts (ensembles de configurations fermés topologiquement et invariants par décalages). Nous verrons alors que les sous-shifts sofiques (introduits par Weiss dans les années 70) ne correspondent pas aux sous-shifts définissables par formules EMSO. Nous donnerons néanmoins une caractérisation logique des sous-shifts sofiques et, inversement, nous donnerons une caractérisation ``combinatoire'' des ensembles de configurations définissables dans EMSO.