Logo BC logique

Travaux de recherche de B. Courcelle

LaBRI UMR 5800 (CNRS)

Equipe "Logique, Automates, Algorithmique et Applications".

Mise à jour : Janvier 2004


This text in English.

Liste des  publications.

Graphes et Logique

Orientation générale et questions ouvertes

Contexte scientifique

La représentation des graphes par des structures relationnelles permet d'écrire formellement leurs propriétés au moyen de formules logiques. On peut donc classer les propriétés de graphes en fonction de la structure syntaxique des formules qui les représentent. Cette approche s'étend aux hypergraphes et aux structures relationnelles.
A la suite du travail pionnier de Fagin (1974), il en résulte des descriptions des classes de complexité en termes de langages logiques, indépendantes des définitions données initialement en termes de machines de Turing. D'autre part, des algorithmes polynomiaux et parfois même linéaires peuvent être obtenus par des constructions effectives à partir de formules logiques pour certains types de graphes.
Les langages logiques qui se prêtent bien à cette approche sont la logique du premier ordre, ses extensions par des opérateurs de point fixe, le mu-calcul, essentiel en sémantique des processus, et la logique du second-ordre monadique (MS). En effet, les problèmes de vérification (test de propriété avec réponse par oui ou non), les problèmes d'optimisation (tels que déterminer la longueur d'un plus court chemin dans un graphe satisfaisant telle ou telle propriété), les problèmes de dénombrement (tels que compter le nombre de plus courts chemins satisfaisant telle ou telle propriété) formulables dans ce langage logique ont des algorithmes polynomiaux, souvent même linéaires, pour des graphes et autres structures donnés par des structurations hiérarchiques.
Les graphes qui relèvent de cette approche sont les graphes de degré borné, et surtout, les graphes que l'on peut structurer de manière arborescente, soit au moyen des décompositions arborescentes introduites par Robertson et Seymour, soit au moyen des décompositions modulaires, ou de décompositions en bipartis complets.
Ces notions sont essentielles dans la théorie des grammaires de graphes: la structuration arborescente correspond aux arbres syntaxiques de la théorie des langages classique et la logique du second-ordre monadique fournit une notion algébrique de reconnaissabilité (en termes de congruences ayant un nombre fini de classes), en l'absence d'automates finis dotés de bonnes propriétés.
Cette approche peut s'étendre à des structures combinatoires plus complexes que les graphes, en particulier les cartes combinatoires qui sont des graphes enrichis de relations qui définissent (à homéomorphisme près) des représentations planaires (ou sur des surfaces plus complexes) avec ou sans croisements d'arêtes.
D'autre part, aussi bien pour les applications algorithmiques que pour le développement des fondements théoriques, il faut étudier les transformations de structures et leur "compatibilité" avec les langages logiques cités ci-dessus. Deux notions sont essentielles, celle de transduction de structures MS-définissable, (le terme transduction fait référence à la théorie des langages), c'est à dire que l'on peut spécifier par des formules de la logique du second-ordre monadique, et celle de transduction MS-compatible, c'est à dire telle que les propriétés exprimables en logique du second-ordre monadique de la structure transformée sont exprimables aussi en logique du second-ordre monadique dans la structure d'origine. Cela donne une réduction algorithmique pour les théories du second-ordre monadique des structures concernées. Toute transduction MS-définissable est  MS-compatible mais l'inverse n'est pas vrai.  

Activités de recherche

Ce cadre général donne lieu à plusieurs ensembles de questions.
Les références sont numérotées comme dans la page principale.

 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 ?


Version courte pour la présentation du LaBRI.

 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.