Introduction

There have been several approaches towards the combination of description logics [5] and formal concept analysis [12] for knowledge acquisition, knowledge exploration, and knowledge completion. Rudolph [19] invented a method for the exploration of concept inclusions holding in an FLE-interpretation. Baader, Ganter, Sattler, and Sertkaya, [3,4,20] provided a technique for completion of knowledge bases. Furthermore, Baader and Distel [1,2,9] gave a method for computing a finite base of all concept inclusions holding in a finite EL-interpretation by means of the Duquenne-Guiges-base [13] of a so-called induced formal context. Finally, Borchmann [6][7][8] extended the results by defining the notion of confidence for concept inclusions, and utilized the Luxenburger-base [16][17][18] of the induced formal context to formulate a base for the concept inclusions whose confidence exceeds a given threshold.

In the following text we provide a method to compute a knowledge base for concept and role inclusions holding in an ALEQR Self -interpretation or description graph, respectively, which entails all knowledge that is encoded in the interpretation/graph and can be expressed in ALEQR Self . For this purpose we need the notion of a model-based most-specific concept description. It is defined as a concept description which describes a given individual x, i.e., the individual is an instance of the concept, and is most specific w.r.t. this property, i.e., for all concept descriptions C that have x as an individual, the most-specific concept is subsumed by C. Since we do not want to use greatest fixpoint semantics here, we restrict the role-depth to ensure existence of most-specific concepts. The description logic ALEQR Self is chosen for knowledge representation here, since it is an expressive description logic that does not allow for disjunctions (like ALC), and hence will not model the examples in the input graph too exactly.

We start with a short introduction of the description logic ALEQR Self . Then we define description graphs, and show their equivalence to interpretations. Furthermore, we then present model-based most-specific concept descriptions, and their relationships to formal concept analysis. We then continue with induced concept contexts and induced role contexts, and eventually utilize them to construct the desired knowledge base.

Please note that many of the results on model-based most-specific concept descriptions, induced concept contexts, and bases of general concept inclusions, have already been observed and proven by Baader and Distel [1,2,9] for the light-weight description logic EL ⊥ w.r.t. greatest fixpoint semantics, which allows for the bottom concept, conjunctions, existential restrictions, and general concept inclusions. Their results are extended to the additional concept constructors of ALEQR Self , and furthermore we also take complex role inclusions into account.

The Description Logic ALEQR Self

Let (N C , N R ) be a signature, i.e., N C is a set of concept names, and N R is a set of role names, such that N C and N R are disjoint. We stick to the usual notations and hence concept names are written as upper-case latin letters, e.g., A and B, and role names are written as lower-case latin letters, e.g., r and s. An interpretation over (N C , N R ) is a tuple I = (∆ I , • I ) where ∆ I is a non-empty set, called domain, and • I is an extension function that maps concept names A ∈ N C to subsets A I ⊆ ∆ I and role names r ∈ N R to binary relations r I ⊆ ∆ I × ∆ I .

The set of all ALEQR Self -concept descriptions is denoted by ALEQR Self (N C , N R ), and is inductively defined as follows. Every concept name A ∈ N C , the bottom concept ⊥, and the top concept , is an atomic ALEQR Self -concept description. If A ∈ N C is a concept name, r ∈ N R is a role name, C, D ∈ ALEQR Self (N C , N R ) are concept descriptions, and n ∈ N + is a positive integer, then ¬A, C D, ∃ r. C, ∀ r. C, ≥ n. r. C, ≤ n. r. C, and ∃ r. Self, are complex ALEQR Self -concept descriptions. The extension function of an interpretation I is canonically extended to all ALEQR Self -concept descriptions as shown in the semantics column of Figure 1.

Note that every individual without any r-successors in the interpretation I at all is an element of the extension of every value restriction ∀ r. C for arbitrary concept descriptions C. We use the usual notation X k for the set of all subsets of X with exactly k elements. It is well-known that X k = |X| k . Furthermore, ALEQR Self allows to express the following terminological axioms. If A is a concept name, and C, D are concept descriptions, then C D is a (general) concept inclusion (abbr. GCI), and A ≡ C is a concept definition. Of course, every concept definition A ≡ C can be simulated by two concept inclusions A C and C A. If r, r 1 , . . . , r n , s are role names, then r s is a simple role inclusion, and r 1 • . . . • r n s is a complex role inclusion, also called role inclusion axiom (abbr. RIA). We then say that an interpretation I is a model of an axiom α, denoted as

