A generalization of the well known Next-Closure algorithm is presented, which is able to enumerate finite semilattices from a generating set. We prove the correctness of the algorithm and apply it on the computation of the intents of a formal context. c 2012 by the paper authors. CLA 2012, pp. 9-20. 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´alaga (Dept. Matem´atica Aplicada), Spain.
Next-Closure is one of the best known algorithms in Formal Concept Analysis [
As it turns out, Next-Closure is not about enumerating closed sets of a closure operator, even not on an abstract ordered set. The algorithm is merely about enumerating elements of a certain semilattice, given as an operation together with a generating set. This observation shall turn out to be quite natural.
It has to be noted that there have been prior attempts to generalize
NextClosure to a more general setting [
This paper is organized as follows. First of all we shall revisit the original version of Next-Closure, together with the basic definitions. Then we present our generalized version working on semilattices, together with a complete proof of its correctness. Then we show how this generalized form is indeed a generalization of the original Next-Closure. Additionally, we present another algorithm for enumerating the intents of a given formal context, which is very similar to Close-by-One. Finally, we give some outlook on further questions which might be interesting within this line of research.
Before we are going to discuss our generalized form of Next-Closure, let us
revisit the original version as it is given in [
Let M be a finite set and let c : PpP q ÝÑ PpP q be a function such that
b) c is monotone, i.e. if A Ď B, then cpAq Ď cpBq for all A, B Ď M , and c) c is extensive, i.e. A Ď cpAq for all A Ď M .
The mapping c is then said to be a closure operator on P . A set A Ď M is called closed (with respect to c) if A “ cpAq, and the image of c is defined as crPpM qs :“ t cpAq | A Ď M u.
Without loss of generality, let M “ t 1, . . . , n u for some n P N. For two sets A, B P crPpM qs with A ‰ B and i P M we say that A is lectically smaller than B at position i if and only if
i “ minpA ∆ B q and i P B, where A ∆ B “ pAzBq Y pBzAq denotes the symmetric difference of A and B. We shall write A ăi B if A is lectically smaller than B at position i. Finally, we say that A is lectically smaller than B, for A, B P crPpM qs, if A “ B or A ăi B for some i P M . We shall write A ĺ B in this case.
It has to be noted that, in contrast to our definition, the lectic order is normally defined for all sets A, B Ď M in the very same spirit as given above. However, as we shall see, this is not necessary, which is why we have restricted our definition to closed sets only.
Now let us define for A P crPpM qs and i P M
A ‘ i :“ cpt j P A | j ă i u Y t i uq.
Theorem 1 (Next-Closure [
A` “ A ‘ i with i P M being maximal with A ăi A ‘ i.
This is the original version of Next-Closure, as it is given in [
A` “ minăt B P crPpM qs | A ă B u.
Our generalization now starts with the following observation: the set A ‘ i can be seen as the smallest closed set containing both t j P A | j ă i u and t i u, or equivalently, both cpt j P A | j ă i uq and cpt i uq. This means that we can rewrite A ‘ i as
A ‘ i “ cpt j P A | j ă i uq _ cpt i uq, where X _ Y is the smallest closed set containing both X, Y P crPpM qs, the supremum of X and Y , which is simply given by X _ Y “ cpX Y Y q. This observation suggests to consider Next-Closure on abstract algebraic structures with a binary operation _ with some certain properties, namely on semi-lattices. To do so we need a more general notion of cpt i uq, since we do not necessarily deal with subsets, and a more general notion of t j P A | j ă i u, which likewise might not be expressible in a more general setting. Finally, we need to find a starting point for our enumeration, which is cpHq in the original description of Next-Closure, but may vary in other cases. Luckily, all this is possible and quite natural, as we shall see in the next section. 3
The aim of this section is to present a generalization of the Next-Closure algorithm that works on semilattices. For this recall that a semilattice L “ pL, _q is an algebraic structure with a binary operation _ which is associative, commutative and idempotent. It is well known that by
x ďL y : ðñ x _ y “ y, px, y P Lq an order relation on L is defined in such a way that for every two elements a, b P L the element a _ b is the least upper bound of both a and b with respect to ďL.
For the remainder of this section let L “ pL, _q be an arbitrary but fixed semilattice. Furthermore, let pxi | i P Iq be an enumeration of a finite generating set t xi | i P I u Ď L of L. Finally, let ďI be a total order on I.
Definition 1. Let a, b P L and let i P I. Set
∆ a,b :“ t j P I | pxj ďL a and xj ďL bq or pxj ďL a and xj ďL bq u. We then define
a ăi b : ðñ i “ min ∆ a,b and xi ďL b.
Furthermore we write a ă b if a ăi b for some i P I and write a ď b if a “ b or a ă b.
One can see the similarity of this definition to the one of the lectic order. Here, the set ∆ a,b generalizes a ∆ b and xi ďL b somehow represents the fact that i P b, or equivalently t i u Ď b, in the special case of L “ PpM q and i P M .
Note that if a ăi b and k P I with k ăI i, then
xk ďL a ðñ xk ďL b. This observation is quite useful and will be used in some of the proofs later on.
The first thing we want to consider now are two easy results stating that ď is a total order relation on L extending ďL.
Lemma 1. The relation ă is irreflexive and transitive. Furthermore, for every two elements a, b P L with a ‰ b, it is either a ă b or b ă a.
Proof. If a “ b, then the set ∆ a,b defined above is empty, therefore we cannot have a ăi a for some i P I. This shows the irreflexivity of ă. Let us now consider the transitivity of ă. For this let a, b, c P L, i, j P I and suppose that a ăi b and b ăj c. We have to show that a ă c. Let us consider the following cases.
Case i ăI j. We have xi ďL a and xi ďL b because of a ăi b. Due to i ăI j it follows that xi ďL c. Suppose that there exists k P I, k ăI i with xk ďL a and xk ďL c. Then if xk ďL b we would have xk ďL a because of k ăI i, a contradiction. But if xk ďL b, then xk ďL c because of k ăI i ăI j, again a contradiction. Thus we have shown that a ă c.
Case j ăI i. We have xj ďL b, xj ďL c because of b ăj c. Due to j ăI i it follows that xj ďL a. Now if there were a k P I, k ăI j with xk ďL a and xk ďL c, then xk ďL b would imply xk ďL c and xk ďL b would imply xk ďL a, analogously to the first case, a contradiction. Hence such a k cannot exist and a ă c.
Case i “ j. This cannot occur since otherwise xi ďL b, because of a ăi b, and xi ďL b, because of b ăi c, a contradiction.
Overall we have shown that a ă c in any case and therefore ă is a transitive relation.
Finally let a, b P L with a ‰ b. Then because t xi | i P I u is a generating set, the set ∆ a,b is not empty, since otherwise a “ b. With i :“ min ∆ a,b we either have a ăi b if xi ďL b and b ăi a otherwise.
Lemma 2. Let a, b P L with a ďL b. Then a ď b. In particular, if a ďL c and b ďL c for a, b, c P L, then a _ b ď c.
Proof. We show xi ďL a ùñ xi ďL b for all i P I. This shows b ă a, hence a ď b by Lemma 1. Now if xi ďL a, then because of a ďL b we see that xi ďL b and the claim is proven.
The next step towards a general notion of Next-Closure is to provide a generalization of ‘.
Definition 2. Let a P L and i P I. Then define a ‘ i :“ ł xj _ xi.
jăIi xjďLa
With all these definitions at hand we are now ready to formulate and prove the promised generalization. For this, we generalize the proof of Next-Closure as it is given in [8, page 67]. Lemma 3. Let a, b P L and i, j P I. Then the following statements hold: i) a ăi b, a ăj c, i ăI j ùñ c ăi b. ii) a ă a ‘ i if xi ďL a. iii) a ăi b ùñ a ‘ i ď b. iv) a ăi b ùñ a ăi a ‘ i.
Proof. i) It is xi ďL a and due to i ăI j we get xi ďL c as well. Furthermore, xi ďL b because of a ăi b. Now if there would exist a k P I with k ăI i such that xk ďL c, xk ďL b, then xk ďL a because of k ăI i and xk ďL a because of k ăI i ăI j, a contradiction. With the same argumentation a contradiction follows from the assumption that there exists a k P I, k ăI i with xk ďL c, xk ďL b. In sum we have shown c ăi b, as required. ii) We have xi ďL a and xi ďL a ‘ i. Furthermore, for k P I, k ăI i and xk ďL a we have xk ďL a ‘ i by definition. This shows a ă a ‘ i. iii) Let a ăk b for some k P I. Then ŽjăIk,xjďLa xj ďL b and xk ďL b, hence with Lemma 2 we get a ‘ k ď b. iv) Let a ăi b. Then xi ďL a and with (ii) we get a ă a ‘ i. By (iii), a ‘ i ď b.
If for k P I, k ăI i it holds that xk ďL a ‘ i and xk ďL a, then we also have xk ďL a ‘ i ďL b, i.e. xk ďL b, contradicting the minimality of i. Theorem 2 (Next-Closure for Semilattices). Let a P L. Then the next element a` P L with respect to ă, if it exists, is given by
a` “ a ‘ i with i P I being maximal with a ăi a ‘ i.
Proof. Let
a` “ minăt b P L | a ă b u be the next element after a with respect to ă. Then a ăi a` for some i P I and by Lemma 3.iv we get a ăi a ‘ i and with Lemma 3.iii we see a ‘ i ď a`, hence a ‘ i “ a`. The maximality of i follows from Lemma 3.i.
To find the correct element i P I such that a` “ a‘i we can utilize Lemma 3.ii. Because of this result, only elements i P I with xi ďL a have to be considered, a technique which is also known for the original form of Next-Closure.
However, to make the above theorem practical for enumerating the elements of a certain semilattice, one has to start with some element, preferably the smallest element in L with respect to ď. This element must also be minimal in L with respect to ďL, by Lemma 2. Since t xi | i P I u is a generating set of L, and a ď a _ b for all a, b P L, the minimal elements of L with respect to ďL must be among the elements xi, i P I. So to find the first element of L with respect to ď, find all minimal elements in t xi | i P I u and choose the smallest element with respect to ď from them. But because of xi ď xj if and only if j ăI i, one just has to take the largest index j with respect to ăI to find the smallest element in L with respect to ď.
As a final remark for this section note that the set t xi | i P I u must always include the _-irreducible elements of L. These are all those elements a P L that cannot be represented as a join of other elements, or, equivalently, t b P L | b ăL a u “ H or ł b ăL a. băLa It is also easy to see that the set of _-irreducible elements of L is also sufficient, i. e. that it is a generating set of L. 4
Computing the Intents of a Formal Context We have seen an algorithm that is able to enumerate the elements of a semilattice from a given generating set. We have also claimed that this is a generalization of Next-Closure, which we want to demonstrate in this section. Furthermore, we want to give another example of an application of this algorithm, namely the computation of the intents of a given formal context.
Firstly, let us reconstruct the original Next-Closure algorithm from Theorem 2 and the corresponding definitions. For this let M be a finite set and let c be a closure operator on M “ t 0, . . . , n ´ 1 u, say. We then apply Theorem 2 to the semilattice P “ pcrPpM qs, _q. We immediately see that ďP “ Ď and that ăi is the usual lectic order on P . Then the set
t cpt i uq | i P M u Y t cpHq u is a finite generating set of P and we can define xi :“ cpt i uq and xn :“ cpHq, i.e. I “ t 0, . . . , n u. For a closed set A Ď M and i P I then follows A ‘ i “ ł xi _ xi jăi xjĎA “ cp ď jăi xjĎA
xj q _ xi “ cpďt cpt j uq | j ă i, j P A uq _ cpt i uq “ cpt j | j ă i, j P A uq _ cpt i uq “ cpt j | j ă i, j P A u Y t i uq which is the original definition of ‘ for Next-Closure. Furthermore, it is A‘n “ A since cpHq Ď A for each closed set A. We therefore do not need to consider xn when looking for the next closed set, and indeed, the only reason why xn “ cpHq has been included is that it is the smallest closed set in P . All in all, we see that Next-Closure is a special case of Theorem 2.
However, for a closure operator c on a finite set M it seems more natural to consider the semilattice P “ pcrPpM qs, Xq, because the intersection of two closed sets of c again yields a closed set of c. One sees that ďP “ Ě. As a generating set we take the set of X-irreducible elements t Xi | i P G u for some index set G. Let A, B P crPpM qs and let ăG be a linear ordering on G. Then A ă B if and only if there exists i P G such that i “ mint j P G | pXi Ě A, Xi Ğ Bq or pXi Ğ A, Xi Ě Bq u and Xi Ě B and ‘ is just given by
A ‘ i “ č
Xj X Xi.
Xj ăjĚGAi
Now note that ‘ does not need the closure operator c anymore. This means
that if the computation of c is very costly and the X-irreducible elements (or
a superset thereof) is known, this approach might be much more efficient. In
general, however, it is not known how to efficiently determine the X-irreducible
closed sets of c. But if c is given as the ¨2 operator of a formal context, these
irreducible elements can be determined quickly [
Let G and M be two finite sets and let J Ď G ˆ M . We then call the triple K :“ pG, M, J q a formal context, G the objects of the formal context and M the attributes of the formal context. For g P G and m P M we write g J m for pg, mq P J and say that object g has attribute m.
Let A Ď G and B Ď M . We then define the derivations of A and B to be
t t g u1 | g P G u contains the irreducible elements we are looking for, except M (note that the order relation on pIntpKq, Xq is Ě.) Furthermore, it is possible to omit certain objects g from K without changing IntpKq. Every object g P G can be omitted from K for which the set t g u1 is either equal to M or can be represented as a proper intersection of other sets t g1 u1, . . . , t gn u1 for some elements g1, . . . , gn P G. It is also clear that if there exist two distinct objects g1 and g2 with t g1 u1 “ t g2 u1, that we can remove one of them without changing IntpKq. A formal context for which no such objects exist is called object clarified and object reduced. If K “ pG, M, J q is an object clarified and object reduced formal context, then the
Listing 1.1. Compute the Next Intent of a Formal Context set t t g u1 | g P G u is exactly the set of X-irreducible intents of K, except for the set M .
The algorithm described above now takes the following form when applied to the semilattice pIntpKq, Xq. As index set we choose the set G of object of the given formal context, ordered by ăG. For every object g P G we set xg :“ t g u1. Then the set t xg | g P G u is a generating set of the semilattice pIntpKqzt M u, Xq, which we want to enumerate (since we get the set M for free). For A being an intent of K and g P G we have
A ‘ g :“
č t h u1 X t g u1 t h u1ĚA hăGg and as the first intent we take M . For an intent A Ď M of K we then have to find the maximal object g P G (with respect to ăG) such that A ăg A ‘ g. This is equivalent to g being maximal with t g u1 Ğ A and @h P G, h ăG g : t h u1 Ě A ðñ t h u1 Ě A ‘ g. However, the direction “ùñ” is clear, hence we only have to ensure
All these considerations yield the algorithm shown in Listing 1.1. Of course, the derivations of the form t g u1 should not be computed every time they are needed but rather stored somewhere for reuse.
Let us simplify Listing 1.1 a bit further. If A is an intent of K, then for g P G it is true that
t g u1 Ğ A ðñ g R A1.
t g u1 Ě A ùñ t g u2 Ď A1 ùñ g P A1
Listing 1.2. Simplified version of Listing 1.1 and therefore t g u1 Ě A ðñ g P A1, i. e. t g u1 Ğ A ðñ g R A1. Using this, we can simplify the condition or equivalently to B1 X Gg Ď A1 X Gg, where Gg :“ t h P G | h ăG g u. This leads to the algorithm of Listing 1.2.
Curiously enough, this algorithm is now very similar to Close-by-One. To make this similarity more apparent, let us give a brief description of the algorithm Close-by-One. In contrast to Next-Closure, which enumerates the intents of the formal context K, Close-by-One enumerates the formal concepts of K. These are pairs pC, Dq of sets C Ď G, D Ď M such that C1 “ D and D1 “ C. The set of all formal concepts of K is denoted by BpKq. The formal concepts BpKq of K can be ordered by
pC1, D1q ď pC2, D2q ðñ C1 Ď C2p ðñ D2 Ď D1q.
It turns out that the set pBpKq, ďq forms a (complete) lattice, i. e. an ordered set such that for each set of formal concepts there exists a smallest upper and a largest lower bound. This lattice is also called the concept lattice of K.
Close-by-One now performs a depth-first search in this lattice to compute
all formal concepts of K. Following the description of [
Listing 1.3. Close-by-One [
We can now spot some similarities between the functions next-intent from Listing 1.2 and generate-from. The most striking similarity to note is the occurrence of the same tests in both functions: “B1 X Gg Ď A1 X Gg” in line 4 of Listing 1.2, and “F X Mm Ď D X Mm” in line 11 of Listing 1.3. If we substitute the definitions of the involved variables, these tests get the following form: next-intent: pA X t g u1q1 X Gg Ď A1 X Gg generate-from: pC X t m u1q1 X Mm Ď C1 X Mm So except that we consider sets of objects in the function next-intent and sets of attributes in the function generate-from, both test conditions are the same.
Still, the functions next-intent and generate-from are very different in how they compute the next intent and formal concept, respectively. While next-intent computes for a given intent just a new one, generate-from performs a depth-first search and enumerate all formal concepts of K. 5
We have seen a natural generalization of the Next-Closure algorithm to enumerate elements of a semilattice from a generating set. We have proven the algorithm to be correct and applied it to the standard task of computing the intents of a given formal context, yielding a another algorithm to accomplish this. This algorithm turned out to have a lot of similarity to Close-by-One.
There are still some interesting ideas one might want to look at.
Firstly, a variation of the original Next-Closure algorithm is able to compute the canonical base of a formal context, a very compact representation of its implicational knowledge. It would be interesting to know whether the generalization given in this paper gives more insight into the computation, and therefore into the nature of the canonical base. This is, however, quite a vague idea.
Secondly, the algorithm discussed above to compute the intents of a formal
context enumerates them in a certain order, which might or might not be a
lectic one. Understanding this order relation might be fruitful, especially with
respect to the complexity results obtained recently which consider enumerating
pseudo-intents of a formal context in lectic order [
Thirdly, there exists a variant of the Next-Closure algorithm that is able to compute intents of a formal context up to symmetry [8, Theorem 51]. Given a set Γ of automorphisms of a formal context, this variant is able to compute for each orbit of intents under Γ exactly one representative. It would be interesting to know whether we can find a variant of our generalized Next-Closure algorithm that accomplishes the same thing.
Finally, and more technically, it might be interesting to look for other
applications of our general algorithm. As already mentioned in the introduction,
the enumeration of fuzzy concepts of a fuzzy formal context might be worth
investigating (and it might be interesting comparing it to [
The author is grateful for the useful comments of the anonymous reviewers, especially for pointing out the similarity of Listing 1.1 to Close-by-One, which the author had overlooked.