Membership Constraints in Formal Concept Analysis

1 Introduction

Conceptual Knowledge Processing and Representation is a particular approach to knowledge management, acknowledging the constitutive role of thinking, arguing and communicating human beings in dealing with knowledge and its processing. The term processing also underlines the fact that obtaining or approximating knowledge is a process which should always be conceptual in the above sense. The methods of Conceptual Knowledge Processing have been introduced and discussed by Rudolf Wille in [Wille, 2006], based on the pragmatic philosophy of Charles Sanders Peirce, continued by Karl-Otto Apel and J¨urgen Habermas.

Wille defines Conceptual Knowledge Processing as an applied discipline dealing with knowledge which is constituted by conscious reflexion, discursive argumentation and human communication on the basis of cultural background, social conventions and personal experiences. Its main aim is to develop and maintain formal methods and instruments for processing information and knowledge which support rational thought, judgment and action of human beings and therewith promote critical discourse (see also [Wille, 1994; 1997; 2000]).

The mathematical theory underlying Conceptual Knowledge Processing is Formal Concept Analysis, providing a powerful and elegant mathematical tool for understanding and investigating knowledge, based on a set-theoretical semantics, comprising methods for representation, acquiring, and retrieval of knowledge, as well as for further theory building in several other domains of science.

Formal Concept Analysis (FCA) appeared at the end of the 1980's in order to restructure classical lattice theory into a form that is suitable for applications in data analysis. The fundamental data structure FCA uses is a formal context, which exploits the fact that data is quite often represented by incidence structures relating objects and attributes. FCA provides also a mathematization of the traditional, philosophical understanding of a concept as a unit of thought consisting of an extent (the set of objects falling under the concept) and an intent (the set of attributes characterizing the concept). Using mathematical operations, concepts are computed from the object-attribute data table. They can be naturally ordered, resulting in a conceptual hierarchy, called concept lattice. The entire information stored in a formal context is preserved by this operation and the concept lattice is the basis for further data analysis. It can be represented graphically in order to allow navigation among concepts, as well as to support communication. Different algebraic methods can be used in order to study its structure and to compute data dependencies. FCA also provides elegant methods to significantly reduce the effort of mining association rules.

Classical FCA was extended by Wille and Lehmann to the triadic case, featuring a ternary (objects vs. attributes vs. conditions) instead of a binary (objects vs. attributes) incidence relation [Lehmann and Wille, 1995], leading to the notions of tricontext and triconcept. This extension has been successfully used in inherently triadic scenarios such as collaborative tagging [J¨aschke et al., 2008].

Nevertheless, if the number of concepts is very large, a holistic graphical representation may become inefficient and unwieldy. Note that the number of concepts may be exponentially in the size of the underlying (tri)context.

Hence, a way of narrowing down the set of "interesting" concepts by specifying criteria appears as a crucial feature of conceptual knowledge management applications, in order to focus exactly on the data subset one is interested to explore or start exploration from. As a straightforward form of such criteria, we introduce membership constraints which specify that a formal concept's extent or intent must include certain elements and exclude others. The question of satisfiability of such membership constraints, i.e., to determine if there exists at all a formal concept is the starting point of our current research. In this paper, we analyze the computational complexity of this problem, both for the classical dyadic case and for higher arity generalizations of FCA, first for triadic data sets and then for the n-adic case. Moreover, we also discuss a generic answer set programming (ASP) encoding of membership constraint problems, which allows for deploying available highly optimized ASP tools for its solution. Finally, we turn our attention to the question wherefrom the entire problem setting started, namely we discuss the importance of membership constraints in the context of navigational approaches to data analysis and provide some conclusions of our work.

2 Preliminaries

2.1 Formal Concept Analysis

In the following, we briefly sketch some basic notions about FCA. For more, please refer to [Ganter and Wille, 1999].

Definition 1. A formal context is a triple K = (G,M, I) with G and M being sets called objects and attributes, respectively, and I ⊆ G × M the binary incidence relation where gIm means that object g has attribute m.

Finite formal contexts can be represented as cross-tables, the rows of which are representing objects, the columns attributes, while the incidence relation is represented by crosses in that table.

