[MUSIC] We're now going to explain an algorithm that computes closed sets in lectic order. But first let's introduce some notation. Suppose that we have a set of attributes and mi which is an attribute from m. So we define a+mi as follows. Keep in a only those attributes that are smaller than mi. Remember, all our attributes are linearly ordered. So we're keep in A all the attributes that are smaller than mi. Then we add mi and we take the closure. So this is what we call A plus mi. So basically we take a prefix of A up to mi, then we add mi and we take the closure. This is A plus mi. Let me give an example. So suppose that A is a, c, d, f and mi attribute is e. So if we use our binary presentation then a, c, d, f can be represented by this cross row. So we can represent a, c, d, f as a cross row. We'll have a cross at the first position because this set contains a. We'll have a dot at the second position because it doesn't contain b and so on. And we want to compute A plus mi where mi is e. So we want to compute A plus e. The arrow point of the position of e. So this set a, c, d, f, it doesn't contain e. The first thing we need to do is to remove all attributes that are greater than e. So that's we get here. So we can give in to section of a, c, d, f with all the areas preceeding e with a, b, c, d. And we get a, c, d, as a result. And then, we add the attribute mi which is e and we take its closure and that's going to be a, c, d, f plus e. Well, we haven't specified the closure operator. So, we can't compute any further right now. But, well, the answer is going to be like this. It's A + e = {a,c,d,e]. And now there's a crucial theorem that makes it possible to enumerate closed sets in lectic order. So what it says is that if you have a set A. And we want to compute a closed set that follows a lectic order, then this set is going to be A plus mi where mi is the largest attribute, such that A is mi less than A plus mi. So I'm going to prove it now, but let me explain it a little bit. So what is A plus mi? Remove from A all attributes that are smaller than mi, we'll add mi, and we compute the closure. And then we want a to be mi smaller than this closure. When does it happen? It happens if and only if, this closure contains no element, that is more than mi. So, this theorem says that we can find the lectical next closed set of the A by finding an mi, such that, when we remove from A all attributes greater than mi and then add mi to A, and take the closure. This closure will not contain any new elements that are smaller than mi. So let's prove it. Let B be the lectically smallest closed set after A. We want to prove that B's of the form A plus mi for some mi such that A is mi less than B. Well first of all, because B is lectically greater than A, there must be some attribute mi such that A is mi less than B. But this means that all elements from A that are smaller than mi belong to B and mi also belongs to B. So this set, A intersection m1 mi minus one, U and MI. This is a subset of B. Okay. What's the lectically smallest set that contains this subset? Of course, it is A plus mi because A plus mi is just the closure of this set. So we have that a is less than a plus mi and a plus mi is less than b. Or less than or equal to b. A plus mi and b are both closed. And we say that b is the lectical smallest closet set after a so it must be that a plus mi is in fact, equal to B. So, what we've just proved is that Bs of the form A plus MI for some MI such that A is MI less than B but we'll also need to prove that MI is the largest element satisfying this property. So suppose that they graph two elements, mi and mj, such that A is mi less than a plus mi, and a is also mj less than a plus mj. I will also assume that mj is smaller than mi. Well then by a proposition that was stated earlier, a plus mi must be smaller lectically smallert than A plus mj. And so this shows that the lectically smaller set of A is the one for which mi is the largest. So it's define properly. And so this completes the proven theory. Right, so let's use the theorem to give an algorithm that enumerates all closed sets for an arbitrary closure operator. So we have a closure operator that maps a set X to X double prime where X is subset of some finite linearly ordered set M. On which we have this close operator defined. And we want to output all close set in lectic order. So the overall structure of the algorithm is very simple. We start by computing the lectical first closure A, output it and then we call another procedure which we'll define next called Next Closure. And this procedure takes A and it returns the lectical next closed set after A. Using the theory we just proved. And at some point it will generate the maximal closed set. M, and then with infinite returns this bottom symbol, or null over there. So it somehow tells us that no goal sets remain to be generated. While this is not the case, we complete generating them. As soon as we've generated all of them, we stop. Right, so this is the overall structure. Now let's look at these two sub procedures, first closure and next closure. Well, first closure is really simple. It simply computes the closure of the empty set, and that's it. This is the lectical of the first close set. Well, next closure must find the maximal m, the maximum attribute m such that A is m less than A plus m. And as soon as it finds this m, it knows that a plus m is the next close after a. So we go through all m in reverse order. We start with the maximal attribute and then go to the preceding one and then to another preceding one and so on. Well there may be two cases for each such attribute. If m is already part of A, then we simply remove it from A. Because if nothing happens, the set will not change. If however the attribute is not in m, then we form the union of a and m and take the closure of this unit. This is going to be b. And this B is in fact A plus m. Why so? Because what is A plus M? We'll take all attributes that are greater than M and remove them but we've done it before at the previous situations for our loop. So, what remains in A at that moment, at this particular moment, are only attributes that are smaller than M. And then we take the course. So this is in fact b at this point is a plus n. And now we have to check if a is m less than b. So we have to check if b minus a contains an element less than m. If it does contain an element less than m, then m is not the smallest element in which B and A differ. And so A is not M less than B. But if B minus A contains no element less than M, then A is indeed M less than B. And so by the theorem B is the lectically next closed set and we return it. Well, if we go through all attributes and we don't find anything that return and wer think now that there are no more closed elements to be generated. Well, this is the algorithm so let's look at how it works in practice. [MUSIC]