[MUSIC] We will now study a more efficient algorithm for generating all closed sets of a given closure operator. This algorithm will generate sets in a certain order, which we'll call "lectic". Let's introduce it first. Suppose that M is a finite set whose elements are linearly ordered, that is, we can assign a distinct number to each element so that an element with a smaller number is less than an element with a larger number. We assume that m1 is less than m2 and so on. Now, every subset S of M can be represented by a bit vector, a vector of ones and zeroes, in such a way that the vector has one at position no. i if and only if attribute m_i is in S. We call such vector the characteristic vector of S. For example, if we work with attributes a, b, c, d, e, f, g ordered alphabetically, then the characteristic vector of {a, c, d, f} is 1011010. We can write crosses instead of ones and blanks instead of zeros, as we do in cross-tables representing formal contexts. Now, let's use the linear order on attributes to define a linear order on attribute subsets. So far, we have only partial order on attribute subsets, the containment order: a set is less than or equal to another set if it is its subset. The linear order we're about to define is going to be the extension of this containment order, that is, a set will always be greater than all its proper subsets. So this is the definition of this linear order, which we call "lectic". A set A is lectically smaller than B if the smallest element in which A and B differ belongs to B. In other words, there is attribute i contained in B, but not in A, such that every attribute strictly smaller than i belongs to both A and B or neither of them. Note that this definition is indeed compatible with the containment order: if A is a proper subset of B, it must be lectically smaller than B, because all the attributes in which they differ belong to B. For example, {a, c, e, f} is lectically smaller than {a, c, d, f}, because the first element in which they differ, d, belongs to {a, c, d, f}. Note that this order is precisely the natural order on characteristic vectors. If we interpret characteristic vectors as natural numbers in binary encoding, then the lectic order is just the usual "less than order" on numbers: {a, c, e, f} simply corresponds to a smaller number than {a, c, d, f}. We'll also use the following notation. We say that A is m-less than B if m is the smallest attribute in which A and B differ and it belongs to B. Let's state two properties that we'll need later. First, A is lectically smaller than B if and only if it is m-less than B for some attribute m. Well, if A is lectically smaller than B, the smallest element in which they differ belongs to B and, if we denote this element by m, we'll get that A is m-less than B. Second, suppose that A is m-less than B and n-less than C, and attribute m is less than attribute n. In this case, which is lectically smaller: B or C? Note that A, B, and C contain the same elements up to m, but excluding m. A doesn't contain m, and neither does C, because it agrees with A on all elements smaller than n, and m is smaller than n. However, B contains element m, since A is m-less than B. Therefore, C is lectically smaller than B and m is the first element in which they differ. So C is, in fact, m-less than B. [MUSIC]