Definition 2. For a set A ⊆ G of objects we define the derivation operator AI := {m | gIm for all g ∈ A} and for a set B ⊆ M of attributes, we analogously define BI = {g | gIm for all m ∈ B}. A formal concept of a context K is a pair (A, B) with extent A ⊆ G and intent B ⊆ M satisfying AI = B and BI = A. We denote the set of formal concepts of the context K by B(K).

An alternative, useful way of characterizing formal concepts is that A × B ⊆ I and A, B are maximal w.r.t. this property, i.e., for every C ⊇ A and D ⊇ B with C ×D ⊆ I must hold C = A and D = B.

Definition 3. If (A,B), (C,D) ∈ B(K), we say that (A,B) is a subconcept of (C,D) (or equivalently, (C,D) is a superconcept of (A,B)), and we write (A,B) ≤ (C,D) if and only if A ⊆ C (⇔ D ⊆ B).

The set B(K) of formal concepts, ordered by the subconcept-superconcept relationship is a complete lattice and can be graphically represented as an order diagram.

F. Lehmann and R. Wille extended in [Lehmann and Wille, 1995] the theory of FCA to deal with threedimensional data. This has been called Triadic FCA (3FCA), where objects are related to attributes and conditions.

Definition 4. A tricontext is a quadruple K = (G,M,B, Y ) with G, M, and B being sets called objects, attributes, and conditions, respectively, and Y ⊆ G ×M × B the ternary incidence relation where (g,m, b) ∈ Y means that object g has attribute m under condition b.

Finite tricontexts can be represented as three-dimensional cross-tables, which are typically displayed in "slices", e.g.:

Definition 5. A triconcept of a tricontext K is a triple (A1,A2,A3) with extent A1 ⊆ G, intent A2 ⊆ M, and modus A3 ⊆ B satisfying A1 × A2 × A3 ⊆ Y and for every C1 ⊇ A1, C2 ⊇ A2, C3 ⊇ A3 that satisfy C1×C2×C3 ⊆ Y holds C1 = A1, C2 = A2, and C3 = A3. We denote by T(K) the set of all triconcepts of K.

With the rise of folksonomies as data structure of social resource sharing systems, triadic FCA was directly applied in the study of folksonomies [J¨aschke et al., 2008]. Efficient algorithms to determine all (or all frequent) triconcepts of a tricontext have been developed. However, a visualization that would be as intuitive as concept lattices for classical FCA has remained elusive for the triadic case. Initial investigations into interactive ways of browsing the space of triconcepts have been made [Rudolph et al., 2015].

2.2 Complexity Theory

We assume the reader to be familiar with complexity theory [Papadimitriou, 1994] and, in particular, the complexity classes AC0 and NP.

We briefly recap that AC0 (problems solvable by Boolean circuits of polynomial size and constant depth) coincides with expressibility by first-order formulae [Immerman, 1999]. It is worth noting that such problems can be solved in logarithmic space.

NP is the class of problems solvable by a nondeterministic Turing machine in polynomial time. We will provide here a traditional, prototypical NP-complete problem, which we will use later to show NP-hardness of certain problems.

problem: 3SAT

input: family L = {L1, . . . ,Ln} of 3-element sets Li of literals of the form p or ¬p.

output: YES in case the Boolean formula ϕL := ∧{ℓ1,ℓ2,ℓ3}∈L(ℓ1 ∨ ℓ2 ∨ ℓ3) is satisfiable, NO otherwise.

Example 1. Consider L = {L1,L2,L3} with L1 = {r, s, ¬q}, L2 = {s, ¬q, ¬r}, and L3 = {¬q, ¬r, ¬s}. The corresponding 3SAT problem amounts to checking if ϕL = (¬q ∨ r ∨ s) ∧ (¬q ∨ ¬r ∨ s) ∧ (¬q ∨ ¬r ∨ ¬s) is satisfiable. The answer is yes, since for the valuation v = {q ↦→ true, r ↦→ false, s ↦→ true} the formula ϕL evaluates to true.