I | = α, if the condition in the name syntax C semantics C I bottom concept ⊥ ∅ top concept ∆ I primitive negation ¬A ∆ I \ A I conjunction C D C I ∩ D I existential restriction ∃ r. C { x ∈ ∆ I | ∃y ∈ ∆ I : (x, y) ∈ r I ∧ y ∈ C I } value restriction ∀ r. C { x ∈ ∆ I | ∀y ∈ ∆ I : (x, y) ∈ r I → y ∈ C I } qualified number ≥ n. r. C { x ∈ ∆ I | ∃Y ∈ ∆ I n : { x } × Y ⊆ r I ∧ Y ⊆ C I } restriction ≤ n. r. C { x ∈ ∆ I | ∀Y ∈ ∆ I n+1 : { x } × Y ⊆ r I → Y ⊆ C I } self restriction ∃ r. Self { x ∈ ∆ I | (x, x) ∈ r I } Fig.I | = α concept inclusion C D C I ⊆ D I concept definition A ≡ C A I = C I simple role inclusion r s r I ⊆ s I complex role inclusion r 1 • r 2 • . . . • r n s r I 1 • r I 2 • . . . • r I n ⊆ s I Fig. 2. Axiom Constructors of ALEQR Self • denotes the product operator where R • S := { (x, z) | ∃y : (x, y) ∈ R ∧ (y, z) ∈ S }.

Definition 1 (Knowledge Base). Let I be an interpretation. A knowledge base for I is a knowledge base K that has the following properties.

(sound) All axioms in K hold in I, i.e., I | = K.

(complete) All axioms that hold in I, are entailed by K, i.e., I | = α ⇒ K | = α.

(irredundant) None of the axioms in K follows from the others, i.e., K \ {α} | = α for all α ∈ K.

Graphs

The semantics of ALEQR Self can also be characterized by means of description graphs, which are cryptomorphic to interpretations. A description graph over (N C , N R ) is a tuple G = (V, E, ), such that the following conditions hold.

1. (V, E) is a directed graph, i.e., V is a set of vertices, and E ⊆ V × V is a set of directed edges on V. For an edge (v, w) ∈ E we say that v and w are connected, v is the source vertex, and w is the target vertex of (v, w).

2. = V ∪ E is a labeling function where V : V → 2 N C maps each vertex v ∈ V to a label set V (v) ⊆ N C , and E : E → 2 N R maps each edge (v, w) ∈ E to a label set E (v, w) ⊆ N R .

The vertices of the graph G are labeled with subsets of N C to indicate the concept names they belong to. Analogously, the edges are labeled with subsets of N R to allow multiple (named) relations between the same two vertices in the graph. Usually, one would also specify a root vertex v 0 ∈ V for description graphs, but this is not necessary for our purposes here.

A description graph may also be called folksonomy or social network here. For example, the set N R of role names in the signature may contain a relation friend that connects friends in a social network (graph). Other relations are for example isMarriedWith, sentFriendrequestTo, likes, follows, and hasAttendedEvent, with their obvious meaning. The vertices in a social network are of course the users (and possibly other objects). The vertex labels in the set N C of concept names can be used to categorize the users in a social network, e.g., by nationality, sex, marital status, profession, etc.

For each description graph G = (V, E, ) we define a canonical interpretation I G that contains all information that is provided in G as follows. The domain is just the vertex set, i.e., ∆ I G := V, and the extensions of concept names A ∈ N C , and of role names r ∈ N R , respectively, are given as follows.

A I G := −1 V (A) = { v ∈ V | A ∈ (v) } r I G := −1 E (r) = { (v, w) ∈ E | r ∈ (v, w)

} Furthermore, we can easily construct a description graph G I from an interpretation I = (∆ I , • I ) by setting G I := (V, E, ) where

V := ∆ I E := r∈N R r I V (v) := A ∈ N C v ∈ A I E (v, w) := r ∈ N R (v, w) ∈ r I .

It can be readily verified that both transformations are mutually inverse, i.e., I G I = I for all interpretations I, and G I G = G for all description graphs G.

