NextClosures with Constraints Francesco Kriegel Institute of Theoretical Computer Science Technische Universität Dresden, Dresden, Germany francesco.kriegel@tu-dresden.de Abstract. In a former paper, the algorithm NextClosures for computing the set of all formal concepts as well as the canonical base for a given formal context has been introduced. Here, this algorithm shall be generalized to a setting where the data-set is described by means of a closure operator in a complete lattice, and furthermore it shall be extended with the possibility to handle constraints that are given in form of a second closure operator. As a special case, constraints may be predefined as implicational background knowledge. Additionally, we show how the algorithm can be modified in order to do parallel Attribute Exploration for unconstrained closure operators, as well as give a reason for the impossibility of (parallel) Attribute Exploration for constrained closure operators if the constraint is not compatible with the data-set. Keywords: Formal Concept Analysis, Implication, Canonical Base, Con- straint, Closure Operator, Parallel Computation, Parallel Exploration 1 Introduction Recently, in [18, 20] a parallel algorithm for the computation of canonical bases (and the set of formal concepts as a byproduct) for formal contexts has been introduced. Furthermore, in [18, 19] some extensions have been provided that allow for the parallel exploration of canonical bases by means of experts. However, not all data-sets occurring in practical applications can efficiently be described as a formal context. Henceforth, it can be useful to describe a generalization of the NextClosures algorithm which allows to compute canonical bases for implications valid in a closure operator in a complete lattice. Of course, powersets are always complete lattices, and the composition of the two derivation operators of a formal context is a closure operator in the powerset lattice – hence this is indeed a generalization. Since the algorithm proceeds in a level-wise order that is compatible with the set-theoretic subset ordering, the generalization presupposes a strict order-homomorphism of the underlying lattice into the ordered set (N, ≤) of the natural numbers with their usual ordering (called a quasi-rank function). Furthermore, this paper presents some possible applications, e.g., in Formal Concept Analysis [13], for interpretations in Description Logics [2], and for Pattern Structures [12]. First, the notion of a closure operator in a complete lattice is defined, and it is proven that the set of all closure operators in a fixed complete lattice forms a complete lattice itself. Consequently, it is possible to construct infima and suprema of sets of closure operators. As applications, we discuss what it means for implications to be valid in infima and suprema, and furthermore generalize the notion of C-implications (constrained implications, where C is a closure operator) in [4] from the special case of Formal Concept Analysis to the more general case of closure operators. In [24], Stumme introduced an extension of Ganter’s Attribute Exploration [10, 11] that can handle background knowledge in form of an implication set. A further gen- eralization [9] allows for arbitrary propositional background knowledge. The input data is given as a formal context K = (G, M, I) as well as an implication set L ⊆ Imp(M) that is valid in K. Then by generalizing the notions of pseudo-intents and canonical bases, it is possible to compute a minimal extension of L which is sound and complete for K. This minimal extension is called canonical base of K relative to L. However, it has not been addressed what can be done in the case where L is not valid in K. There are at least two possibilities to handle such cases. One may either compute a base for the implications that are valid in K as well as are entailed by L, or one can compute a base for the constrained implications of (K, L). We will discuss some details here, and provide solutions by utilizing infima and suprema of closure operators in lattices. Higuchi has shown in [16] that the set of all closure operators on a set constitutes a complete lattice. More generally, this is also true for the set of all closure operators in a complete lattice. The order of closure operators is defined as follows: A closure operator φ is smaller than another closure operator ψ if each closure of ψ is also a closure of φ, i.e., if φ is more fine-grained than ψ which means that each closure of ψ can be expressed as an infimum of closures of φ. Furthermore, it is easy to verify that implications are valid in an infimum of two closure operators if, and only if, they are valid in each of the closure operators. The dual case considers implications valid in suprema, which are exactly those implications valid for all models that are closures of all involved closure operators. In general, one may think of infima describing unions of data-sets, and suprema as describing intersections (or mergings) of data-sets. The last case investigated in this document considers the constrained implications. As input two closure operators are necessary, one describing the data-set and the other one describing the constraints to be met. Then a base for all those implications may be computed, for which both premise and conclusion is a closure of the constraining closure operator, and all common closures of both closure operators are models. In particular, we will show an application where we have some implications which have been proven to be correct, and a possibly faulty data-set. As a result, we may construct implications that are compatible with the background knowledge, and furthermore are valid w.r.t. all closures of the data-set which are also models of the background implications. This document is structured as follows. In Section 2, the notion of a closure operator in a complete lattice is defined, and it is shown that the set of all closure operators constitute a complete lattice itself, i.e., we present an order on closure operators as well as give the equations for the corresponding infimum and supremum operations. Then in Section 3, we consider implications in a complete lattice and define the notion of validity w.r.t. closure operators, as well as entailment for implication sets. Next, Section 4 generalizes the parallel NextClosures algorithm from [20] to the case of closure operators (with constraints) in complete lattices. Proofs are ommited, as on the one hand they have already been given in [18], and on the other hand could be generalized from those given in [19, 20] without too much effort. Before finishing this document with some conclusions in Section 6, several possible applications are described, in particular, in Formal Concept Analysis, in Description Logics, and for Pattern Structures. 2 The Complete Lattice of Closure Operators in a Complete Lattice VW Throughout the whole section, we assume that M = (M, ≤, , , >, ⊥) is a complete lattice, i.e., M is a set; ≤ is an order relation V on M, i.e., it is reflexive,Vantisymmetric, and transitive; for each subset X ⊆ M, X is Vthe infimumWof X, i.e., X ≤ x for all x ∈ X, and y ≤ x for all x ∈ X implies y ≤ X; dually, X is the supremum of X; > is the greatest V element and ⊥ is the smallestW element, i.e., ⊥ ≤ x ≤ > for all x ∈ M. We set x ∧ y := {x, y} as well as x ∨ y := {x, y}. For x ∈ M, its (prime) ideal is ↓ x := { y ∈ M | y ≤ x }, and its (prime) filter is ↑ x := { y ∈ M | x ≤ y }. For further information on (complete) lattices, the interested reader is referred to [5, 7, 13, 14]. A closure operator in M is a mapping φ: M → M that is extensive, monotone, and idempotent, cf. [6, 7, 16]. ClOp(M) denotes the set of all closure operators in M. An element x ∈ M is a closure of φ if x = xφ, and we shall denote the set of all closures of φ by Clo(φ). Furthermore, it is well-known that the following statements are equivalent characterizations of a closure operator φ: 1. x ≤ xφ, x ≤ y ⇒ xφ ≤ yφ, and xφφ = xφ, for all x, y ∈ M. 2. x ≤ yφ ⇔ xφ ≤ yφ for all x, y ∈ M. 3. x ∨ yφφ ≤ (x ∨ y)φ for all x, y ∈ M. 4. x ≤ xφ, and (x ∨ y)φ = (xφ ∨ yφ)φ, for all x, y ∈ M. It is easy to verify that the following statements hold for a closure operator φ: 1. (x ∧ y)φ ≤ xφ ∧ yφ for all x, y ∈ M. 2. (xφ ∧ yφ)φ = xφ ∧ yφ for all x, y ∈ M. V A closure system in M is a -closed subset of M. A subset P ⊆ M is a closure system in M if, and only if, { p ∈ P | x ≤ p } = ↑ x ∩ P has a smallest element for all x ∈ M. Then there is a one-to-one correspondence between closure operators and closure systems as follows. For each closure operator in M, the set of its closures is V a closure system in M. Vice versa, if P is a closure system in M, then φP : x → 7 (↑ x ∩ P ) is a closure operator in M. The operations are mutually inverse. It turns out that the set of all closure operators in a complete lattice constitutes a complete lattice itself, see also [16, 23]. Indeed, closure operators can be ordered by , where φ  ψ if Clo(φ) ⊇ Clo(ψ). This condition is equivalent to both φ ◦ ψ = ψ and φ ≤ ψ (w.r.t. pointwise order, i.e., xφ ≤ xψ for all x ∈ M). Obviously, the smallest closure operator is given by the identity mapping ⊥: x → 7 x, and the greatest closure operator is given by the constant c mapping >:bx → 7 >. If Φ is a set of closure operators in M, then its infimum Φ and supremum Φ are given by the following equations: k ^ Φ: x →7 { xφ | φ ∈ Φ }, j ^ and Φ: x → 7 { y | x ≤ y and y = yφ for all φ ∈ Φ }. Of course, all complete lattices are (isomorphic to) a formal concept lattice, cf. [13]. In particular, the lattice of closure operators is isomorphic to the concept lattice of (ClOp(M), ClOp(M), ), but also to the concept lattice of the smaller formal context (ClOp(M), M, C) where φ C x if x is a closure of φ. The corresponding isomorphisms are j ^ φ→7 (↓ φ, Clo(φ)) and (Φ, X) → 7 Φ: x → 7 (↑ x ∩ X). 3 Implications in Closure Operators An implication in M is an expression of the form p → c with premise p ∈ M and conclusion c ∈ M. An element m ∈ M is a model of p → c if p ≤ m implies c ≤ m. It is valid in φ if all closures of φ are models of p → c, and we shall denote this by φ |= p → c. Furthermore, it can easily be shown that φ |= p → c is equivalent to c ≤ pφ. We shall denote the set of all implications in M by Imp(M). For an implication set L ∪ {p → c} ⊆ Imp(M), we say that L entails p → c, symbolized as L |= p → c, if each model of L, i.e., each model of all implications in L, is a model of p → c. For each element x ∈ M, there is a smallest element xL W above x that is a model of L, and the corresponding closure operator satisfies xL = { xL,n | n ≥ 1 } where _ xL,1 := x ∨ { c | ∃p: p → c ∈ L and p ≤ x }, and xL,n+1 := (xL,1)L,n for each n ∈ N. Then, L entails p → c if, and only if, c ≤ pL. Additionally, we define a similar closure operator L∗ where p ≤ x is replaced with p x in the definition of xL,1. For an implication set L, we symbolize by Lk the subset consisting of all implications from L the premises of which have a quasi-rank not exceeding k. A pseudo-closure of φ is an element p ∈ M which is not a closure of φ, but contains the closure of each strictly smaller pseudo-closure. PsClo(φ) denotes the set of all pseudo- closures of φ, and then Bcan(φ) := { p → pφ | p ∈ PsClo(φ) } constitutes an implicational base for φ, i.e., for all implications p → c ∈ Imp(M), φ |= p → c if, and only if, Bcan(φ) |= p → c. We call Bcan(φ) the canonical base of φ, and furthermore it can be shown that it is a minimal implicational base, i.e., there is no base of smaller cardinality. Algorithm 1 can be utilized to compute the canonical base of φ, for which the constraining closure operator ψ must be set to the identity mapping ⊥ that imposes no constraints at all. 3.1 Implications in Infima As we have seen in Section 2, the infimum of two closure operators φ and ψ in a complete lattice M is given as φ f ψ : x → 7 xφ ∧ xψ . The corresponding closure system is the smallest that contains all closures of φ as well as all closures of ψ. Consequently, an implication is valid in the infimum if, and only if, it is valid in both closure operators. For formal contexts K1 and K2, the infimum of their intent closure operators can be obtained as the intent closure operator of the subposition K K2 . In general, the infimum 1 somehow corresponds to the union of two data-sets. Using the infimum operation it is furthermore possible to construct implicational bases from streams. Suppose that (φn)n∈N is a sequence of closure operators in M such that φn is only available at time point n, i.e., we do not have access to the whole sequence at once, but only to the most recent closure operator. However, for each time point n ∈ N, it is desired to have a base for the implications that are valid in all closure operators φ` with ` ≤ n. This can easily be achieved as follows: 1. Set B0 := Bcan(φ0). 2. Set Bn+1 := Bcan(Bn f φn+1) for each n ∈ N. cn By construction, then each Bn is an implicational base for `=0 φ` , i.e., for the implications which are valid in φ0, . . . , φn. 3.2 Implications in Suprema Consider two closure operators φ and ψ in a complete lattice M. Then, their supremum φ g ψ maps each element x ∈ M to the smallest element of M that is greater than x, and both a closure of φ and ψ. The corresponding closure system is the smallest that contains the intersection Clo(φ) ∩ Clo(ψ). Hence, the supremum corresponds to the intersection (or merging) of data-sets. An implication is valid in φ g ψ if, and only if, it has all common closures of φ and ψ as models. Note that there may be implications valid in φ g ψ which are neither valid in φ, nor valid in ψ. 3.3 Constrained Implications As a special case of implications being valid in a supremum, we consider so-called constrained implications. This notion has first been defined by Belohlávek and Vychodil in [4] for formal contexts. Consider a formal context K = (G, M, I) and a closure operator C on M, then a C-implication over M is an implication the premise as well as the conclusion of which are closures of C. Furthermore, a C-implication is valid in K if it has as models all intents of K that are closures of C. We can generalize this to the case of closure operators in complete lattices as follows. Again, suppose that φ and ψ are closure operators in a complete lattice M. We then call the pair (φ, ψ) a closure operator with constraint where φ is the constrained, and ψ is the constraining closure operator. An implication p → c is constrained by ψ if both its premise p and conclusion c are closures of ψ. Furthermore, p → c is valid in (φ, ψ) if it has all closures of the supremum φ g ψ as models, i.e., if φ g ψ |= p → c. In order to construct bases for constrained implications in a closure operator with constraint, we shall adapt the notions of pseudo-closures and the canonical base accordingly. An element p ∈ M is a pseudo-closure of (φ, ψ) if p is not a closure of φ, but a closure of ψ, and furthermore qφgψ ≤ p for all pseudo-closures q p of (φ, ψ). Then, the set Bcan (φ, ψ) := { p → pφgψ | p ∈ PsClo(φ, ψ) } is a minimal implicational base of (φ, ψ) where PsClo (φ, ψ) denotes the set of all pseudo-closures of (φ, ψ). Comparing the two approaches for computing implications in a supremum, the first one in Section 3.2 only restricts the possible models, in particular, only closures of φ are considered that are also closures of ψ. The second approach in Section 3.3 also imposes constraints on the implications, i.e., only implications are considered where both premise and conclusion are closures of ψ. 4 A Generalized NextClosures Algorithm Let M be a complete lattice. Throughout the whole section, we assume that there is a strict order-preserving function |·|: (M, ≤) → (N, ≤), i.e., x y implies |x| |y| for all x, y ∈ M. W.l.o.g. |⊥| = 0. (If |⊥| = n for n > 0, then || · ||: x →7 |x| − n is also a strict order-homomorphism, and ||⊥|| = 0.) Then | · | is a quasi-rank function on (M, ≤), and we say that an element x ∈ M has quasi-rank |x|. In particular, for all graded complete lattices, the corresponding rank function |·| is a quasi-rank function such that furthermore |x|+1 = |y| if x is a lower neighbor of y. For our purposes, we do not need the additional property that the ranks of neighboring elements only differ by an amount of 1. Consider two closure operators φ and ψ in M. Then the set containing all closures of φ g ψ and all pseudo-closures of (φ, ψ) is a closure system in M, and the corresponding ∗ ∗ closure operator is (φ, ψ) := Bcan (φ, ψ) . Our aim is to find an automatic method for ∗ constructing all closures of (φ, ψ) . The following Algorithm 1 has been introduced in [18], and the special case of φ being the intent closure operator induced by a formal context, and the constraining closure operator ψ being the identity ⊥ (i.e., no constraints are given), has been handled in [20]. The proof is left out here, as it can be found in [18], or can be generalized from the proof in [20]. We will describe Algorithm 1 in the following text. According to the definition of a pseudo-closure, for all elements p ∈ M, it suffices to know all strictly smaller pseudo-closures q p in order to correctly determine whether p is pseudo-closed. Hence, we may compute them in a level-wise approach w.r.t. increasing quasi-rank, since if we have computed all pseudo-closures q where |q| |p|, then we can find those pseudo-closures with q p among them. In particular, if L is a set of ψ-implications that contains exactly all implications p → pφgψ where p is a (φ, ψ)-pseudo-closure with quasi-rank not exceeding k, and some arbitrary implications ∗ with premise quasi-rank k + 1, then the closure operators (φ, ψ) and L∗ coincide on ∗ ∗ all elements with a quasi-rank of at most k + 1, i.e., |x| ≤ k + 1 implies x(φ,ψ) = xL . Furthermore, it can be proven that the following statements are satisfied: 1. If p ∈ M is a (φ, ψ)-pseudo-closure, then there is neither a φ g ψ-closure nor a (φ, ψ)-pseudo-closure strictly between p and pφgψ . 2. If m ∈ M is a φ g ψ-closure, then the next φ g ψ-closures or (φ, ψ)-pseudo-closures ∗ are of the form n(φ,ψ) for upper neighbors n  m. ∗ ∗ 3. If x, y ∈ M with x y are neighboring (φ, ψ) -closures, then y = z(φ,ψ) for all upper neighbors z  x with z ≤ y. Algorithm 1. NextClosures V W Input: a complete lattice M = (M, ≤, , , >, ⊥) Input: a quasi-rank function | · |: (M, ≤) → (N, ≤) Input: a closure operator with constraint (φ, ψ) in M Initialize: a set I := ∅ Initialize: an implication set L := ∅ Initialize: a candidate set C := {⊥} 1 for k = 0, 1, . . . , |>| do 2 for all c ∈ C with |c| = k do in parallel ∗ 3 if c = cL then 4 if c =6 cφgψ then 5 L := L ∪ {c → cφgψ } 6 I := I ∪ {cφgψ } 7 C := C ∪ { d | cφgψ ≺ d } 8 else ∗ 9 C := C ∪ {cL } 10 Wait for termination of all parallel processes. Output: the set I of all (φ, ψ)-closures Output: the canonical base L of (φ, ψ) Algorithm 1 manages a set C of candidates, an implication set L, and a set I of closures. Initially, ⊥ is the only candidate in C. Algorithm 1 is in state k if it has processed all candidates with a quasi-rank ≤ k, but none of quasi-rank > k. In state k, Ck denotes the set of candidates, Lk denotes the implication set, and Ik denotes the set of closures. It can be shown that the following invariants are always satisfied during Algorithm 1’s run: 1. Ck contains all pseudo-closures of (φ, ψ) with quasi-rank k + 1, and all closures of φ g ψ with quasi-rank k + 1 that are not already contained in Ik . 2. Ik contains exactly all closures of φ g ψ with a quasi-rank not exceeding k. 3. Lk contains exactly all implications p → pφgψ for which the premise p is a pseudo-closure of (φ, ψ) with a quasi-rank of at most k. ∗ 4. Between the states k and k + 1, the closure operators (φ, ψ) and L∗ coincide on all elements with quasi-rank k + 1, i.e., an element with quasi-rank k + 1 is either a closure of φ g ψ or a pseudo-closure of (φ, ψ) if, and only if, it is a closure of L∗. As a consequence, we obtain that in the final state |>|, Algorithm 1 outputs the set of all closures of φ g ψ as well as the canonical base of (φ, ψ). 4.1 A Generalized Parallel Attribute Exploration As an extension, we suppose that the given closure operator only describes a part of the data-set, and furthermore there is an expert available (very much in the same way as for Attribute Exploration [10, 11] in the case of Formal Concept Analysis). The exploration of a closure operator in a lattice is explained in full detail in [18], and the special case of exploring a formal context is considered in [19] (including extensive proofs). However, we will give a short summary here. An expert in a lattice M is a partial mapping χ: Imp(M) →p M such that the following conditions hold: 1. If χ(p → c) is defined, then the value is a counterexample against p → c, i.e., χ(p → c) = m implies p ≤ m and c ≤ 6 m. 2. If χ(p → c) is undefined, then all counterexamples of χ are models of p → c, i.e., whenever χ(q → d) = m, then p ≤ m implies c ≤ m. We say that χ accepts p → c if it does not provide a counterexample against p → c, i.e., χ(p → c) is undefined, and that χ refutes p → c otherwise. Furthermore, χ is induced by a closure operator φ if for all implications p → c, χ(p → c) is undefined if, and only if, p → c is valid in φ. The expert χ is optimal if it accepts p → c ∧ x whenever it refutes p → c with counterexample x. For an arbitrary expert χ, it is always possible to construct an optimal expert χ b that accepts the same implications as follows: Let p → c be an implication. Then χ b accepts p → c if χ accepts p → c. Otherwise, let c0 := c and n := 0. While χ rejects cn with counterexample Vn xn, set cn+1 := cn ∧ xn, and increase n. Eventually, define χ b(p → c) := k=0 xk . As input the generalized Parallel Attribute Exploration requires a closure operator φ, an expert χ, as well as an implication set L in M, such that there is an inaccessible closure operator δ describing the domain of interest where χ is induced by δ, δ  φ, i.e., Clo(φ) ⊆ Clo(δ), and L is valid in δ. W.l.o.g. we may assume that χ is optimal. The goal is to compute an implicational base for the domain closure operator δ by utilizing the background knowledge L, and querying the expert χ. In order to insert new closures into the closure operator φ, we define an operation ↓: ClOp(M) × M → ClOp(M) by φ ↓ x := φ f ρx where ρx(m) := x if m ≤ x, and ρx(m) := > otherwise. It is readily verified that φ ↓ x is the greatest closure operator below φ that has x as a closure. Then x |= y → yφ implies yφ ↓ x = yφ. Furthermore, if x is a model of all implications p → pφ where p is a pseudo-closure of (φ, L) with |p| ≤ k, then the pseudo-closures of (φ, L) and (φ ↓ x, L) with a quasi-rank of at most k are the same. As a corollary, we get that then also the canonical bases of (φ, L) and (φ ↓ x, L) co- incide for the implications the premises of which have a quasi-rank not exceeding k. By an inductive application, it follows that Bcan(φ, L)k = Bcan((φ ↓ x1, . . . , xn), L)k if each xi is a model of Bcan(φ, L)k . This fact enables us to execute a parallel attribute exploration. Algorithm 2. ParallelAttributeExploration V W Input: a complete lattice M = (M, ≤, , , >, ⊥) Input: a quasi-rank function | · |: (M, ≤) → (N, ≤) Input: a closure operator φ in M Input: an expert χ in M Input: a set L of background implications that are valid in φ Initialize: an implication set B := ∅ Initialize: a candidate set C := {⊥} 1 for k = 0, . . . , |>| − 1 do 2 for all c ∈ C with |c| = k do in parallel ∗ 3 if c = cB and c = cL then 4 while c = 6 cφ and χ(c → cφ ) = x do 5 φ := φ ↓ x 6 if c = 6 cφ then 7 B := B ∪ {c → cφ } 8 C := C ∪ { d | d  cφ } 9 else ∗ 10 C := C ∪ {cB gL } 11 Wait for termination of all parallel processes. Output: the refined closure operator φ Output: the canonical base B of φ relative to L Algorithm 2 is in state k if it has processed all candidates of a quasi-rank not exceeding k, but none of a greater quasi-rank. Let Ck denote the set of candidates in state k, and let Bk denote the implication set in state k. Furthermore, xk1 , . . . , xnk k denote all counterex- amples provided by the expert between states k and k+1, and φk is the closure operator in state k, i.e., φk ↓ xk1 , . . . , xnk k = φk+1. Then the following statements are always satisfied. 1. Ck contains all pseudo-closures of (φk+1, L) with quasi-rank k + 1. 2. Bk consists of all implications p → pφgψ where p is a pseudo-closure of (φk , L) with a quasi-rank of at most k, i.e., Bcan(φk , L)k = Bk . 3. Between the states k and k + 1, every element with quasi-rank k + 1 is a closure of B∗ if, and only if, it is either a closure of φk+1 g L or a pseudo-closure of (φk+1, L). As a corollary, we infer that in the final state |>|, Algorithm 2 returns a refinement of φ that has the same closures as δ, and a minimal implicational base of δ relative to L, i.e., a minimal superset of L that constitutes an implicational base of δ. Additionally, there is no algorithm that computes a minimal relative implicational base of δ, but poses less questions to χ than Algorithm 2. 4.2 A Problem for the Exploration of Constrained Implicational Bases A further generalization of Algorithm 2 to arbitrary closure operators ψ instead of implication sets L valid in φ is not easily possible. We may only replace L by a closure operator ψ such that ψ  φ, otherwise when receiving counterexamples from the expert, they may not be inserted into the closure operator φ, but must be inserted into the supremum φ g ψ, since we cannot ensure that y(φ ↓ x)gψ = yφgψ if x is a ψ-model of the ψ-implication y → yφgψ . This is due to the fact that the lattice of closure operators is not distributive, and this fact can be proven by means of [22, Lemmata 1 and 2]. 5 Applications In this section, we will present some applications of the generalized NextClosures algorithm. It is trivial that there is an application for Formal Concept Analysis, since the powerset of the attribute set constitutes a complete lattice, and the composition of the derivation operators is a closure operator. Further applications can be found for interpretations in Description Logics, and for Pattern Structures. We will shortly describe each of the cases in the following subsections. 5.1 Application: Formal Concept Analysis For each formal context K = (G, M, I), the mapping II : X → 7 X II is a closure operator in the powerset ℘(M). The closure system induced by II is the set of all intents of K, and thus it is easy to verify that an implication is valid in K if, and only if, it is valid in II. Hence, Algorithm 1 can be utilized to compute both the set of intents of K and the canonical base of K. If furthermore a constraining closure operator C in ℘(M) is given, cf. [4] as well as Section 3.3, then Algorithm 1 is also applicable, and computes all C-intents as well as a base of the C-implications. As a special case, we may consider the case where the constraining closure operator C is given by means of an implication set L ⊆ Imp(M), i.e., C : X → 7 X L assigns to each attribute set X ⊆ M the smallest superset that is a model of L. Then there are two cases to consider: either K |= L, or K |6 = L. First, assume that L is valid in K. Then each intent of K is a model of L, i.e., L  II, and thus II f L = L as well as II g L = II. Consequently, it is uninteresting to consider the infimum or supremum. Furthermore, it can be shown that the canonical base of K with constraint L from Section 3.3 coincides with the canonical base of K relative to L from [9, 24], i.e., is a minimal extension of L which constitutes an implicational base for K. However, both documents [9, 24] have not addressed the remaining case where L is not valid in K. Second, let K |6 = L. Then, an implication is valid in the infimum II f L if, and only if, it is valid in K as well as is entailed by L. This is useful for the case where a sequence (Kn)n∈N of formal contexts is observed, and for each time point n, a base for the subposition of K0, . . . , Kn shall be constructed. Note that this has already been discussed in Section 3.1 for the general case. For the supremum, an implication is valid if, and only if, it has as models all intents of K that are also models of L. Consider the case where K contains faulty objects, e.g., due to wrong observations inserted to K, and where the implication set L has been manually created or verified to ensure that all its implications are valid in the domain of interest. Then, constructing implications that are valid in II g L is a suitable method, since only those intents of K are allowed as models that are already models of L, i.e., satisfy the existing implicational knowledge. A further restriction is imposed by also requiring the premises and conclusions to be models of L, i.e., only considering implications that are L-constrained. For both cases, Algorithm 1 can be used to compute a canonical base in parallel. However, it remains to investigate whether the implications valid in II g L, or the L-constrained implications of K, are more useful in practise. 5.2 Application: Pattern Structures A pattern structure, as introduced by Ganter and Kuznetsov in [12], is a triple (G, (M, u), δ) consisting of a set G of objects, a semi-lattice (M, u) of patterns, and a description function δ : G → M, such that the set { δ(g)|g ∈ G } induces a complete sub- semi-lattice (Mδ , u) of (M, u). Furthermore, then a galois connection between the pow- erset ℘(G) and the pattern lattice (M, v) (where x v y iff xuy = x) is given as follows: l A := { δ(g) | g ∈ A } for all A ⊆ G, d := { g ∈ G | δ(g) v d } for all d ∈ M. A pattern implication is a term x → y where x, y ∈ M, and is valid in (G, (M, u), δ) if x ⊆ y. Since (·, ·) is a galois connection, it follows that the composition · is a closure operator in the lattice of all descriptions. Hence, it is possible to apply the generalized NextClosures algorithm for the case of pattern structures, too, provided that there is a quasi-rank function | · |: (M, v) → (N, ≤). 5.3 Application: Description Logics As a special case of pattern structures, we consider interpretations in Description Logics [2] as input data-sets. First, fix a finite signature (NC , NR ), i.e., NC is a set of concept names, and NR is a set of role names. An interpretation is a pair I = (∆I , ·I ) consisting of a non-empty set ∆I , called domain, and an extension function ·I such that AI ⊆ ∆I for all concept names A ∈ NC , and rI ⊆ ∆I ×∆I for all role names r ∈ NR . An EL⊥-concept description may be built according to the following inductive rule: C ::= ⊥ | > | A | C u C | ∃ r. C. Then, the extension function ·I is extended to all EL⊥-concept descriptions by means of the following definitions: ⊥I := ∅, >I := ∆I , (C u D)I := C I ∩ DI , and (∃ r. C)I := { d ∈ ∆I | ∃e ∈ ∆I : (d, e) ∈ rI and e ∈ C I }. Please note that an implication between concept descriptions is rather called a gen- eral concept inclusion. An implicational base for the closure operator ·II , where the first ·I is the extension mapping, and the second ·I is the model-based most-specific concept description mapping, is a base of GCIs for I, as it has been investigated by Baader and Distel in [1, 8]. The set of all EL⊥-concept descriptions constitutes a bounded lattice. First we define a quasi-order v, the subsumption order, by C v D if C I ⊆ DI for all interpretations I. The corresponding equivalence relation is denoted as ≡. For simplicity, we do not distinguish between equivalence classes and their representatives. The set of all equiv- alence classes is a bounded lattice with the smallest element ⊥, the greatest element >, and where the conjunction u is the infimum operation, and the least common subsumer mapping t is the supremum operation. It is easy to verify that both u and t are compatible with ≡, hence they are well-defined for the equivalence classes. If we do not restrict the role-depth, and use descriptive semantics (as defined above) instead of greatest-fixpoint semantics, then however the lattice of concept descriptions is not complete, as there are infinitely many mutually distinct EL⊥-concept descriptions, e.g., the concept descriptions (∃ r.)n A for n ∈ N, and conjunction is only allowed for a finite number of concept descriptions. It turns out, that this is no restriction for the application of Algorithm 1, since for finite interpretations (i.e., with a finite domain), the canonical base is finite, and hence for the computation of closures w.r.t. the current implication set in Algorithm 1 only finitary suprema are necessary. For defining a quasi-rank function, we may first observe that the dual lattice of EL⊥-concept descriptions is well-founded, i.e., there are no infinite strictly ascending chains C0 v C1 v C2 v . . ., cf. Baader and Morawska in [3, Proposition 3.5]. Hence, p p p a quasi-rank function could be defined by |C| := n where n is the maximal length of a chain starting at C and ending at >. Since each concept description has only finitely many subsumers (for a finite signature), there are only finitely many mutually distinct chains in the interval [C, >], and thus | · | as above is well-defined. For the same reason, the set of upper neighbors of an arbitrary concept description is computable. 6 Conclusion In this document, the NextClosures algorithm has been generalized to arbitrary closure operators in complete lattices, and has been extended to handle constraints that are given in form of another closure operator. Furthermore, some exemplary applications have been presented, e.g., in the field of Formal Concept Analysis, Description Logics, and for Pattern Structures. While some experiments of an implementation specialized to formal contexts as input structures have shown that there is an almost inverse linear correlation between the computation time and the number of available processor cores, experiments for other types of input structures are outstanding. A complexity analysis taking into account the complexities of the lattice operations as well as of the closure operator could be interesting. Acknowledgements The author gratefully thanks the anonymous reviewers for their constructive hints and helpful remarks. References [1] Franz Baader and Felix Distel. “A Finite Basis for the Set of EL-Implications Holding in a Finite Model”. In: Formal Concept Analysis, 6th International Conference, ICFCA 2008, Montreal, Canada, February 25-28, 2008, Proceedings. 2008, pp. 46–61. [2] Franz Baader and Carsten Lutz. “Description Logic”. In: Handbook of Modal Logic. Ed. by Patrick Blackburn, Johan van Benthem, and Frank Wolter. Elsevier, 2006. Chap. 13. [3] Franz Baader and Barbara Morawska. “Unification in the Description Logic EL”. In: Logical Methods in Computer Science 6.3 (2010). [4] Radim Belohlávek and Vilém Vychodil. “Formal Concept Analysis with Constraints by Closure Operators”. In: Conceptual Structures: Inspiration and Application, 14th International Conference on Conceptual Structures, ICCS 2006, Aalborg, Denmark, July 16-21, 2006, Proceedings. 2006, pp. 131–143. [5] Garrett Birkhoff. “Lattice theory”. In: Colloquium Publications. 3rd ed. Vol. 25. Amer. Math. Soc., 1967. [6] Nathalie Caspard and Bernard Monjardet. “The Lattices of Closure Systems, Closure Operators, and Implicational Systems on a Finite Set: A Survey”. In: Discrete Applied Mathematics 127.2 (2003), pp. 241–269. [7] Brian A. Davey and Hilary Ann Priestley. Lattices and Order. 2nd ed. Cambridge University Press, Apr. 2002. [8] Felix Distel. “Learning description logic knowledge bases from data using methods from formal concept analysis”. PhD thesis. Dresden University of Technology, 2011. [9] Bernhard Ganter. “Attribute Exploration with Background Knowledge”. In: Theor. Comput. Sci. 217.2 (1999), pp. 215–233. [10] Bernhard Ganter. Two Basic Algorithms in Concept Analysis. FB4-Preprint 831. Darmstadt, Germany: Technische Hochschule Darmstadt, 1984. [11] Bernhard Ganter. “Two Basic Algorithms in Concept Analysis”. In: Formal Concept Analysis, 8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010. Proceedings. 2010, pp. 312–340. [12] Bernhard Ganter and Sergei O. Kuznetsov. “Pattern Structures and Their Projections”. In: Conceptual Structures: Broadening the Base, 9th International Conference on Conceptual Structures, ICCS 2001, Stanford, CA, USA, July 30-August 3, 2001, Proceedings. 2001, pp. 129–142. [13] Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foundations. 1st ed. Springer, Dec. 1999. [14] George Grätzer. General Lattice Theory. 2nd ed. Birkhäuser Verlag, 1998. [15] Jean-Luc Guigues and Vincent Duquenne. “Famille minimale d’implications informatives résultant d’un tableau de données binaires”. In: Mathématiques et Sciences Humaines 95 (1986), pp. 5–18. [16] Akira Higuchi. “Lattices of closure operators”. In: Discrete Mathematics 179.1-3 (1998), pp. 267–272. [17] Francesco Kriegel. Concept Explorer FX. Software for Formal Concept Analysis, available at https://github.com/francesco-kriegel/conexp-fx. 2010–2016. [18] Francesco Kriegel. NextClosures – Parallel Exploration of Constrained Closure Operators. LTCS-Report 15-01. Dresden, Germany: Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, 2015. [19] Francesco Kriegel. “Parallel Attribute Exploration”. In: Graph-based Modeling of Con- ceptual Structures - 22nd International Conference on Conceptual Structures, ICCS 2016, Annecy, France, July 5-7, 2016, Proceedings. 2016. [20] Francesco Kriegel and Daniel Borchmann. “NextClosures: Parallel Computation of the Canonical Base”. In: Proceedings of the 12th International Conference on Concept Lattices and Their Applications (CLA 2015), Clermont-Ferrand, France, October 13-16, 2015. 2015, pp. 181–192. [21] David Maier. The Theory of Relational Databases. Computer Science Press, 1983. [22] José Morgado. “Note on the distributive closure operators of a complete lattice”. In: Portugaliae Mathematica 23 (1964), pp. 11–25. [23] Sebastian Rudolph. “On the Succinctness of Closure Operator Representations”. In: Formal Concept Analysis - 12th International Conference, ICFCA 2014, Cluj-Napoca, Romania, June 10-13, 2014. Proceedings. 2014, pp. 15–36. [24] Gerd Stumme. “Attribute Exploration with Background Implications and Exceptions”. In: Data Analysis and Information Systems. Ed. by Hans-Hermann Bock and Wolfgang Polasek. Studies in Classification, Data Analysis, and Knowledge Organization. Springer, 1996, pp. 457–469. [25] Marcel Wild. “A Theory of Finite Closure Spaces Based on Implications”. In: Advances in Mathematics 108.1 (1994), pp. 118 –139.