3 Membership Constraints

In this section, we introduce membership constraints for formal concepts. These constraints express which objects and attributes should be part of the concept and which should not.

Definition 6. A membership constraint on a formal context K = (G,M, I) is a quadruple C = (G+,G-,M +,M -) with G+ ⊆ G called required objects, G- ⊆ G called forbidden objects, M + ⊆ M called required attributes, and M - ⊆ M called forbidden attributes.

A formal concept (A,B) of K is said to satisfy such a membership constraint if all the following conditions hold: G+ ⊆ A, G- ∩ A = ∅, M + ⊆ B, M - ∩ B = ∅.

A membership constraint is said to be satisfiable with respect to K, if it is satisfied by one of its formal concepts.

Next we define the decision problem of membership constraint satisfiability (MCSAT).

problem MCSAT

input: formal context K, membership constraint C output: YES if C satisfiable w.r.t. K, NO otherwise.

In the general case, the complexity of the (MCSAT) problem turns out to be intractable.

Theorem 7. MCSAT is NP-complete, even when restricting to membership constraints of the form (∅, G-, ∅,M -)

Proof. NP membership is straightforward: after guessing a pair (A,B) from 2G × 2M , it can be checked in polynomial time if (A,B) is a formal concept of K and if it satisfies C.

We prove NP hardness via a reduction from 3SAT. Given a set L = {L1, . . . , Ln} of propositional literal sets over the set {p1, . . . , pk} of propositional variables, define the formal context KL = (G, M, I) with

• G = L∪P + ∪P - with P + = {p1, . . . , pk} and P - = {¬p1, . . . , ¬pk},
• M = P + ∪P - ∪ ˜ P with ˜ P = {˜ p1, . . . , ˜ pk},

Furthermore, let CL denote the membership constraint (∅,L, ∅, ˜ P ).

Note that both KL and CL can be computed in polynomial time and are of polynomial size with respect to ‖L‖.

We will now show that L is satisfiable exactly if C is satisfiable w.r.t. K.

"⇒": if L is satisfiable there must be a valuation v : {p1, . . . pk} → {true, false} under which L evaluates to true. Let Lv be the set of literals such that p ∈ Lv whenever v(p) = true and ¬p ∈ Lv whenever v(p) = false. We next show that ((P + ∪ P -) \ Lv, Lv) is a formal concept of KL. On one hand we have: ((P + ∪ P -) \ Lv)I = {m ∈ P + ∪ P - | m ̸∈ (P + ∪ P -) \ Lv} ∪ {˜ p ∈ ˜ P | p, ¬p ̸∈ (P + ∪P -)\Lv} = Lv. On the other hand LIv = {Li | Lv ⊆ M \ Li} ∪ {l | l ̸∈ Lv} = ∅ ∪ (P + ∪P -) \ Lv.

Next, we observe that this formal concept satisfies CL, since none of the Li are contained in the extent and none of the ˜ pj are contained in its intent. Therefore, we have found a concept witnessing the satisfiability of CL w.r.t. KL.

"⇐": Assume CL is satisfiable w.r.t. KL. Then there must be a formal concept (A, B) of KL with L ∩ A = ∅ as well as ˜ P ∩ B = ∅. Observe that A must contain one of p or ¬p for each propositional variable p, since otherwise ˜ p ∈ B would hold. Consequently B cannot contain both p and ¬p for any propositional variable p. Moreover, for every Li ∈ L there must be one l ∈ B ∩ (P + ∪ P -) with l ∈ Li. Next, let ˆB := P + ∩B∪{¬p | p ̸∈ B}. By our observation above, we know that B ⊆ ˆB therefore ˆB still contains at least one literal from every Li. On the other hand, ˆB directly corresponds to a valuation v ˆB : {p1, . . . pk} → {true, false} mapping pi to true if pi ∈ ˆB and to false if ¬pi ∈ ˆB. Consequently, v ˆB is a valuation making ϕ true and hence showing that it is satisfiable.

The following example demonstrates the reduction of 3SAT to MCSAT deployed in the previous proof.

