November 29, 2021
Julien Grange (LACL)On s’intéressera au pouvoir d’expression d’une extension particulière de la logique du premier ordre portant sur deux variables (FO^2).
On enrichira nos structures d’un ordre linéaire sur leurs sommets, en s’imposant toutefois la limitation suivante: une formule peut s’appuyer sur cette relation d’ordre uniquement si son évaluation est indépendante de cet ordre.
Cette notion d’invariance pour l’ordre est très naturelle en complexité descriptive, et son application à FO^2 l’est d’autant plus que la propriété d’invariance est décidable dans ce contexte.
Il apparaît clairement que l’ajout de cet ordre invariant accroît le pouvoir d’expression de FO^2, en autorisant le comptage.
On proposera ici une borne supérieure à son pouvoir d’expression sur les classes de structures de degré borné.