An Algorithmic Study of Deduction in Simple Conceptual Graphs with Classical Negation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2008

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

Michel Leclère

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.

Dates and versions

lirmm-00355493 , version 1 (22-01-2009)

Identifiers

Cite

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⟩
84 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More