Example 2. The 3SAT problem from Example 1 can be reduced to the question if the membership constraint (∅, {L1, L2, L3}, ∅, {˜ q, ˜ r, ˜ s}) is satisfiable in the following context:

When analyzing the problem further it turns out that the simultaneous presence of forbidden objects and forbidden attributes in a membership constraint is the (only) reason for the established intractability. If one of the sets becomes empty, the complexity drops to a very pleasant level.

Theorem 8. When restricted to membership constraints of the form (G+, ∅,M +,M -) or (G+,G-,M +, ∅) MCSAT is in AC0.

Proof. We show the claim for constraints of the form C = (G+, ∅,M +,M -), the other case follows by duality. First observe that (M +I ,M +II ) is a formal concept of K and it is subset-maximal w.r.t. its extent and subset-minimal w.r.t. its intent among all formal concepts whose intent contains M +. Therefore, (G+, ∅,M +,M -) is satisfiable w.r.t. K if and only if it is satisfied by (M +I ,M +II ). By definition, this is the case iff (1) G+ ⊆ M +I and (2) M +II ∩M - = ∅. Statement (1) can be rephrased into the condition G+ × M + ⊆ I, while Statement (2) is equivalent to the condition that for every m ∈ M - there exists some g ∈ (M +)I with (g,m) ̸∈ I.

We now define a first-order-logic interpretation IK,C = (∆, ·I ) over the predicates pG, pM, pG+, pM+, pM- (all unary) and the binary predicate pI as follows: ∆ = G ∪M, for every X ∈ {G,M,G+,M +,M -} we let pIX = X, and pII = I. Obviously, I is an immediate representation of the MCSAT problem. Now the above formulated Statement (1) can be expressed by the first-order formula ϕ1 defined as

while Statement (2) can be expressed by ϕ2 defined as

Consequently, satisfiability of C w.r.t. K coincides with the satisfaction of the fixed first-order-logic formula ϕ = ϕ1 ∧ϕ2 in IK,C. By the corresponding result from descriptive complexity theory [Immerman, 1999], we can conclude that the considered restricted version of MCSAT is in AC0.

Finally, if only required objects or required attributes are given, MCSAT becomes trivial.

Theorem 9. When restricted to membership constraints of the form (G+, ∅, ∅, ∅) or (∅, ∅,M +, ∅) MCSAT is trivially true.

Proof. For the form (G+, ∅, ∅, ∅), note that (G,G′ ) is always a formal concept and always satisfies such a constraint. The other case follows by duality.

4 Membership Constraints in Triadic FCA

Next we define and investigate membership constraints and the corresponding satisfiability problem for the triadic case.

Definition 10. A triadic membership constraint on a tricontext K = (G,M,B, Y ) is a sextuple C = (G+, G-, M +, M -, B+, B-) with G+ ⊆ G called required objects, G- ⊆ G called forbidden objects, M + ⊆ M called required attributes, M - ⊆ M called forbidden attributes, B+ ⊆ B called required conditions, and B- ⊆ B called forbidden conditions A triconcept (A1,A2,A3) of K is said to satisfy such a membership constraint if all the following conditions hold: G+ ⊆ A1, G- ∩ A1 = ∅, M + ⊆ A2, M - ∩ A2 = ∅, B+ ⊆ A3, B- ∩ A3 = ∅.

A triadic membership constraint is said to be satisfiable with respect to K, if it is satisfied by one of its triconcepts.

problem TMCSAT

input: tricontext K, triadic membership constraint C output: YES if C satisfiable w.r.t. K, NO otherwise.

Interestingly, in the triadic case, we find two possible sources for intractability. One of them (two nonempty forbidden sets) is tightly related to the case discussed in the previous section, while the other one (required and forbidden set of the same type) is tractable for classical FCA and becomes intractable only when going triadic.

Theorem 11. TMCSAT is NP-complete, even when restricting to triadic membership constraints of the following forms:

• (∅,G-,∅,M -,∅,∅), (∅,G-,∅,∅,∅,B-), (∅,∅,∅,M -,∅,B-),
• (G+,G-,∅,∅,∅,∅), (∅,∅,M +,M -,∅,∅), (∅,∅,∅,∅,B+,B-).

