In this paper, we consider two methods for computing lower cover of elements in closure systems for which we know an implicational basis: intersecting meet-irreducible elements or computing minimal transversals of sets of minimal generators. We provide experimental results on the runtimes for single computations of lower covers and depth- rst searches.
What we are interested in is the problem of performing depth- rst searches
starting from the maximal element in closure systems for which we know an
implicational basis. This amounts to computing lower covers of closed sets using
the implications, a problem shown to be NP-hard [
Basic De nitions Let us use E to denote a set of elements.
De nition 1 A closure operator c : 2E 7! 2E is an extensive (X c(X)), increasing (X Y ) c(X) c(Y )) and idempotent (c(c(X)) = c(X)) function.
A set S 2 2E such that S = c(S) is said to be closed. The intersection of two closed sets is closed. The set of all sets closed for a given closure operator c ordered by inclusion forms a lattice that will here be denoted by c. De nition 2 An implication on E is a pair (A; B) 2 2E written A ! B. 2E , most commonly De nition 3 Let I be a set of implications. We denote by I( ) the closure operator, sometimes called logical closure, that maps a set X to its smallest superset Y such that 8A ! B 2 I; A
Y ) B
Y
The logical closure is a closure operator. As such, for an implication set I, we will use I to denote the lattice of implication-closed sets ordered by inclusion. De nition 4 A minimal generator G of X 2 2E for a closure operator c is an inclusion-minimal set such that c(G) = X.
In the remainder of this paper, we will use the term minimal generator, without any more details, to talk about the minimal generators for the logical closure. The set of minimal generators of a set S for an implication set I will be denoted GenI (S).
De nition 5 Let L = (E; ) be a lattice. A meet-irreducible element is an element e E that has a single upper cover, i.e. fx 2 E j x > eg has a single inclusion-minimal element. We use M(L) to denote the set of meet-irreducible elements of the lattice L.
Any element of the lattice L is the in mum of a set of meet-irreducible elements.
E .
De nition 6 Let H = (E ; V ) be a hypergraph. A minimal transversal of E is a set S V such that 8X 2 E , X \ S 6= ;.
We use T r(E ) to denote the set of minimal transversals of a set of hyperedges 2.2 If we want to perform a depth- rst search from the top in a lattice I for which we know I, we have to be able to compute the lower covers of a set S 2 I . We present here two methods that can be used to compute them.
Proposition 1 For any S 2 I , the lower covers of S are the inclusion-maximal elements of fS \ M j M 2 M( I ) and S 6 M g.
Proof Every element of I is the in mum of a subset of M( I ). Additionally,
I being a closure system, the in mum of two sets is their intersection. As such, for any M 2 M( I ), S \M S is an I-closed set. S \M being strictly contained in S, if it is inclusion-maximal then it is a lower cover of S.
Using Proposition 1 to compute lower covers requires that we rst know the meet-irreducible elements of the lattice. In most case, they must be explicitly computed beforehand. Algorithm 1, presented in Section 3.1, does this. Proposition 2 For any S 2 T 2 T r(GenI (S)).
I , the lower covers of S are the sets S n T with Proof Let T be a minimal transversal of GenI (S). For any e 2 S n T , (S n T ) [ feg = S n (T n feg) contains a minimal generator of S because of the minimality of T . Therefore, there is no closed set between S and S n T and S n T is a lower cover of S.
Using Proposition 2 to compute the lower covers of S would require that we compute the minimal generators S rst, then their minimal transversals. The algorithms we use for these problems are described in Section 4.
3.1
Computing Meet-irreducible Elements from an Implication
Base
We use Wild's algorithm [
a2A where X
Y = fx \ y j x 2 X; y 2 Y g.
max00(e; I n fIg) max(a; I n fIg)
Algorithm 1 uses this property to compute the meet-irreducible elements of I from I = fA1 ! B1; :::; An ! Bng by computing the meet irreducibles of every lattice Ii such that Ii = fA1 ! B1; :::; Ai ! Big with 0 i n.
Algorithm 1 has a runtime exponential in the size of its output, which can itself be exponential in the size of the implication base. Once the meet-irreducible elements of the lattice are known, we can compute the lower covers of a set S by intersecting it with the meet-irreducible sets that are not supersets of S and keeping the inclusion-maximal elements. Algorithm 2 runs in time polynomial in the size of M( I ).
Computing Minimal Generators
We compute the minimal generators of an implication-closed set with Algorithms
3 and 4 proposed in [
Algorithm 2: Intersection of meet-irreducible elements
Output: The lower covers of S 1 C = ; 2 foreach M 2 M( I ) do 3 C = C [ (S \ M ) 4 end 5 Return max(C) Algorithm 3: First minimal generator
Algorithm 3, given a set P and an implication set L, computes a rst minimal
generator of P . Algorithm 4 computes all the minimal generators of a set P for
an implication set L. It has time complexity O(jLj jGj jPj (jGj + jPj)).
The problem of computing minimal transversals is a classic that, while
extensively studied, still holds many interesting question [
H1 _ H2 = fh1 [ h2 j h1 2 H1 and h2 2 H2g We then have Which gives rise to Algorithm 5.
T r(H1 [ H2 = min(T r(H1) _ T r(H2)) 5
We implemented both methods, used them on randomly generated implicational bases and compared their runtimes. Implications were generated by using
Output: T r(H) 1 T = ; 2 foreach E 2 H do 3 T = min(T _ ffvg j v 2 Eg) 4 end 5 Return T NextClosure on formal contexts (O; A; R) randomly generated with 50 objects, 12 attributes and a probability d (called density ) to have (o; a) 2 R.
Two cases were considered: { Single computations of lower covers { Depth- rst searches in lattices involving multiple computations of lower covers
For the rst case, we simply computed the lower covers of A. For the second case, we removed some implications as to introduce, in the lattice, sets that are not intents of the formal contexts and we performed the depth- rst searches starting from A and going deeper everytime we encountered a non-intent. 5.1
Single Computations We generated 1000 contexts with varying numbers of implications and computed the lower covers of A using the two methods we presented. Figure 1 presents the quadratic interpolation of the runtimes for each method relative to the number of implications in the basis.
In our experiments, the algorithm using meet-irreducible elements outperformed the one based on minimal generators 79% of the time. Computing the meet-irreducible elements represents 98% of its runtime. The second method devotes 75% of its time to computing minimal generators and 25% on minimal transversals. As with single computations, we randomly generated 1000 contexts with varying numbers of implications and performed depth- rst searches starting from A. Runtimes Relative to the Size of the Basis Figure 2 presents the interpolation of the runtimes for each methods relative to the number of implications in the basis.
Once again, using meet-irreducibles is the most e cient method (it outperformed the minimal generators 72% of the time) and this trend accentuates with the size of the implicational basis. Computing the meet-irreducible elements represents 86% of the total runtime. The second methods devotes 69% of its runtime to the computation of minimal generators and 31% on minimal transversals. Runtimes Relative to the Depth Figure 3 presents the interpolation of the runtimes for each methods relative to the depth of the search.
We can notice that the algorithm using meet-irreducible elements is much less a ected by the depth of the search, most likely due to the fact that most of the computation is done prior to the actual search. Interestingly, the algorithm using minimal generators is least e cient for relatively shallow searches. We believe this is due to the fact that deep searches imply that the lattice is mostly composed of sets that have the property we are looking for. As we used closedness relative to a formal context, this means that those lattices correspond to nearly empty implicational bases.
Runtimes with Increasing Bases We used both methods to perform depthrst searches in a sequence of lattices corresponding to implicational bases ; I1 ::: In. Results are presented in Figure 4.
Once again, the runtime of the algorithm using minimal generators skyrockets when the basis grows. The meet-irreducibles method presents much less variance. It should be noted that the meet-irreducible elements are computed from scratch for each basis when Algorithm 1 could be used to speed up the process by using the meet-irreducible elements of the previous lattice to compute the new ones. 6
Experimental results indicate that the most e cient way to compute lower covers of implication-closed sets is to rst compute the meet-irreducible elements of the lattice and then intersect them. It outperforms the method based on computing minimal transversals of minimal generators even when minimal generators have to be computed only once. During deeper searches, minimal generators have to be computed at each step and the di erence is thus more pronounced.
While the algorithm we used for computing minimal transversals is not the most e cient, the fact that this computation represents only a small portion of the second method indicates that, even with the best algorithm, using meetirreducible elements would be best. Computing these meet-irreducible elements is time-consuming but, once we have them, they are easy to intersect. We believe there is still more room for improvement on the problem of computing meetirreducible elements from implicational bases.
Acknowledgments The author was supported by the European Union and the French Region Auvergne - Rh^one-Alpes.