Algorithms for k-meet-semidistributive lattices

Abstract : In this paper we consider k-meet-semidistributive lattices and we are interested in the computation of the set-colored poset associated to an implicational base. The parameter k is of interest since for any finite lattice L there exists an integer k for which L is k-meet-semidistributive. When k=1 they are known as meet-semidistributive lattices. We first give a polynomial time algorithm to compute an implicational base of a k-meet-semidistributive lattice from its associated colored poset. In other words, for a fixed k, finding a minimal implicational base of a k-meet-semidistributive lattice L from a context (FCA literature) of L can be done not just in output-polynomial time (which is open in the general case) but in polynomial time in the size of the input. This result generalizes that in [26]. Second, we derive an algorithm to compute a set-colored poset from an implicational base which is based on the enumeration of minimal transversals of a hypergraph and turns out to be in polynomial time for k-meet-semidistributive lattices [13,20]. Finally, we show that checking whether a given implicational base describes a k-meet-semidistributive lattice can be done in polynomial time.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2017, 658, pp.391 - 398. 〈10.1016/j.tcs.2015.10.029〉
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01571243
Contributeur : Marie-France Sagot <>
Soumis le : mardi 1 août 2017 - 19:46:46
Dernière modification le : jeudi 28 juin 2018 - 14:38:51

Fichier

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

Identifiants

Citation

Laurent Beaudou, Arnaud Mary, Lhouari Nourine. Algorithms for k-meet-semidistributive lattices. Theoretical Computer Science, Elsevier, 2017, 658, pp.391 - 398. 〈10.1016/j.tcs.2015.10.029〉. 〈hal-01571243〉

Partager

Métriques

Consultations de la notice

222

Téléchargements de fichiers

57