Skip to Main content Skip to Navigation
Journal articles

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 metadata
Contributor : Christine Carvalho de Matos <>
Submitted on : Sunday, May 31, 2020 - 9:05:31 PM
Last modification on : Wednesday, November 4, 2020 - 11:32:01 AM


2002_Baget_Journal of Aetifici...
Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License




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⟩



Record views


Files downloads