Proof. NP membership is straightforward: after guessing a triple (A1, A2, A3) from 2G ×2M ×2B , it can be checked in polynomial time if (A1,A2,A3) is a triconcept of K and if it satisfies C.

We proceed by showing hardness for the restricted cases. Given some (dyadic) formal context K = (G,M, I), we define its triadic version T(K) = (G,M, {∗}, I × {∗}). Then, the set of all triconcepts of T(K) is {(G,M, ∅)} ∪ {(A1,A2, {∗}) | (A1,A2) concept of K}. Therefore, every MCSAT problem with context K and constraint (∅, G-, ∅,M -) can be reduced to the TMCSAT problem with tricontext T(K) and (∅,G-, ∅,M -, ∅, ∅). Since the former problem is NP-complete due to Theorem 7, the latter must be NP-hard. By symmetry, this argument carries over to constraints of the form (∅,G-, ∅, ∅, ∅,B-) and (∅, ∅, ∅, M -, ∅, B-).

Next, we show hardness for constraints of the form (G+,G-, ∅, ∅, ∅, ∅). Again, we do so by a reduction from 3SAT. Given a set L = {L1, . . . ,Ln} of propositional literal sets over the set {p1, . . . , pk} of propositional variables, define the tricontext KL = (G, M, B, Y ) with

• G = {∗} ∪L,
• M = {∗, p1, . . . , pk}
• B = {∗, ¬p1, . . . , ¬pk}
• Y = G×M ×B \ ({(∗, pi, ¬pi) | 1 ≤ i ≤ k} ∪{(Lj, pi, ∗) | pi ∈ Lj} ∪ {(Lj, ∗, ¬pi) | ¬pi ∈ Lj})

Furthermore, let CL denote the membership constraint ({∗}, L, ∅, ∅, ∅, ∅).

Note that both KL and CL can be computed in polynomial time and are of polynomial size with respect to ‖L‖.

We will now show that L is satisfiable exactly if C is satisfiable w.r.t. K.

"⇒": if L is satisfiable there must be a valuation v : {p1, . . . pk} → {true, false} under which L evaluates to true. Let Lv be the set of literals such that p ∈ Lv whenever v(p) = true and ¬p ∈ Lv whenever v(p) = false. We next show that (A1, A2, A3) = ({∗}, {∗}∪(Lv ∩M), {∗}∪(Lv ∩ B)) is a triconcept of KL: First, A1 ×A2 ×A3 ⊆ Y , since Lv cannot both contain some pi and ¬pi as it stems from a valuation. We now show that (A1,A2,A3) is also maximal, i.e., no component can be extended while maintaining A1 × A2 × A3 ⊆ Y . Since Lv already contains for every i ∈ {1, . . . , n} either pi or ¬pi, extending A2 or A3 would lead to some i satisfying pi ∈ A2 and ¬pi ∈ A3 which contradicts (∗, pi, ¬pi) ̸∈ Y . It remains to show that A1 cannot be extended. Toward a contradiction, suppose it can, i.e., for some Lj ∈ L holds {Lj} × A2 × A3 ⊆ Y . However, by construction, we know that Lj ∩Lv is non-empty. Assuming there is some pi ∈ Lj ∩ Lv, we conclude pi ∈ A2 and thus (Lj, pi, ∗) ∈ Y which is wrong by construction. Assuming there is some ¬pi ∈ Lj ∩ Lv, we conclude ¬pi ∈ A3 and thus (Lj, ∗, ¬pi) ∈ Y which, again, is wrong by construction. Hence A1 cannot be extended either and (A1,A2,A3) is indeed a triconcept, which obviously also satisfies CL.

