Computing minimal generators from implications: a logic-guided approach P. Cordero, M. Enciso, A. Mora, M Ojeda-Aciego⋆ Universidad de Málaga. Spain. pcordero@uma.es, enciso@lcc.uma.es, amora@ctima.uma.es, aciego@uma.es Abstract. Sets of attribute implications may have a certain degree of redundancy and the notion of basis appears as a way to characterize the implication set with less redundancy. The most widely accepted is the Duquenne-Guigues basis, strongly based on the notion of pseudo-intents. In this work we propose the minimal generators as an element to remove redundancy in the basis. The main problem is to enumerate all the minimal generators from a set of implications. We introduce a method to compute all the minimal generators which is based on the Simplification Rule for implications. The simplification paradigm allows us to remove redundancy in the im- plications by deleting attributes inside the implication without removing the whole implication itself. In this work, the application of the Simpli- fication Rule to the set of implications guides the search of the minimal generators in a logic-based style, providing a deterministic approach. 1 Introduction A concept is a general idea that corresponds to some kind of entities and that may be characterized by some essential features of the class. When Wille [18] conceived Formal Concept Analysis (FCA), he probably did not foresee the wide diffusion of his original idea, both in the theoretical and in the applied areas. Application areas of FCA ranges from data analysis, information retrieval, or data mining to knowledge representation or the semantic web. The main goal of Formal Concept Analysis is to identify the relationships between sets of objects and sets of attributes from information in a binary table. These relationships establish a Galois connection which allows us to identify the concepts by using lattice theory. The construction of the lattice of concepts is known to be a hard problem due to its exponential complexity. For this task, probably the most cited method is the NEXTCLOSURE algorithm developed by Ganter [5]. Apart from building the concept lattice itself, one of the key problems is to extract the set of attribute implications which hold in the concept lattice. In ⋆ Supported by grants P09-FQM-5233 of the Junta de Andalucı́a, and TIN09-14562- C05-01 and TIN2011-28084 of the Science and Innovation Ministry of Spain, co- funded by the European Regional Development Fund (ERDF). c 2012 by the paper authors. CLA 2012, pp. 187–198. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors. Local Proceedings in ISBN 978–84–695–5252–0, Universidad de Málaga (Dept. Matemática Aplicada), Spain. 188 P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego real applications the size of the concept lattice is usually huge and is impossible for the user to visualize it. Belohlavek and Vychodil developed [1] a method of expressing implications by means of closure operators. The main effect is to filter-out outputs to the user. The study of implications allowed those authors to reduce the number of formal concepts extracted from the input data: “Using background knowledge thus enables a focused extraction of knowledge and may considerably reduce the amount of information presented to the user” [2]. The problem arises when the set of implications has a high degree of re- dundancy: by the existence of redundant implications or redundant attributes inside the implications. One desired goal in this area is to remove redundancy and obtain a minimal basis. The most widely approach comes from the notion of Duquenne-Guigues Basis [6] also called stem base. This basis is minimal w.r.t. the number of implications, i.e. if one of the implications is removed from the basis, there are non-redundant implications which are valid in the dataset and cannot be inferred, using the Armstrong’s Axioms, from the new reduced basis. Nevertheless, this notion of minimality and its associated redundancy may be improved. To illustrate this assertion, we present here an example appeared in [5, pp. 30 and 84] where Ganter presents a context of developing countries. In the example, 130 countries and six attributes are considered: Group of 77, Non-aligned, LLDC (Least Developed Countries), MASC (Most Seriously Af- fected Countries), OPEC (Organization of Petrol Exporting Countries) and ACP (African, Caribbean and Pacific Countries). Ganter builds the concept lattice from this context and provides the following Duquenne-Guigues basis: OPEC → Group 77, Non-aligned MASC → Group 77 Non-aligned → Group of 77 Group 77, Non-aligned, MASC, OPEC → LLDC, ACP Group 77, Non-aligned, LLDC, OPEC → MASC, ACP Note, however, that in the last two implications, there still exist redundant attributes in the left hand side, whereas in the first and in the last implications the redundancy appears in the right hand sides. This implies that it is possible to provide an equivalent and simpler set of implications: OPEC → Non-aligned MASC → Group 77 Non-aligned → Group of 77 MASC, OPEC → LLDC, ACP LLDC, OPEC → MASC Thus, we have an example in which the Duquenne-Guigues basis still can contain redundant information. In order to obtain the latter basis it is necessary to consider minimal generators instead of pseudo-intents. Implications define a closure system, and for this reason, a closure system can be replaced by their equivalent implications. The relationship between closed sets and implications are the key of the attribute exploration techniques [8, 13]. In [12] we introduced a closure algorithm strongly based on the simplification logic [3]. Here, our closure operator is used to guide the search of all the minimal generators of the closed sets corresponding to a given set of implications. Methods for obtaining generators of closed sets have been studied in [4,10,17]. Minimal generators [14–16] appear in the literature under different names in Computing MGs from implications: a logic-guided approach 189 various fields. For instance, in relational databases they are called minimal keys. In [17], the authors emphasize the importance of studying minimal generators although “they have been paid little attention so far in the FCA literature”. We would like to provide, in a further step, an alternative definition of ba- sis built around the notion of minimal generator, since our goal is to avoid redundancy inside the implications, instead of just minimizing the number of implications. As a preliminary step, we have to design a method to enumerate all the minimal generators and their corresponding closed sets. This paper is structured in the following way: in Section 2 some preliminaries about formal concept analysis and the Simplification paradigm are presented. In Section 3 a method to enumerate all the minimal generators from an implication set is introduced and in subsection 3.2 the algorithm is modified to compute the non-trivial minimal generators. The paper ends with a section on conclusions and prospects for future work. 2 Preliminaries 2.1 Formal Concept Analysis Intuitively, Formal Concept Analysis (FCA) provides methods to describe the relationship between a set of objects and a set of attributes. A formal context is a triple K := (G, M, I) where G is a set of objects, M is a set of attributes and I ⊆ G × M is a binary relation between G and M such that, for o ∈ G and a ∈ M , o I a means that the object o has the attribute a. From this triple two mappings can be defined. One of them ( )′ : 2G → 2M is defined for all A ⊆ G as A′ = {m ∈ M | g I m for all g ∈ A}. The other one, ( )′ : 2M → 2G is defined for all B ⊆ M as B ′ = {g ∈ G | g I m for all m ∈ B}. Both mappings are denoted by the same symbol because no confusion arises. This pair of mappings is a Galois connection and both are antitone mappings (A1 ⊆ A2 implies A′2 ⊆ A′1 for all A1 , A2 ⊆ G, and, for all B1 , B2 ⊆ M , if B1 ⊆ B2 then B2′ ⊆ B1′ ) The composition of the intent and the extent mappings, and vice versa, give us two closure operators ( )′′ : 2G → 2G and ( )′′ : 2M → 2M . That is, both are extensive (X ⊆ X ′′ ), idempotent ((X ′′ )′′ = X ′′ ) and isotone (if X1 ⊆ X2 then X1′′ ⊆ X2′′ ). In order to make this work self-contained, the notion of closed set (as a fixpoint of a closure operator) is defined below: Definition 1. A formal concept is a pair (A, B) such that A ⊆ G, B ⊆ M , A′ = B and B ′ = A. Consequently, A and B are closed sets of objects and attributes, respectively called extent and intent. It is well-known that the set of formal concepts is a complete lattice, the con- cept lattice associated to the context, with the following partial ordering is considered: (A1 , B1 ) ≤ (A2 , B2 ) if and only if A1 ⊆ A2 (or equivalently B1 ⊇ B2 ) Related to the notion of closed set, the minimal generator (mingen) and implication are defined as follows: 190 P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego Definition 2. Let K = (G, M, I) be a formal context and A ⊆ M . The set of attributes A is said to be a minimal generator (mingen) if, for all set of attributes X ⊆ A if X ′′ = A′′ then X = A. Attribute implication allows us to capture all the information which can be deduced from a context. They are expressions A → B being A and B sets of attributes. A context satisfies the implication A → B if every object that has all the attributes from A also has all the attributes from B. Definition 3. An (attribute) implication of a formal context K = (G, M, I) is defined as a pair (A, B), written A → B, where A, B ⊆ M . Implication A → B holds (is valid) in K if A′ ⊆ B ′ . The set of all valid implications in a context satisfies the well-known Arm- strong’s axioms: A⊇B A→B A→B, B→C [Ref] , [Augm] , [Trans] A→B A ∪ C→B ∪ C A→C An implication basis of K is defined as a set L of implications of K from which any valid implication for K can be deduced by using Armstrong rules. The goal is to obtain a implication basis with minimal size. This condition is satisfied by the so-called Duquenne-Guigues basis [6] or stem basis, which is built over the set of the pseudo-intents [5]. As we have illustrated in the introduction, the definition of the Duquenne- Guigues basis refers to minimality only in the size of the set of implicants, but redundant attributes use to appear in this kind of minimal basis. This situation comes from the use of pseudo-intents in the construction of the basis. To avoid redundant attributes, we propose to consider minimal generators in the left hand side of the implications. In this work we do not provide such alternative definition of minimal basis, but focus on the problem of enumerating all the minimal generators. This is the main goal of Section 3, but before we need to recall the basics of the simplification logic. 2.2 Simplification logic and closures Armstrong’s axiom system has influenced the design of several logics for func- tional dependencies [9,11], all of them built around the transitivity paradigm. In this section, we summarize the axiom system of Simplification Logic for Func- tional Dependencies SLF D . It avoids the use of transitivity and is guided by the idea of simplifying the set of functional dependencies by efficiently removing some redundant attributes [3]. To begin with, SLF D logic considers reflexivity as axiom scheme A⊇B [Ref] A→B together with the following inference rules called fragmentation, composition and simplification respectively. Computing MGs from implications: a logic-guided approach 191 A→B ∪ C A→B, C→D A→B, C→D [Frag] [Comp] [Simp] A→B A ∪ C→B ∪ D A ∪ (C r B)→D The equivalence between SLF D logic and Armstrong’s Axioms and an ef- ficient algorithm to compute the closure of a set of attributes were proposed in [12]. We have also conducted a comparison to other closure algorithms in the literature in order to prove the better performance of our logic-based system. The main advantage of SLF D is that inference rules can be considered as equiva- lence rules, and that is enough to compute all the derivations (see [12] for further details). Proposition 1. Let A, B, C, D sets of attributes. In SLF D logic, the following equivalences hold: 1. {A→B} ≡ {A→B r A} 2. {A→B, A→C} ≡ {A→B ∪ C} 3. A ∩ B = ∅ and A ⊆ C imply {A→B, C→D} ≡ {A→B, C r B→D r B} It is well-known that, given a basis of a context, the closure of attribute sets ′′ defined based on Armstrong’s axioms coincides with the closure () : 2M → 2M . On the other hand, Armstrong’s axioms and the axiom system in SLF D logic are equivalent. Definition 4. Let Γ be a set of implications and A be a set of attributes. The closure of A in SLF D logic is defined as the maximum set of attributes A+ such that Γ ⊢ A→A+ . Theorem 1. Let K = (G, M, I) a formal context and Γ a basis for K. For all A ⊆ M , the equality A+ = A′′ holds. As we have said, in [12] we present a novel algorithm to compute closures using SLF D Logic. The formula ∅→A is used as a seed by the reasoning method to render the closure A+ of A (which coincides with A′′ ) just by applying some operators based on the [Simp] inference rule. The algorithm is based on the following results: Theorem 2. Let A and B be sets of attributes and Γ be a set of implications. Γ ⊢ A→B if and only if {∅→A} ∪ Γ ⊢ {∅→B} The closure algorithm is based on the previous theorem and the systematic application of the following equivalences which are direct consequences of the simplification equivalence (item 3 in Proposition 1). Proposition 2. Let A, B and C be sets of attributes, then the following equiv- alences hold: – Eq. I: If B ⊆ A then {∅→A, B→C} ≡ {∅→A ∪ C}. – Eq. II: If C ⊆ A then {∅→A, B→C} ≡ {∅→A}. – Eq. III: Otherwise {∅→A, B→C} ≡ {∅→A, B r A→C r A}. 192 P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego Given a set of implications Γ and a set of attributes A, the execution of the SLF D closure method begins with the construction of the guide ∅→A. The three equivalences are systematically applied to Γ , which produces a growth of the guide. When none of the three equivalences can be applied, in the guide we have the closure. Method 1 Let Γ be a set of implications and A a subset of attributes. The following method computes the closure A+ of the set A w.r.t. Γ : 1. Build the guide as follows {∅→A} 2. While there exist B→C ∈ Γ such that A ∩ B 6= ∅ or A ∩ C 6= ∅ (being {∅→A} the guide in this state of the execution), execute the corresponding equivalence: – If B ⊆ A then remove B→C from Γ and change the guide {∅→A} by {∅→A ∪ C}. – If C ⊆ A then remove B→C from Γ . – Otherwise substitute B→C by B r A→C r A in Γ . 3. If {∅→A} is the guide (in this state) then return A. Example 1. Let Γ = {ab→c, bc→d, de→f, ce→f } and A = de. The following table summarizes the execution of Method 1 to compute A+ = def . Guide Γ ∅→de ab→c bc→d de→f ce→f ∅→de ab→c bc→6 d 6 d6 e→f c6 e→f ∅→def ab→c c→6 f ∅→def ab→c The new closure operator was proven to be faster than other closure algo- rithms [12]. Finally, it is possible to define a modification of the closure algorithm to return not only the closure but also the resulting set Γ . This algorithm will be denoted by Cls. So, considering the previous example, Cls(de, {ab→c, bc→d, de→f, ce→f }) = (def, {ab→c}) 3 Computing all mingens from a basis In this section, we present how the Simplification paradigm can be considered as a powerful tool to guide the search of all minimal generator sets. In the first method we present here, we will compute mingens (the set of all minimal generators) from a set of implicant set. The algorithm works by applying the SLF D Closure algorithm to the set of implications. This application provides a new candidate to be added to mingen and a smaller implications set which guides us in the search of new sets of attributes to be added to mingens. The input of this algorithm is a set of attributes M and a set of implications Γ over the attributes in M . The output is the set of closed sets endowed with all the mingens that generate them, i.e. Computing MGs from implications: a logic-guided approach 193 {hC, mg(C)i : C is a closed set of attributes} where mg(C) = {D : D is a mingen and D+ = C}. For example, if M = {a, b, c} and Γ = {a→b, b→a} the output must be {habc, {ac, bc}i, hab, {a, b}i, hc, {c}i, h∅, {∅}i} It can be seen as the concept lattice in which we have added labels with the mingens to each closed set. With this idea we are going to need operators that allow us to work with this kind of sets, i.e. sets of pairs hA, Bi such that A ⊆ M is an intent and B ⊆ 2M satisfies the following conditions: 1. X ⊆ A for all X ∈ B. 2. X, Y ∈ B and X ⊆ Y imply X = Y . This kind of sets are called labeled set of intents (LSI). Given two LSIs Φ and Ψ , we define the join of both, Φ ⊔ Ψ , as the the minimum LSI that satisfies: – If hA1 , B1 i ∈ Φ and A1 6= A2 for all hA2 , B2 i ∈ Ψ then hA1 , B1 i ∈ Φ ⊔ Ψ – If hA1 , B1 i ∈ Ψ and A1 6= A2 for all hA2 , B2 i ∈ Φ then hA1 , B1 i ∈ Φ ⊔ Ψ – If hA, B1 i ∈ Ψ and hA, B2 i ∈ Φ then hA, B3 i ∈ Φ ⊔ Ψ being B3 the set of minimal elements of B1 ∪ B2 . We define an operator, the trivial operator, that given M and Γ returns the following LSI: trv(M, Γ ) = {hX, {X}i : X ⊆ M with A 6⊆ X for all A→B ∈ Γ } For example, trv({a, b, c}, {a→b, b→a}) = {hc, {c}i, h∅, {∅}i}. We will also need a way to add a pair to an LSI; it is defined as follows: Add(hC, {D}i, Φ) = {hA ∪ C, {X ∪ D : X ∈ B}i : hA, Bi ∈ Φ} For example, Add(hab, {a}i, {hc, {c}i, h∅, {∅}i}) = {habc, {ac}i, hab, {a}i} Add(hc, {c}i, {hab, {a, b}i, h∅, {∅}i}) = {habc, {ac, bc}i, hc, {c}i} 3.1 MinGen Algorithm We already have all the tools needed to define the algorithm, which is introduced below, together with an illustrative example of its application. Example 2. We want to compute MinGen({a, b, c, d}, {a→b, c→bd, bd→ac}) Step 1. Φ = trv({a, b, c, d}, {a→b, c→bd, bd→ac} = = {hb, {b}i, hd, {d}i, h∅, {∅}i} 194 P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego Algorithm 1: MinGen Data: M, Γ Result: Φ begin if Γ = ∅ then Φ = trv(M, Γ ) else Let Φ = trv(M, Γ ); foreach A→B ∈ Γ do Let (A+ , Γ ′ ) = Cls(A, Γ ); Let Φ := Φ ⊔ Add(hA+ , {A}i, MinGen(M r A+ , Γ ′ ); Return Φ Step 2. Considering a→b ∈ Γ , ∅→a a→b c→bd bd→ac Cls(a, Γ ) = (ab, {c→d, d→c}) ∅→a 6 a→b c→bd bd→6 ac ∅→ab c→6 bd 6 bd→c and call to MinGen({c, d}, {c→d, d→c}) Step 2.1. This label (2.1) points that we have passed to a lower level, i.e. we have made a recursive call to the procedure. Φ1 = trv({c, d}, {c→d, d→c} = {h∅, {∅}i} Step 2.2. Considering c→d ∈ Γ1 , ∅→c c→d d→c Cls(c, Γ1 ) = (cd, ∅) ∅→c 6 c→d d→6 c ∅→cd and MinGen(∅, ∅) = {h∅, {∅}i}. And so Φ1 = {h∅, {∅}i} ⊔ Add(hcd, {c}i, {h∅, {∅}i}) = {hcd, {c}i, h∅, {∅}i} Step 2.3. Considering d→c ∈ Γ1 , ∅→d c→d d→c Cls(d, Γ1 ) = (cd, ∅) ∅→d c→6 d 6 d→c ∅→cd and MinGen(∅, ∅) = {h∅, {∅}i}. And so Φ1 = {hcd, {c}i, h∅, {∅}i} ⊔ Add(hcd, {d}i, {h∅, {∅}i}) = {hcd, {c, d}i, h∅, {∅}i} Returning to the higher level, Φ = {hb, {b}i, hd, {d}i, h∅, {∅}i} ⊔ Add(hab, {a}i, {hcd, {c, d}i, h∅, {∅}i}) = {habcd, {ac, ad}i, hab, {a}i, hb, {b}i, hd, {d}i, h∅, {∅}i} Step 3. Considering c→bd ∈ Γ , ∅→c a→b c→bd bd→ac Cls(bc, Γ ) = (abcd, ∅) ∅→c a→b 6 c→bd bd→a6 c ∅→bcd a→6 b 6 b6 d→a and MinGen(∅, ∅) = {h∅, {∅}i}. ∅→abcd Φ = {habcd, {ac, ad}i, hab, {a}ihb, {b}i, hd, {d}i, h∅, {∅}i} ⊔ Add(habcd, {c}i, {h∅, {∅}i}) = {habcd, {c, ad}i, hab, {a}i, hb, {b}i, hd, {d}i, h∅, {∅}i} Computing MGs from implications: a logic-guided approach 195 Note that {habcd, {ac, ad}i} ⊔ {habcd, {c}i} = {habcd, {c, ad}i}. Step 4. Considering bd→ac ∈ Γ , ∅→bd a→b c→bd bd→ac Cls(bd, Γ ) = (abcd, ∅) ∅→bd a→6 b c→6 b6 d 6 b6 d→ac and MinGen(∅, ∅) = {h∅, {∅}i}. ∅→abcd Φ = {habcd, {c, ad}i, hab, {a}i, hb, {b}i, hd, {d}i, h∅, {∅}i} ⊔ Add(habcd, {bd}i, {h∅, {∅}i}) = {habcd, {c, ad, bd}i, hab, {a}ihb, {b}i, hd, {d}i, h∅, {∅}i} Finally, the algorithm returns {habcd, {c, ad, bd}i, hab, {a}ihb, {b}i, hd, {d}i, h∅, {∅}i} 3.2 Non-trivial minimal generators. Notice that the first method we have just introduced computes all minimal generators, including trivial mingens with non-relevant information. In this subsection, we slightly modify the previous algoritm to produce only the relevant information (not trivial mingens), by considering that trv(M, Γ ) returns always only {h∅, {∅}i}. This new algorithm is called L MinGen0 . Fig. 1. SLF D guides the construction of the MinGen set 196 P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego Example 3. We want L to compute MinGen0 ({a, b, c, d, e, f }, {a→b, bc→d, de→f, ace→f }) The full execution of the method MinGen0 is depicted in Figure 1. In Figure 2 we show the lattice of closed sets built with the non-trivial mingens provided by MinGen0 . Fig. 2. Lattice of minimal generators Step 1. Φ = {h∅, {∅}i} Step 2. Considering a→b ∈ Γ , compute Cls(a, Γ ) = (ab, {c→d, de→f, ce→f }) Now we compute MinGen0 ({c, d, e, f }, {c→d, de→f, ce→f }) Step 2.1. Φ1 = {h∅, {∅}i} Step 2.2. Considering c→d ∈ Γ ′ , compute Cls(c, Γ ) = (cd, {e→f }). Now we are going to compute MinGen0 ({e, f }, {e→f }). Step 2.2.1 Φ1.1 = {h∅, {∅}i} Step 2.2.2 Considering e→f ∈ Γ ′′ , Cls(e, Γ ′′ ) = (ef, ∅). And so Φ1.1 = {h∅, {∅}i} ⊔ Add(hef, {e}i, {h∅, {∅}i}) = {hef, {e}i, h∅, {∅}i} Returning to the higher level, Φ1 = {h∅, {∅}i} ⊔ Add(hcd, {c}i, {hef, {e}i, h∅, {∅}i}) = {hcdef, {ce}i, hcd, {c}i, h∅, {∅}i} Step 2.3. Considering de→f ∈ Γ ′ , Cls(de, Γ ) = (def, ∅). Moreover, MinGen0 ({c}, ∅) = {h∅, {∅}i} Φ1 = {hcdef, {ce}i, hcd, {c}i, h∅, {∅}i} ⊔ Add(hdef, {de}i, {h∅, {∅}i}) = {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i} Step 2.4. Considering ce→f ∈ Γ ′ , compute Cls(ce, Γ ) = (cdef, ∅). Moreover MinGen0 (∅, ∅) = {h∅, {∅}i} Φ1 = {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i} ⊔ Add(hcdef, {ce}i, {h∅, {∅}i}) = {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i} Computing MGs from implications: a logic-guided approach 197 Returning to the high level, Φ = {h∅, {∅}i} ⊔ Add(hab, {a}i, {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i}) = {habcdef, {ace}i, habdef, {ade}i, habcd, {ac}i, hab, {a}i, h∅, {∅}i} Step 3. Considering bc→d ∈ Γ , Cls(bc, Γ ) = (bcd, {e→f, ae→f }). Now we compute MinGen0 ({a, e, f }, {e→f, ae→f }). Step 3.1. Φ2 = {h∅, {∅}i} Step 3.2. Considering e→f ∈ Γ ′ , compute Cls(e, Γ ) = (ef, ∅) and MinGen0 ({a}, ∅) = {h∅, {∅}i} Φ2 = {h∅, {∅}i} ⊔ Add(hef, {e}i, {h∅, {∅}i}) = {hef, {e}i, h∅, {∅}i} Step 3.3. Considering ae→f ∈ Γ ′ , Cls(ae, Γ ) = (aef, ∅). Moreover MinGen0 (∅, ∅) = {h∅, {∅}i} Φ2 = {hef, {e}i, h∅, {∅}i} ⊔ Add(haef, {ae}i, {h∅, {∅}i}) = {haef, {ae}i, hef, {e}i, h∅, {∅}i} Returning to the high level, Φ = {habcdef, {ace}i, habdef, {ade}i, habcd, {ac}i, hab, {a}i, h∅, {∅}i} ⊔Add(hbcd, {bc}i, {haef, {ae}i, hef, {e}i, h∅, {∅}i}) = {habcdef, {ace}i, habdef, {ade}i, habcd, {ac}i, hab, {a}i, h∅, {∅}i} ⊔{habcdef, {abce}i, hbcdef, {bce}i, hbcd, {bc}i} ={habcdef, {ace}i, habdef, {ade}i, hbcdef, {bce}i, habcd, {ac}i, hbcd, {bc}i, hab, {a}i, h∅, {∅}i} Notice that the last application of the ⊔ operator does not add the set {abce} to mingen because it produces the same closed set than {ace}. Thus, in Figure 1 this leaf appears with gray color. Step 4. Considering de→f ∈ Γ , renders Φ = {habcdef, {ace}i, habdef, {ade}i, hbcdef, {bce}i, habcd, {ac}i, hbcd, {bc}i, hdef, {de}i, hab, {a}i, h∅, {∅}i} Step 5. Considering ace→f ∈ Γ , renders Φ = {habcdef, {ace}i, habdef, {ade}i, hbcdef, {bce}i, habcd, {ac}i, hbcd, {bc}i, hdef, {de}i, hab, {a}i, h∅, {∅}i} 4 Conclusions and future works In this work we have proposed the minimal generators as a basic notion to remove redundancy in sets of implications. To achieve this goal, the first step is to design a method to compute all minimal generators corresponding to a set of implications. The simplification paradigm is the key to design the MinGen and MinGen0 algorithms. The application of SLF D closure algorithm guides the search of minimal generators. As future work we will present a thorough study about the soundness, com- pleteness, and complexity of the mingens algorithms, which have not been in- cluded here due to space limitations; moreover, a definition of basis center within the notion of minimal generators will be studied, together with a method to com- pute such a basis. 198 P. Cordero, M. Enciso, A. Mora and M. Ojeda-Aciego References 1. R. Belohlavek and V. Vychodil, Formal Concept Analysis with Constraints by Closure Operators, LNCS, 4068: 131–143, 2006. 2. R. Belohlavek and V. Vychodil, Formal Concept Analysis with Background Knowl- edge: Attribute Priorities. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 39: 399–409, 2009. 3. P. Cordero, M. Enciso, A. Mora, I.P, de Guzmán: SLFD logic: Elimination of data redundancy in knowledge representation, LNCS 2527: 141–150, 2002. 4. C. Frambourg, P. Valtchev, and R. Godin, Merge-based computation of minimal generators. Discrete Mathematics, LNCS 3596: 181–194, 2005. 5. B. Ganter, Two basic algorithms in concept analysis. Technische Hochschule, Darmstadt, 1984. 6. J.L. Guigues and V. Duquenne, Familles minimales d’implications informatives résultant d’un tableau de données binaires. Math. Sci. Humaines, 95, 5–18, 1986. 7. M. Hermann and B. Sertkaya, On the Complexity of Computing Generators of Closed Sets. ICFCA 2008: 158–168 8. S. O. Kuznetsov and A. Revenko, Attribute Exploration of Properties of Functions on Sets. Fundamenta Informaticae, 115 (4): 377–394, 2012. 9. C. Beeri, and R. Fagin and J.H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proc. ACM SIGMOD Conf., pp. 47-61, 1977. 10. A. Day, The lattice theory of functional dependencies and normal decompositions, International Journal of Algebra and Computation, 2: pp. 209–431, 1990. 11. R. Fagin, Functional dependencies in a relational database and propositional logic, IBM. Journal of research and development, 21 (6), (1977), pp. 534–544. 12. A. Mora, P. Cordero, M. Enciso, I.Fortes, Closure via functional dependence sim- plification, International Journal of Computer Mathematics, 89(4): 510–526, 2012. 13. G. Stumme, Attribute Exploration with Background Implications and Exceptions. Data Analysis and Information Systems. Statistical and Conceptual approaches. Proc. GfKl’95. Studies in Classification, Data Analysis, and Knowledge Organiza- tion 7: 457–469, 1996. 14. L. Szathmary and A. Napoli and S. O. Kuznetsov, ZART: A Multifunctional Item- set Mining Algorithm , Proc. of the 6th Intl. Conf. on Concept Lattices and Their Applications (CLA ’08): 47–58, 2008. 15. L. Szathmary and P. Valtchev and A. Napoli and R. Godin, An Efficient Hybrid Algorithm for Mining Frequent Closures and Generators, Proc. of the 5th Intl. Conf. on Concept Lattices and Their Applications (CLA ’07): 26–37, 2007. 16. L. Szathmary and P. Valtchev and A. Napoli and R. Godin, Efficient Vertical Mining of Frequent Closures and Generators, LNCS 5772: 393–404, 2009. 17. K. Nehmé, P. Valtchev, M. H. Rouane, R. Godin, On Computing the Minimal Generator Family for Concept Lattices and Icebergs, LNCS 3403: 192–207, 2005. 18. R. Wille, Restructuring lattice theory: an approach based on hierarchies of con- cepts. In I. Rival (ed.), Ordered sets, pp. 445-470, 1982.