Extensions of Simple Conceptual Graphs: The Complexity of Rules and Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Artificial Intelligence Research Year : 2002

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

Jean-François Baget

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.
Fichier principal
Vignette du fichier
2002_Baget_Journal of Aetificial Intelligence Research_1.pdf (549.23 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

lirmm-00268460 , version 1 (31-05-2020)

Licence

Identifiers

Cite

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

Altmetric

Share

More