A study of algorithms relating distributive lattices, median graphs, and Formal Concept Analysis - Irisa Accéder directement au contenu
Article Dans Une Revue International Journal of Approximate Reasoning Année : 2022

A study of algorithms relating distributive lattices, median graphs, and Formal Concept Analysis

Alain Gély
Miguel Couceiro
Amedeo Napoli

Résumé

In this paper, we study structures such as distributive lattices, distributive semilattices, and median graphs from an algorithmic point of view. Such structures are very useful in classification and phylogeny for representing lineage relationships for example. A distributive lattice can be considered as a median graph while a distributive ∨-semilattice can be considered as a median graph provided that some conditions holding on triple of elements are satisfied. Starting from a lattice structure with different representations, we study the problem of building a median graph from such structures. We make precise and propose algorithms for checking how a lattice can be distributive and can be a median graph. Then, we adapt the problem to semilattices as a lattice where the bottom element is removed is a ∨-semilattice. We also state the problem in terms of Formal Concept Analysis and the representation of a lattice as a formal context, i.e., a binary table. Moreover, we also propose as input a system of implications such as the Duquenne-Guigues basis of a lattice, and we study how to compute such a basis for a distributive semilattice. In the paper, we provide algorithms and examples which illustrate the difficulties related to these different classification tasks. In particular, the minimality of the output lattices is a condition which is hard to ensure and which cannot be always achieved.
Fichier principal
Vignette du fichier
Considerations_on_median_graph_computation_using_FCA.pdf (743.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03537744 , version 1 (20-01-2022)

Identifiants

Citer

Alain Gély, Miguel Couceiro, Laurent Miclet, Amedeo Napoli. A study of algorithms relating distributive lattices, median graphs, and Formal Concept Analysis. International Journal of Approximate Reasoning, 2022, 142, pp.370-382. ⟨10.1016/j.ijar.2021.12.011⟩. ⟨hal-03537744⟩
67 Consultations
146 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More