Extension des règles de SGs avec la négation atomique

Voir tous les sujets RCR

Encadrement

Michel Leclère et Marie-Laure Mugnier 

Mots-clés

Graphes conceptuels, Règles, Négation

Contexte

 Nous avons proposé d'étendre les graphes conceptuels simples (SGs) avec la négation atomique (sur les relations), interprétée de différentes façons : en faisant l'hypothèse du monde clos ("non P" est considéré comme vrai si on ne peut pas déduire "P") ou l'hypothèse du monde ouvert ("non P" est considéré comme vrai si on peut déduire "non P") ; dans ce deuxième cas, on s'intéresse à une déduction sans utilisation du tiers-exclu (déduction intuitioniste) ou à la déduction classique. Dans le cadre de systèmes questions/réponses, la déduction intuitioniste est particulièrement intéressante car elle capture exactement la notion d'existence d'une réponse. Voir le rapport de recherche "On querying Simple Conceptual Graphs with Negation".

D'autre part, nous avons un formalisme qui étend les SGs avec des règles de graphes (ce modèle est appelé SR dans le cadre de la famille SG [Baget Mugnier 2002]). Une base de connaissances est alors composée d'un ensemble de faits (des SGs) G et d'un ensemble de règles R. Le problème de déduction devient le suivant : étant donné une base K et un SG Q (représentant par exemple une requête), peut-on déduire Q de K, c'est-à-dire existe-t-il une dérivation de G à un SG Q', cette dérivation utilisant les règles de R, telle que Q se projette de Q'? On a montré que ce problème correspond exactement à la déduction logique (Q se déduit de K par la définition précédente si et seulement si Phi(Q) se déduit de Phi(K), Phi(V), où V est le vocabulaire).

Les règles de graphes étant positives, ces deux extensions sont "orthogonales".

Etude proposée

L'objectif de ce stage est d'étudier l'extension du modèle SR=SGs+règles avec la négation atomique (sur les relations toujours), selon une ou plusieurs interprétations de la négation.

Travail à réaliser en stage