Skip to Main content Skip to Navigation
Conference papers

Arc Consistency Projection: A New Generalization Relation for Graphs

Michel Liquière 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The projection problem (conceptual graph projection, homomorphism, injective morphism, θ-subsumption, OI-subsumption) is crucial to the efficiency of relational learning systems. How to manage this complexity has motivated numerous studies on learning biases, restricting the size and/or the number of hypotheses explored. The approach suggested in this paper advocates a projection operator based on the classical arc consistency algorithm used in constraint satisfaction problems. This projection method has the required properties : polynomiality, local validation, parallelization, structural interpretation. Using the arc consistency projection, we found a generalization operator between labeled graphs. Such an operator gives the structure of the classification space which is a concept lattice.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Martine Peridier <>
Submitted on : Monday, September 16, 2019 - 12:43:18 PM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM
Long-term archiving on: : Saturday, February 8, 2020 - 1:05:09 PM


Publisher files allowed on an open archive




Michel Liquière. Arc Consistency Projection: A New Generalization Relation for Graphs. ICCS: International Conference on Conceptual Structures, Jul 2007, Sheffield, United Kingdom. pp.333-346, ⟨10.1007/978-3-540-73681-3_25⟩. ⟨lirmm-00196399⟩



Record views


Files downloads