An Algorithmic Study of Deduction in Simple Conceptual Graphs with Classical Negation

Michel Leclère 1 Marie-Laure Mugnier 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Polarized conceptual graphs (PGs) are simple conceptual graphs added with a restricted form of negation, namely negation on relations. Classical deduction with PGs (in short PG-Deduction) is highlyintractable; it is indeed Pi-2-P-complete. In [LM06] a brute-force algorithm for solving PG-Deduction was outlined. In the present paper, we extend previous work with two kinds of results. First, we exhibit particular cases of PGs for which the complexity of PG-Deduction decreases and becomes not more difficult than in simple conceptual graphs. Secondly, we improve the brute-force algorithm with several kinds of techniques based on properties concerning the graph structure and the labels.
Type de document :
Rapport
RR-08005, 2008, pp.14
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00260315
Contributeur : Marie-Laure Mugnier <>
Soumis le : lundi 3 mars 2008 - 17:51:44
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

  • HAL Id : lirmm-00260315, version 1

Collections

Citation

Michel Leclère, Marie-Laure Mugnier. An Algorithmic Study of Deduction in Simple Conceptual Graphs with Classical Negation. RR-08005, 2008, pp.14. 〈lirmm-00260315〉

Partager

Métriques

Consultations de la notice

153