"⇐": Assume CL is satisfiable w.r.t. KL. Then there must be a triconcept ({∗}, A2, A3) of KL. Since (∗, pi, ¬pi) ̸∈ Y , we know that for no pi holds pi ∈ A2 and ¬pi ∈ A3 at the same time. On the other hand, by maximality, for every pi one of pi ∈ A2 and ¬pi ∈ A3 must hold. Therefore, we can define a valuation v by letting v(pi) = true whenever pi ∈ A2 and letting v(pi) = false whenever ¬pi ∈ A3. We now show that v is a valuation mapping L to true and thus witnessing satisfiability of L. By assumption, ({∗},A2,A3) is maximal, thus - by maximality of the first component - for every Lj ∈ L must hold that {Lj}×A2 ×A3 ̸⊆ Y . Then, by construction of KL there must be either some pi ∈ Lj with pi ∈ A2 or there must be some ¬pi ∈ Lj with ¬pi ∈ A3. In any case, this means that Lj is mapped to true under v. Since the same argument applies to every Lj ∈ L we find that v is indeed a valuation witnessing the satisfiability of L.

The subsequent example demonstrates the 3SAT to 3MCSAT reduction for the new intractable case.

Example 3. The 3SAT problem from Example 1 can be reduced to the question if the membership constraint ({∗}, {L1,L2,L3}, ∅, ∅, ∅, ∅) is satisfiable in the following tricontext:

This is the case as witnessed by the triconcept ({∗}, {∗, q, s}, {∗, ¬r}).

We finish the section by showing that excluding the critical cases discussed above, we regain tractability. We also identify the cases when the problem becomes trivial.

Theorem 12. TMCSAT is in AC0 when restricting to membership constraints of the forms (∅,G-,M +, ∅,B+, ∅), (G+, ∅, ∅, M -, B+, ∅), and (G+, ∅, M +, ∅, ∅, B-).

Proof. For C of the form (∅,G-,M +, ∅,B+, ∅), note that (GU,M,B) with GU = {g | {g} × M × B ⊆ Y } is a triconcept and for every triconcept (A1,A2,A3) of K hold GU ⊆ A1 and (trivially) A2 ⊆ M as well as A3 ⊆ B. Therefore C is satisfiable w.r.t. K if and only if (GU,M,B) satisfies it. To check the latter, it suffices to check if GU ∩G- = ∅ which amounts to checking if for every g ∈ G- there are m ∈ M and b ∈ B with (g,m, b) ̸∈ Y . This, in turn is equivalent to IK,C satisfying the first-order formula

Again we can invoke descriptive complexity theory [Immerman, 1999] to conclude that the considered restricted version of TMCSAT is in AC0.

AC0 membership for the other forms of C follows by symmetry.

Theorem 13. TMCSAT is trivially true when restricting to membership constraints of the forms (∅, ∅,M +, ∅,B+, ∅), (G+, ∅, ∅, ∅, B+, ∅), or (G+, ∅, M +, ∅, ∅, ∅).

Proof. For the form (∅, ∅,M +, ∅,B+, ∅), note that the triconcept (GU,M,B) with GU = {g | {g} ×M ×B ⊆ Y } satisfies any constraint of this form, thus satisfiability is always ensured. The other cases follow by symmetry.

5 Membership Constraints in n-adic FCA

Classical FCA and triadic FCA can be seen as two instances of a general framework that we call n-adic FCA. We provide the corresponding definitions and observe that the already identified causes of intractability are the only ones also when increasing the arity of the incidence relation further.

Definition 14. An n-context is an (n+1)-tuple K = (K1, . . . ,Kn,R) with K1, . . . ,Kn being sets, and R ⊆ K1 × . . . ×Kn the n-ary incidence relation.

An n-concept of an n-context K is an n-tuple (A1, . . . , An) satisfying A1 × . . . × An ⊆ R and for every n-tuple (C1, . . . ,Cn) with Ai ⊇ Ci for all i ∈ {1, . . . , n}, satisfying C1 ×. . .×Cn ⊆ R holds Ci = Ai for all i ∈ {1, . . . , n}.

Definition 15. A n-adic membership constraint on a ncontext K = (K1, . . . ,Kn,R) is a 2n-tuple C = (K+ 1 ,K1 , . . . ,K+ n ,Kn ) with K+ i ⊆Ki called required sets and Ki ⊆Ki called forbidden sets.

