Recently, exact conditions for the existence of the least common subsumer (lcs) computed w.r.t. general EL-TBoxes have been devised [13]. This paper extends these results and provides necessary and su cient conditions for the existence of the lcs w.r.t. EL+-TBoxes. We show decidability of the existence in PTime and polynomial bounds on the maximal role-depth of the lcs, which in turn yields a computation algorithm for the lcs w.r.t. EL+-TBoxes.
In the area of Description Logics (DLs) the least common subsumer (lcs) is an
inference that is applied to a collection of concepts and yields a complex concept
that captures all commonalities of the input concepts. Unfortunately, the lcs
doesn't need to exist, if computed w.r.t. general EL-TBoxes [
ple: We want to compute the lcs of Woman and Man. Both are Human and have Grandparents that are Woman or Man, respectively. This leads to a cyclic de nition and thus the least common subsumer cannot be captured by a nite EL-concept, since this would need to express the cycle.
The DL EL+ allows, in addition to EL, for role inclusion axioms as for exam
In fact, for cyclic de nitorial EL-TBoxes exact conditions for the existence of
the lcs have been devised [
There are also several approaches to compute the lcs even in the presence of
general TBoxes. In [
In this paper we rst introduce basic notions for the DL EL+ and its canonical models, which serve as a basis for the characterization of the lcs in the subsequent sections. There we show that the characterization can be used to verify whether a given common subsumer is indeed the least one and show that the size of the lcs, if it exists, is polynomially bounded in the size of the input. These results yield a decision procedure for the existence problem for the lcs in EL+. The paper ends with some conclusions. 2 2.1
The Description Logic EL+ Let NC and NR be disjoint sets of concept and role names. Let A 2 NC and r 2 NR. EL-concepts are built according to the syntax rule
C ::= > j A j C u D j 9r:C
An interpretation I = ( I ; I ) consists of a non-empty domain I and a function I that assigns subsets of I to concept names and binary relations on
I to role names. The function is extended to complex concepts in the usual
way. For a detailed description of the semantics of DLs see [
Let C, D denote EL-concepts. A general concept inclusion (GCI) is an expression of the form C v D. The DL EL+ allows also for role inclusion axioms (RIAs) of the form r1 ::: rn v r with n 1 and ri 2 NR for i = 1; :::; n and r 2 NR. A (general) TBox T is a nite set of GCIs and an RBox R is a nite set of RIAs. An ontology O consists of a TBox T and an RBox R, denoted by O = (T ; R).1 1 Since we only use the DL EL+, we write `concept' instead of `EL-concept' and assume all TBoxes and RBoxes to be written in EL+ in the following.
on roles is interpreted as DI . The operator rI sI := f(d; f ) j 9e 2
I s.t. (d; e) 2 rI ^ (e; f ) 2 sI g: A RIA r1 ::: rn v r is satis ed in an interpretation I if r1I ::: rnI rI . An interpretation I is a model of T , if it satis es all GCIs in T . An interpretation I is a model of R if it satis es all RIAs in R. I is a model of an ontology O = (T ; R) if I is a model of T and R.
An important reasoning task considered for DLs w.r.t. TBoxes and RBoxes is subsumption. A concept C is subsumed by a concept D w.r.t. an ontology O (denoted by C vO D) i CI DI holds in all models I of O. A concept C is equivalent to a concept D w.r.t. O (denoted by C O D) i C vO D and D vO C hold. Similarly, a concept C is subsumed by a concept D w.r.t. an RBox R (denoted by C vR D) i CI DI holds in all models I of R.
Subsumption w.r.t. ontologies can be decided for EL+ in polynomial time [
De nition 1 (least common subsumer). Let C; D be concepts and O an ontology. The concept E is the lcs of C, D w.r.t. O (lcsO(C; D)) if the properties 1. C vO E and D vO E, and 2. C vO F and D vO F implies E vO F . are satis ed. If a concept E satis es Property 1 it is a common subsumer of C and D w.r.t. O.
The lcs in a DL that o ers conjunction is unique up to equivalence, thus we speak of the lcs. In contrast to this, common subsumers are not unique, thus we write F 2 csO(C; D).
The role depth (rd(C)) of a concept C denotes the maximal number of nestings of 9 in C. If in De nition 1 the concepts E and F have a role-depth bound less than or equal k, then E is the role-depth bounded lcs (k-lcsO(C; D)) of C and D w.r.t. O, which is also unique up to equivalence. 2.2
Canonical Models and Simulation Relations
The correctness proof of the computation algorithms for the lcs depends on
the characterization of subsumption. In case of the lcs in EL without a TBox,
homomorphisms between syntax trees of concepts [
Let X be a concept, a TBox, an RBox or an ontology, then sub(X) denotes the subconcepts in X.
De nition 2 (canonical model [
D vR 9r:D0 for D0 2 sub(C)g for all r 2 NR: To identify properties of canonical models we use simulation relations between interpretations.
De nition 3 (simulation). Let I1 and I2 be interpretations. S I1 is called a simulation from I1 to I2 if the following conditions are satis ed: I2 1. For all concept names A 2 NC and all (e1; e2) 2 S it holds: e1 2 AI1 implies e2 2 AI2 . 2. For all role names r 2 NR and all (e1; e2) 2 S and all f1 2 I1 with (e1; f1) 2 rI1 there exists f2 2 I2 such that (e2; f2) 2 rI2 and (f1; f2) 2 S. To denote an interpretation I together with a particular element d 2 I we write (I; d). It holds that (I; d) is simulated by (J ; e) (written as (I; d) . (J ; e)) if there exists a simulation S I J with (d; e) 2 S. The relation . is a preorder, i.e. it is re exive and transitive. (I; d) is simulation-equivalent to (J ; e) (written as (I; d) ' (J ; e)) if (I; d) . (J ; e) and (J ; e) . (I; d) holds.
Now we summarize some important properties of canonical models in EL+
that were shown in [
Lemma 1. Let C be a concept and O an ontology. 1. IC;O is a model of O. 2. For all models I of O and all d 2 I holds:
d 2 CI i (IC;O; dC ) . (I; d). 3. C vO D i dC 2 DIC;O i (ID;O; dD) . (IC;O; dC ).
This lemma gives us a characterization of subsumption by means of canonical models. In order to employ it for the characterization of the lcs, we need to recall some operations on interpretations.
Starting from an element of the domain of an interpretation as the root, the interpretation can be unraveled into a possibly in nite tree. The nodes of the tree are words that correspond to paths starting in d. The word = dr1d1r2d2r3::: is a path in an interpretation I if the domain elements di and di+1 are connected via riI+1 for all i.
De nition 4 (tree unraveling of an interpretation). Let I be an interpretation w.r.t. names from NC and NR with d 2 I . The tree unraveling Id of I in d is de ned as follows:
Id := fdr1d1r2:::rndn j (di; di+1) 2 riI+1 ^ 0 i < n ^ d0 = dg; AId := f d0 j d0 2
Id ^ d0 2 AI g; for all A 2 NC; rId := f( ; rd0) j ( ; rd0) 2
Id
Id g; for all r 2 NR: The length of an element 2 Id (denoted by j j), is the number of role names occurring in . If is of the form dr1d1r2:::rmdm, then dm is the tail of denoted by tail( ) = dm. The interpretation Id` denotes the nite subtree rooted in d of the tree unraveling Id containing all elements up to depth `. Such a tree can be translated into an `-characteristic concept of an interpretation (I; d). De nition 5 (characteristic concept). Let (I; d) be an interpretation. The `-characteristic concept X`(I; d) is de ned as follows: 2
X0(I; d) := lfA 2 NC j d 2 AI g X`(I; d) := X0(I; d) u l lf9r:X` 1(I; d0) j (d; d0) 2 rI g
r2NR Another operation that we will use later is the product of two interpretations that is de ned as follows.
De nition 6 (product of interpretations). Let I and J be interpretations. The product interpretation I J is de ned by
I J :=
I
J ; AI J := f(d; e) j (d; e) 2
I J ^ d 2 AI ^ e 2 AJ g, for all A 2 NC; rI J := f((d; e); (f; g)) j ((d; e); (f; g)) 2 I J
I J ^ (d; f ) 2 rI ^ (e; g) 2 rJ g, for all r 2 NR: 3
In this section we develop a decision procedure for the problem whether for two given concepts and a given ontology the least common subsumer of these two concepts w.r.t. the given ontology exists. If not stated otherwise, the two input concepts are denoted by C and D and the ontology by O.
We follow the method used in [
Similar to the approach used in [
2. Characterize the existence of the lcs. Find a condition such that the problem whether a given common subsumer of C and D w.r.t. O is least (w.r.t. vO), can be decided by testing this condition. 2 For a set M of concepts we write d M as shorthand for dF 2M F . If M is empty, then d M is equal to >.
3. Establish an upper bound on the role-depth of the lcs. We give a bound ` such that if the lcs exists, then it has a role-depth less than or equal `. By the use of such an upper bound one needs to check only for nitely many of the lcs-candidates if they are least (w.r.t. vO).
The next subsection addresses the rst two problems, afterwards we show that such a desired upper bound exists. 3.1
Characterizing the Existence of the lcs
The characterization presented here is based on the product of canonical models.
This product construction is adopted from [
To obtain the k-lcsO(C; D) we build the product of the canonical models (IC;O; dC ) and (ID;O; dD) and then take the k-characteristic concept of this product model.
Lemma 2. Let k 2 N. 1. Xk(IC;O ID;O; (dC ; dD)) 2 csO(C; D). 2. Let E 2 csO(C; D) with rd(E) k.
It holds that Xk(IC;O ID;O; (dC ; dD)) vO E.
In the proof we only need to refer to the canonical models and its properties
given in Lemma 1, thus the proof is a straightforward variant of the one given
in [
In the following we use Xk(IC;O ID;O; (dC ; dD)) as a representation of the k-lcsO(C; D). It is implied by Lemma 2 that the set of k-characteristic concepts of the product model (IC;O ID;O; (dC ; dD)) for all k is the set of lcs-candidates for the lcsO(C; D), which can be stated as follows.
Corollary 1. The lcsO(C; D) exists i there exists a k 2 N such that for all ` 2 N: k-lcsO(C; D) vO `-lcsO(C; D).
Obviously, this condition does not yield a decision procedure for the problem whether the k-lcsO(C; D) is the lcs, since subsumption cannot be checked for in nitely many ` in nite time.
Next, we address step 2 and show a condition on the common subsumers that decides whether a common subsumer is least or not. The main idea is that the product model (IC;O ID;O; (dC ; dD)) captures all commonalities of the input concepts C and D. Thus we need to compare the canonical models of the common subsumers and the product model by using simulation-equivalence '. (IC;O Lemma 3. Let E be a concept. E
O lcsO(C; D) i
ID;O; (dC ; dD)) ' (IE;O; dE).
Proof sketch. For any F 2 csO(C; D) it holds by Lemma 1, Claim 3 that (IF;O; dF ) is simulated by (IC;O; dC ) and by (ID;O; dD) and therefore also by (IC;O ID;O; (dC ; dD)).
Assume that (IE;O; dE ) is simulation-equivalent to the product model. We need to show that E O lcsO(C; D). By transitivity of . it is implied that (IF;O; dF ) . (IE;O; dE ) and E vO F by Lemma 1. Therefore E O lcsO(C; D).
For the other direction assume E O lcsO(C; D). It has to be shown that (IE;O; dE ) simulates the product model. Let J(dC;dD) be the tree unraveling of the product model. Since E is more speci c than the k-characteristic concepts of the product model for all k (by Corollary 1), (IE;O; dE ) simulates the subk tree J(dC;dD) of J(dC;dD) limited to elements up to depth k, for all k. For each k k we consider the maximal simulation from J(dC;dD) to (IE;O; dE ). Note that ((dC ; dD); dE ) is contained in any of these simulations. Let be an element of J(dC;dD) at an arbitrary depth `. We show how to determine the elements of IE;O , that simulate this xed element . Let Sn( ) be the maximal set of elements from IE;O that simulate in each of the trees J(ndC;dD) with n `. We can observe that the in nite sequence (S`+i( ))i=0;1;2;::: is decreasing (w.r.t. ). Therefore at a certain depth we reach a xpoint set. This xpoint set exists for any . It can be shown that the union of all these xpoint sets yields a simulation from the product model to (IE;O; dE ).
By the use of Lemma 3 it can be veri ed whether a given common subsumer is the least one or not, which we illustrate by an example.
Example 1. Consider the following TBox with O1 = (T1; ;) and now the following extended ontology In Figure 1 we can see that
T1 = fC v E u 9r:C;
D v E u 9r:D;
E v 9s:Eg O2 = (T1; fs s v rg)
E u 9s:E 2 csO1 (C; D); but this concept is not the lcs of C and D, because its canonical model cannot simulate the product model (IC;O1 ID;O1 ; (dC ; dD)). The concept E, however, is the lcs of C and D w.r.t. O2. We have (IC;O2 ID;O2 ; (dC ; dD)) . (IE;O2 ; dE ) since (dC ; dD) and (dE ; dE ) are simulated by dE .
The characterization of the existence of the lcs given in Corollary 1 can be reformulated using Lemma 3.
Corollary 2. The lcsO(C; D) exists i there exists a k such that the canonical model of Xk(IC;O ID;O; (dC ; dD)) w.r.t. O simulates (IC;O ID;O; (dC ; dD)). This corollary still doesn't yield a decision procedure for the existence problem, since the depth k is still unrestricted. Such a restriction will be developed in the next section. (dC ; dD) (dE; dE) 2 EI In this section we show that, if the lcs exists, its role-depth is bounded by the size of the product model. First, consider again the ontology O2 from Example 1, where E vO2 9r:E holds, which results in an r-loop in the product model through the element (dE; dE) with the same name appearing in both components. Furthermore, the cycles in the product model involving the roles r and s are exactly those captured by the canonical model IE;O2 . Therefore E O2 lcsO2 (C; D). On this observation we build our general method.
We call elements (dF ; dF 0 ) 2 IC;O ID;O synchronous if F = F 0 and asynchronous otherwise. The structure of (IC;O ID;O; (dC ; dD)) can now be simpli ed by considering only synchronous successors of synchronous elements.
In order to nd a number k, such that the product model is simulated by the canonical model of K = Xk(IC;O ID;O; (dC ; dD)), we rst represent the model (IK;O; dK ) as a subtree of the tree unraveling of the product model J(dC;dD) with root (dC ; dD). We construct this representation by extending the subtree k J(dC;dD) by new tree models at depth k. We need to ensure that the resulting k interpretation, denoted by Jb(dC;dD), is a model of O, that is simulation-equivalent to (IK;O; dK ). The elements 2 J(kdC;dD) with j j = k that we extend and the corresponding trees we append to them are selected as follows: Let M be a conjunction of concept names and 9s:F 2 sub(O). If 2 M J(kdC;dD) and M vO 9r:F , then we append the tree unraveling of the canonical model I9r:F;O. Note that the role names s and r can be di erent due to the presence of RIAs in O. Furthermore, we consider elements that have a tail that is a synchronous element. If tail( ) = (dF ; dF ), then F is called tail concept of . To select the elements with a synchronous tail, that we extend by the canonical model of their tail k concept, we use embeddings of J(dC;dD) into (IK;O; dK ). Let H = fZ1; :::; Zng k be the set of all functional simulations Zi from J(dC;dD) to (IK;O; dK ) with Zi((dC ; dD)) = dK . We say that with tail concept F is matched by Zi if
J(kdC;dD) with j j = k, that are matched by a functional simulation Zi is called matching set, denoted by M(Zi). Now consider the set M(H) := fM(Z1); :::; M(Zn)g. If is contained in all maximal matching sets from M(H), then we extend by the tree unraveling of the canonical model of its tail concept w.r.t. O. Intuitively, this condition corresponds to a minimization of changes which is required since the canonical model we want to obtain is minimal w.r.t. .. We can show that the resulting k interpretation Jb(dC;dD) has the desired properties.
Lemma 4. Let K = Xk(IC;O
k Jb(dC;dD) ' (IK;O; dK ).
k
ID;O; (dC ; dD)). Jb(dC;dD) is a model of O and Having this representation of the canonical model of the k-lcsO(C; D) at hand, we rst show a su cient condition for the existence of the lcs.
Corollary 3. If all cycles in (IC;O ID;O; (dC ; dD)), that are reachable from (dC ; dD) consist of synchronous elements, then the lcsO(C; D) exists. Proof sketch. There exists an ` 2 N such that all paths in the tree unraveling J(dC;dD) of (IC;O ID;O; (dC ; dD)) starting in (dC ; dD) have a maximal asynchronous pre x up to length `, i.e., if there exists an element at depth ` + 1, then it is a synchronous element. Consider the number
m := max(frd(F ) j F 2 sub(O) [ fC; Dgg): We unravel (IC;O ID;O; (dC ; dD)) up to depth ` + m + 1 such that we get `+m+1. Now it is ensured that the corresponding model Jb(`d+Cm;d+D1) contains J(dC;dD) all paths with a maximal asynchronous pre x up to length `. It is implied that Jb(`d+Cm;d+D1) = J(dC;dD). From Lemma 4 and from Corollary 2 it follows that X`+m+1(IC;O
ID;O; (dC ; dD)) is the lcs.
As seen in Example 1 for O2, this is not a necessary condition for the existence of the lcs. Since although the lcs of C and D exists w.r.t. O2, the product model has also a cycle involving the asynchronous element (dC ; dD).
Another consequence of Lemma 4 is, that if the product model (IC;O ID;O; (dC ; dD)) has only asynchronous cycles reachable from (dC ; dD), then the k lcsO(C; D) does not exist. Since in this case J(dC;dD) is in nite but Jb(dC;dD) is k ID;O; (dC ; dD)) to Jb(dC;dD) never nite for all k 2 N, a simulation from (IC;O exists for all k.
The interesting case is where there are both asynchronous and synchronous cycles reachable from (dC ; dD) in the product model. In this case we choose a k that is large enough and then check whether the corresponding canonical model of Xk(IC;O ID;O; (dC ; dD)) w.r.t. O simulates the product model.
We show in the next lemma that the role-depth of the lcsO(C; D), if it exists, can be bounded by a polynomial, that is quadratic in the size of the product model.
Lemma 5. Let m := max(frd(F ) j F 2 sub(O)[fC; Dgg) and n := j IC;O ID;O j. If lcsO(C; D) exists then (IC;O ID;O; (dC ; dD)) . Jb(nd2C+;dmD+) 1. Proof sketch. Assume lcsO(C; D) exists. From Corollary 2 and Lemma 4 it follows that there exists a number ` such that (IC;O
` ID;O; (dC ; dD)) . Jb(dC;dD): (1) Every path in Jb(`dC;dD) has a maximal asynchronous pre x of length `. From ` depth ` + 1 on there are only synchronous elements in the tree Jb(dC;dD). From (1) it follows that every path p in (IC;O ID;O; (dC ; dD)) starting in (dC ; dD), is ` simulated by a corresponding path p` in Jb(dC;dD) also starting in (dC ; dD). The simulation chain of p and p` is depicted in Figure 2. The idea of a simulation ` chain is to use the simulating path p` to construct a simulating path in Jb(dC;dD) (also starting in (dC ; dD)) with a maximal asynchronous pre x of length n2, where n2 is the number of pairs of elements from IC;O ID;O . Intuitively, if p` has a maximal asynchronous pre x that is longer than n2, then there must be pairs in the simulation chain that occur more than once. These are used to construct a simulating path with a shorter maximal asynchronous pre x step-wise. After a nite number of steps the result is a simulating path, such that all pairs consisting of asynchronous elements in the corresponding simulation chain are ` pairwise distinct. Therefore we need only asynchronous elements from Jb(dC;dD) up to depth n2 to simulate the product model. Then we add m + 1 to n2 to ensure that Jb(nd2C+;dmD+) 1 contains all paths from J(dC;dD) starting in (dC ; dD), that have a maximal asynchronous pre x of length n2. As argued above Jb(nd2C+;dmD+) 1 simulates (IC;O
ID;O; (dC ; dD)).
Using Lemma 3 and Lemma 5 we can now show the main result of this paper. Theorem 1. Let C; D be concepts and O an EL+-ontology. It is decidable in polynomial time whether the lcsO(C; D) exists. If the lcsO(C; D) exists then it can be computed in polynomial time.
Proof. First we compute the bound k as given in Lemma 5 and then the
kcharacteristic concept K of (IC;O ID;O; (dC ; dD)). The canonical model of K
can be build according to De nition 2 in polynomial time [
The results from this section can be easily generalized to the lcs of an arbitrary
set of concepts M = fC1; :::; Cmg w.r.t. an ontology O. But in this case the size
of the lcs is already exponential w.r.t. an empty TBox [
ICm;O; (dC1 ; ; dCm )); whose size is exponential in the size of M and O, as input for the methods introduced in this section. Then the same steps as for the binary version can be applied. 4
In this paper we have studied the conditions for the existence of the lcs, if
computed w.r.t. EL+-ontologies. In this setting the lcs doesn't need to exist. We
showed that the existence problem of the lcs of two concepts is decidable in
polynomial time. Furthermore, we showed that the role-depth of the lcs can be
bounded by a polynomial. This upper bound k can be used to compute the lcs, if
it exists. Otherwise the computed concept can still serve as an approximation [
Future work on the practical side includes to improve the described procedure
in order to obtain a practical algorithm such that an appropriate
implementation can be integrated into existing tools [