Removing an incidence from a formal context Martin Kauer? and Michal Krupka?? Department of Computer Science Palacký University in Olomouc 17. listopadu 12, CZ-77146 Olomouc Czech Republic martin.kauer@upol.cz michal.krupka@upol.cz Abstract. We analyze changes in the structure of a concept lattice cor- responding to a context resulting from a given context with a known concept lattice by removing exactly one incidence. We identify the set of concepts affected by the removal and show how they can be used for computing concepts in the new concept lattice. We present algorithms for incremental computation of the new concept lattice, with or without structural information. 1 Introduction When computing concept lattices of two very similar concepts (i.e., differing only in a small number of incidences), it doesn’t seem to be efficient to compute both concept lattices independently. Rather, an incremental method of computing one of the lattices using the other would be more desirable. Also, analyzing structural differences between concept lattices of two similar contexts would be interesting from the theoretical point of view. This paper presents first results in this direction. Namely, we consider two formal contexts differing in just one incidence and develop a method of comput- ing the concept lattice of the context without the incidence from the other one. In other words, we give a first answer to the question “What happens to the concept lattice, if we remove one cross from the context?”. Our results are the following. We consider contexts hX, Y, Ii and hX, Y, Ji such that J results from I by removing exactly one incidence. Further we consider the respective concept lattices B(I) and B(J). For these contexts and concept lattices we 1. identify concepts in B(I), affected by the removal (they form an interval in B(I)), ? The author acknowledges support by IGA of Palacky University, No. PrF 2014 034 ?? The author acknowledges support by the ESF project No. CZ.1.07/2.3.00/20.0059. The project is co-financed by the European Social Fund and the state budget of the Czech Republic. 2. show how they transform to concepts in the new concept lattice (they will either vanish entirely, or transform to one or two concepts), 3. derive several further results on the correspondence between the two lattices, 4. propose two basic algorithms for transforming incrementally B(I) to B(J). Several algorithms for incremental computation of concept lattices have been developed in the past [1, 5, 8, 6, 7, 2] (see also [4] for a comparison of some of the algorithms). In general, the algorithms build a concept lattice incrementally by modifying formal contexts by adding or removing objects one by one. Our approach is different as we focus on removing just one incidence. 2 Formal concept analysis Formal Concept Analysis has been introduced in [9], our basic reference is [3]. A (formal) context is a triple C = hX, Y, Ii where X is a set of objects, Y a set of attributes and I ⊆ X × Y a binary relation between X and Y . For hx, yi ∈ I it is said “The object x has the attribute y”. For subsets A ⊆ X and B ⊆ Y we set A↑I = {y ∈ Y | for each x ∈ A it holds hx, yi ∈ I}, B ↓I = {x ∈ X | for each y ∈ B it holds hx, yi ∈ I}. The pair h↑I , ↓I i is a Galois connection between sets X and Y , i.e., it satisfies for each A, A1 , A2 ⊆ X, B, B1 , B2 ⊆ Y , 1. If A1 ⊆ A2 , then A↑2I ⊆ A↑1I , if B1 ⊆ B2 , then B2↓I ⊆ B1↓I . 2. A ⊆ A↑I ↓I and B ⊆ B ↓I ↑I . If A↑I = B and B ↓I = A, then the pair hA, Bi is called a formal concept of hX, Y, Ii. The set A is called the extent of hA, Bi, the set B the intent of hA, Bi. A partial order ≤ on the set B(X, Y, I) of all formal concepts of hX, Y, Ii is defined by hA1 , B1 i ≤ hA2 , B2 i iff A1 ⊆ A2 (iff B2 ⊆ B1 ). B(X, Y, I) along with ≤ is a complete lattice and is called the concept lattice of hX, Y, Ii. Infima and suprema in B(X, Y, I) are given by * [  ↓I ↑I + ^ \ hAj , Bj i = Aj , Bj , (1) j∈J j∈J j∈J * + _ [  ↑I ↓I \ hAj , Bj i = Aj , Bj . (2) j∈J j∈J j∈J One of immediate consequences of (1) and (2) is that the intersection of any system of extents (resp. intents) is again an extent (resp. intent). Mappings γI : x 7→ h{x}↑I ↓I , {x}↑I i and µI : y 7→ h{y}↓I , {y}↓I ↑I i assign to each object x its object concept and to each attributeW y its attribute concept. V We call a subset K ⊆ L, where L is a complete lattice, -dense (resp. -dense) if and only if any element of L can be expressed by suprema (resp. infima) of some W elements fromV K. The set of all object concepts (resp. attribute concepts) is - dense (resp. -dense) in B(X, Y, I). This can be easily seen from (1) (resp. (2)). We will also need a notion of an interval in lattice L. We call a subset K ⊆ L an interval, if and only if there exist elements a, b ∈ L such that K = {k ∈ L | a ≤ k ≤ b}. We denote K as [a, b]. 3 Problem statement and basic notions Let hX, Y, Ii, hX, Y, Ji be two contexts over the same sets of objects and at- tributes such that hx0 , y0 i ∈ / J and I = J ∪ {hx0 , y0 i}. We usually denote concepts of hX, Y, Ii by c, c1 , hA, Bi, hA1 , B1 i, etc., and concepts of hX, Y, Ji by d, d1 , hC, Di, hC1 , D1 i, etc. The respective concept lattices will be denoted B(I) and B(J). Our goal is to find an efficient way to compute the concept lattice B(J) from B(I). We provide two solutions to this problem. First solution computes just elements of B(J), the second one adds also information on its structure. In this section we introduce some basic tools and prove simple preliminary results. The following proposition shows a correspondence between the derivation operators of contexts hX, Y, Ii and hX, Y, Ji. Proposition 1. For each A ⊆ X and B ⊆ Y it holds  ↑  ↓ ↑J A I if x0 ∈ / A, ↓J B I if y0 ∈ / B, A = B = A↑I \ {y0 } if x0 ∈ A, B ↓I \ {x0 } if y0 ∈ B. In particular, A↑J ⊆ A↑I and B ↓J ⊆ B ↓I . Proof. Immediate. Formal concepts from the intersection B(I) ∩ B(J) are called stable. These concepts are not influenced by removing the incidence hx0 , y0 i from I. When computing B(J) from B(I), stable concepts need not be recomputed. Proposition 2. A concept c ∈ B(I) is not stable iff c ∈ [γI (x0 ), µI (y0 )]. Proof. If c = hA, Bi ∈/ [γI (x0 ), µI (y0 )], then either x0 ∈/ A, or y0 ∈ / B. If, for instance, x0 ∈/ A, then by Proposition 1, B = A↑I = A↑J , showing B is the intent of a d ∈ B(J). Now by Proposition 1,  ↓ B I =A if y0 ∈ / B, B ↓J = ↓I B \ {x0 } = A \ {x0 } = A if y0 ∈ B and so d = c. The case y0 ∈ / B is dual. To prove the opposite direction it is sufficient to notice that c ∈ [γI (x0 ), µI (y0 )] is equivalent to hx0 , y0 i ∈ A × B, excluding the case hA, Bi ∈ B(J). For concepts c = hA, Bi ∈ B(I), d = hC, Di ∈ B(J) we set c = hA , B  i = hA↑J ↓J , A↑J i, c = hA , B i = hB ↓J , B ↓J ↑J i, d = hC  , D i = hD↓I , D↓I ↑I i, d = hC , D i = hC ↑I ↓I , C ↑I i. Evidently, c , c ∈ B(J) and d , d ∈ B(I). c (resp. c ) is called the upper (resp. lower ) child of c. In our setting, d = d (it would not be the case if I \ J had more than one element). It is the (unique) concept from B(I), containing, as a rectangle, the rectangle represented by d. The following theorem shows basic properties of the pairs h ,  i and h ,  i. Proposition 3 (child operators). The mappings c 7→ c , c 7→ c , and d 7→ d are isotone and satisfy c ≤ c , d ≤ d , c = c , d = d , c ≥ c , d ≥ d , c = c , d = d . Proof. Isotony follows directly from definition. Let c = hA, Bi. From Proposition 1 we have A↑J ⊆ A↑I . Thus, A = A↑I ↓I ⊆ ↑J ↓I A , whence c ≤ c . Similarly, for d = hC, Di, D↓J ⊆ D↓I , whence D↓I ↑J ⊆ ↓J ↑J D = D. To prove c = c it suffices to show that for the extent A of c it holds A↑J ↓I ↑J = A↑J . By Proposition 1, we have two possibilities: either A↑J = A↑I , or A↑J = A↑I \ {y0 }. In the first case A↑J ↓I ↑J = A↑J holds trivially, in the second case A↑J ↓I = A↑J ↓J (by the same proposition, because y0 ∈ / A↑J ) and ↑J ↓I ↑J ↑J ↓J ↑J ↑J   A =A = A . The equality d = d can be proved similarly. The assertions for lower children are dual. Corollary 1. The mappings c 7→ c and d 7→ d are closure operators and the mappings c 7→ c and d 7→ d are interior operators. Following two theorems utilize the operators  ,  ,  ,  to give several equiv- alent characterizations of stable concepts. First we prove a proposition. Proposition 4. The following assertions are equivalent for any c = hA, Bi ∈ B(I). 1. c is stable, 2. A↑I = A↑J , 3. B ↓I = B ↓J . Proof. “2 ⇒ 3”: by Proposition 1, A ⊆ A↑J ↓J = B ↓J ⊆ B ↓I = A. “3 ⇒ 2”: dual. The other implications follow by definition, since c is stable iff both 2. and 3. are satisfied. Proposition 5 (stable concepts in B(I)). The following assertions are equiv- alent for a concept c ∈ B(I): 1. c is stable, 2. c ∈ / [γI (x0 ), µI (y0 )], 3. c = c , 4. c = c , 5. c = c . Proof. Directly from Proposition 4. Proposition 6 (stable concepts in B(J)). The following assertions are equiv- alent for a concept d ∈ B(J): 1. d is stable, 2. d = d , 3. d is stable. Proof. Directly from Proposition 4. 4 Computing B(J ) without structural information Proposition 7. The following holds for c = hA, Bi ∈ B(I) and d = hC, Di ∈ B(J): If d = c , then B ∈ {D, D ∪ {y0 }} and if d = c , then A ∈ {C, C ∪ {x0 }}. Proof. By definition of  , D = A↑J , which is by Proposition 1 either equal to B, or to B \ {y0 }. Similarly for  . Proposition 8. A non-stable concept d ∈ B(J) is a (upper or lower) child of exactly one concept c ∈ B(I). This concept is non-stable and satisfies c = d = d . Proof. Let d = hC, Di. Since d is non-stable, then either C ↑I 6= C ↑J , or D↓I 6= D↓J . Suppose C ↑I 6= C ↑J and set A = C, B = C ↑I . By Proposition 1, x0 ∈ C, y0 ∈/ D and B = D ∪ {y0 }. By the same proposition, A = C = D↓J = D↓I , whence A is an extent of I. Thus, c = hA, Bi ∈ B(I) and it is non-stable because x0 ∈ A and y0 ∈ B (Proposition 2). Since D = C ↑J = A↑J , d = c . A = C yields c = d . We prove uniqueness of c. By Proposition 7, if for c0 = hA0 , B 0 i ∈ B(I) we have d = c0 , then either B 0 = D, or B 0 = D ∪ {y0 }. The first case is impossible, because it would make D an intent of I and, consequently, d a stable concept. The second case means c0 equals c above. There is a third case left: if d = c0 , then C = B 0↓J . Since x0 ∈ C, we have y0 ∈ / B 0 (Proposition 1). Thus, C = B 0↓I (Proposition 1 again). Consequently, C ↑I = B 0 and since y0 ∈ / B 0 , B 0 = C ↑J (Proposition 1 for the last time). Thus, d = c0 , which is a contradiction with non-stability of d. The case D↓I 6= D↓J is proved dually (in this case we obtain d = c ). The meaning of the previous theorem is that for each non-stable concept in B(J) there exists exactly one non-stable concept in B(I), such that these two are related via mappings  ,  or  ,  . The theorem leads the following simple way of constructing B(J) from B(I). For each c ∈ B(I) the following has to be done: 1. If c is stable, then it has to be added to B(J). 2. If c is not stable, then each its non-stable child (i.e., each non-stable element of {c , c }) has to be added to B(J). This method ensures that all proper elements will be added to B(J) (i.e., no element will be omitted) and each element will be added exactly once. Stable (resp. non-stable) concepts can be identified by means of Proposition 11. The following proposition shows a simple way of detecting whether a child of a non-stable concept from B(I) is stable. It also describes the role of fixpoints of operators  and  . Proposition 9. Let c ∈ B(I) be non-stable. Then – c is non-stable iff c is a fixpoint of  , – c is non-stable iff c is a fixpoint of  . Proof. If c is not stable, then c = (c ) by Theorem 8. On the other hand, if c is stable, then c = c by Theorem 6, which rules out c = c, because in that case c would be equal to c , which would make it stable by Theorem 5. The proof for c is dual. Example 1. In Fig. 1 we can see some examples of contexts with concepts of different types w.r.t. operators  ,  . The method is utilized in Algorithm 1. Algorithm 1 Transforming B(I) into B(J) (without structural information). procedure TransformConcepts(B(I)) B(J) ← B(I); for all c = hA, Bi ∈ [γI (x0 ), µI (y0 )] do B(J) ← B(J) \ {c}; if c = c then B(J) ← B(J) ∪ {c }; end if if c = c then B(J) ← B(J) ∪ {c }; end if end for return B(J); end procedure Time complexity of Algorithm 1 is clearly O(|B(I)||X||Y |) in the worst case scenario. Indeed, the number of non-stable concepts is at most equal to |B(I)| and the computation of operators  ,  can be done in O(|X| · |Y |) time. 5 Computing B(J ) with structural information To analyze changes in the structure of a concept lattice after removing an inci- dence, we need to investigate deeper properties of the closure operator  and the interior operator  and the sets of their fixpoints. y1 y2 y3 y0 y0 y1 y2 x0 × × × • x0 • × × x1 × × x1 x2 × × x2 x3 × × (a) The least concept is not sta- (b) Several non-trival non-stable ble and is a fixpoint of both op- concepts are fixpoints of both op- erators. erators. y1 y2 y0 y0 y1 y2 x0 × • x0 • × x1 × × x1 × × × x2 × x2 (c) Concept h{x0 , x1 }, {y0 , y2 }i (d) Concept h{x0 , x1 }, {y0 , y1 }i is a fixpoint of  , but not  . is a fixpoint of  , but not  . y1 y2 y3 y4 y0 y0 y1 y2 x0 × × • x0 • x1 × × × x1 × × x2 × x2 x3 × × × (e) Concept h{x0 , x1 }, {y0 }i is x4 × not a fixpoint of any operator. (f) Two concepts are not fix- points of any operator. Fig. 1: Examples of contexts with concepts of different types w.r.t. operators  ,  . Proposition 10. Each stable concept is a fixpoint of both  and  . Proof. Follows directly from Theorem 5 and Theorem 6. Since  is an interior operator and  is a closure operator on B(I), we have for each c ∈ B(I), c ≤ c ≤ c . Thus, we can consider the interval [c , c ] ⊆ B(I). Proposition 11. For any c ∈ B(I), each concept from [c , c ]\{c} is stable. Proof. First we prove that either c equals c, or is its upper neighbor. Let c = hA, Bi. By definition, the intent of c is equal to A↑J ↓I ↑I . By Proposition 1, A↑J ∈ {B, B \ {y0 }}. Thus, A↑J ↓I ↑I ∈ {B, B \ {y0 }}. If it equals B, then c = c. Otherwise the intents of c and c differ in exactly one attribute, which makes c and c neighbors. Also notice that in this case c is stable because its intent does not contain y0 (Proposition 2). Now let c0 ≤ c be non-stable. If c = c , then c0 ≤ c. If c < c , then c is non-stable (Proposition 10) whereas c is stable. Non-stable concepts in B(I) form an interval (Theorem 5). Thus, c0 ∨ c is non-stable and should be less than c . Hence, c0 ∨ c = c (c is a lower neighbor of c ), concluding c0 ≤ c again. In a similar way we obtain the inequality c0 ≥ c for each non-stable c0 ≥ c . The following proposition shows an important property of the sets of fixpoints w.r.t. the ordering on B(I): The set of fixpoints of  is a lower set whereas the set of fixpoints of  is an upper set. Proposition 12. Let c ∈ B(I) be a non-stable concept. If c is a fixpoint of  , then each c0 ≤ c is also a fixpoint of  . If c is a fixpoint of  , then each c0 ≥ c is also a fixpoint of  . Proof. Let c = c and c0 ≤ c. If c0 is stable, then the assertion follows by Proposition 10. Suppose c0 is not stable. By extensivity and isotony of  , c0 ≤    c0 ≤ c = c. Thus, c0 is not stable (Proposition 2) and c0 = c0 by Proposition 11. The case c = c is dual. The above results are used in Algorithm 2, which computes the lattice B(J) together with the information of its ordering. The algorithm is more complicated than the previous one. We provide a short description of the algorithm, together with some examples. Due to space limitations, we will not dwell into details. We will also leave out dual parts of similar cases. The algorithm processes all non-stable concepts of B(I) in a bottom-up di- rection, using an arbitrary linear ordering v such that if c1 ≤ c2 , then c1 v c2 . Each concept is either modified (by removing x0 from the extent or y0 from in- tent), or disposed of entirely. Sometimes, new concepts are created. All concepts also get updated their lists of upper and lower neighbors. Let c = hA, Bi be an arbitrary non-stable concept from B(I) (c ∈ [γI (x0 ), µI (y0 )]). – If c = c , c = c , then c will “split” into d1 ≤ d2 . - We set d1 = c and d2 = c . - The concept d1 will be a lower neighbor of d2 . - If for a lower neighbor cl of c it holds cl = cl  , cl 6= cl , then it will be a lower neighbor of d2 . It is necessary to check whether d1 and cl will be neighbors. It certainly holds cl ≤ d1 , but there can be a concept k, such that cl ≤ k ≤ d1 . - Dually for upper neighbors. - If for a non-stable neighbor cn of c it holds cn = cn  , cn = cn , i.e., the same conditions as for c (cn will split into dn1 , dn2 ), then d1 , dn1 and d2 , dn2 will be neighbors. - All other upper (resp. lower) neighbors will be neighbors of d2 (resp. d1 ). – If c = c and c 6= c , then c will lose y0 from its intent. - Denote the transformed c as d = hC, Di = c = hA, B \ {y0 }i. - If for an upper neighbor cu it holds cu = cu , cu 6= cu  (cu will lose x0 from its extent), then cu and d will become incomparable. It is necessary to check whether c , cu and c, cu  should be neighbors (again, there can be a concept between them). – If c 6= c and c = c , then c will lose x0 from its extent. - Denote transformed c as d = hC, Di = c = hA \ {x0 }, Bi. – If c 6= c and c 6= c , then c will vanish entirely. - It is necessary to check whether c and c should be neighbors (again, a concept can lie between them). - Denote by U the set of all upper neighbors of c, except for c . There is no fixed point of  among the elements from U . - Denote by L the set of all lower neighbors of c, except for c . - Concepts from U and L will not be neighbors. Concepts will either become incomparable or one of them or both will vanish. There is also no need for additional checks regarding neighbor- hood relationship between concepts from U and c (resp. L and c ) or their neighbors. - It holds ∀cl ∈ L : cl ≤ c ≤ c , but it is necessary to check if there is a concept between them. - Similarly, it holds ∀cu ∈ U : c ≤ c ≤ cu , but again it is necessary to check if there is a concept between them. The number of iterations in TransformConceptLattice is at most |B(I)|, which occurs when each concept in B(I) is non-stable. In each of the iterations, tests c = c and c = c are performed and one of the procedures Split- Concept, RelinkReducedIntent, UnlinkVanishedConcept is called. It can be easily seen that the tests can be performed quite efficiently and do not add to the time complexity. The most time consuming among the above three procedures is SplitCon- cept. It iterates through all upper (which can be bounded by |X|) and lower (which can be bounded by |Y |) neighbors of the concept c. For each of the neighbors it might be necessary to check if the interval between the neighbor and certain other concept is empty (and we should make a new edge). This can be done by checking intents/extents of its neighbors. The above considerations lead to the result that time complexity of Algorithm 2 is in the worst case O(|B| · |X|2 · |Y |). Example 2. In Fig. 2, we can see some examples of transformations of non-stable concepts from B(I) into concepts of B(J). In Algorithm 2 we will assume that following functions are already defined: – U pperN eighbors(c) - returns upper neighbors of c; – LowerN eighbors(c) - returns lower neighbors of c; – Link(c1 , c2 ) - introduces neighborhood relationship between c1 and c2 ; – U nlink(c1 , c2 ) - cancels neighborhood relationship between c1 and c2 . Algorithm 2 Transforming B(I) with structural information into B(J). procedure LinkIfNeeded(c1 , c2 ) if @k ∈ B(I) : c1 < k < c2 then Link(c1 , c2 ); end if end procedure procedure SplitConcept(c ∈ [γI (x0 ), µI (y0 )]) d1 = c ; d2 = c ; Link(d1 , d2 ); for all u ∈ U pperN eighbors(c) do U nlink(c, u); Link(d2 , u); end for for all l ∈ LowerN eighbors(c) do U nlink(l, c); Link(l, d1 ); end for for all u ∈ U pperN eighbors(c) do if u 6= u then U nlink(d2 , u); Link(d1 , u); LinkIf N eeded(d2 , u ); end if end for for all l = hC, Di ∈ LowerN eighbors(c) do if y0 ∈/ D then U nlink(l, d1 ); Link(l, d2 ); LinkIf N eeded(l , d1 ); end if end for return d1 , d2 ; end procedure procedure RelinkReducedIntent(c ∈ [γI (x0 ), µI (y0 )]) for all u = hC, Di ∈ U pperN eighbors(c) do if u 6= u then U nlink(c, u); LinkIf N eeded(c , u); LinkIf N eeded(c, u ); end if end for end procedure procedure UnlinkVanishedConcept(c ∈ [γI (x0 ), µI (y0 )]) for all u ∈ U pperN eighbors(c) do U nlink(c, u); LinkIf N eeded(c , u); end for for all l ∈ LowerN eighbors(c) do U nlink(l, c); end for end procedure procedure TransformConceptLattice(B(I)) for all c = hA, Bi ∈ [γI (x0 ), µI (y0 )] from least to largest w.r.t. v do if c = c and c = c then . Concept will split. B(I) ← B(I) \ {c}; B(I) ← B(I) ∪ SplitConcept(c); else if c 6= c and c = c then . Extent will be smaller. A ← A \ {x0 }; else if c = c and c 6= c then . Intent will be smaller. RelinkReducedIntent(c); B ← B \ {y0 }; else if c 6= c and c 6= c then . Concept will vanish. B(I) ← B(I) \ {c}; U nlinkV anishedConcept(c); end if end for end procedure cu  cu  cu   cu = cu cu cu = cu cu c c = c = c cu cl c cl cl = cl  cl = cl  cl cl cl cl (a) Concepts become incomparable. (b) Concept in middle “splits into two”. c cu = cu c cu c cu = cu c cu c c c cl = cl  c cl c cl = cl  c cl (c) Concept in the middle vanishes. (d) Concept in the middle vanishes. There is already another concept be- tween its children. Fig. 2: Examples of transformations of non-stable concepts from B(I) into con- cepts of B(J). 6 Conclusion We analyzed changes of the structure of a concept lattice, caused by removal of exactly one incidence from the associated formal context. We proved some theoretical results and presented two algorithms with time complexities O(|B| · |X| · |Y |) (Algorithm 1; without structure information) and O(|B| · |X|2 · |Y |) (Algorithm 2; with structure information). There exist several algorithms for incremental computation of concept lattice [1, 5, 8, 6, 7, 2], based on addition and/or removal of objects. Our approach is new in that we recompute a concept lattice based on a removal of just one incidence. Note that the algorithm proposed by Nourine and Raynaud in [7] has time complexity O((|Y | + |X|) · |X| · |B|), which is better than complexity of our Algorithm 2. However, experiments presented in [5] indicate that this algorithm sometimes performs slower than some algorithms with time complexity O(|B| · |X|2 ·|Y |). In the case of our Algorithm 2, some preliminary experiments indicate that the size of the interval of non-stable concepts is usually relatively small, which substantially reduces the overall processing time of the algorithm. A natural next step would be investigate adding incidences to a formal con- text, instead of removing. This problem, however, seems to be more difficult than the first one, namely because the set of non-stable concepts in the lattice B(J) has more complicated structure (it is not an interval) and also because not all non-stable concepts in B(I) can be computed via the operator  . We will try to address this issues in the future. We will also focus on the following: – experimenting with proposed algorithms on various datasets and comparing them with other known algorithms, – generalizing the results to allow removing and adding more incidences at the same time. References 1. Carpineto, C., Romano, G.: Concept Data Analysis: Theory and Applications. John Wiley & Sons (2004) 2. Dowling, C.E.: On the irredundant generation of knowledge spaces. J. Math. Psy- chol. 37(1), 49–62 (1993) 3. Ganter, B., Wille, R.: Formal Concept Analysis – Mathematical Foundations. Springer (1999) 4. Kuznetsov, S.O., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. Journal of Experimental and Theoretical Artificial Intelligence 14, 189–216 (2002) 5. Merwe, D., Obiedkov, S., Kourie, D.: Addintent: A new incremental algorithm for constructing concept lattices. In: Eklund, P. (ed.) Concept Lattices, Lecture Notes in Computer Science, vol. 2961, pp. 372–385. Springer Berlin Heidelberg (2004) 6. Norris, E.M.: An algorithm for computing the maximal rectangles in a binary rela- tion. Revue Roumaine de Mathématiques Pures et Appliquées 23(2), 243–250 (1978) 7. Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inf. Process. Lett. 71(5-6), 199–204 (1999) 8. Outrata, J.: A lattice-free concept lattice update algorithm based on *CbO. In: Ojeda-Aciego, M., Outrata, J. (eds.) CLA. CEUR Workshop Proceedings, vol. 1062, pp. 261–274. CEUR-WS.org (2013) 9. Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts. In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Boston (1982)