Hermes: an efficient algorithm for building Galois sub-hierarchies

Anne Berry 1 Marianne Huchard 2 Amedeo Napoli 3 Alain Sigayret 1
1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
2 MAREL - Models And Reuse Engineering, Languages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Given a binary relation R on a set O of objects and a set A of attributes, the Galois sub-hierarchy (also called AOC-poset) is the partial order on the introducers of objects and attributes in the corresponding concept lattice. We present a new efficient algorithm for building a Galois sub-hierarchy which runs in O(min{nm, n ^{\alpha}}), where n is the number of objects or attributes, m is the size of the relation, and n ^{\alpha} is the time required to perform matrix multiplication (currently \alpha = 2.376).
Keywords : Galois lattice Galois Sub-Hierarchy Concept lattice AOC-concept poset algorithm
Type de document :
Communication dans un congrès
Laszlo Szathmary, Uta Priss. CLA: Concept Lattices and their Applications, Oct 2012, Fuengirola, Málaga, Spain. Universidad de Malaga, 9th International Conference on Concept Lattices and Applications, pp.21-32, 2012, 〈http://www.matap.uma.es/cla2012/CLA2012/〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00743882
Contributeur : Marianne Huchard <>
Soumis le : dimanche 21 octobre 2012 - 15:52:56
Dernière modification le : lundi 5 février 2018 - 09:24:58
Document(s) archivé(s) le : mardi 22 janvier 2013 - 03:39:06

Fichier

paperAnneBerry.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-00743882, version 1

Collections

INRIA | PRES_CLERMONT | MAREL | UNIV-LORRAINE | LIRMM | SIGMA-CLERMONT | LORIA-NLPKD | LORIA | MIPS | UNIV-MONTPELLIER | LIMOS

Citation

Anne Berry, Marianne Huchard, Amedeo Napoli, Alain Sigayret. Hermes: an efficient algorithm for building Galois sub-hierarchies. Laszlo Szathmary, Uta Priss. CLA: Concept Lattices and their Applications, Oct 2012, Fuengirola, Málaga, Spain. Universidad de Malaga, 9th International Conference on Concept Lattices and Applications, pp.21-32, 2012, 〈http://www.matap.uma.es/cla2012/CLA2012/〉. 〈lirmm-00743882〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

676

Téléchargements de fichiers

391

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD