Simple conceptual graphs revisited: hypergraphs and conjunctive types for efficient projection algorithms

Abstract : Simple Conceptual Graphs (SGs) form the cornerstone for the "Conceptual Graphs" family of languages. In this model, the subsumptio operation is called projection; it is a labelled graphs homomorphism (a NP-hard problem). Designing efficient algorithms to compute projections between two SGs is thus of uttermost importance for the community building languages on top of this basic model. This paper presents some such algorithms, inspired by those developped for Constraint Satisfaction Problems. In order to benefit from the optimization work done in this community, we have chosen to present an alternate version of SGs, differences being the definition of these graphs as hypergraphs and the use of conjunctive types.
Type de document :
Communication dans un congrès
Aldo De Moor, Wilfried Lex, Bernhard Ganther. Proc. 11th international conference on conceptual sructures (ICCS), Jul 2003, Dresden, Germany. Springer Verlag, 2746, pp.229-242, 2003, Lecture notes in computer science. 〈10.1007/978-3-540-45091-7_16〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00906599
Contributeur : Jérôme Euzenat <>
Soumis le : mercredi 20 novembre 2013 - 10:05:33
Dernière modification le : mercredi 11 avril 2018 - 01:55:57
Document(s) archivé(s) le : vendredi 21 février 2014 - 04:24:34

Fichier

baget2003a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-François Baget. Simple conceptual graphs revisited: hypergraphs and conjunctive types for efficient projection algorithms. Aldo De Moor, Wilfried Lex, Bernhard Ganther. Proc. 11th international conference on conceptual sructures (ICCS), Jul 2003, Dresden, Germany. Springer Verlag, 2746, pp.229-242, 2003, Lecture notes in computer science. 〈10.1007/978-3-540-45091-7_16〉. 〈hal-00906599〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

155