I) Pouvoir d'expression de la logique du second-ordre monadique.
Il s'agit de délimiter le pouvoir d'expression de la logique
du second-ordre monadique, en ce qui concerne les propriétés
de graphes, de structures combinatoires telles que les cartes, les structures
relationnelles et les hypergraphes, ainsi que les transformations
de telles structures. Les propriétés les plus intéressantes
sont issues soit de la théorie des graphes (et de leurs dessins),
soit de la vérification ("model-checking").
L'écriture logique immédiate d'une propriété
de graphe ne fournit pas en général une formule de logique
du second-ordre monadique (ou des langages apparentés). Il faut faire
appel à des propriétés particulières des graphes
considérés (coloriabilité, orientations particulières,
configurations exclues, etc...) pour obtenir ce type de formulation logique.
Le cas des graphes infinis dénombrables pose la question
de l'extension des constructions relatives aux graphes finis, ce qui n'est
pas toujours possible.
Un autre thème est l'étude des spécifications
partielles de dessins planaires de graphes, et de leur réalisabilité,
des points de vue algorithmiques et logiques.
Questions et thèmes de recherche:
Q1: Est-ce-que la classe des "croquis" (en anglais "sketches", structures logiques représentant les dessins de graphes avec croisements d'arcs est MS-définissable (i.e., définissable en logique du Second-Ordre Monadique)? Voir article M9.
Q2: Etude de plusieurs classes de cartes partielles: thèse de V. Dussaux.
Q3: Application des matroïdes orientés à
l'étude des arrangements de pseudo-droites et extensions. Voir T4 ; thèse de E. Gioan.
Q4: Quelles opérations sur les graphes et les structures relationnelles
donnent lieu à des évaluations (détermination du graphe
à partir de l'arbre syntaxique) MS-définissables, ou seulement
MS-compatibles ?
Q5: Existe-t-il des transformations de graphes ou de structures
qui sont MS-compatibles sans être exprimables comme compositions de
développements arborescents ("tree expansions de Shelah, Stupp, Muchnik
et Walukiewicz) et de transformations MS-définissables ?
II) Structurations des graphes
Il s'agit de l'étude logique, combinatoire et algorithmique des
structurations hiérarchiques des graphes, essentielles pour
la construction d'algorithmes efficaces.
En particulier, la décomposition d'un graphe en un recollement
arborescent de bipartis complets (qui donne lieu à la notion
de largeur de clique ou "clique-width") soulève des problèmes
de caractérisation par configurations interdites et de complexité
(on ne sait pas si le calcul de la largeur de clique d'un graphe est un
problème polynomial). L'extension de cette notion aux structures
relationnelles et aux hypergraphes reste à explorer.
La définissabilité logique de ces structurations est aussi
un problème ouvert. (On peut définir, en logique du second-ordre
monadique, les décompositions arborescentes.)
L'extension aux structures relationnelles et aux hypergraphes des décompositions
modulaires est un problème important en vue des applications
grammaticales et algorithmiques.
Elle justifie l'étude des opérations sur les structures
relationnelles combinant des opérations de base comme l'union
disjointe, les quotientages par des relations d'équivalence définies
de façon adéquate et les transformations par redéfinition
de relations au moyen de formules sans quantificateurs.
Une autre manière d'exploiter l'existence d'une structuration,
linéaire ou arborescente, consiste à implanter un graphe à
n sommets en associant à chaque sommet une information de taille
O(log(n)) de telle sorte que des propriétés
fixées d'un couple de sommets (ou leur distance) puissent être
évaluées en ne consultant que les informations sur le graphe
attachées aux sommets donnés. On dira qu'une telle propriété
ou fonction est compilée dans un graphe. C'est possible pour
les graphes dotés de structurations linéaires, et les propriétés
et fonctions exprimables en logique du second-ordre monadique.
Questions et thèmes de recherche :
Q'1: Est-ce que la reconnaissance de l'ensemble des graphes de cwd au plus k, ou de cwdl (largeur de clique linéaire) au plus k est un problème polynomial?
Q'2: Quelle la meilleure majoration de la cwd (de la cwdl) d'un graphe en fonction du nombre de ses sommets? Mêmes questions en fonction de la twd (largeur arborescente, ou "tree-width") et de la pwd (largeur arborescente linéaire ou "pathwidth").
Q'3: Une propriété de graphe, ou une fonction d'optimisation exprimable en logique MS est évaluable en temps O(A(k)n) sur un graphe à n sommets et de twd k, donné par sa décomposition. Il faudrait analyser la croissance de la fonction A(k), pour différentes propriétés de graphes intéressantes, et si possible la relier à la syntaxe de la formule MS qui la définit. On obtiendra peut-être des complexités intéressantes pour des familles de graphes dont la twd est O(log(n)).
Q'4: Trouver de bonnes heuristiques pour le calcul de la cwd.
Q'5: Soit un graphe de cwd k. Si on enlève un sommet ou un arc, de combien au plus la cwd peut-elle augmenter?
Q'6: Trouver des règles de réduction qui caractérisent les graphes de cwd au plus k.
Sur la cwd consulter T3. Voir M6-M8 pour les applications algorithmiques.
Q'7: Quels sont les graphes minimaux (pour la relation de sous-graphe induit) de cwd au moins k? Pour k = 3 il n'y a que P4. Pour k = 4 il y en a une infinité. En donner une caractérisation grammaticale ou logique.
Q'8: Certains problèmes ont des algorithmes polynomiaux sur les graphes d'intervalles, ou les graphes triangulés ("chordal graphs") qui ne sont pas de cwd bornée. Ces problèmes ont-ils une forme logique commune ? (Contraintes syntaxiques sur des formules MS les exprimant)?
Q'9: Borner supérieurement la cwd d'un graphe fini construit avec p étiquettes, les opérations correspondantes de renommages d'étiquettes et de fusion de sommets, et les redéfinitions d'arcs sans quantificateurs. On sait qu'elle existe d'après des travaux de Courcelle et Makowsky (M12).
Q'10: Définir et étudier la cwd des graphes infinis dénombrables. Etudier pour ces graphes la question Q'9.
Q'11: Quelles propriétés peuvent être compilées dans des graphes de cwd bornée, avec des informations de taille O(log(n)), de taille O(log(n)**2) ? (Résultats partiels de Courcelle et Vanicat (M13)).
III) Conjecture de D. Seese
Un troisième grand thème est fourni par une conjecture toujours
ouverte de D. Seese, établie dans plusieurs cas particuliers, selon
laquelle:
les seuls ensembles de graphes dont la théorie monadique est
décidable sont ceux disposant d'une structuration arborescente
de cwd bornée.
Voir les articles et exposé M10, M11, et OC13 et pour des résultats partiels.
Questions :
Q"1: Cette conjecture est vraie pour les graphes orientés
si et seulement si elle est vraie pour les graphes non orientés:
sa validité entraîne-t-elle sa validité pour les hypergraphes
orientés?
Q"2 : A défaut de prouver cette conjecture dans le cas général,
peut-on la prouver pour des familles particulières de graphes : graphes
de comparabilité, graphes d'intervalles, familles de graphes définies
par sous-graphes induits exclus ?
Mots clés décrivant le contexte scientifique:
Complexité descriptive, Logique et théorie des graphes, Structurations hiérarchiques des graphes et applications algorithmiques.
Description brève
L'essentiel de ces recherches peut se regrouper en trois grands
thèmes.
* Il s'agit de délimiter le pouvoir d'expression de la logique
monadique du second-ordre et des logiques utilisant des opérateurs
de point fixe, en ce qui concerne les propriétés de graphes,
les cartes, les structures relationnelles et les hypergraphes, ainsi que
les transformations de telles structures. Les propriétés les
plus intéressantes sont issues de la théorie des graphes (et
de leurs dessins), et de la vérification ("model-checking").
L'écriture logique utilise des propriétés particulières
des graphes considérés (coloriabilité, orientations
particulières, configurations exclues, etc...).
* Un second thème est l'étude logique, combinatoire et algorithmique
des structurations hiérarchiques des graphes, essentielles
pour la construction d'algorithmes efficaces. La décomposition d'un
graphe en un recollement arborescent de bipartis complets soulève des
problèmes de caractérisation par configurations interdites et
de complexité. L'extension de cette notion aux structures relationnelles
et aux hypergraphes reste à explorer.
* Un troisième thème est fourni par une conjecture toujours
ouverte de D. Seese, selon laquelle les seuls ensembles de graphes dont
la théorie monadique est décidable sont ceux disposant
d'une structuration arborescente de "largeur de clique" bornée.
Travaux de recherche de B. Courcelle:http://www.labri.fr/~courcell
Labri group working on Logic, Automata, Algorithms
and Applications.