# 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.
Document type :
Conference papers

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00355493
Contributor : Michel Leclère <>
Submitted on : Thursday, January 22, 2009 - 5:57:03 PM
Last modification on : Wednesday, June 5, 2019 - 11:58:13 AM

### 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. pp.119-132, ⟨10.1007/978-3-540-70596-3_8⟩. ⟨lirmm-00355493⟩

Record views