Conceptual Graphs are Also Graphs

Michel Chein 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 : The main objective of this paper is to add one more brick in building the CG model as a knowledge representation model autonomous from logic. The CG model is not only a graphical representation of logic, it is much more: it is a declarative model encoding knowledge in a mathematical theory, namely labelled graph theory, which has efficient computable forms, with a fundamental graph operation on the encodings to do reasoning, projection, which is a labelled graph morphism. Main topics of this paper are: a generalized formalism for simple CGs; a strong equivalence between CSP (Constraint Satisfaction Problem) and labelled graph morphism. This correspondence allows the transportation of efficient algorithms from one domain to the other, and confirms that projection —or more generally labelled graph morphism— firmly moors CGs to combinatorial algorithmics, which is a cornerstone of computer science. The usual sound and complete first order logic semantics for CGs is still valid for our generalized model. This, plus the ease of doing important reasonings with CGs —for instance plausible reasonings by using some maximal join operations— without, at least for the moment, logical semantics, strengthens our belief that CGs must also be studied and developed independently from logic.
Type de document :
Communication dans un congrès
Madalina Croitoru. ICCS: International Conference on Conceptual Structures, Jul 2014, Iasi, Romania. Springer, 21st International Conference on Conceptual Structures, LNCS (8577), pp.1-18, 2014, Graph-Based Representation and Reasoning. 〈10.1007/978-3-319-08389-6_1〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01090141
Contributeur : Michel Chein <>
Soumis le : mercredi 3 décembre 2014 - 09:57:26
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Annexe

Identifiants

Collections

Citation

Michel Chein, Marie-Laure Mugnier. Conceptual Graphs are Also Graphs. Madalina Croitoru. ICCS: International Conference on Conceptual Structures, Jul 2014, Iasi, Romania. Springer, 21st International Conference on Conceptual Structures, LNCS (8577), pp.1-18, 2014, Graph-Based Representation and Reasoning. 〈10.1007/978-3-319-08389-6_1〉. 〈lirmm-01090141〉

Partager

Métriques

Consultations de la notice

143

Téléchargements de fichiers

78