# Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation

3 MAREL - Models And Reuse Engineering, Languages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Given a relation $\Rel\subseteq\Obj\times\Attr$ on a set $\Obj$ of objects and a set $\Attr$ of attributes, the AOC-poset (Attribute/Object Concept poset), is the partial order defined on the introducers'' of objects and attributes in the corresponding concept lattice. In this paper, we present \hermes, a simple and efficient algorithm for building an AOC-poset which runs in $O(min\{nm,\,n^\alpha\})$, where $n$ is the number of objects and attributes, $m$ is the size of the relation, and $n^\alpha$ is the time required to perform matrix multiplication (currently $\alpha=2.376$). Finally, we compare the execution time of \hermes~with the execution time of other published algorithms which compute the AOC-poset: \ares, \ceres~and \pluton. We characterize the cases where each of these algorithms is relevant to use.
Keywords :
Type de document :
Article dans une revue
Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 72 (1), pp.45-71. 〈10.1007/s10472-014-9418-6〉
Liste complète des métadonnées

Littérature citée [35 références]

https://hal.inria.fr/hal-01101144
Contributeur : Amedeo Napoli <>
Soumis le : vendredi 9 janvier 2015 - 17:10:05
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : samedi 12 septembre 2015 - 00:45:37

### Fichier

berry-etal-amai72-2014 (1).pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Anne Berry, Alain Gutierrez, Marianne Huchard, Amedeo Napoli, Alain Sigayret. Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 72 (1), pp.45-71. 〈10.1007/s10472-014-9418-6〉. 〈hal-01101144〉

### Métriques

Consultations de la notice

## 442

Téléchargements de fichiers