As a consequence, we do not have to distinguish between interpretations and description graphs, and we may also compute model-based most-specific concept descriptions (which are usually defined for individuals of an interpretation, cf. next section) for vertices in description graphs. In the following we want to propose a method to compute a knowledge base K = (T , R) from a given description graph G that entails all knowledge that is encoded in G and is expressible in the description logic ALEQR Self .

Model-Based Most-Specific Concept Descriptions

The role depth rd(C) of a concept description C is defined as the greatest number of roles in a path in the syntax tree of C. Formally, we inductively define the role depth as follows.

1. Every atomic concept description A, ⊥, , and every primitive negation ¬A, has role depth 0. 2. The role depth of a conjunction is the maximum of the role depths of the conjuncts, i.e., rd(C D) := rd(C) ∨ rd(D) for all concept descriptions C and D. 3. The role depth of a restriction is the successor of the role depth of the concept description in the restriction's body, i.e., rd(Q r. C) := 1 + rd(C) for all quantifiers Q ∈ {∃, ∀, ≥ n, ≤ n}, role names r ∈ N R , and concept descriptions C. 4. The role depth of a self restriction is just defined as 1, i.e., rd(∃ r. Self) := 1.

It is easy to see that the role-depth of a concept description is well-defined. However, equivalent concept descriptions do not necessarily have the same role depth. For example the concept description ⊥ and ∃r.⊥ are equivalent, but the former concept description has role depth 0 and the latter has role depth 1. Since all model-based most-specific concept descriptions of X w.r.t. I and δ are unique up to equivalence, we speak of the mmsc, and denote it by X I δ . Lemma 3. Let I be an interpretation over the signature (N C , N R ). Then the following statements hold for all subsets X, Y ⊆ ∆ I , and concept descriptions C, D ∈ ALEQR Self (N C , N R ) with a role-depth ≤ δ.

Definition 2 (Model-Based Most-Specific Concept Description). Let (N C , N R ) be a signature, I = (∆ I , • I ) an interpretation over (N C , N R ), δ ∈ N a role-depth bound1. X ⊆ C I if, and only if, X I δ C. 2. X ⊆ Y implies X I δ Y I δ . 4. X ⊆ X I δ I . 6. X I δ ≡ X I δ II δ . 3. C D implies C I ⊆ D I . 5. C C II δ . 7. C I = C II δ I .

It then follows that • II δ is a closure operator on the concept description poset (ALEQR Self (N C , N R ), ) factorized by concept equivalence, and a concept inclusion C D holds in I if, and only if, the implication C → D holds in the closure operator • II δ . It follows that there is a (finite) canonical base of concept inclusions holding in a (finite) interpretation I.

Definition 4 (Least Common Subsumer).

Let C, D be ALEQR Self -concept descriptions w.r.t. the signature (N C , N R ). Then a concept description E ∈ ALEQR Self (N C , N R ) is called a least common subsumer (abbr. lcs) of C and D if the following conditions are fulfilled.

1. E subsumes both C and D, i.e., C E and D E. 2. Whenever F is a common subsumer of C and D, then F subsumes E, i.e., C F and D F implies E F for all concept descriptions F ∈ ALEQR Self (N C , N R ). Lemma 5. Let (X t ) t∈T be a family of subsets X t ⊆ ∆ I , and (C s ) s∈S a family of concept descriptions C s ∈ ALEQR Self (N C , N R ). Then the following statements hold. Beforehand we have observed a pair of mappings that has similar properties like the well-known galois connection which is induced by a formal context. More specifically, the pair (• I δ , • I ) is an adjunction. Consequently, we adapt the notions of a formal concept and a formal concept lattice as follows.

Definition 7 (Description Concept).

Let I be a finite interpretation over the signature (N C , N R ), and δ ∈ N a role-depth bound.

A description concept of I and δ is a pair (X, C) that consists of a subset X ⊆ ∆ I , and an ALEQR Self -concept description over (N C , N R ), such that X is the extension C I , and C is the model-based most-specific concept description X I δ . Furthermore, we call X the extent, and C the intent of (X, C). The set of all description concepts of I and δ is denoted as B(I, δ). Analogously, Ext(I, δ) and Mmsc(I, δ) denote the sets of all extents and intents, respectively.

