We extend the description logic EL++ with re°exive roles and range restrictions, and show that subsumption remains tractable if a certain syntactic restriction is adopted. We also show that subsumption becomes PSpace-hard (resp. undecidable) if this restriction is weakened (resp. dropped). Additionally, we prove that tractability is lost when symmetric roles are added: in this case, subsumption becomes ExpTimehard.
The W3C recommendation OWL is currently being revisited by a W3C working
group with the goal of re¯ning and extending the existing version OWL 1.0 [
A notable fragment of this kind is the description logic E L++, which has been
introduced in [
The basis of E L++ is the description logic E L, which provides as concept
constructors the top concept (i.e., owl:Thing), conjunction (i.e.,
objectIntersectionOf), and existential restriction (i.e., objectSomeValuesFrom). In E L++, this
somewhat frugal list is extended with a number of constructors such as the
bottom concept (i.e., owl:Nothing) and nominals (i.e., objectOneOf with a single
argument), to name only two. Additional features of E L++ include GCIs (i.e.,
unrestricted subClassOf) and complex role inclusions, which allow to express
role hierarchies (i.e., subObjectPropertyExpression), transitive roles, and right
identities. A complete description of E L++ is given in Section 2, and, in a more
OWL-ish way, at [
One of the most prominent constructors not included in E L++ is universal
value restriction (i.e., objectAllValuesFrom). The reason for omitting it is that,
as shown in [
Introducing E L++ In E L++, concepts are inductively de¯ned from a set NC of concept names, a set NR of role names, and a set NI of individual names, using the constructors shown in the top ¯ve rows of Table 1. As usual, we use C and D to refer to concepts, r to refer to a role name, and a and b to refer to individual names. The semantics of E L++-concepts is de¯ned in terms of an interpretation I = (¢I ; ¢I ). The domain ¢I is a non-empty set of individuals and the interpretation function ¢I maps each concept name A 2 NC to a subset AI of ¢I , each role name r 2 NR to a binary relation rI on ¢I , and each individual name a 2 NI to an individual aI 2 ¢I . The extension of ¢I to arbitrary concept descriptions is inductively de¯ned as shown in the third column of Table 1.
The logic E L++ can be parameterized by one or more concrete domains D1; : : : ; Dn, which correspond to datatypes in OWL and permit reference to concrete data objects such as strings and integers. Formally, a concrete domain D is a pair (¢D; PD) with ¢D a set and P D a set of predicate names. Each p 2 P is associated with an arity n > 0 and an extension pD µ (¢D)n. To provide a link between the DL and the concrete domains D1; : : : ; Dn, we introduce a set of feature names NF and the concrete domain constructor shown in Table 1. We use Name top bottom nominal conjunction existential restriction concrete domain GCI RI domain restriction range restriction concept assertion role assertion
Syntax > ? fag C u D 9r:C
Semantics ¢I ; faI g CI \ DI fx 2 ¢I j 9y 2 ¢I : (x; y) 2 rI ^ y 2 CIg p(f1; : : : ; fk) fx 2¢I j 9y1; : : : ; yk 2 ¢Dj : for p 2 PDj fiI (x) = yi for 1 · i · k ^ (y1; : : : ; yk) 2 pDj g
C v D CI µ DI r1 ± ¢ ¢ ¢ ± rk v r r1I ± ¢ ¢ ¢ ± rkI µ rI dom(r) v C rI µ CI £ ¢I ran(r) v C
rI µ ¢I £ CI C(a) r(a; b) aI 2 CI (aI ; bI ) 2 rI p to denotes a predicate of a concrete domain and f1; : : : ; fk to denote feature names. The interpretation function is required to map each feature name f to a partial function from ¢I to S1·i·n ¢Di . Moreover, we generally assume that ¢Di \ ¢Dj = ; for 1 · i < j · n.
An E L++ knowledge base comprises two sets, the TBox and the ABox. While the TBox contains intensional knowledge de¯ning the main notions relevant to the domain of discourse, the ABox contains extensional knowledge about individual objects in the domain. Formally, a TBox is a ¯nite set of constraints, which can be general concept inclusions (GCIs), role inclusions (RIs), domain restrictions (DRs) and range restrictions (RRs). All of them are shown in Table 1. In RIs, we allow the case where k = 0, written as " v r. An ABox is a ¯nite set of concept assertions and role assertions, which are also shown in Table 1. An interpretation I is a model of a TBox T (resp. ABox A) if, for each constraint (resp. assertion) it contains, the conditions given in the third column of Table 1 are satis¯ed.
Regarding the expressive power of E L++, we remark the following. First, our
RIs generalize several means of expressivity important in ontology applications:
{ role hierarchies r v s can be expressed as r v s;
{ role equivalences r ´ s can be expressed as r v s; s v r;
{ transitive roles can be expressed as r ± r v r;
{ re°exive roles can be expressed as " v r;
{ left-identity rules can be expressed as r ± s v s;
{ right-identity rules can be expressed as r ± s v r.
Second, the bottom concept in combination with GCIs can be used to express
disjointness of complex concept descriptions: C u D v ? says that C; D are
disjoint. Finally, the identity of two individuals can be expressed as fag v fbg, and
their distinctness as fag u fbg v ?. We remark that the version of E L++
presented here extends the original version in [
In this paper, we are interested in the reasoning task of subsumption because
it allows to compute the classi¯cation of a TBox, i.e., a hierarchy which shows the
subconcept-superconcept relations between the concepts de¯ned in a TBox. We
say that a concept C subsumes a concept D w.r.t. a TBox T , written C vT D,
if CI µ DI in every model I of T . As shown in [
To avoid intractability (and even undecidability), we have to impose a restriction on the structure of TBoxes that prevents the otherwise too intricate interplay of range restrictions and role inclusions. For a TBox T and role names r; s, we write T j= r v s i® r = s or T contains role inclusions
r1 v r2; : : : ; rn¡1 v rn with r = r1 and s = rn: We write T j= ran(r) v C if there is a role name s with T j= r v s and ran(s) v C 2 T . Now, the mentioned restriction is as follows:
If r1 ± ¢ ¢ ¢ ± rn v s 2 T with n ¸ 1 and T j= ran(s) v C, then T j= ran(rn) v C.
The restriction ensures that if a role inclusion r1 ± ¢ ¢ ¢ ± rn v s, n ¸ 1, implies a role relationship (d; e) 2 sI , then the RR on s do not impose new concept memberships of e. Note that the condition is vacuously true if the role inclusion is a re°exivity statement, a role hierarchy statement, a transitivity statement, or a generalized left-identity of the form r1 ± ¢ ¢ ¢ ± rk v rk. In the following, we assume without further notice that this restriction is satis¯ed. We will show in Section 5 that dropping the restriction results in undecidability, and even if only right identities are allowed as role inclusions it still leads to PSpace-hardness and thus intractability. 4
We show that, in the version of E L++ presented in this paper, subsumption
can be decided in polytime. In fact, the extension with RIs of the form " v r
is technically a minor one, and it is easy to see how to extend the polytime
algorithm for subsumption in the original version of E L++ given in [
Given a TBox T formulated in E L++, we use BCT to denote the set of basic concept descriptions in T , i.e., the smallest set of concept descriptions that contains the top concept >, all concept names used in T , and all concepts of the form fag and p(f1; : : : ; fk) appearing in T , possibly as subconcepts.
1. all concept inclusions have one of the following forms, where C1; C2 2 BCT and D 2 BCT [ f?g: C1 u ¢ ¢ ¢ u Cn v D, C1 v 9r:C2, and 9r:C1 v D 2. for all role inclusions r1 ± ¢ ¢ ¢ ± rk v r 2 T , we have k · 2; 3. there are no domain restrictions and all range restrictions are of the form ran(r) v A, where A is a concept name.
By introducing new concept and role names, any TBox T can be turned into
a normalized TBox T 0 such that every model of T 0 is also a model of T , and
every model of T can be extended to a model of T 0 by appropriate choice of the
interpretations of the additional concept and role names. The transformation
can be performed in linear time. More details can be found in [
Let T be a TBox in normal form. For each role name r, we use ranT (r) to denote the set of concept names A such that T j= ran(r) v A. To eliminate range restrictions, we introduce a fresh concept name Xr;D for every GCI C v 9r:D in T . Intuitively, Xr;D denotes the range of r intersected with the extension of D. Now, let T 0 be the TBox obtained from T by dropping all range restrictions and, additionally, performing the following operations: 1. exchange every CI C v 9r:D with the CIs C v 9r:Xr;D, Xr;D v D, and
Xr;D v A for all A 2 ranT (r); 2. if " v r 2 T , then add the CI > v A for all A 2 ranT (r); Then we have the following.
Lemma 1. For all concept names A; B occurring in T , A vT B i® A vT 0 B. Proof. The \(" direction is trivial since every model I of T can be extended to a model of T 0 by interpreting every fresh concept name Xr;D as fd 2 DI j 9e : (e; d) 2 rI g. Thus, we concentrate on the \)" direction.
We show t0he co n0trapositive. Let A0 6vT 0 B0. Then there is a model I0 of T 0 such that A0I n B0I 6= ;. I0 is not necessarily a model of T since it need not satisfy the RRs in T . To ¯x this problem, we remove r-edges from I 0 that violate the range restrictions. The resulting interpretation turns out to be a model of T . More speci¯cally, convert I 0 into a new interpretation I by changing the interpretation of all role names r as follows: rI = f(d; e) 2 rI0 j e 2 \ AI0 g:
A2ranT (r) To show that I is a model of T , we only consider those constraints in T that could possibly be in°uenced by the modi¯cation: Observe that eliminating range restrictions induces only a quadratic blowup in the size of the original TBox. We expect that, in practical cases, the blowup will actually only be linear. 5
More on Range Restrictions and Role Inclusions We show that dropping the syntactic restriction adopted in E L++ leads to undecidability of subsumption, even if we allow only the concept constructors of E L, i.e., conjunction and existential restriction. If we restrict further by admitting only right identities as role inclusions, subsumption is still at least PSpace-hard. This shows that weakening the restriction by excluding right identities (which play an important role in medical knowledge bases) does not recover polytime reasoning. The PSpace lower bound applies even if a well-known acyclicity condition on role inclusions is adopted.
We consider E L with RIs and range restrictions as the only constraints in TBoxes
(no GCIs!). The proof is by reduction of the emptiness problem of the intersection
of two context-free grammars, which is known to be undecidable [
Let G = (§; N; P; S) and G0 = (§; N 0; P 0; S0) be two context-free grammars. W.l.o.g., we may assume that N \ N 0 = ;. We show how to translate G and G0 into a TBox T and concepts C and D such that L(G) \ L(G0) = ; i® C 6vT D. In the TBox T , we use role names rx and rx0 for every x 2 § [ N [ N 0 and two concept names A and B. More precisely, we set
C = u 9ra0:> and D = 9rS :(A u B); a2§ and T contains the following constraints: 1. the RR ran(ra0) v u 9rb:> and ran(ra) v u 9rb:> for all a 2 §; b2§ b2§ 2. the RIs rx1 ± ¢ ¢ ¢ ± rxn v rv and rx01 ± rx2 ± ¢ ¢ ¢ ± rxn v rv for every production v ` x1 ¢ ¢ ¢ xn 2 P [ P 0, 3. the range restrictions ran(rS0 ) v A and ran(rS00 ) v B.
To understand the construction, let d be an instance of C in some model I of T .
The de¯nition of C and the RRs in Points 1 ensure that, for every word w =
a1 ¢ ¢ ¢ an 2 §¤, there is an element dw in I reachable along the path ra01 ra2 ¢ ¢ ¢ ran
from d. The RIs in Point 2 ensure that if w 2 L(G), then (d; dw) 2 rS0 I , and
likewise for G0 and rS00 . We use the role rS0 here instead of rS to distinguish, at
the elements dw, incoming role edges that originate in d from edges originating
elsewhere. The RIs in Point 3 simply mark those dw with w 2 L(G) with A, and
those with w 2 L(G0) with B. It is now easy to show that L(G) \ L(G0) = ; i®
C 6vT D. We remark that similar reductions have been used in [
In [
PSpace-hardness
We show that even if RIs are restricted to acyclic right identities, subsumption
in E L with range restrictions is at least PSpace-hard. Although it is possible to
establish the result without any GCIs, we include them to improve readability.
The proof uses acyclic role inclusions. It is by reduction of the validity of QBFs,
i.e., formulas of the form à = Q1x1 ¢ ¢ ¢ Qnxn:' where Qi 2 f9; 8g for 1 · i · n
and ' is a propositional formula. We refer to [
We start with building up a tree of depth n rooted in A. Roles r1; : : : ; rn are used to connect left successor in the tree, and roles r1; : : : ; rn for right successors. We use concept names Li, 1 · i · n, to mark the di®erent levels of the tree: A v L0
Li v 9ri+1:Li+1 u 9ri+1:Li+1 for 1 · i < n Intuitively, nodes in the tree represent partial truth assignments. An incoming ri edge means that the variable xi is true, and an incoming ri edge that it is false. We ensure that, once we have decided on the truth value of a variable, we keep it in all descendant nodes. For 1 · i < j · n: ri ± rj v ri ri ± rj v ri ri ± rj v ri ri ± rj v ri Clearly, the leafs of the tree represent all possible (non-partial) truth assignments. For what is to follow, we represent these assignments not only in terms of incoming edges, but also by concept names. We use a concept name Ti to indicate that xi is true, and Fi for false. For 1 · i · n: ran(ri) = Ti ran(ri) = Fi In each leaf, we evaluate the formula. To this end, we introduce a concept name Aµ for every subformula µ of '. Then put:
Ln u Ti v Axi for 1 · i · n
Ln u Fi v A:xi for 1 · i · n
Ln u A u Aµ v AÂ^µ for all subformulas  ^ µ of Á
Ln u A and Ln u Aµ v AÂ_µ for all subformulas  _ µ of Á To evaluate the QBF Ã, we proceed from the leafs to the root. Each level corresponds to a quanti¯er in Ã, and we distinguish the case of an existential quanti¯er from that of a universal quanti¯er:
Li u 9ri+1:B and Li u 9ri+1:B v B for 0 · i < n with Qi+1 = 9 Li u 9ri+1:B u 9ri+1:B v B for 0 · i < n with Qi+1 = 8
Ln u A' v B
It is not hard to check that, as intended, Ã is valid i® A vT B. It is easily veri¯ed
that the right identities in the proof are acyclic in the sense of [
The best known upper bound for the considered version of E L is an ExpTime
one, and it only applies to acyclic right identities [
E L++ provides for re°exive and transitive roles, but not for symmetric ones.
The purpose of the current section is to explain why this is the case: adding
symmetric roles leads to ExpTime-hardness already for E L with GCIs. This
result is established in two steps. First, we consider E LI, i.e., E L extended with
inverse roles which come in the form of existential restrictions 9r¡:C interpreted
as fd 2 ¢I j 9e 2 CI : (e; d) 2 rI g. We show that, in E LI with GCIs,
subsumption is ExpTime-hard. This ¯lls a gap in [
Because of space limitations, we cannot present the details of the ¯rst step
and instead refer to the extended version of this paper [
Theorem 3. In E LI, subsumption w.r.t. GCIs is ExpTime-complete.
Let E Lsym be the extension of E L with symmetric roles, i.e., there is a countably
in¯nite subset NsRym µ NR such that rI = f(y; x) j (x; y) 2 rI g for all r 2 NsRym.
To show ExpTime-hardness of subsumption in E Lsym with GCIs, we reduce
subsumption in E LI with GCIs using a small trick due to Halpern and Moses [
It is not hard to see that for any two concept names A and B, we have A vT B in
E LI i® A vT 0 B in E Lsym. We have thus established ExpTime-hardness. A
corresponding upper bound is obtained from the obvious reduction of subsumption
in E Lsym with GCIs to satis¯ability in Converse-PDL [
Theorem 4. In E Lsym,subsumption w.r.t. general TBoxes is ExpTime-complete. Acknowledgements. We are grateful to Meng Suntisrivaraporn for discussions and suggestions.