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.
Type de document :
Article dans une revue
Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2002, 16, pp.425-465. 〈10.1613/jair.918〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00268460
Contributeur : Christine Carvalho de Matos <>
Soumis le : mardi 1 avril 2008 - 09:27:24
Dernière modification le : mercredi 12 décembre 2018 - 14:38:02

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

218