Approximating most specific concepts in description logics with existential restrictions.
Computing the most specific concept (msc) is an inference task that allows to abstract from individuals defined in description logic (DL) knowledge bases. For DLs that allow for existential restrictions or number restrictions, however, the msc need not exist unless one allows for cyclic concepts interpreted with the greatest fixed-point semantics. Since such concepts cannot be handled by current DL-systems. we propose to approximate the msc. We show that for the DL ALE, which has concept conjunction, a restricted form of negation, existential restrictions, and value restrictions as constructors, approximations of the msc always exist and can effectively be computed.
Introduction
The most specic concept (msc) of an individual b is a concept description
that has b as instance and is the least concept description (w.r.t. subsump-
tion) with this property. Roughly speaking, the msc is the concept description
that, among all concept descriptions of a given DL, represents b best. Closely
related to the msc is the least common subsumer (lcs), which, given concept
descriptions is the least concept description (w.r.t. subsumption)
subsuming Thus, where the msc generalizes an individual, the lcs
generalizes a set of concept descriptions.
In [2{4], the msc (rst introduced in [15]) and the lcs (rst introduced in
[5]) have been proposed to support the bottom-up construction of a knowledge
base. The motivation comes from an application in chemical process engineering
[17], where the process engineers construct the knowledge base (which consists of
descriptions of standard building blocks of process models) as follows: First, they
introduce several \typical" examples of a standard building block as individuals,
and then they generalize (the descriptions of) these individuals into a concept
description that (i) has all the individuals as instances, and (ii) is the most
This work was carried out while the author was still at the LuFG Theoretische
Informatik, RWTH Aachen, Germany.
specic description satisfying property (i). The task of computing a concept
description satisfying (i) and (ii) can be split into two subtasks: computing the
msc of a single individual, and computing the lcs of a given nite number of
concepts. The resulting concept description is then presented to the knowledge
engineer, who can trim the description according to his needs before adding it
to the knowledge base.
The lcs has been thoroughly investigated for (sublanguages of) Classic [5,
2, 12, 11], for DLs allowing for existential restrictions like ALE [3], and most
recently, for ALEN , a DL allowing for both existential and number restrictions
[13]. For all these DLs, except for Classic in case attributes are interpreted
as total functions [12], it has turned out that the lcs always exists and that
it can eectively be computed. Prototypical implementations show that the lcs
algorithms behave quite well in practice [7, 4].
For the msc, the situation is not that rosy. For DLs allowing for number
restrictions or existential restrictions, the msc does not exist in general. Hence,
the rst step in the bottom-up construction, namely computing the msc, cannot
be performed. In [2], it has been shown that for ALN , a sublanguage of
Classic, the existence of the msc can be guaranteed if one allows for cyclic
concept descriptions, i.e., concepts with cyclic denitions, interpreted by the
greatest xed-point semantics. Most likely, such concept descriptions would also
guarantee the existence of the msc in DLs with existential restrictions. However,
current DL-systems, like FaCT [10] and RACE [9], do not support this kind of
cyclic concept descriptions: although they allow for cyclic denitions of concepts,
these systems do not employ the greatest xed-point semantics, but descriptive
semantics. Consequently, cyclic concept descriptions returned by algorithms
computing the msc cannot be processed by these systems.
In this paper, we therefore propose to approximate the msc. Roughly speak-
ing, for some given non-negative integer k, the k-approximation of the msc of
an individual b is the least concept description (w.r.t. subsumption) among all
concept descriptions with b as instance and role depth at most k. That is, the
set of potential most specic concepts is restricted to the set of concept descriptions
with role depth bounded by k. For (sublanguages of) ALE we show that
k-approximations always exist and that they can eectively be computed. Thus,
when replacing \msc" by \k-approximation", the rst step of the bottom-up
construction can always be carried out. Although the original outcome of this
step is only approximated, this might in fact suce as a rst suggestion to the
knowledge engineer.
While for full ALE our k-approximation algorithm is of questionable practical
use (since it employs a simple enumeration argument), we propose improved
algorithms for the sublanguages EL and EL: of ALE . (EL allows for conjunction
and existential restrictions, and EL: additionally allows for a restricted form of
negation.) Our approach for computing k-approximations in these sublanguages
is based on representing concept descriptions by certain trees and ABoxes by
certain (systems of) graphs, and then characterizing instance relationships by
homomorphisms from trees into graphs. The k-approximation operation then
consists in unraveling the graphs into trees and translating them back into con-
Table

1. Syntax and semantics of concept descriptions.
Construct name Syntax Semantics EL EL: ALE
top-concept >  x x x
conjunction C u D C I \ D I x x x
existential restriction 9r:C fx 2
primitive negation :P  n P I x x
value restriction 8r:C fx 2
cept descriptions. In case the unraveling yields nite trees, the corresponding
concept descriptions are \exact" most specic concepts, showing that in this
case the msc exists. Otherwise, pruning the innite trees on level k yields k-
approximations of the most specic concepts.
The outline of the paper is as follows. In the next section, we introduce the
basic notions and formally dene k-approximations. To get started, in Section 3
we present the characterization of instance relationships in EL and show how
this can be employed to compute k-approximations or (if it exists) the msc. In
the subsequent section we extend the results to EL: , and nally deal with ALE
in Section 5. The paper concludes with some remarks on future work. Due to
space limitations, we refer to [14] for all technical details and complete proofs.
Preliminaries
Concept descriptions are inductively dened with the help of a set of construc-
tors, starting with disjoint sets NC of concept names and NR of role names. In
this work, we consider concept descriptions built from the constructors shown
in

Table

1, where r 2 NR denotes a role name, P 2 NC a concept name, and
C; D concept descriptions. The concept descriptions in the DLs EL, EL: , and
ALE are built using certain subsets of these constructors, as shown in the last
three columns of Table 1.
An ABox A is a nite set of assertions of the form (a; (role assertions) or
are individuals from a set N I (disjoint from
role name, and C is a concept description. An ABox is called
L-ABox if all concept descriptions occurring in A are L-concept descriptions.
The semantics of a concept description is dened in terms of an interpretation
The domain  of I is a non-empty set of objects and the
interpretation function  I maps each concept name P 2 NC to a set P I  ,
each role name r 2 NR to a binary relation r I  , and each individual
I to an element a I 2  such that a 6= b implies a I 6= b I (unique name
assumption). The extension of  I to arbitrary concept descriptions is inductively
dened, as shown in the third column of Table 1. An interpretation I is a model
of an ABox A i it satises (a I ; b I I for all role assertions (a;
and a I 2 C I for all concept assertions a : C 2 A.
The most important traditional inference services provided by DL-systems
are computing the subsumption hierarchy and instance relationships. The concept
description C is subsumed by the concept description D (C v D) i
C I  D I for all interpretations I; C and D are equivalent (C  D) i they
subsume each other. An individual a 2 N I is an instance of C w.r.t. A (a 2A C)
i a I 2 C I for all models I of A.
In this paper, we are interested in the computation of most specic concepts
and their approximation via concept descriptions of limited depth. The
depth depth(C) of a concept description C is dened as the maximum of nested
quantiers in C. We also need to introduce least common subsumers formally.
Denition 1 (msc, k-approximation, lcs). Let A be an L-ABox, a an individual
in A, C; C
{ C is the most specic concept (msc) of a w.r.t. A (mscA (a)) i a 2A C,
and for all L-concept descriptions C 0 , a 2A C 0 implies C v C
{ C is the k-approximation of a w.r.t. A (msc k;A (a)) i a 2A C, depth(C)
k, and for all L-concept descriptions C 0 , a 2A C 0 and depth(C 0 )  k imply
{ C is the least common subsumer (lcs) of C
descriptions C
for all
Note that by denition, most specic concepts, k-approximations, and least common
subsumers are uniquely determined up to equivalence (if they exist).
The following example shows that in DLs allowing for existential restrictions
the msc of an ABox-individual b need not exist.
Example 1. Let L be one of the DLs EL, EL: , or ALE . Consider the L-ABox
rg. It is easy to see that, for each n  0, b is an instance of the
L-concept description
Cn := 9r:    9r
| {z }
times
The msc of b can be written as the innite conjunction un0 Cn , which, however,
cannot be expressed by a (nite) L-concept description. As we will see, the k-
approximation of b is the L-concept description u 0nk Cn .
3 Most specic concepts in EL
In the following subsection, we introduce the characterization of instance relationships
in EL, which yields the basis for the algorithm computing k-approxi-
mations (Section 3.2). All results presented in this section are rather straightfor-
ward. However, they prepare the ground for the more involved technical problems
one encounters for EL: .
3.1 Characterizing instance in EL
In order to characterize instance relationships, we need to introduce description
graphs (representing ABoxes) and description trees (representing concept
descriptions). For EL, an EL-description graph is a labeled graph of the form
whose edges vrw 2 E are labeled with role names r 2 NR and
whose nodes v 2 V are labeled with sets '(v) of concept names from NC . The
empty label corresponds to the top-concept. An EL-description tree is of the
is an EL-description graph which is a tree
with root v
EL-concept descriptions can be turned into EL-description trees and vice
versa [3]: Every EL-concept description C can be written (modulo equivalence)
as f>g. Such a
concept description is recursively translated into an EL-description tree
follows: The set of all concept names P i occurring on the top-level
of C yields the label '(v 0 ) of the root v 0 , and each existential restriction
yields an r i -successor that is the root of the tree corresponding to C i . For
example, the concept description
yields the description tree depicted on the left hand side of Figure 1.
Every EL-description tree translated into an EL-concept
description CG as follows: the concept names occurring in the label of v 0 yield
the concept names in the top-level conjunction of C G , and each v 0
an existential restriction 9r:C, where C is the EL-concept description obtained
by translating the subtree of G with root v. For a leaf v 2 V , the empty label is
translated into the top-concept.
Adapting the translation of EL-concept descriptions into EL-description trees,
an EL-ABox A is translated into an EL-description graph G(A) as follows: Let
Ind(A) denote the set of all individuals occurring in A. For each a 2 Ind(A),
let C a := u a:D2A D, if there exists a concept assertion a : D 2 A, otherwise,
C a := >. Let G(C a denote the EL-description tree obtained
from C a . (Note that the individual a is dened to be the root of G(C a ); in
particular, a 2 V a .) W.l.o.g. let the sets V a , a 2 Ind(A) be pairwise disjoint.
Then, is dened by
{ V :=
{
{ '(v) := ' a (v) for v 2 V a .
As an example, consider the EL-ABox
The corresponding EL-description graph G(A) is depicted on the right hand side
of

Figure

1.
r s
s r
r
r
s
s r
r
s
Fig. 1. The EL-description tree of C and the EL-description graph of A.
Now, an instance relationship, a 2A C, in EL can be characterized in terms
of a homomorphism from the description tree of C into the description graph
of A: a homomorphism from an EL-description tree into an
EL-description graph VH such that
Theorem 1. [14] Let A be an EL-ABox, a 2 Ind(A) an individual in A, and
C an EL-concept description. Let G(A) denote the EL-description graph of A
and G(C) the EL-description tree of C. Then, a 2A C i there exists a homomorphism
' from G(C) into G(A) such that '(v 0 is the root of
G(C).
In our example, a is an instance of C, since mapping v 0 on a, v i on w i ,
and v 3 on b and v 4 on c yields a homomorphism from G(C) into G(A).
Theorem 1 is a special case of the characterization of subsumption between
simple conceptual graphs [6], and of the characterization of containment of conjunctive
queries [1]. In these more general settings, testing for the existence of
homomorphisms is an NP-complete problem. In the restricted case of testing homomorphisms
mapping trees into graphs, the problem is polynomial [8]. Thus,
as corollary of Theorem 1, we obtain the following complexity result.
Corollary 1. The instance problem for EL can be decided in polynomial time.
Theorem 1 generalizes the following characterization of subsumption in EL introduced
in [3]. This characterization uses homomorphisms between description
trees, which are dened just as homomorphisms from description trees into description
graphs, but where we additionally require to map roots onto roots.
Theorem 2. [3] Let C, D be EL-concept descriptions, and let G(C) and G(D)
be the corresponding description trees. Then, C v D i there exists a homomorphism
from G(D) into G(C).
3.2 Computing k-approximations in EL
In the sequel, we assume A to be an EL-ABox, a an individual occurring in
A, and k a non-negative integer. Roughly, our algorithm computing msc k;A (a)
works as follows: First, the description graph G(A) is unraveled into a tree with
root a. This tree, denoted T (a; G(A)), has a nite branching factor, but possibly
innitely long paths. Pruning all paths to length k yields an EL-description
tree T k (a; G(A)) of depth  k. Using Theorem 1 and Theorem 2, one can show
that the EL-concept description C Tk (a;G(A)) is equivalent to msc k;A (a). As an
immediate consequence, in case T (a; G(A)) is nite, C T (a;G(A)) yields the msc of
a. In what follows, we dene T (a; G(A)) and T k (a; G(A)), and prove correctness
of our algorithm.
First, we need some notations: For an EL-description graph
is a path from v 0 to vn of length and with label
n. The empty path
in which case the label of p is the empty word ". The node v n is an r 1    r n -
successor of v 0 . Every node is an "-successor of itself. A node v is reachable from
there exists a path from v 0 to v. The graph G is cyclic, if there exists a
non-empty path from a node in G to itself.
Denition 2. Let and a 2 V . The tree T (a; G) of a w.r.t. A is
dened by T (a;
{ V T := fp j p is a path from a to some node in Gg,
{
{ ' T (p) := '(v) if p is a path to v.
For IN, the tree T k (a; G) of a w.r.t. G and k is dened by T k (a; G) :=
{ V T
{
{ ' T
k .
Now, we can show the main theorem of this section.
Theorem 3. Let A be an EL-ABox, a 2 Ind(A), and k 2 IN. Then, C
is the k-approximation of a w.r.t. A. If, starting from a, no cyclic path in A can
be reached (i.e., T (a; G(A)) is nite), then C T (a;G(A)) is the msc of a w.r.t. A;
otherwise no msc exists.
Proof sketch. Obviously, there exists a homomorphism from T k (a; G(A)), a tree
isomorphic to G(C with a mapped on a. By Theorem 1,
this implies a 2A C
Let C be an EL-concept description with a 2A C and depth(C)  k. Theorem
1 implies that there exists a homomorphism ' from G(C) into G(A). Given ',
it is easy to construct a homomorphism from G(C) into T k (a; G(A)). Thus, with
Theorem 2, we conclude C C. Altogether, this shows that C
is a k-approximation as claimed.
Now, assume that, starting from a, a cycle can be reached in A, that is,
(a; G(A)) is innite. Then, we have a decreasing chain C
k-approximations C k ( C increasing depth k, k  0. From
Theorem 2, we conclude that there does not exist an EL-concept description
subsumed by all of these k-approximations (since such a concept description
only has a xed and nite depth). Thus, a cannot have an msc.
Conversely, if T (a; G(A)) is nite, say with depth k, from the observation
that all k 0 -approximations, for k 0  k, are equivalent, it immediately follows
that C T (a;G(A)) is the msc of a. ut
Obviously, there exists a deterministic algorithm computing the k-approximation
(i.e., C The size jAj of A is dened by
a:C2A
where the size jCj of C is dened as the sum of the number of occurrences of
concept names, role names, and constructors in C. Similarly, one obtains an
exponential complexity upper bound for computing the msc (if it exists).
Corollary 2. For an EL-ABox A, an individual a 2 Ind(A), and k 2 IN, the k-
approximation of a w.r.t. A always exists and can be computed in time O(jAj k ).
The msc of a exists i starting from a no cycle can be reached in A. The
existence of the msc can be decided in polynomial time, and if the msc exists, it
can be computed in time exponential in the size of A.
In the remainder of this section, we prove that the exponential upper bounds
are tight. To this end, we show examples demonstrating that k-approximations
and the msc may grow exponentially.
Example 2. Let sg. The EL-description graph G(A) as well
as the EL-description trees T 1 (a; G(A)) and T 2 (a; G(A)) are depicted in Figure 2.
It is easy to see that, for k  1, T k (a; G(A)) yields a full binary tree of depth k
where
{ each node is labeled with the empty set, and
{ each node except the leaves has one r- and one s-successor.
By Theorem 3, C Tk (a;G(A)) is the k-approximation of a w.r.t. A. The size of
Moreover, it is not hard to see that there does not exist an
EL-concept description C which is equivalent to but smaller than C
The following example illustrates that, if it exists, also the msc can be of exponential
size.
Example 3. For n
Obviously, An is acyclic, and the size of An is linear in n. By Theorem 3,
is the msc of a 1 w.r.t. An . It is easy to see that, for each n,
coincides with the tree obtained in Example 2. As before we obtain
that
{ C T (a1 ;G(A)) is of size exponential in jAn j; and
{ there does not exist an EL-concept description C equivalent to but smaller
than C T (a1 ;G(A)) .
r s
r s
Fig. 2. The EL-description graph and the EL-description trees from Example 2.
Summarizing, we obtain the following lower bounds.
Proposition 1. Let A be an EL-ABox, a 2 Ind(A), and k 2 IN.
{ The size of mscA;k (a) may grow with jAj k .
{ If it exists, the size of mscA (a) may grow exponentially in jAj.
Most specic concepts in EL:
Our goal is to obtain a characterization of the (k-approximation of the) msc in
EL: analogously to the one given in Theorem 3 for EL. To achieve this goal, rst
the notions of description graph and of description tree are extended from EL to
EL: by allowing for subsets of NC [f:P j P 2 NC g[f?g as node labels. Just as
for EL, there exists a 1{1 correspondence between EL: -concept descriptions and
EL: -description trees, and an EL:-ABox A is translated into an EL: -description
graph G(A) as described for EL-ABoxes. The notion of a homomorphism also
remains unchanged for EL: , and the characterization of subsumption extends to
EL: by just considering inconsistent EL: -concept descriptions as a special case:
there exists a homomorphism ' from G(D) into G(C).
Second, we have to cope with inconsistent EL:-ABoxes as a special case: for
an inconsistent ABox A, a 2A C is valid for all concept descriptions C, and
hence, mscA (a)  ?. However, extending Theorem 1 with this special case does
not yield a sound and complete characterization of instance relationships for
EL: . If this was the case, we would get that the instance problem for EL: is
in P, in contradiction to complexity results shown in [16], which imply that the
instance problem for EL: is coNP-hard.
The following example is an abstract version of an example given in [16]; it
illustrates incompleteness of a nave extension of Theorem 1 from EL to EL: .
Example 4. Consider the EL: -concept description
the EL:-ABox
rg; G(A) and G(C) are depicted in Figure 3. Obviously, there does not exist
r
r
r
r
r
r
Fig. 3. The EL:-description graph and the EL:-description tree from Example 4.
a homomorphism ' from G(C) into G(A) with '(w 0 neither
For each model I of A, however, either b I
I or
I
I , and in fact, a I 2 C I . Thus, a is an instance of C w.r.t. A though
there does not exist a homomorphism ' from G(C) into G(A) with '(w 0
In the following section, we give a sound and complete characterization of instance
relationships in EL: , which again yields the basis for the characterization
of k-approximations given in Section 4.2.
4.1 Characterizing instance in EL:
The reason for the problem illustrated in Example 4 is that, in general, for the
individuals in the ABox it is not always xed whether they are instances of
a given concept name or not. Thus, in order to obtain a sound and complete
characterization analogous to Theorem 1, instead of G(A), one has to consider
all so-called atomic completions of G(A).
Denition 3 (Atomic completion). Let be an EL: -description
graph and N
'(v)g. An
EL: -description graph G  ) is an atomic completion of G if, for all
1. '(v)  '  (v),
2. for all concept names P 2 N
Note that by denition, all labels of nodes in completions do not contain a con-
ict, i.e., the nodes are not labeled with a concept name and its negation. In
particular, if G has a con
icting node, then G does not have a completion. It is
easy to see that an EL:-ABox A is inconsistent i G(A) contains a con
icting
node. For this reason, in the following characterization of the instance relation-
ship, we do not need to distinguish between consistent and inconsistent ABoxes.
Theorem 4. [14] Let A be an EL:-ABox, the corresponding
description graph, C an EL: -concept description,
the corresponding description tree, and a 2 Ind(A). Then, a 2A C i for each
atomic completion G(A)  of G(A), there exists a homomorphism ' from G(C)
into G(A)  with '(w 0
The problem of deciding whether there exists an atomic completion G(A)  such
that there exists no homomorphism from G(C) into G(A)  is in coNP. Adding
the coNP-hardness result obtained from [16], this shows
Corollary 3. The instance problem for EL: is coNP-complete.
4.2 Computing k-approximations in EL:
Not surprisingly, the algorithm computing the k-approximation/msc in EL does
not yield the desired result for EL: . For instance, in Example 4, we would get
But as we will see, mscA (a)
As in the extension of the characterization of instance relationships from
EL to EL: , we have to take into account all atomic completions instead of the
single description graph G(A). Intuitively, one has to compute the least concept
description for which there exists a homomorphism into each atomic completion
of G(A). In fact, this can be done by applying the lcs operation on the set of all
concept descriptions C obtained from the atomic completions G(A)
of G(A).
Theorem 5. Let A be an EL:-ABox, a 2 Ind(A), and k 2 IN. If A is inconsis-
tent, then msc k;A (a)  mscA (a)  ?. Otherwise, let be the
set of all atomic completions of G(A).
Then, lcs(C If, starting from a, no
cycle can be reached in A, then lcs(C T
otherwise the msc does not exist.
Proof sketch. Let A be a consistent EL:-ABox and the atomic
completions of G(A). By denition of C there exists a homomorphism
i from C denote the lcs of
g. The characterization of subsumption for EL:
yields homomorphisms ' i from G(C k ) into G(C
Now it is easy to see that  i ' i yields a homomorphism from G(C k ) into
mapping the root of G(C k ) onto a. Hence, a 2A C k .
Assume C 0 with depth(C 0 )  k and a 2A C 0 . By Theorem 4, there exist
homomorphisms i from G(C 0 ) into G(A) i for all 1  i  n, each mapping the
root of G(C 0 ) onto a. Since depth(C 0 )  k, these homomorphisms immediately
yield homomorphisms 0
i from G(C 0 ) into G(C
the characterization of subsumption yields C
and hence C k v C 0 . Thus, C k  msc k;A (a).
Analogously, in case starting from a, no cycle can be reached in A, we conclude
(a). Otherwise, with the same argument
as in the proof of Theorem 3, it follows that the msc does not exist. ut
In Example 4, we obtain two atomic completions, namely
fPg, and G(A) 2 with ' 2 (b 2 f:Pg. Now Theorem 5 implies mscA (a)
which is equivalent to
The examples showing the exponential blow-up of the size of k-approx-
imations and most specic concepts in EL can easily be adapted to EL: . However,
we only have a double exponential upper bound (though we strongly conjecture
that the size can again be bounded single-exponentially): the size of each tree
(and the corresponding concept descriptions) obtained from an atomic completion
is at most exponential, and the size of the lcs of a sequence of EL: -concept
descriptions can grow exponentially in the size of the input descriptions [3].
Moreover, by an algorithm computing the lcs of the concept descriptions
obtained from the atomic completions, the k-approximation (the msc) can be
computed in double exponential time.
Corollary 4. Let A be an EL:-ABox, a 2 Ind(A), and k 2 IN.
{ The k-approximation of a always exists. It may be of size jAj k and can be
computed in double-exponential time.
{ The msc of a exists i A is inconsistent, or starting from a, no cycle can be
reached in A. If the msc exists, its size may grow exponentially in jAj, and
it can be computed in double-exponential time. The existence of the msc can
be decided in polynomial time.
5 Most specic concepts in ALE
As already mentioned in the introduction, the characterization of instance relationships
could not yet be extended from EL: to ALE . Since these structural characterizations
were crucial for the algorithms computing the (k-approximation of
the) msc in EL and EL: , no similar algorithms for ALE can be presented here.
However, we show that
1. given that NC and NR are nite sets, the msc k;A (a) always exists and can
eectively be computed (cf. Theorem 6);
2. the characterization of instance relationships in EL is also sound for ALE
(cf. Lemma 1), which allows for approximating the k-approximation; and
3. we illustrate the main problems encountered in the structural characterization
of instance relationships in ALE (cf. Example 5).
The rst result is achieved by a rather generic argument. Given that the signa-
ture, i.e., the sets NC and NR , are xed and nite, it is easy to see that also
the set of ALE-concept descriptions of depth  k built using only names from
NC [NR is nite (up to equivalence) and can eectively be computed. Since the
instance problem for ALE is known to be decidable [16], enumerating this set
and retrieving the least concept description which has a as instance, obviously
yields an algorithm computing msc k;A (a).
Theorem 6. Let NC and NR be xed and nite, and let A be an ALE-ABox built
over a set N I of individuals and NC [NR . Then, for k 2 IN and a 2 Ind(A), the
k-approximation of a w.r.t. A always exists and can eectively be computed.
Note that the above argument cannot be adapted to prove the existence
of the msc for acyclic ALE-ABoxes unless the size of the msc can be bounded
appropriately. Finding such a bound remains an open problem.
The algorithm sketched above is obviously not applicable in real applications.
Thus, in the remainder of this section, we focus on extending the improved
algorithms obtained for EL and EL: to ALE .
5.1 Approximating the k-approximation in ALE
We rst have to extend the notions of description graph and of description
tree from EL: to ALE : In order to cope with value restrictions occurring in
ALE-concept descriptions, we allow for two types of edges, namely those labeled
with role names r 2 NR (representing existential restrictions of the form 9r:C)
and those labeled with 8r (representing value restrictions of the form 8r:C).
Again, there is a 1{1 correspondence between ALE-concept descriptions and ALE-
description trees, and an ALE-ABox A is translated into an ALE-description
graph G(A) just as described for EL-ABoxes. The notion of a homomorphism also
extends to ALE in a natural way. A homomorphism ' from an ALE-description
into an ALE-description graph is a
mapping satisfying the conditions (1) and (2) on homomorphisms
between EL-description trees and EL-description graphs, and additionally (3)
We are now ready to formalize soundness of the characterization of instance
relationships for ALE .
Lemma 1. [14] Let A be an ALE-ABox with C an ALE-concept
description with
If there exists a homomorphism ' from GC into G(A) with '(v 0
a 2A C.
As an immediate consequence of this lemma, we get a 2A C
k  0, where the trees T (a; G(A)) and T k (a; G(A)) are dened just as for EL.
This in turn yields msc k;A (a) v C hence, an algorithm computing
an approximation of the k-approximation for ALE . In fact, such approximations
already turned out to be quite usable in our process engineering application [4].
The following example now shows that the characterization is not complete
for ALE , and that, in general, C In particular, it demonstrates
the diculties one encounters in the presence of value restrictions.
Example 5. Consider the ALE-ABox
A
and the ALE-concept description are
depicted in Figure 4. Note that G(A) is the unique atomic completion of itself
(w.r.t.
r r
r
r
s
r
s
r
Fig. 4. The ALE-description graph and the ALE-description tree from Example 5.
It is easy to see that there does not exist a homomorphism ' from G(C) into
However, a 2A C: For each model I of A, either b I
does
not have an s-successor, or at least one s-successor. In the rst case, b I
and hence b I
2 yields the desired r-successor of a I in (8s:P u 9r:9s:>) I . In the
second case, it is b I
I , and hence b I
1 yields the desired r-successor of
a I . Thus, for each model I of A, a I 2 C I .
Moreover, for
9r:(P u 9s:P ))) u 9r:(P u 9r:(P u 9s:P )). It is easy to see that C T4 (a;A) 6v C.
Hence, C T4 (a;A) u C < C T4 (a;A) , which implies msc 4;A (a) < C T4 (a;A) .
Intuitively, the above example suggests that, in the denition of atomic com-
pletions, one should take into account not only (negated) concept names but
also more complex concept descriptions. However, it is not clear whether an appropriate
set of such concept descriptions can be obtained just from the ABox
and how these concept descriptions need to be integrated in the completion in
order to obtain a sound and complete structural characterization of instance
relationships in ALE .
6 Conclusion
Starting with the formal denition of the k-approximation of msc we showed
that, for ALE and a nite signature (NC ; NR ), the k-approximation of the msc
of an individual b always exists and can eectively be computed. For the sublanguages
EL and EL: , we gave sound and complete characterizations of instance
relationships that lead to practical algorithms. As a by-product, we obtained
a characterization of the existence of the msc in EL-/EL:-ABoxes, and showed
that the msc can eectively be computed in case it exists.
First experiments with manually computed approximations of the msc in
the process engineering application were quite encouraging [4]: used as inputs
for the lcs operation, i.e., the second step in the bottom-up construction of the
knowledge base, they led to descriptions of building blocks the engineers could
use to rene their knowledge base. In next steps, the run-time behavior and the
quality of the output of the algorithms presented here is to be evaluated by a
prototype implementation in the process engineering application.



--R

Foundations of Databases.


Building and structuring description logic knowledge bases using least common subsumers and concept analysis.
Computing least common subsumers in description logics.
Conceptual graphs: Fundamental notions.
Learning the classic description logic: Theoretical and experimental results.
Computers and Intractability: A Guide to the Theory of NP-Completeness

Using an expressive description Logic: FaCT or




Reasoning and Revision in Hybrid Representation Systems.
On the complexity of the instance checking problem in concept languages with existential quanti
ROME: A repository to support the integration of models over the lifecycle of model-based engineering processes
--TR
On the complexity of the instance checking problem in concept languages with existential quantification
Foundations of Databases
Computers and Intractability
Building and Structuring Description Logic Knowledge Bases Using Least Common Subsumers and Concept Analysis
Computing Least Common Subsumers in Description Logics with Existential Restrictions
Computing the Least Common Subsumer and the Most Specific Concept in the Presence of Cyclic ALN-Concept Descriptions
description logics;non-standard inferences;most specific concepts