To ensure formal correctness, we require that B(I, δ) only contains at most one description concept with the extent X. This is no limitation as we will see in the next lemma that all description concepts with the same extent have equivalent intents. Definition 8 (Subconcept, Superconcept, Description Concept Lattice). Let (X, C) and (Y, D) be two description concepts. Then (X, C) is a subconcept of (Y, D) if X ⊆ Y holds. We then also write (X, C) ≤ (Y, D), and call (Y, D) a superconcept of (X, C).

Additionally, the pair B(I, δ) := (B(I, δ), ≤) is called description concept lattice of I and δ.

Lemma 9 (Order on Description Concepts).

Let I be a finite interpretation over the signature (N C , N R ), and δ ∈ N a role-depth bound.

1. For two description concepts (X, C) and (Y, D) it is true that

(X, C) ≤ (Y, D) ⇔ X ⊆ Y ⇔ C D.

The relation ≤ is an order on B(I, δ).

We may furthermore observe that the set of all description concepts with the given order ≤ is a complete lattice.

Definition 10 (Description Lattice).

Let I be a finite interpretation over the signature (N C , N R ), and δ ∈ N a role-depth bound. Then B(I, δ) is a complete lattice whose infima and suprema are given by the following equations.

t∈T

(X t , C t ) =   t∈T X t , t∈T C t II δ   t∈T (X t , C t ) =   t∈T X t I δ I , t∈T C t  

A description lattice is a nice visualization of the information provided in a description graph or in an interpretation, respectively. Since interpretations and description graphs are cryptomorphically defined, we do not need to further distinguish between them. One can think of description lattices as a natural generalization of concept lattices which do not only allow conjunctions of attributes as intents, but also more complex concept descriptions that can be expressed in the underlying description logic. Of course, if the chosen description logic is L 0 , i.e., only allows for conjunctions , then the concept lattices and description lattices w.r.t. L 0 coincide. However, for more complex description logics like EL or FLE or extensions thereof, we can further involve roles in the intents of the description concepts which adds further expressivity.

There is also a strong correspondence to the pattern structures and their lattices that have been introduced by Ganter and Kuznetsov [11]. Of course, the set of patterns consists of all concept descriptions that are expressible in the underlying description logic w.r.t. the given signature (N C , N R ). The similarity operation is simply given by the least common subsumer mapping which is the infimum in the lattice of all concept descriptions.

Induced Concept Contexts

Definition 11 (Induced Context). Let I be an interpretation, and M a set of concept descriptions, both over the signature (N C , N R ). Then the induced context of I and M is defined as the formal context K I,M := ∆ I , M, I , where the incidence I is defined via (x, C) ∈ I if, and only, if x ∈ C I . For a concept description C over (N C , N R ) its projection to M is defined as π M (C)

:= { D ∈ M | C D }. A concept description C is expressible in terms of M if C ≡ U for a subset U ⊆ M.

We have ∅ = and U = C∈U C for all subsets ∅ = U ⊆ M. Lemma 12. Let I be an interpretation, and M a set of concept descriptions. Then the following statements hold for all subsets X, Y ⊆ M, and all concept descriptions C, D.

1. X ⊆ π M (C) if, and only if, C X. 2. X ⊆ Y implies X Y. 4. X ⊆ π M ( X) 6. X ≡ π M ( X). 3. C D implies π M (C) ⊇ π M (D). 5. C π M (C). 7. π M (C) = π M ( π M (C)).

Lemma 13. Let K I,M be an induced context. Then the following statements hold for all concept descriptions C over (N C , N R ), all subsets U ⊆ M, and X ⊆

∆ I . 1. π M (X I ) = X I 2. ( U) I = U I 3. C I ⊆ π M (C) I 4. π M ( U) II = U II 5. C ≡ π M (C) if C is expressible in terms of M. 6. C I = π M (C) I if C is expressible in terms of M. 7. U = π M ( U) if U is an intent of K I,M .

The next lemma tells us that we can directly decide in the induced context K I,M , whether a concept inclusion between conjunctions of concept descriptions of M holds in the given interpretation I.

Lemma 14 (Implications and concept inclusions).

Let I be an interpretation, and M a set of concept descriptions, both over the signature (N C , N R ). Then for all subsets X, Y ⊆ M, the concept inclusion X Y holds in I if, and only if, the implication X → Y holds in K I,M .

