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

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.

Domaines: Intelligence artificielle [cs.AI]

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⟩