=Paper=
{{Paper
|id=Vol-2123/paper9
|storemode=property
|title=Steps Towards Achieving Distributivity in Formal Concept Analysis
|pdfUrl=https://ceur-ws.org/Vol-2123/paper9.pdf
|volume=Vol-2123
|authors=Alain Gély,Miguel Couceiro,Amedeo Napoli
|dblpUrl=https://dblp.org/rec/conf/cla/GelyCN18
}}
==Steps Towards Achieving Distributivity in Formal Concept Analysis==
https://ceur-ws.org/Vol-2123/paper9.pdf
Steps Towards Achieving Distributivity in
Formal Concept Analysis
Alain Gély1 , Miguel Couceiro2 , and Amedeo Napoli2
1
Université de Lorraine, CNRS, LORIA, F-57000 Metz, France
2
Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
{alain.gely,miguel.couceiro,amedeo.napoli}@loria.fr
Abstract. In this paper we study distributive lattices in the framework
of Formal Concept Analysis (FCA). The main motivation comes from
phylogeny where biological derivations and parsimonious trees can be
represented as median graphs. There exists a close connection between
distributive lattices and median graphs. Moreover, FCA provides efficient
algorithms to build concept lattices. However, a concept lattice is not
necessarily distributive and thus it is not necessarily a median graph.
In this paper we investigate possible ways of transforming a concept
lattice into a distributive one, by making use Birkhoff’s representation
of distributive lattices. We detail the operation that transforms a reduced
context into a context of a distributive lattice. This allows us to reuse
the FCA algorithmic machinery to build and to visualize distributive
concept lattices, and then to study the associated median graphs.
1 Context and Motivations
Formal Concept Analysis (FCA) has proved to be an effective tool in data anal-
ysis and knowledge discovery in several application domains [10,14]. Concept
lattices provide a valuable support for several tasks, such as classification, infor-
mation retrieval and pattern recognition. Besides lattices, trees and their exten-
sions [4,5,13] are used in biology, notably, in phylogeny, for modeling inter-species
filiations. In this domain, one of the main problems is to find evolution trees for
representing existing species from accessible DNA fragments. When several trees
are leading to the same inter-species filiations, the preferred ones are the most
“parsimonious”, i.e. the number of modifications such as mutations for example,
is minimal for the considered species. However, several possible parsimonious
trees may exist. Such a situation arises with inverse or parallel mutations, e.g.,
when a gene goes back to a previous state or the same mutation appears for
two non-linked species. This asks for a generic representation of such a family of
trees.
Bandelt [2,3] proposes the notion of median graph to overcome this issue,
since he noticed that a median graph is capable of encoding all parsimonious
trees. A median graph is a connected graph such that for any three vertices
a, b, c, there is exactly one vertex x which lies on a shortest path between each
pair of vertices in ta, b, cu. Alternatively, median graphs can be thought of as a
c paper author(s), 2018. Proceedings volume published and copyrighted by its editors.
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp.
105–116, Department of Computer Science, Palacký University Olomouc, 2018.
Copying permitted only for private and academic purposes.
106 Alain Gély, Miguel Couceiro, and Amedeo Napoli
generalization distributive lattices [8,15]. However, the extraction of such struc-
tures directly from data remained unaddressed.
Uta Priss [19,20] made a first attempt to use algorithmic machinery of FCA
and the links between distributive lattices and median graphs, to analyze phylo-
genetic trees. However, not every concept lattice is distributive, and thus FCA
alone does not necessarily outputs median graphs. In [20] Uta Priss sketches
an algorithm to convert any lattice into a median graph. The key step is to
transform any lattice into a distributive lattice.
In this article, we propose an algorithm supporting such a transformation
that minimizes the changes introduced to the original lattice. Using the context
of an initial concept lattice as input, the algorithm outputs the context of a
distributive lattice, without necessarily building the lattice. Our approach relies
on Birkhoff’s representation of distributive lattices [6,7]. Moreover, we illustrate
our approach with a generic example that reveals the difficulties of transforming
of a concept lattice into a distributive lattice. We do not settle this issue entirely,
but we propose major steps and an approach towards its solution.
The paper is organized as follows. In Sections 2 and 3 we recall the basic
background and notation as well as some key results on distributive lattices. The
transformation algorithm is presented in Section 4 and we discuss the strengths
and limitations of our approach in Section 5.
2 Definitions and Notations
In this section we recall basic notions and notation needed throughout the paper.
We will mainly adopt the formalism of [14], and we refer the reader to [11,12]
for further background.
2.1 Partially Ordered Sets, Lattices and Homomorphisms
A partially ordered set (or poset for short) is a pair pP, ďq where P is a set
and ď is a partial order on P , that is, a reflexive, antisymmetric and transitive
binary relation on P . A poset pP 1 , ď1 q is a subposet of pP, ďq if P 1 Ď P and
ď1 Ďď. For a subset X Ď P , let Ó X “ ty P P : y ď x for some x P Xu and
Ò X “ ty P P : x ď y for some x P Xu. If X :“ txu, we use the notation Ó x and
Ò x instead of Ó txu and Ò txu, respectively. In this paper, we will only consider
finite posets pP, ďq and, when there is no danger of ambiguity, we will refer to
them by their underlying universes P .
A set X Ď P is a (poset) ideal (resp. filter ) if X “Ó X (resp. X “Ò Xq. If
X “Ó x (resp. X “Ò x) for some x P P , then X is said to be a principal ideal
(resp. filter) of P . For x, y P P , the greatest element of Ó x X Ó y (resp. least
element Ò x X Ò y) if it exists, is called the infimum (resp. supremum) of x and y.
A lattice is a poset pL, ďq such that the infimum and the supremum of any pair
x, y P L exist, and they are denoted respectively by x ^ y and x _ y. A subset
X Ď L is a sublattice of L if for every x, y P X we have that x ^ y, x _ y P X. As
Steps Towards Achieving Distributivity in Formal Concept Analysis 107
for posets, we will only consider finite lattices pL, ďq and we will refer to them
by their underlying universes L.
In this finite setting, posets and lattices can be represented and clearly visu-
alized by their Hasse-diagrams [12]. Also, the notions of infimum and supremum
naturally extend from pairs to any subset of elements of a given lattice L. In this
way, the notions of ^- and _-irreducible elements (that constitute the Ź building
˚
blocks of lattices)
Ž can be defined as follows. For x P L, let x “ pÒ xztxuq
and x˚ “ pÓ xztxuq. Then x P L is said to be a ^-irreducible element of L
if x ‰ x˚ . Dually, x is said to be a _-irreducible element of L if x ‰ x˚ . We
will denote the set of ^-irreducible elements and _-irreducible elements of L
by M pLq and JpLq, respectively. Observe that both M pLq and JpLq are posets
when ordered by ď.
We now recall the notions of poset and lattice homomorphisms.
Let pP, ďq and pP 1 , ď1 q be two posets. A mapping f : P Ñ P 1 is said to be a
(poset) homomorphism if x ď y implies f pxq ď1 f pyq. In addition, if f : P Ñ P 1 is
injective (one-to-one), then it is called a (poset) embedding. If it is a bijection and
an embedding such that, for every x1 , y 1 P P 1 , x1 ď1 y 1 implies f ´1 px1 q ď f ´1 py 1 q,
then it is called a (poset) isomorphism.
In the case of lattices, the notions of homomorphism, embedding and iso-
morphism become more stringent. Let pL, ^, _q and pL1 , ^1 , _1 q be two lattices.
A mapping f : L Ñ L1 is said to be a (lattice) homomorphism if f px ^ yq “
f pxq ^1 f pyq and f px _ yq “ f pxq _1 f pyq. In addition, if f : L Ñ L1 is injective,
then it is called a (lattice) embedding. If it is a bijection and it is an embedding
such that f ´1 is also an embedding, then it is called a (lattice) isomorphism.
When it is clear from the context, we will drop “(poset)” and “(lattice)” and
simply refer to homomorphism, embedding and isomorphism.
It is noteworthy that the image f pLq of a homomorphism f : L Ñ L1 is a
sublattice of L1 , and that two isomorphic lattices have the same Hasse diagram.
In particular, two lattices L and L1 are isomorphic if and only if both (1) JpLq
and JpL1 q, and (2) M pLq and M pL1 q are isomorphic. In the case of distributive
lattices, Birkhoff [7] showed that (1) suffice to guarantee that L and L1 are
isomorphic (pJ, ďq and pM, ďq are isomorphic). The latter result is key ingredient
in Birkhoff ’s representation of distributive lattices that we will discuss in Section
3, and that we will use in Section 4 to devise an algorithm to modify any finite
lattice into an “optimal” distributive lattice containing it.
2.2 Formal Concept Analysis
Reduced Contexts, Concepts and Concept Lattices. We denote by C “
pO, A, Iq a formal context where O is a set of objects, A a set of attributes and
I an incidence relation between objects and attributes. In phylogenetic data,
objects are usually species, attributes are mutations, and po, aq P I –or oIa–
when mutation a is spotted in species o.
108 Alain Gély, Miguel Couceiro, and Amedeo Napoli
Definition 1 (Galois connections). For a set X Ď O, Y Ď A we define:
X 1 “ ty P A | xIy for all x P Xu
Y 1 “ tx P O | xIy for all y P Y u
Then a formal concept is a pair pX, Y q, where X Ď O, Y Ď A and X 1 “ Y
and Y 1 “ X. X is the extent and Y is the intent of the concept. The set of all
formal concepts ordered by inclusion of the extents –dually the intents– denoted
by ď generates the concept lattice of the context C “ pO, A, Iq.
For o P O, γo “ po2 , o1 q denotes the concept introducing object o. For a P A,
µa “ pa1 , a2 q denotes the concept introducing attribute a.
A clarified context is a context such that x1 “ y 1 implies x “ y for any
element of O and any element of A. Moreover, a clarified context is reduced iff
it contains:
– no vertex x P O such that x1 “ X 1 with X Ď O, x R X
– no vertex x P A such that x1 “ X 1 with X Ď A, x R X
The reduced context is also called a standard context. Note that the standard
context of lattice L is such that O “ JpLq and A “ M pLq.
Arrow Relations.
Definition 2. Let us consider a context pO, A, Iq, an object o P O and an at-
tribute a P A, then:
– o a iff po, aq R I and if a1 Ď x1 , a1 “ x1 then po, xq P I
Ò Ó
– o a iff po, aq R I and if o1 Ď x1 , o1 “ x1 then px, aq P I
– o a iff o a and o a
Ø
Ò
Ó
Stated differently, o a iff o1 is maximal among all object intents which do
Ó
not contain a. It can be shown that:
Ž
o a ô γo P JpLq and γo ^ µa “ pγoq˚ pwith x˚ “ Ź pÓ xztxuqq
Ó Ò
o a ô µa P M pLq and γo _ µa “ pµaq˚ pwith x˚ “ pÒ xztxuqq
Arrow relations are related to irreducible elements in JpLq and M pLq. In the
following, we only consider arrow relations in reduced contexts.
An alternative equivalent definition of arrow relations is the following:
Definition 3. Let L be a lattice, j P JpLq and m P M pLq, then:
– j m iff µm P maxpLz Ò γjq where maxp.q denotes the maximal elements.
Ò Ó
– j m iff γj P minpLz Ó µmq where minp.q denotes the minimal elements.
– j m iff j m and j m.
Ø
Ò
Ó
C “ pJ, M, I, , q is the reduced context with arrow relations. It can be
Ó
Ò
represented by a table with (irreducible) objects in lines, (irreducible) attributes
in columns, and in cell pj, mq (intersection of row j and column m):
Steps Towards Achieving Distributivity in Formal Concept Analysis 109
– ˆ if j ď m where ď is the partial ordering in the concept lattice,
– if j m,
Ó Ò
Ó Ò Ó
– if j m,
– if j m and j m,
Ø
Ò
– otherwise an empty cell.
Fig. 1 shows three examples of reduced contexts with arrow relations C “
pJ, M, I, , q and the corresponding concept lattices. The two first lattices
Ó
Ò
on the left are respectively named M3 and N5 and they are the smallest non-
distributive lattices. The third lattice on the right is a distributive lattice.
Distributive lattice
M3 N5
a b c d
a b c a b c
1 ˆ ˆ ˆ
Ø
1 ˆ 1 ˆ
Ø
Ø Ø
Ø
ˆ ˆ ˆ
Ó
2
Ø
2 ˆ 2 ˆ ˆ
Ø Ø
Ø
3 ˆ ˆ
Ø
3 ˆ 3 ˆ
Ø
Ø
ˆ ˆ
Ò
4
Ø
Fig. 1. Three lattices and their reduced contexts with arrow relations.
3 Distributive Lattices and Their Representation
A lattice is distributive if ^ and _ are distributive one with respect to the over.
Formally, a lattice L is distributive if for every x, y, z P L, we have that one (or,
equivalently, both) of the following identities holds:
piq x _ py ^ zq “ px _ yq ^ px _ zq, piiq x ^ py _ zq “ px ^ yq _ px ^ zq.
Distributive lattices appear naturally in any classification task or as compu-
tation and semantic models; see, e.g., [11,12,16,17]. This is partially due to the
fact that any distributive lattice can be thought of as a sublattice of a power-set
lattice, i.e., the set PpXq of subsets of a given set X. This result is a corollary
to Birkhoff’s representation of distributive lattices that we will further discuss
in Subsection 3.2.
3.1 Characterization of Distributive Lattice
The distributive property of lattices has been equivalently described in several
ways. We recall a few useful characterizations that we will use in the following
sections of the paper.
110 Alain Gély, Miguel Couceiro, and Amedeo Napoli
Theorem 1. A lattice L is distributive if and only if one (or, equivalently, all)
of the following conditions hold:
1. px ^ yq _ py ^ zq _ pz ^ xq “ px _ yq ^ py _ zq ^ pz _ xq;
2. L does not contain neither N5 nor M3 as sublattice;
3. the reduced context of L with arrow relations contains exactly one double-
arrow in each row and in each column, and no other arrows.
Ø
The first characterization establishes a correspondence between distributive
lattices and median algebras. Indeed, a median algebra is a structure pM, mq
where M is a nonempty set and m : M 3 Ñ M is an operation, called median op-
eration, that satisfies the following conditions mpa, a, bq “ a and mpmpa, b, cq, d, eq
“ mpa, mpb, c, dq, mpb, c, eqq, for every a, b, c, d, e P M . It is not difficult to see
that if L is distributive, then mpa, b, cq “ pa ^ bq _ pb ^ cq _ pc ^ aq is a me-
dian operation. The connection to median graphs was established by Avann [1]
who showed that every median graph is the Hasse diagram of a median algebra
(thought of as a semilattice). For further background see, e.g., [2].
The second characterization describes distributive lattices in terms of two
forbbiden structures, namely, M3 and N5 (see Fig. 1) that are, up to isomor-
phism, the smallest non distributive lattices. The third characterization is given
in terms of formal contexts and it is also illustrated in Fig. 1: neither M3 nor
N5 are distributive since
– for M3 , there are two double arrows by row and column;
– for N5 , there is one double arrow by row and column, but additional simple
arrows.
3.2 Distributive Lattices and Ideal Lattices
Let pP, ďq be a poset and consider the set OpP q of ideals of P , i.e.,
ď
OpP q “ t Ó x | X Ď P u.
xPX
It is well-known that for every poset P , the set OpP q ordered by inclusion is a
distributive lattice, called ideal lattice of P , and that two posets P and P 1 are iso-
morphic if and only if OpP q and OpP 1 q are isomorphic as lattices. Furthermore,
the poset of _-irreducible elements of OpP q is
JpOpP qq “ tÓ x | x P P u
and it is (order) isomorphic to P .
Dually, we saw in Subsection 2.1 that for any lattice L the set JpLq of _-
irreducible elements of L is a poset ordered by inclusion, and that if two lattices
L and L1 are isomorphic, then JpLq and JpL1 q are also isomorphic (as posets).
Moreover, for any lattice L the set OpJpLqq of ordered ideals of JpLq is a distribu-
tive lattice that contains an isomorphic copy of L as a subposet. In particular,
if L is isomorphic to OpJpLqq, then L must be distributive. The representation
theorem of Birkhoff [6] states that the converse is true.
Steps Towards Achieving Distributivity in Formal Concept Analysis 111
Birkhoff ’s Representation Theorem 1 Let L be a (finite) distributive lat-
tice and JpLq. Then the mapping x ÑÓ x X JpLq is a (lattice) isomorphism from
L to OpJpLqq.
As immediate consequences we have that every (finite) distributive lattice can
be thought of as a sublattice of a powerset lattice or, equivalently, as a lattice
of ideals of a poset. Figure 2 illustrates the latter assertion: on the left is a
poset P , and on the right is the lattice of ideals of P . For an arbitrary lattice L,
Fig. 2. Illustration of Birkhoff’s Representation Theorem.
not necessarily distributive, there may be several lattices such that their poset
of _-irreducible elements are isomorphic but only one of them is a distributive
lattice [9,18]. Our goal is to make use of the previous results to present an
algorithmic approach that receives a lattice L as input, and outputs an “optimal”
distributive lattice Ld such that pJpLq, ďq is isomorphic topJpLd q, ďd q. Here, by
“optimal” it should be understood “with the least number of modifications”
(notably, insertions).
4 Proposal for Building a Distributive Lattice
From any lattice L, we want to obtain a distributive one Ld . Moreover, we want
Ld to be “similar” to L. In this work, Ld is considered as similar to L if the
posets of _-irreducible elements of Ld and of L are isomorphic. In this case, L
can be embedded in Ld (Ld is a _-completion of L).
With this definition of “similar” (which can dually be applied to ^-irreducible
elements), we can use Birkhoff Representation Theorem to compute Ld or its
reduced context.
The main idea of algorithm 1 is to compute the context of Ld from the reduced
context of L as input. Our approach relies on the underlying poset pJ, ďq which
is used to compute Md .
Property 1. Algorithm 1 outputs the reduced context of the ideal lattice of JpLq.
Proof. By construction, there is only one double-arrow by row and by column,
and no other arrows. It follows that Cd is the context of a distributive lattice
As discussed in section 2.1, this lattice is the ideal poset of pJpLq, ďq. It follows
that pJpLq, ďq and pJpLd q, ďd q are isomorphic. \
[
112 Alain Gély, Miguel Couceiro, and Amedeo Napoli
Algorithm 1: Construction of context of distributive lattice.
Data: Reduced context CpJ, M, Iq
Result: Reduced context Cd pJ, Md , Id q of pOpJq, Ď, X, Yq
Md Ð H
Id Ð H
foreach j P J do
Òj Ð H
foreach i P J do
if j 1 Ď i1 then Ò j ÐÒ j Y i
Md Ð Md Y mj // add a ^-irreducible element mj such that j mj
Ø
X Ð Jz Ò j // elements of poset J which are not greater than j
foreach x P X do
Id Ð Id Y px, mj q
To illustrate the algorithm, we use N5 context as input. At the beginning of
the algorithm, the context Cd has |J| rows but zero columns. Each step of the
external loop computes mj , a new ^-irreducible element of Cd such that j
Ø
mj .
Step 1. Computation of m1 using Jz Ò 1. The algorithm computes the _-
representation of m1 , the ^-irreducible element such that 1 m1 . At the end
Ø
of this step of the loop, Cd has a unique column which correspond to m1 .
m1
1
2 ˆ
3 ˆ
Step 2. Computation of m2 using Jz Ò 2. The algorithm computes the _-
representation of m2 , the ^-irreducible element such that 2 m2 . At the end
Ø
of this step of the loop, Cd has two columns which correspond to m1 and to a
newly computed element m2 .
m1 m2
1 ˆ
2 ˆ
3 ˆ
Step 3. Computation of m3 using Jz Ò 3. The algorithm computes the _-
representation of m3 , the ^-irreducible element such that 3 m3 . At the end
Ø
of this step of the loop, Cd has three columns which correspond to m1 , m2 and
Steps Towards Achieving Distributivity in Formal Concept Analysis 113
to a newly computed element m3 .
m1 m2 m3
1 ˆ ˆ
2 ˆ ˆ
3 ˆ
The whole context Cd for Ld is now computed. By construction, the only
arrow relations are double arrows between j and mj Below, Ld is drawn with
black circles for concepts which were present in L and white circles for new
concepts.
m1 m2 m3
1 ˆ ˆ
Ø
2 ˆ ˆ
Ø
3 ˆ
Ø
5 Discussion and Conclusion
Motivated by the work of Priss [20] on the use of FCA on phylogenetic problems,
we have proposed an algorithmic approach to compute the reduced context of a
distributive lattice Ld from the reduced context of any lattice L, that ensures an
order embedding from L into Ld that preserves ^. So, Ld can be considerated
“not too far” from L and thus suitable for applications in phylogeny. In the
remainder of this final section, we discuss some features of this algorithm.
First, we discuss an interpretation of the behavior of the algorithm for phylo-
genetic data. The algorithm computes ^-irreducible elements of Ld without any
consideration for ^-irreducible elements of L but, as discussed in Subsection 3.2,
this is not a problem. Now, for real data, two cases may appear:
1. µmj P L: in this case, we can use the initial label m of the object (this label
may represent a particular gene mutation);
2. µmj R L: this case suggests a gene mutation that is not spotted in the data,
but that is necessary to provide a parsimonious tree.
Similarly, it is possible that m P M pLq but m R M pLd q but in any case, µm exists
in L and Ld . This is the case when a mutation m is regarded as the infimum of
other mutations.
Second, we propose an algorithm to build the context of a distributive lattice
from any context. However, it is only a partial solution to the problem considered
in [20]:
“an algorithm for converting a concept lattice [into a median graph]
consists of omitting the bottom node and then checking every principal
filter for distributivity and turning it into a distributive lattice if it is
not already one.”
114 Alain Gély, Miguel Couceiro, and Amedeo Napoli
In the following, we discuss the whole process presented in [20]. We have
proposed an algorithmic approach to “turning it into a distributive lattice if it
is not already one”. However, there is still some work to do as the suggestion in
[20] does provide suitable solutions. This is illustrated by the example given in
Figure 3.
a b c d e
1 ˆˆ ˆ
2 ˆˆ ˆ
3 ˆ ˆ
4 ˆ ˆ
5 ˆ
6 ˆ
Fig. 3. Problematic context and associated concept lattice
Indeed, if we were to follow the steps suggested by Priss [20] on this example,
the procedure would not provide a correct solution (i.e., a distributive lattice for
principal filters). Consider a local approach on Ò 1 and Ò 2. The first step is to
compute the reduced context of Ò 1 (since the example is symmetric for 1 and
2, we only give details for 1). The reduced context C 1 of L1 “Ò 1 can be built
from CpJ, M, Iq by first observing that 11 “ ta, b, du, which entails the following
context:
a b d
and that reduces to:
1 ˆˆˆ
2 ˆ a b d
3 ˆ ˆ 2 ˆ
4 3 ˆ ˆ
5 ˆ 5 ˆ
6
Algorithm 1 then returns the context Cd1 of a distributive lattice; similarly,
Algorithm 1 returns context Cd2 of L2 “Ò 2.
Cd1 m2 m3 m5 Cd2 m1 m4 m6
2 ˆ ˆ 1 ˆ ˆ
3 ˆ ˆ 4 ˆ ˆ
5 ˆ 6 ˆ
Moreover, in the whole lattice, every m P M 1 is greater than 1 and every
m P M 2 is greater than 2. Hence we obtain the left context for the whole lattice
and the reduced context on the right:
Steps Towards Achieving Distributivity in Formal Concept Analysis 115
m2 m3 m5 m1 m4 m6 m2 m5 m1 m6
2 ˆ ˆ ˆ ˆ ˆ 2 ˆ ˆ ˆ
3 ˆ ˆ 3 ˆ ˆ
5 ˆ 5 ˆ
1 ˆ ˆ ˆ ˆ ˆ 1 ˆ ˆ ˆ
4 ˆ ˆ 4 ˆ ˆ
6 ˆ 6 ˆ
The resulting lattice is presented in Figure 4.a; not every principal filter is
distributive. The problem comes from the fact that the modified parts of the
lattice belong to intersection of Ò 1 and Ò 2. The new added elements in a filter
may belong to other filters, and this may “break” the consistency achieved in
the other filters.
Now we applied this procedure in parallel for Ò 1 and Ò 2, and someone could
argue that it should be iterated filter by filter until a fixed point is reached.
Nevertheless, an optimal solution cannot be found through the general procedure
suggested by Priss [20], since all filters must be considered simultaneously. In
the present case, there exists an optimal solution with only one new concept.
This solution is given in Figure 4.b
paq pbq
Fig. 4. paq Solution obtained after a local approach and pbq optimal solution.
The difficulty of simultaneously considering all the filters should be studied
and solved to deal with phylogenetic data. This entails to the two following open
problems.
Problem 1 (Lattice version). Given a lattice L, propose an efficient algorithm to
output a lattice Ld such that:
– for each atom x of Ld , Ò x is a distributive lattice,
– there is an order embedding from L to Ld , and
– |Ld | ´ |L| is minimal.
Problem 2 (Context version). Given the reduced context of a lattice L, propose
an efficient algorithm to output the reduced context of a lattice Ld such that:
– for each atom x of Ld , Ò x is a distributive lattice,
116 Alain Gély, Miguel Couceiro, and Amedeo Napoli
– there is an order embedding from L to Ld , and
– |Ld | ´ |L| is minimal.
We are currently working on these two variations of the problem. The ob-
jective is to establish an operational bridge between FCA (concept lattices) and
distributive lattices to allow the use of FCA algorithms in phylogeny.
References
1. Avann, S.P.: Median algebras. Proceedings of the American Mathematical Society
12, 407–414 (1961)
2. Bandelt, H.J., Hedlı́ková, J.: Median algebras. Discrete mathematics 45(1), 1–30
(1983)
3. Bandelt, H.J., Forster, P., Röhl, A.: Median-joining networks for inferring intraspe-
cific phylogenies. Molecular biology and evolution 16(1), 37–48 (1999)
4. Bertrand, P., Diatta, J.: Multilevel clustering models and interval convexities. Dis-
crete Applied Mathematics 222, 54–66 (2017)
5. Bertrand, P., Janowitz, M.F.: Pyramids and weak hierarchies in the ordinal model
for clustering. Discrete Applied Mathematics 122(1), 55–81 (2002)
6. Birkhoff, G.: On the combination of subalgebras. In: Mathematical Proceedings of
the Cambridge Philosophical Society. vol. 29, pp. 441–464. Cambridge University
Press (1933)
7. Birkhoff, G.: Lattice theory. In: Colloquium Publications, vol. 25. Amer. Math.
Soc., 3. edn. (1967)
8. Birkhoff, G., Kiss, S.A.: A ternary operation in distributive lattices. Journal of
Symbolic Logic 13(1), 50–51 (1948)
9. Bordalo, G.H., Monjardet, B.: The lattice of strict completions of a poset. Elec-
tronic Notes in Discrete Mathematics 5, 38–41 (2000)
10. Carpineto, C., Romano, G.: Concept Data Analysis: Theory and Applications.
John Wiley & Sons (2004)
11. Caspard, N., Leclerc, B., Monjardet, B.: Ensembles Ordonnés Finis: Concepts,
Résultats et Usages, vol. 60. Springer (2007)
12. Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge uni-
versity press (2002)
13. Diatta, J.: Galois weak hierarchies: Theoretical and computational issues. In: UK
Workshop on Computational Intelligence. p. 3 (2005)
14. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer (1999)
15. Grätzer, G.: General Lattice Theory (Second Edition). Birkhäuser (1996)
16. Hopcroft, J.E., Motwani, R., Rotwani, Ullman, J.D.: Introduction to Automata
Theory, Languages and Computability. Addison-Wesley Longman Publishing Co.,
Inc., Boston, MA, USA, 2nd edn. (2000)
17. Mattern, F.: Virtual time and global states of distributed systems. Parallel and
Distributed Algorithms 1(23), 215–226 (1989)
18. Nation, J., Pogel, A.: The lattice of completions of an ordered set. Order 14(1),
1–7 (1997)
19. Priss, U.: Concept lattices and median networks. In: CLA. pp. 351–354 (2012)
20. Priss, U.: Representing median networks with concept lattices. In: ICCS. pp. 311–
321. Springer (2013)