Definition 15 (ApproximationM I,δ := { ⊥ } ∪ { A, ¬A | A ∈ N C } ∪                  ∃ r. X I δ−1 , ∀ r. X I δ−1 , ≥ n. r. X I δ−1 , ≤ m. r. X I δ−1 , ∃ r. Self r ∈ N R , 1 ≤ m < n ≤ ∆ I , ∅ = X ⊆ ∆ I                  .

Then every model-based most specific concept description of I with role-depth ≤ δ is expressible in terms of M I,δ . Furthermore, the induced context of I and δ is defined as the induced context K C I,δ := K I,M I,δ of I and M I,δ .

Lemma 19 (Intents and MMSCs).

Let I be an interpretation over (N C , N R ), and K I,δ its induced context w.r.t. the role-depth bound δ ∈ N. Then the following statements hold for all subsets U ⊆ M I,δ , and concept descriptions C over (N C , N R ).

1. ( U) II δ ≡ U II .

2. If U is an intent of K I,δ , then U is a mmsc of I with role-depth ≤ δ.

3. If C is a mmsc of I with role-depth ≤ δ, then π M I,δ (C) is an intent of K I,δ .

Consequently, the mapping : M I,δ → ALEQR Self (N C , N R ) is an isomorphism from the intent-lattice (Int(K I,δ ), ∩) to the mmsc-lattice (Mmsc(I, δ), ), and has the inverse π M I,δ . This shows the strong correspondence between the formal concept lattice of K I,δ and the description concept lattice of I w.r.t. role depth ≤ δ. We can infer the following corollary from Lemmata 12 and 19.

Corollary 20. The intent lattice of K I,δ is isomorphic to the mmsc lattice of I, δ.

We can further observe that the concept inclusions holding in I and the implications holding in K I,δ are also in a strong correspondence. We can show that whenever the implication U → V holds in K I,δ , then also the concept inclusion U V holds in I. Furthermore, since every mmsc of I with a role depth ≤ δ is expressible in terms of M I,δ , and conjunctions of intents of K I,δ are exactly the mmscs of I, and every concept inclusion C D holding in I is entailed by the concept inclusion C C II , we can deduce that indeed every concept inclusion holding in I is entailed by the transformation of the canonical implicational base of K I,δ , which consists of all GCIs that have a conjunction of a pseudo-intent as premise and the conjunction of the closure of the pseudo-intent as conclusion.

Lemma 21. Let I be an interpretation over the signature (N C , N R ), δ ∈ N a role-depth bound, and C D a concept inclusion, such that both concepts C, D have a role-depth ≤ δ.

Ext(K I,δ ) Int(K I,δ ) Mmsc(I, δ) B(K I,δ ) B(I, δ) • I • I π M • I δ • I π 1 (id, • I ) π 2 (• I , id) π 1 (id, • I δ ) π 2 (• I , id)

Corollary 22 (Concept Inclusion Base).

Let I be an interpretation over the signature (N C , N R ), and δ ∈ N a role-depth bound. Then the following statements hold:

1. For all subsets X, Y ⊆ M I,δ , the implication X → Y holds in K I,δ if, and only if, the concept inclusion X Y holds in I. 2. The intents of K I,δ are exactly the model-based most-specific concept descriptions of I with role-depth bound ≤ δ. 3. If L is an implicational base for K I,δ , then L := { X Y | X → Y ∈ L } is a sound and complete TBox for all concept inclusions holding in I, δ. Especially this holds for the following TBox.

P

P II P is a pseudo-intent of K I,δ

Induced Role Contexts

Role contexts have been introduced by Zickwolff [21], and have been used by Rudolph [19] for gaining knowledge on binary relations or roles (that are interpreted as binary relations). We use their definition here for the deduction of complex role inclusions holding in an interpretation.

Definition 23 (Induced Role Context).

Let I be an interpretation over the signature (N C , N R ), and δ ∈ N a role depth bound. Furthermore, assume that X = { x 0 , x 1 , . . . , x δ } is a set of δ + 1 variables. Then the induced role context for I and δ is defined as

K R I,δ := ∆ I X , X × N R × X, J

where ( f , (x, r, y)) ∈ J if, and only if, ( f (x), f (y)) ∈ r I .

Lemma 24 (Role Inclusions and Implications). Let I be an interpretation over (N C , N R ), δ ∈ N a role-depth bound, and n ≤ δ. Then the complex role inclusion r 1 • r 2 • . . . • r n s holds in I if, and only if, the implication { (x 0 , r 1 , x 1 ), (x 1 , r 2 , x 2 ), . . . , (x n−1 , r n , x n ) } → { (x 0 , s, x n ) } holds in the induced role context K R I,δ .

In particular, we are only interested in implications whose premise contains a subset of the form { (x 0 , r 1 , x 1 ), (x 1 , r 2 , x 2 ), . . . , (x k−1 , r k , x k ) }. Hence, we define a constrain- ing closure operator φ R on the attribute set X × N R × X of the induced role context as follows.

φ R (B) :=          B if ∃k ∈ N + ∃r 1 , r 2 , . . . , r k ∈ N R ∃ { x 0 , x 1 , . . . , x k } ∈ X k+1 : { (x 0 , r 1 , x 1 ), . . . , (x k−1 , r k , x k ) } ⊆ B, B ∪ { (x 0 , r, x 1 ) | r ∈ N R } otherwise.

We shall now formulate a base of all complex role inclusions holding in an interpretation. For this purpose, we refer to [15] for the notions of constrained implications and their bases. A φ-constrained implication over M is an implication X → Y over M such that both premise X and conclusion Y are φ-closed. A φ-constrained implicational base for a formal context K is a set of φ-constrained implications that is valid in K, and furthermore entails all φ-constrained implications that hold in K.

Theorem 25 (Role Inclusion Base). Let I be an interpretation over (N C , N R ). If L is a φ R -constrained implicational base of K I,R , then the following RBox R I,δ is sound, complete, and irredundant, for all complex role inclusions holding in I, δ.

R I,δ :=                  r 1 • r 2 • . . . • r k s ∃X → Y ∈ L ∃r 1 , r 2 , . . . , r k , s ∈ N R ∃ { x 0 , x 1 , . . . , x k } ∈ X k+1 : X ⊇ { (x 0 , r 1 , x 1 ), (x 1 , r 2 , x 2 ), . . . , (x k−1 , r k , x k ) } Y (x 0 , s, x k )                 

Construction of the Knowledge Base

By means of the results of the previous Sections 5 and 6 we are now ready to formulate a knowledge base for an interpretation I, or for a description graph G, respectively. Beforehand, it is necessary to inspect the interplay of role and concept inclusions to ensure irredundancy of the knowledge base. First, we list some trivial concept inclusions that hold in all interpretations.

Lemma 26. Let m, n ∈ N + be non-negative integers with n < m, r ∈ N R a role name, and C a concept description. The following general concept inclusions hold in every interpretation I.

A ¬A ⊥ ∃ r. Self ∀ r. C C ∃ r. Self C ∃ r. C ∃ r. Self C ≤ 1. r. C ∀ r. C ∃ r. C ∀ r. D ∃ r. (C D) ≥ n. r. C ∀ r. D ≥ n. r. (C D) ≤ n. r. C ∀ r. D ≤ n. r. (C D) ∃ r. C ≥ 1. r. C ≥ n. r. C ∃ r. C ≤ n. r. C ≤ m. r. C ≥ m. r. C ≥ n. r. C ≥ ∆ I . r. C C ∀ r. C ∃ r. Self ≤ ∆ I . r. C

Please note that there are no direct subsumptions between existential restrictions ∃ r. C and value restrictions ∀ r. C, i.e., both ∃ r. C ∀ r. C and ∀ r. C ∃ r. C do not hold. There is also a crossover between both constructors existential restriction and value restriction. The constructor is denoted by ∀∃, and has the semantics (∀∃ r. C) I := (∃ r. C) I ∩ (∀ r. C) I , i.e., a domain element is in the extension of ∀∃ r. C if, and only if, there is an r-successor in C, and all r-successors are in C.

The next two lemmata show us which concept inclusions can be inferred from known role inclusions.

Lemma 27. Let I be a model of the role inclusion axiom r s, C an arbitrary concept description, Q 1 ∈ { ∃, ≥ n }, Q 2 ∈ { ∀, ≤ n }, and n ∈ N + . Then I is also a model of the following general concept inclusions.

Q 1 r. C Q 1 s. C ∃ r. Self ∃ s. Self Q 2 s. C Q 2 r. C Lemma 28. Let I be a model of the complex role inclusion r 1 • r 2 • . . . • r k s, C an arbitrary concept description, Q 1 ∈ { ∃, ≥ n }, Q 2 ∈ { ∀, ≤ n }, and n ∈ N + . Then I is also a model of the following concept inclusions. ∃ r 1 . ∃ r 2 . . . . Q 1 r k . C Q 1 s. C Q 2 s. C ∀ r 1 . ∀ r 2 . . . . Q 2 r k . C

As final step we use the trivial concept inclusions and concept inclusions that are entailed by valid role inclusions to define some background knowledge for the computation of the canonical implicational base of the induced concept context which is trivial in terms of description logics, but not for formal concept analysis due to their different semantics.

Theorem 29 (Knowledge Base). Let I be an interpretation over the signature (N C , N R ), and δ ∈ N a role-depth bound. Furthermore, assume that L is an implicational base of the induced concept context K C I,δ w.r.t. the background knowledge

S I := { C } → { D } C, D ∈ M I,δ , C D ∪ { { A, ¬A } → M I,δ | A ∈ N C } ∪              ∃ r. X I δ−1 , ∀ r. Y I δ−1 → ∃ r. Z I δ−1 , ≥ n. r. X I δ−1 , ∀ r. Y I δ−1 → ≥ n. r. Z I δ−1 , ≤ m. r. X I δ−1 , ∀ r. Y I δ−1 → ≤ m. r. Z I δ−1 , r ∈ N R , ∅ = X, Y, Z ⊆ ∆ I , Z I δ−1 ≡ X I δ−1 Y I δ−1 , 1 ≤ m < n ≤ ∆ I              ∪                        ∃ r. X I δ−1 → ∃ s. X I δ−1 , ∀ s. X I δ−1 → ∀ r. X I δ−1 , ≥ n. r. X I δ−1 → ≥ n. s. X I δ−1 , ≤ m. s. X I δ−1 → ≤ m. r. X I δ−1 , { ∃ r. Self } → { ∃ s. Self } r, s ∈ N R , r s ∈ R, 1 ≤ m < n ≤ ∆ I , ∅ = X ⊆ ∆ I                        .

Then K I,δ = (T I,δ , R I,δ ) is a knowledge base for I where T I,δ := L holds as in Corollary 22, and R I,δ is defined as in Theorem 25.

Other Description Logics

If only a lower expressivity of the underlying description logic is necessary, then one could also use EL, FLE, or extensions thereof with role hierarchies H, or complex role inclusions R. All of the previous results are still valid, however one has to remove some of the used concept descriptions that are not expressible in the chosen description logic. Figure 5 gives an overview on description logics that have a lower expressivity than ALEQR Self , and could also be used for knowledge acquisition.

Role Hierarchies H instead of Complex Role Inclusions R

In the special case of simple role inclusions provided by the extension H it is not necessary to use the induced role context. We can directly extract the role hierarchy from the interpretation I, or the description graph G, respectively, as follows. First, we want to extract a minimal RBox R I from the interpretation that entails all role inclusion axioms holding in I. We therefore define an equivalence relation ≡ I on the role names as follows: r ≡ I s if, and only if, r I = s I . Then let N I R be a set of representatives of this equivalence relation, i.e., N I R ∩ [r] ≡ I = 1 for all role names r ∈ N R . Then add the following role equivalence axioms to R I : For each

constructor EL FL 0 FLE ALE Q Self H R ⊥ × × × × × ¬A × C D × × × × ∃ r. C × × × × ∀ r. C × × × ≥ n. r. C × ≤ n. r. C × ∃ r. Self × C D × × × × C ≡ D × × × × r s × × r 1 • . . . • r n s ×

Conclusion

We have provided an extension of the results of Baader and Distel [1,2,9] for the deduction of knowledge bases from interpretations in the more expressive description logic ALEQR Self w.r.t. descriptive semantics and role-depth bounds. Since role-depthbounded model-based most-specific concept descriptions always exist, this technique can always be applied. Furthermore, the construction of knowledge bases has been reduced to the computation of implicational bases of formal contexts, which is a well-understood problem that has several available algorithms -for example the standard NextClosure algorithm from Ganter [10], or the parallel algorithm that has been introduced in [15] and implemented in [14]. The presented methods are prototypically implemented in Concept Explorer FX [14].