An n-concept (A1, . . . ,An) of K is said to satisfy such a membership constraint if K+ i ⊆ Ai and Ki ∩Ai = ∅ hold for all i ∈ {1, . . . , n}.

An n-adic membership constraint is said to be satisfiable with respect to K, if it is satisfied by one of its n-concepts.

problem nMCSAT

input: n-context K, n-adic membership constraint C

output: YES if C satisfiable w.r.t. K, NO otherwise.

It turns out that the triadic case exhibits all necessary information needed to settle the general case, taking into account some straightforward adaptations, hence the following theorem is immediate.

Theorem 16. For a fixed n > 2, the nMCSAT problem is

• NP-complete for any class of constraints that allows for
• the arbitrary choice of at least two forbidden sets or
• the arbitrary choice of at least one forbidden set and the corresponding required set,
• in AC0 for the class of constraints with at most one forbidden set and the corresponding required set empty,
• trivially true for the class of constraints with all forbidden sets and at least one required set empty.

6 Encoding in Answer Set Programming

Given that satisfiability of membership constraints can in general be NP-complete, it is nontrivial to find efficient algorithms. We note here that the problem can be nicely expressed with answer set programming (ASP, see for instance [Gebser et al., 2012]). We will demonstrate this for the n-adic case. Assuming the specific problem is given by the following set of ground facts FK,C:

· seti(a) for all a ∈ Ki, · rel(a1, . . . , an) for all (a1, . . . , an) ∈ R, · requiredi (a) for all a ∈ K+ i , and · forbiddeni(a) for all a ∈ Ki .

Let P denote the following fixed answer set program (with rules for every i ∈ {1, . . . , n}):

ini(x) ← seti(x) ∧ ∼outi(x) outi(x) ← seti(x) ∧ ∼ini(x) ← ∧j∈{1,...,n} inj(xj) ∧ ∼rel(x1, . . . , xn) exci(xi) ← ∧j∈{1,...,n}\{i} inj (xj ) ∧ ∼rel(x1, . . . , xn) ← outi(x) ∧ ∼exci(x) ← outi(x) ∧ requiredi (x) ← ini(x) ∧ forbiddeni(x)

Intuitively, the first two lines "guess" an n-concept candidate by stipulating for each element of each Ki if they are in or out. The third rule eliminates a candidate if it violates the condition A1 × . . . × An ⊆ R, while the fourth and fifth rule ensure the maximality condition for n-concepts. Finally, the sixth and the seventh rule eliminate n-concepts violating the given membership constraint.

There is a one-to-one correspondence between the answer sets X of FK,C ∪ P and the n-concepts of K satisfying C obtained as ({a | in1(a) ∈ X}, . . . , {a | inn(a) ∈ X}). Consequently, optimized off-the-shelf ASP tools can be used for checking satisfiability but also for enumerating all satisfying n-concepts.

Algorithm 1 interactive n-concept finding algorithm

function FINDNCONCEPTINTERACTIVE(K) Input: n-context K = (K1, . . . , Kn, R) Output: n-concept searched by user Data: membership constraint C=(K+ 1 ,K1 ,. . .,K+ n , Kn ) C := (∅, . . . , ∅) C :=PROPAGATE(K, C) while Ki ̸=K+ i ∪Ki for some i ∈ {1, . . . , n} do have user pick some such i and a ∈ Ki\(K+ i ∪Ki ) have user pick some decision ∈ {in, out} if decision = in then update C by K+ i :=K+ i ∪ {a} else update C by Ki :=Ki ∪ {a} end if C :=PROPAGATE(K, C) end while return (K+ 1 , . . . ,K+ n ) end function

Algorithm 2 propagation of user decisions

function PROPAGATE(K, C) Input: n-context K, membership constraint C Output: updated membership constraint Data: membership constraint C′ for all i ∈ {1, . . . , n} do for all a ∈ Ki \ (K+ i ∪Ki ) do obtain C′ from C by adding a to K+ i if NMCSAT(K, C′ ) = NO then update C by adding a to Ki end if obtain C′ from C by adding a to Ki if NMCSAT(K, C′ ) = NO then update C by adding a to K+ i end if end for end for return C end function

