Extensions of Simple Conceptual Graphs: The Complexity of Rules and Constraints

Jean-François Baget 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 : Simple conceptual graphs are considered as the kernel of most knowledge representation formalisms built upon Sowa's model. Reasoning in this model can be expressed by a graph homomorphism called projection, whose semantics is usually given in terms of positive, conjunctive, existential FOL. We present here a family of extensions of this model, based on rules and constraints, keeping graph homomorphism as the basic operation. We focus on the formal definitions of the different models obtained, including their operational semantics and relationships with FOL, and we analyze the decidability and complexity of the associated problems (consistency and deduction). As soon as rules are involved in reasonings, these problems are not decidable, but we exhibit a condition under which they fall in the polynomial hierarchy. These results extend and complete the ones already published by the authors. Moreover we systematically study the complexity of some particular cases obtained by restricting the form of constraints and/or rules.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00268460
Contributor : Christine Carvalho de Matos <>
Submitted on : Tuesday, April 1, 2008 - 9:27:24 AM
Last modification on : Wednesday, December 12, 2018 - 2:38:02 PM

Links full text

Identifiers

Collections

Citation

Jean-François Baget, Marie-Laure Mugnier. Extensions of Simple Conceptual Graphs: The Complexity of Rules and Constraints. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2002, 16, pp.425-465. ⟨10.1613/jair.918⟩. ⟨lirmm-00268460⟩

Share

Metrics

Record views

242