Depth-first Search for Pseudo-intents through Minimal Transversals Alexandre Bazin contact@alexandrebazin.com Abstract. The enumeration of pseudo-intents is a long-standing prob- lem in which the order plays a major role. In this paper, we present new algorithms that enumerate pseudo-intents in orders that do not necessar- ily respect the inclusion relation. We show that, confirming established results, this enumeration is equivalent to computing minimal transversals in hypergraphs a bounded number of times. 1 Introduction Formal concept analysis, as a field of applied mathematics, is interested in the patterns that can be found in data taking the form of a set of objects described by attributes. Among these patterns are the implications, relations between at- tribute sets A and B representing the fact that every object described by A is also described by B. As often with this type of relation, interest revolves around a small, non redundant set of implications. Such a set, the Duquenne-Guigues basis, is constructed using the notion of pseudo-intent. Indeed, computing the Duquenne-Guigues basis, and thus all the implications in a data set, is equiva- lent to enumerating all the pseudo-intents. In [15], it is shown that the number of pseudo-intents can be exponential in the number of attributes. It has been proven in [6, 2] that pseudo-intents cannot be enumerated with a polynomial delay in lectic or reverse lectic order. However, to the best of our knowledge, no such result exists for other orders. The best-known algorithm, Next Closure [11], enumerates only in the lectic order. In a previous work [4], we proposed an exponential delay algorithm to enumerate in any order that extends the inclu- sion order. In order to continue the study of the influence of the order on the complexity of this enumeration problem, we propose here two new algorithms that, together, can enumerate pseudo-intents without respecting the inclusion. Our algorithms enumerate pseudo-intents incrementally, i.e. given a formal context and a set of previously found implications, they return a new pseudo- intent. In order to do this, we define new conditions under which a pseudo-intent P can be recognized using the lower covers of P in the lattice of attribute sets closed under the implications already found. This allows us to build algorithms that, instead of starting from ∅ and adding attributes to construct sets, start from > and remove attributes, resulting in a depth-first search in the lattice. We show that both constructing and recognizing a pseudo-intent can be done c 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. Local Proceedings also appeared in ISBN 978-84-606-7410-8, Universidad de Málaga (Dept. Matemática Aplicada), Spain. 2 Alexandre Bazin by computing a bounded number of times the minimal transversals of some hypergraph, which makes it easy to bound the delay and isolate special, easier cases. This result establishes a link with the proof in [6] that enumerating pseudo- intents without order is at least as hard as computing minimal transversals. We start by recalling in Section 2 the basic definitions of FCA and results on the enumeration of pseudo-intents and minimal transversals. In Section 3, we present the definition of a recognizable pseudo-intent that we use along with the properties needed for our algorithms. Finally, Sections 4 and 5 are dedicated to the two algorithms, an example and a brief study of their delay. 2 Preliminaries 2.1 Basics In formal concept analysis, data takes the form of a formal context. A formal context is a triple C = (O, A, R) in which O is a set of objects, A is a set of attributes and R ⊆ O × A a relation that maps attributes to objects. An object o ∈ O is said to be described by an attribute a ∈ A if (o, a) ∈ R. Together with the context, there are two ·0 operators defined as ·0 : 2O 7→ 2A O0 = {a ∈ A | ∀o ∈ O, (o, a) ∈ R} ·0 : 2A 7→ 2O A0 = {o ∈ O | ∀a ∈ A, (o, a) ∈ R} Their composition ·00 is a closure operator. A set of attributes A = A00 closed under ·00 is called an intent. 2.2 Implications An implication is a relation between two attribute sets A and B, noted A → B. It is said to hold in the context if and only if A0 ⊆ B 0 or, in other words, if and only if every object described by A is also described by B. A set I of implications is a basis if and only if every implication that holds in the context can be derived from I using Armstrong’s rules : B⊆A A→B A → B, B → C , , A→B A∪C →B∪C A→C A pseudo-intent (or pseudo-closed set) P is a set of attributes that contains the closure of all its subsets and is not an intent. The set B = {P → P 00 | P Depth-first Search for Pseudo-intents through Minimal Transversals 3 Fig. 1. A formal context is a pseudo-intent} is the implication basis with the minimum cardinality and is called the Duquenne-Guigues basis [12]. As such, computing the Duquenne- Guigues basis, and thus all the implications, is enumerating all the pseudo- intents. As one of the great problems in FCA, it has been abundantly studied [12, 15, 6, 17, 4, 3, 16, 1, 19]. As the number of pseudo-intents can be exponential in the size of the context, preventing a polynomial algorithm, the attention is instead focused on the delay, i.e. the time between two pseudo-intents and the last pseudo-intent and the end of the algorithm. It has been shown that pseudo- intents cannot be enumerated with a polynomial delay in lectic [6] or reverse lectic order [2]. For the enumeration without order, it is shown in [6] that it is at least as hard as computing the minimal transversals of a hypergraph. However, the upper bound is not yet known. The problem of recognizing a pseudo-intent has been studied in [1] and found to be coNP-complete. 2.3 Logical Closures A set of implications I gives rises to a logical closure operator I(·) defined as A+ = A ∪ {C | B → C ∈ I and B ⊆ A} I(A) = A++...+ (up to saturation) Similarly, we have the logical pseudo-closure operator I − (·) defined as A◦ = A ∪ {C | B → C ∈ I and B ⊂ A} I − (A) = A◦◦...◦ (up to saturation) It is known that intents are closed under both B − (·) and B(·), whereas a pseudo-intent P is closed under B − (·) and I(·) for I ⊆ B \ {P → P 00 }. An attribute set Y is said to be a generator of an attribute set X under I(·) (resp. I − (·)) if I(Y ) = X (resp. I − (Y ) = X). It is a minimal generator 4 Alexandre Bazin Fig. 2. ΦI with I = {de → bde, be → bde} if there is no generator Z of X such that Z ⊂ Y . We will use GenI (X) to denote the set of all minimal generators of a set X under I(·). The complexity of computing the minimal generators of a set has been studied in [14]. The number of minimal generators can be exponential in the number of attributes and they can be enumerated with an incremental polynomial delay. We shall use ΦI to denote the lattice of attribute sets closed under I(·) ordered by the inclusion relation. For an attribute set A, the set of pseudo- intents P in I such that P ⊆ A and P 00 6⊆ A will be denoted by PI (A). 2.4 Minimal Transversals The problem of computing minimal transversals in hypergraphs or, equivalently, the prime conjunctive normal form of the dual of a Boolean function (otherwise called monotone dualization), have been largely studied in the literature [13, 10, 8, 9, 7]. Given a hypergraph H = (E, V) where E is a set of edges and V ⊆ 2E is a set of vertices, a transversal T ⊆ E is a set of edges such that ∀V ∈ V, T ∩ V 6= ∅. A transversal is minimal if none of its subsets is a transversal. We shall use T r(V ) to denote the set of minimal transversals of a set of vertices V . For example, T r({ace, bce, cde}) = {c, e, abd}. The problem of computing all the minimal transversals of a hypergraph can be solved in quasi-polynomial total time [9, 10, 13]. It is currently not known Depth-first Search for Pseudo-intents through Minimal Transversals 5 whether it is possible to enumerate the transversals with a polynomial delay in the general case. However, many special cases are known to have an output- polynomial delay. Their references can be found in [9]. In this work, we cannot presuppose the nature of the hypergraph and so we are interested in the general case. The problem still being actively studied, we will suppose that we have a blackbox algorithm nextTrans that enumerates the minimal transversals of a set of vertices X. We suppose, for ease of writing, that the transversals Ti this algorithm enumerates in some arbitrary order T1 < T2 < ... < Tn with nextTrans(Ti , X) = Ti+1 and nextTrans(Tn , X) = ∅. For example, Berge Multiplication [5] can be adapted to take the role of nextTrans. It is important to note that a first transversal can be computed in polynomial time by simply removing attributes until the set stops being a transversal. 3 Recognizing a Pseudo-Intent We know that an attribute set is a pseudo-intent if and only if it contains the closure of all its subsets that are pseudo-intents. As for the problem of recognizing pseudo-intents, two cases have been studied. When only a context and a set A are provided, checking whether A is a pseudo-intent is coNP-complete [1]. An algorithm has been proposed in [19] that runs in O(2|A| ). When the context and A are provided alongside all the pseudo-intents (and thus implications) contained in A, checking whether A is a pseudo-intent is easier as we only have to verify the closedness of A for the logical closure and ·00 , which implies a runtime polynomial in the size of the implication set. It is this method that is used in algorithms such as Next Closure or the one we proposed in [4] and its drawback is that it forces an enumeration in an order that extends the inclusion order. In this paper, we are interested in enumerating pseudo-intents in orders that do not extend the inclusion and, as such, we cannot suppose that we know the closure of all the subsets of a set before attempting to recognize its pseudo- closedness. Hence, we propose to consider the problem of recognizing a pseudo- intent A given a context and a set of subsets of A that is not necessarily complete. Proposition 1. An attribute set A ∈ ΦI is a pseudo-intent if A 6= A00 and all its lower covers in ΦI are closed. Proof. Let us suppose that A is not closed and that all its lower covers are closed. Let B be a lower cover of A and X be a subset of A. If B ⊂ X, then I(X) = A and X 00 = A00 . If X ⊆ B and X 00 6⊆ B, then B cannot be closed and we have a contradiction. Therefore, X 00 ⊆ B. Since the closure of every subset of A is either A00 or contained in A, the set A is a pseudo-intent.  This proposition states that some pseudo-intents can be recognized in ΦI only by looking at their lower covers. As such, when I is a subset of the Duquenne- Guigues basis, a new pseudo-intent can be found by looking in ΦI for sets that only have intents as lower covers. 6 Alexandre Bazin Definition 1. A pseudo-intent that can be recognized using Proposition 1 with a set of implication I is said to be recognizable. The set of all the implications that are recognizable with I is denoted by Rec(I). Proposition 2. ∀I ⊂ B, Rec(I) 6= ∅ Proof. Let P be minimal among pseudo-intents that are not premises of impli- cations in I. If there is a lower cover X of P in ΦI that is not closed, then there is a set A ⊂ X in ΦI such that A → A00 holds in the context. If A00 ⊆ P , then P is not minimal. If A00 6⊆ P , then P is not a pseudo-intent. Both cases lead to contradictions so all the lower covers of P are closed and P is recognizable from I. Since we have I ⊂ B, the set of pseudo-intents that are not a premise of I is not empty, so it has minimal elements. Hence, the set of pseudo-intents that are recognizable from I is not empty if I ⊂ B.  We have that, even though some unknown pseudo-intents may not be recog- nizable, there are always additional recognizable pseudo-intents for any subset of the Duquenne-Guigues basis. This ensures that we are able to enumerate all the pseudo-intents with an algorithm that finds recognizable ones. Proposition 3. Let A and B be two elements of ΦI . The set B is a lower cover of A if and only if B = A \ C with C a minimal transversal of GenI (A). Proof. Let C be minimal such that ∀G ∈ GenI (A), G∩C 6= ∅. For any attribute i ∈ A \ C, the set (A \ C) ∪ {i} = A \ (C \ {i}) contains a minimal generator of A because of the minimality of C. Therefore, any B between A \ C and A is such that I(B) = A and cannot be in ΦI . Hence, A \ C is a lower cover of A. Let B be a lower cover of A in ΦI . By definition, I(B ∪ {i}) = A for any attribute i ∈ A \ B so there is a subset C of A such that i ∈ C and (C \ {i}) ⊆ B that is a minimal generator of A.  This proposition states that the lower covers of a set can be computed from and depend on its minimal generators. As such, the number of lower covers can be exponential in the number of minimal generators which can itself be exponential in the size of the attribute set [14]. Definition 2. For any two attribute sets A and B, we say that B is reachable from A if and only if B ⊂ A and there is an ordering x1 < x2 < ... < xn of the elements of A \ B such that, for every m < n, A \ {x1 , x2 , ..., xm } is not closed under I. In other words, B is reachable from A if you can obtain B by removing at- tributes from A and only go through sets that are not closed under I. Evidently, minimal reachable sets are elements of ΦI . Proposition 4. An attribute set A ∈ ΦI is a minimal recognizable pseudo- intent if and only if A is not an intent and all the minimal attributes sets reach- able from A are intents. Depth-first Search for Pseudo-intents through Minimal Transversals 7 Algorithm 1 reachableSets(A) Require: An attribute set A, an implication set I 1: R = ∅ S i ∈ A do 2: for every 3: G = P ∈PI (A\{i}) GenI (P ) 4: C = The first transversal of G 5: while C 6= ∅ do 6: B = A \ ({i} ∪ C) 7: if PI (B) 6= ∅ then 8: R = R ∪ reachableSets(B) 9: else 10: R = R ∪ {B} 11: end if 12: C = nextT rans(C, G) 13: end while 14: end for 15: Return R Proof. If A is a minimal recognizable pseudo-intent, then every subset of A in ΦI is an intent. Thus every minimal reachable set is an intent. Let us suppose that every minimal reachable subset of A is an intent and A 6= A00 . For any set X reachable from A and any attribute set P ⊆ X, if P 00 6⊂ A, then X cannot be an intent. Every minimal reachable subset of A being an intent, A contains the closure of all its subsets so it is a pseudo-intent. If P is a pseudo-intent that is not in I, subsets of A \ {i} with i ∈ P 00 \ P cannot be intents so either P or a superset of P in ΦI that is not an intent is reachable from A. Hence, A is a minimal recognizable pseudo-intent.  A minimal recognizable pseudo-intent can therefore be recognized by com- puting the sets of its minimal reachable subsets. These minimal reachable sets can be computed using Algorithm 1. By definition, reachable sets can be com- puted by removing from A attributes that play a role in the logical closure, i.e. attributes in minimal generators of pseudo-intents P ⊂ A such that P 00 6⊆ A \ X for some A \ X reachable from A. The minimal transversals T make up all the possible ways to remove minimal generators of pseudo-intents and, thus, all the sets T such that for every Y ⊂ T , A \ Y cannot be logically closed. As such, removing minimal transversals of the generators of pseudo-intents used in the logical closure of a set produces a reachable set. The set A \ T is not always logically closed so the algorithm is recursively applied until an element of ΦI is reached. The algorithm is not optimal as some reachable sets can be computed mul- tiple times and the sets reachable from a set A that is not an element of ΦI could be computed directly from PI (A) instead of its direct subsets. However, it is sufficient to give us an upper bound of the runtime. For each recursive call, the algorithm computes PI (A \ {i}) for every attribute i ∈ A. For each of these 8 Alexandre Bazin S attributes, it then computes the minimal transversals of P ∈PI (A\{i}) GenI (P ). There is another recursive call for each pseudo-intent found missing so the run- time is bounded by O(|A| × |I| × T ) where T is the complexity of computing the transversals. In the rest of this paper, we will suppose that we have an algorithm nex- tReach that enumerates minimal reachable sets in the same fashion as next- Trans. 4 Computing a Recognizable Pseudo-Intent 4.1 Algorithm We want to incrementally compute the pseudo-intents in a formal context. In the beginning, we only have the formal context (O, A, R) and an empty set of implications I. The corresponding ΦI is the boolean lattice of subsets of A. In order to find a first pseudo-intent, we can look for a recognizable set (Proposition 1) in ΦI . We know that a non-closed set contains a pseudo-intent. Thus, we can start with A and recursively remove attributes as long as we obtain non-closed sets. When we cannot remove attributes without obtaining an intent, the set is a recognizable pseudo-intent and we have a first implication. This corresponds to the algorithm presented in [6] that computes a first pseudo-intent. We can then generalize the algorithm for other pseudo-intents. As I contains a new implication, sets disappear from ΦI and we now have to look in the new lattice for a second pseudo-intent. As it is not a Boolean lattice anymore, we cannot simply remove attributes to obtain lower covers so we have to use Proposition 3 to compute them. By going through the lattice using non-closed lower covers of sets until we find a set respecting Proposition 1, we can compute a second pseudo-intent. Pseudo-intents can thus be computed incrementally until A no longer has any non-closed lower cover. Algorithm 2, given a context, a subset I of the Duquenne-Guigue Basis and an attribute set A ∈ ΦI , uses this method to compute a new pseudo-intent P ⊆ A. Proposition 5. nextP I(A, I) returns either A or a pseudo-intent that is not in I. Proof. Let X be a set in ΦI . If X 00 6= X, then there is a pseudo-intent P ⊆ X. If a lower cover of X is not closed, then there is a pseudo-intent X ⊂ S. The algorithm returns the first set it finds that has all its lower covers closed. If this set is not A, then it is not closed and is thus a pseudo-intent.  Algorithm 3 uses Algorithm 2 to enumerate pseudo-intents iteratively until it returns A. It is sound but not complete, as exemplified below. Depth-first Search for Pseudo-intents through Minimal Transversals 9 Algorithm 2 nextP I(A, I) Require: Attribute set A, Implication set I 1: P = A 2: G = GenI (A) 3: C = The first transversal of G 4: while C 6= ∅ do 5: S =A\C 6: if S 00 6= S then 7: P = nextP I(S) 8: C=∅ 9: else 10: C = nextT rans(C, G) 11: end if 12: end while 13: RETURN P Algorithm 3 allP I 1: I = ∅ 2: A = nextP I(A, I) 3: while A 6= A do 4: I = I ∪ {A → A00 } 5: A = nextP I(A, I) 6: end while 7: Return I 4.2 Example Let us consider an arbitrary context for which the Duquenne-Guigues basis is {de → bde, bc → bcd, ac → abcd, be → bde, bcde → abcde}. We want to find its pseudo-intents using Algorithm 3 : The set of implications is initially empty. We start with abcde. It has a single minimal generator, itself. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recur- sively with it. The set bcde has a single minimal generator, itself. The first minimal transver- sal of Gen(bcde) is b. The set bcde \ b = cde is not an intent so we continue recursively with it. The set cde has a single minimal generator, itself. The first minimal transver- sal of Gen(cde) is c. The set cde\c = de is not an intent so we continue recursively with it. The set de has a single minimal generator, itself. The first minimal transversal of Gen(de) is d. The set de \ d = e is an intent. The second and last minimal transversal is e. The set de \ e = d is an intent. The algorithm returns de as the first pseudo-intent which gives us I = {de → bde}. 10 Alexandre Bazin Fig. 3. The five steps of the algorithm. In red the sets considered by the recursive calls, in black the lower covers of those sets in ΦI . We start again with abcde. It has a single minimal generator, acde. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it. The set bcde has a single minimal generator, cde. The first minimal transver- sal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second minimal transversal is d. The set bcde \ d = bce is not an intent so we continue recursively with it. The set bce has a single minimal generator, itself. The first minimal transver- sal of Gen(bce) is b. The set bce \ b = ce is an intent. The second minimal transversal is c. The set bce \ c = be is not an intent so we continue recursively with it. The set be has a single minimal generator, itself. The first minimal transversal of Gen(be) is b. The set be \ b = e is an intent. The second and last minimal transversal is e. The set be \ e = b is an intent. The algorithm returns be as the second pseudo-intent which gives us I = {de → bde, be → bde}. We start again with abcde. It has two minimal generators, acde and abce. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it. The set bcde has two minimal generators, bce and cde. The first minimal transversal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second Depth-first Search for Pseudo-intents through Minimal Transversals 11 minimal transversal is bd. The set bcde \ bd = ce is an intent. The third and last minimal transversal is e. The set bcde \ e = bcd is an intent. The algorithm returns bcde as the third pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde}. We start again with abcde. It has two minimal generators, cde and bce. The first minimal transversal of Gen(abcde) is bd. The set abcde \ bd = ace is not an intent so we continue recursively with it. The set ace has a single minimal generator, itself. The first minimal transver- sal of Gen(ace) is a. The set ace \ a = ce is an intent. The second minimal transversal is c. The set ace \ c = ae is an intent. The third minimal transversal is e. The set ace \ e = ac is not an intent so we continue recursively with it. The set ac has a single minimal generator, itself. The first minimal transversal of Gen(ace) is a. The set ac \ a = c is an intent. The second and last minimal transversal is c. The set ac\c = a is intent. The algorithm returns ac as the fourth pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac → abcd}. We start again with abcde. It has three minimal generators, ace, cde and bce. The first minimal transversal of Gen(abcde) is c. The set abcde \ c = abde is an intent. The second minimal transversal is e. The set abcde \ e = abcd is an intent. The third and last minimal transversal is abd. The set abcde \ abd = ce is an intent. The algorithm ends. The algorithm has found four pseudo-intents but is unable to find the set bc when considering the minimal transversals, and thus the sets, in that partic- ular order. Indeed, knowing be → bde and de → bde makes bcde recognizable and blocks every path from abcde to bc in ΦI . Finding bc before either de or be solves the problem. 4.3 Complexity The nature of Algorithm 2 makes it easy to bound the delay between finding two pseudo-intents. As the algorithm starts from A and removes attributes until it ends, it performs a maximum of |A| recursive calls before finding a pseudo- intent. In a call, three different tasks are performed : computing the closure of a set, computing the set of minimal generators and computing the set of all lower covers. The closure of a set is known to be computable in polynomial time. Computing GenI (A) is done in time polynomial in the size of the output. The computation of all the lower covers of A, as we have seen in Section 2.4, can be performed in quasi-polynomial total time, i.e. in time quasi-polynomial in the size of n = |Gen  I (A)|  and m = |T r(GenI (A))| (note that the size of m itself is n bounded by  n  [18]). Hence, the delay is in O(|A| × (C + G + T )) with C 2 the complexity of computing a closure, G the complexity of computing minimal generators and T the complexity of computing the lower covers. 12 Alexandre Bazin Algorithm 4 nextM inP I(A, I) Require: Attribute set A, Implication set I 1: P = A 2: C =The first minimal set reachable from A 3: while C 6= ∅ do 4: if C 00 6= C then 5: P = nextM inP I(C) 6: C=∅ 7: else 8: C = nextReach(C, A) 9: end if 10: end while 11: RETURN P An interesting point of detail is that the algorithm does not necessarily enu- merate all the intents. When all the upper covers of an intent A in ΦI are intents themselves, A cannot be reached by the algorithm anymore. In particu- lar, if A ∪ {i} = (A ∪ {i})00 for every i ∈ A \ A, we are sure that A will never be considered. In the previous example (see Figure 3), we see that the intents abd, ab, ad, bd, de and ∅ are never considered because they do not appear as lower covers of sets. We suppose that this property helps reduce the runtime on dense contexts with a high number of intents. 5 Computing a Minimal Recognizable Pseudo-Intent 5.1 Algorithm The problem with Algorithm 3 is that there are some pseudo-intents it cannot compute. Among those leftover pseudo-intents, there is necessarily at least one that is minimal. We have shown in Proposition 4 that a minimal recognizable pseudo-intent P can be recognized through the minimal sets reachable from P . Those reachable sets can themselves be obtained by computing the transversals of the sets of minimal generators of the pseudo-intents involved in the logical closure of the different P \ {i} (Algorithm 1). Algorithm 4 uses these properties to compute a minimal recognizable pseudo-intent. In a manner similar to that of Algorithm 2, the algorithm starts with A and enumerates the minimal reachable sets. Once one that is not an intent is found, the algorithm is recursively applied. The algorithm ends when it finds a set with only intents as minimal reachable sets. The main difference between Algorithm 2 and Algorithm 4 is that the former performs a depth-first search in the lattice ΦI while the latter performs it in the directed graph in which the nodes are the elements of ΦI and the edges are the pairs in the “reachable” relation. Proposition 6. Algorithm 4 returns either A or a minimal pseudo-intent that is not in I. Depth-first Search for Pseudo-intents through Minimal Transversals 13 Algorithm 5 allP I2 1: I = ∅ 2: A = nextminP I(A, I) 3: while A 6= A do 4: I = I ∪ {A → A00 } 5: A = nextM inP I(A, I) 6: end while 7: Return I Proof. From Proposition 4 we know that if every minimal set T ∈ ΦI reachable from A ∈ ΦI is closed and A is not, then A is a minimal recognizable pseudo- intent. If T ∈ ΦI is not closed, then T contains a minimal recognizable pseudo- intent so the algorithm can be recursively called on T . The algorithm stops when it encounters a set A with only intents as minimal reachable sets. The set A being the only intent on which the algorithm is called, it returns either A or a minimal recognizable pseudo-intent.  We can enumerate all the pseudo-intents with Algorithm 5 using Algorithm 4 in the same fashion as Algorithm 3. Proposition 7. Algorithm 5 is sound and complete. Proof. Soundness follows from Proposition 6. For any implication set I ⊂ B, pseudo-intent P not used in I and attribute set A ∈ ΦI such that P ⊂ A, no set X such that P ⊂ X and P 00 6⊆ X can be an intent so either P or one of its non-closed supersets is reachable from A. Hence, the algorithm does not stop until every pseudo-intent has been found.  5.2 Example Contrary to Algorithm 3, Algorithm 5 is complete. We can either use it to compute all the pseudo-intents or combine it with Algorithm 3. Let us suppose we have used Algorithm 3, as exemplified in Section 4, and that we know the set of implications I = {de → bde, be → bde, bcde → abcde, ac → abcd}. Using Algorithm 5 from there gives us the following : We start with abcde. The first minimal reachable set abcde\(a∪bd) = ce is an intent. The second minimal reachable set abcde \ (a ∪ bc) = de is an intent. The third minimal reachable set abcde\(a∪e) = bcd is an intent. The fourth minimal reachable set abcde \ (b ∪ cd) = ae is an intent. The fifth minimal reachable set abcde\(b∪e) = cd is an intent. The sixth minimal reachable set abcde\(b∪ce) = ad is an intent. The seventh minimal reachable set abcde \ c = abde is an intent. The eighth minimal reachable set abcde \ (d ∪ ab) = ce is an intent. The ninth minimal reachable set abcde \ (d ∪ ae) = bc is not an intent so we continue recursively with it. 14 Alexandre Bazin The set bc contains no pseudo-intents so its minimal reachable sets are bc\b = c and bc \ c = b. They are both intents so the algorithm returns bc as a new pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac → abcd, bc → bcd}. We start again with abcde. The eight first minimal reachable sets computed are the same as in the previous step. The ninth reachable set abcde \ cde = ab is an intent. The tenth and last reachable set abcde \ e = abcd is an intent. The algorithm ends. In this example, the pseudo-intent bc has been found after bcde. Using both Algorithm 3 and Algorithm 5, it is thus possible to enumerate pseudo-intents in orders that do not extend the inclusion. 5.3 Complexity Once again, the delay between two pseudo-intents with Algorithm 5 is easy to bound. Algorithm 4 performs at most |A| recursive calls before returning a pseudo-intent or A. Each call requires the computation of, at most, all the reachable sets in ΦI . We have shown that this can be done in O(|A| × |I| × T ) with T the complexity of computing minimal transversals of minimal generators of pseudo-intents. Thus, the worst case delay of Algorithm 5 is |I| times that of Algorithm 3. A first minimal transversal can be computed in polynomial time. As such, for any attribute set A, we can compute its first reachable set in ΦI in time polynomial in |A| and |I|. Hence, if, for every A ∈ ΦI that is not a pseudo-intent, the reachable sets in ΦI are ordered in such a way that the first one is not closed, Algorithm 5 can compute (but not necessarily recognize) a pseudo-intent in time polynomial in the size of the implication set. A minimal pseudo-intent P , by definition, does not contain any other pseudo-intent so the set of its reachable set is {P \ {p} | p ∈ P } which can be computed in polynomial time. Thus, there are always orderings of reachable sets such that Algorithm 5 can compute minimal pseudo-intents with an incremental polynomial time between two of them. However, as shown in [6], minimal pseudo-intents cannot be enumerated in output polynomial time. Indeed, even though it is possible to compute a minimal pseudo-intent in time polynomial in the size of the implication set, confirming that they have all been found is exponential because non-minimal pseudo-intents and A have a potentially exponential number of reachable sets. 6 Conclusion We have proposed two algorithms for computing pseudo-intents using the com- putation of minimal transversals as their main operation. The first can find pseudo-intents before some of their subsets that are themselves pseudo-intents but it is not complete for some enumeration orders. The second is complete but can only enumerate in orders that respect the inclusion relation. They can be Depth-first Search for Pseudo-intents through Minimal Transversals 15 combined to obtain the enumeration order of the first with the completeness of the second. We expressed their delay as a function of the complexity of com- puting minimal transversals. We showed that, for some orderings of attribute sets, pseudo-intents can be reached, but not recognized, in incremental polyno- mial time. As both reaching and recognizing pseudo-intents, in our context, are related to the problem of computing minimal transversals in hypergraphs for which many special cases are known, we believe that this work may be useful in isolating more cases for which the enumeration of pseudo-intents is easier. On the practical side, the fact that the algorithms do not necessarily enu- merate the entirety of the set of intents should significantly reduce the runtime on dense contexts. Furthermore, the depth-first strategy used in the algorithms allows for some computations to be saved and reused. Further algorithmic opti- mizations and empirical comparisons with other algorithms for the same problem will be the subject of future investigations. References 1. Mikhail A. Babin and Sergei O. Kuznetsov. Recognizing Pseudo-intents is coNP- complete. In Proceedings of the 7th International Conference on Concept Lattices and Their Applications, Sevilla, Spain, October 19-21, 2010, pages 294–301, 2010. 2. Mikhail A. Babin and Sergei O. Kuznetsov. Computing Premises of a Minimal Cover of Functional Dependencies is Intractable. Discrete Applied Mathematics, 161(6):742–749, 2013. 3. Konstantin Bazhanov and Sergei A. Obiedkov. Comparing Performance of Algo- rithms for Generating the Duquenne-Guigues Basis. In Proceedings of The Eighth International Conference on Concept Lattices and Their Applications, Nancy, France, October 17-20, 2011, pages 43–57, 2011. 4. Alexandre Bazin and Jean-Gabriel Ganascia. Enumerating Pseudo-Intents in a Partial Order. In Proceedings of the Tenth International Conference on Concept Lattices and Their Applications, La Rochelle, France, October 15-18, 2013., pages 45–56, 2013. 5. Claude Berge. Hypergraphs: Combinatorics of Finite Sets, volume 45. Elsevier, 1984. 6. Felix Distel and Baris Sertkaya. On the Complexity of Enumerating Pseudo-intents. Discrete Applied Mathematics, 159(6):450–466, 2011. 7. Thomas Eiter and Georg Gottlob. Identifying the Minimal Transversals of a Hy- pergraph and Related Problems. SIAM J. Comput., 24(6):1278–1304, 1995. 8. Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New Results on Mono- tone Dualization and Generating Hypergraph Transversals. SIAM J. Comput., 32(2):514–537, 2003. 9. Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational As- pects of Monotone Dualization: A Brief Survey. Discrete Applied Mathematics, 156(11):2035–2049, 2008. 10. Michael L. Fredman and Leonid Khachiyan. On the Complexity of Dualization of Monotone Disjunctive Normal Forms. J. Algorithms, 21(3):618–628, 1996. 11. Bernhard Ganter. Two Basic Algorithms in Concept Analysis. In Preprint Tech- nische Hochschule Darmstadt, 1984. 16 Alexandre Bazin 12. Jean-Louis Guigues and Vincent Duquenne. Familles Minimales d’Implications Informatives Résultant d’un Tableau de Données Binaires. Mathématiques et Sci- ences humaines, 95:5–18, 1986. 13. Vladimir Gurvich and Leonid Khachiyan. On Generating the Irredundant Con- junctive and Disjunctive Normal Forms of Monotone Boolean Functions. Discrete Applied Mathematics, 96-97:363–373, 1999. 14. Miki Hermann and Baris Sertkaya. On the Complexity of Computing Generators of Closed Sets. In Formal Concept Analysis, 6th International Conference, ICFCA 2008, Montreal, Canada, February 25-28, 2008, Proceedings, pages 158–168, 2008. 15. Sergei O. Kuznetsov. On the Intractability of Computing the Duquenne-Guigues Bas. J. UCS, 10(8):927–933, 2004. 16. Sergei O. Kuznetsov and Sergei A. Obiedkov. Counting Pseudo-intents and #P- completeness. In Formal Concept Analysis, 4th International Conference, ICFCA 2006, Dresden, Germany, February 13-17, 2006, Proceedings, pages 306–308, 2006. 17. Sergei O. Kuznetsov and Sergei A. Obiedkov. Some Decision and Counting Prob- lems of the Duquenne-Guigues Basis of Implications. Discrete Applied Mathemat- ics, 156(11):1994–2003, 2008. 18. Zbigniew Lonc and Miroslaw Truszczynski. On the Number of Minimal Transver- sals in 3-uniform Hypergraphs. Discrete Mathematics, 308(16):3668–3687, 2008. 19. Sebastian Rudolph. Some Notes on Pseudo-closed Sets. In Formal Concept Analy- sis, 5th International Conference, ICFCA 2007, Clermont-Ferrand, France, Febru- ary 12-16, 2007, Proceedings, pages 151–165, 2007.