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)