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

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 highly intractable; 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 :
Communication dans un congrès
ICCS: International Conference on Conceptual Structures, Jul 2008, Toulouse, France. 16th International Conference on Conceptual Structures, LNCS (5113), pp.119-132, 2008, Conceptual Structures: Knowledge Visualization and Reasoning. 〈10.1007/978-3-540-70596-3_8〉

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00355493
Contributeur : Michel Leclère <>
Soumis le : jeudi 22 janvier 2009 - 17:57:03
Dernière modification le : samedi 27 janvier 2018 - 01:30:49

### Citation

Michel Leclère, Marie-Laure Mugnier. An Algorithmic Study of Deduction in Simple Conceptual Graphs with Classical Negation. ICCS: International Conference on Conceptual Structures, Jul 2008, Toulouse, France. 16th International Conference on Conceptual Structures, LNCS (5113), pp.119-132, 2008, Conceptual Structures: Knowledge Visualization and Reasoning. 〈10.1007/978-3-540-70596-3_8〉. 〈lirmm-00355493〉

### Métriques

Consultations de la notice