Skip to Main content Skip to Navigation
Conference papers

Steps in the Representation of Concept Lattices and Median Graphs

Alain Gély 1 Miguel Couceiro 2 Laurent Miclet 3 Amedeo Napoli 2
2 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
3 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Median semilattices have been shown to be useful for dealing with phylogenetic classication problems since they subsume median graphs, distributive lattices as well as other tree based classica-tion structures. Median semilattices can be thought of as distributive ∨-semilattices that satisfy the following property (TRI): for every triple x, y, z, if x ∧ y, y ∧ z and x ∧ z exist, then x ∧ y ∧ z also exists. In previous work we provided an algorithm to embed a concept lattice L into a dis-tributive ∨-semilattice, regardless of (TRI). In this paper, we take (TRI) into account and we show that it is an invariant of our algorithmic approach. This leads to an extension of the original algorithm that runs in polynomial time while ensuring that the output is a median semilattice.
Complete list of metadatas

https://hal.inria.fr/hal-02912312
Contributor : Alain Gely <>
Submitted on : Wednesday, August 5, 2020 - 4:05:20 PM
Last modification on : Thursday, September 3, 2020 - 1:58:24 PM

File

cla2020_medianGraph.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02912312, version 1

Citation

Alain Gély, Miguel Couceiro, Laurent Miclet, Amedeo Napoli. Steps in the Representation of Concept Lattices and Median Graphs. CLA 2020 - 15th International Conference on Concept Lattices and Their Applications, Sadok Ben Yahia; Francisco José Valverde Albacete; Martin Trnecka, Jun 2020, Tallinn, Estonia. pp.1-11. ⟨hal-02912312⟩

Share

Metrics

Record views

33

Files downloads

83