7 Navigation in Conceptual Spaces

In this section we briefly describe an interactive search scenario where membership constraints can be put to use to support a user in finding an n-concept with desired properties. This is particularly useful in cases where the number of nconcepts is very large. The method is formally specified in Algorithm 1 (which calls Algorithm 2, which in turn relies on an nMCSAT solving procedure NMCSAT). We next explain the intuition and the formal arguments behind this approach in more detail.

First, given an n-context K = (K1, . . . , Kn, R) and a corresponding membership constraint C, let [C]K denote the set of all n-concepts of K that satisfy C. Next, observe that for the "zero-constraint" C∅ = (∅, . . . , ∅), the set [C∅]K contains all n-concepts of K. Further, for two membership constraints C1 and C2 with C1 ⪯ C2 (where we let ⪯ denote componentwise ⊆ and read it as "more general than"), we observe [C2]K ⊆ [C1]K. Finally every n-concept C = (A1, . . . ,An) of K gives rise to the characteristic membership constraint CC := (A1,K1 \ A1, . . . , An,Kn \ An) with [CC]K = {C}.

We now want to describe the identification of an n-concept by a user as an iterated approximation process starting from C∅ and going along a chain of ever more specific (but satisfiable) membership constraints until CC is reached for some n-concept C. Thereby, given a current constraint C = (K+ 1 ,K1 , . . . ,K+ n ,Kn ), the next constraint is determined by the user by picking some a ∈ Ki \ (K+ i ∪Ki ) for some i and adding it either to K+ i or Ki . In words, for some element, whose participation in the looked-for n-concept is not yet determined, the user has to decide to include or exclude it. In order to avoid that the membership constraint turns unsatisfiable as a consequence of the user's refinement decision, we will perform constraint propagation on C before the interaction: for every a ∈ Ki \ (K+ i ∪ Ki ) for some i where adding a to K+ i (respectively Ki ) would result in an unsatisfiable constraint, we add it to Ki (respectively K+ i ). Note that not both can be the case at the same time, since otherwise C itself would be unsatisfiable.

Note that the interactive algorithm sketched here does not need to compute all (possibly exponentially many) nconcepts upfront, it merely relies on (polynomially many) subsequent nMCSAT checks. An appropriate user interface for this navigation method would consist in n labeled lists containing the elements of the Ki with elements from K+ i labeled with "in" (or an appropriate color), elements from Ki labeled with "out", and elements from Ki \ (K+ i ∪Ki ) labeled with "unknown". By clicking on one of the "unknown" elements, the user may switch it to "in" or "out". Subsequent constraint propagation as described above then will possibly turn other "unknown" labels into "in" or "out" as a ramification of the user's decision. When no more "unknown" labels are left, the target concept has been identified.

8 Conclusion

Motivated by requirements that arise naturally when applying conceptual analysis techniques to large knowledge sets, we have investigated a way of specifying selection criteria for "interesting" concepts. To this end, we defined membership constraints as collections of required, respectively forbidden objects and attributes. We have studied the computational complexity of the corresponding satisfiability problem (MCSAT) of determining if a formal concept exists that adheres to the given specification. We have proved that in its general form, the MCSAT problem is NP-complete even if we restrict only to "forbidden" objects and attributes. On the other hand, if we have no "forbidden" objects or no "forbidden" attributes, the complexity drops to AC0.

When considering cases of arity three (objects, attributes, and conditions) or higher - with the notion of membership constraints appropriately adjusted - the corresponding problem is again NP-complete in general, but also here tractable special cases can be identified.

We presented a generic answer set programming (ASP) encoding for membership constraints, such that highly optimized ASP tools can be used to solve them. Finally we described an interactive search scenario in order to narrow down the search space for an n-concept with desired properties. This search paradigm relies on efficient methods for nMCSAT checking.

As an obvious and immediate avenue for future work, we will implement and evaluate our navigation framework based on the ASP-based satisfiability checker described.

Acknowledgements

The authors are grateful to the helpful comments from the anonymous reviewers of this paper.