This work studies the expressiveness of the description logics that extend ALCreg (a variant of PDL) with any combination of the features: inverse roles, nominals, quanti ed number restrictions, the universal role, the concept constructor for expressing the local re exivity of a role. We compare the expressiveness of these description logics w.r.t. concepts, positive concepts, TBoxes and ABoxes. Our results about separating the expressiveness of description logics are based on bisimulations and bisimulation-based comparisons. They are naturally extended to the case when instead of ALCreg we have any sublogic of ALCreg that extends ALC.
Expressiveness (expressive power) is a topic studied in the elds of formal
languages, databases and logics. The Chomsky hierarchy provides fundamental
results on the expressiveness of formal languages. In the eld of databases, the
works by Fagin [
The expressiveness of description logics (DLs) has been studied in a number
of works [
This work studies the expressiveness of the DLs that extend ALCreg (a variant of PDL) with any combination of the features: inverse roles, nominals, quanti ed number restrictions, the universal role, the concept constructor for expressing the local re exivity of a role. We compare the expressiveness of these DLs w.r.t. concepts, positive concepts, TBoxes and ABoxes. Our results about separating the expressiveness of DLs are based on bisimulations and bisimulationbased comparisons studied in our joint works [8{10]. They are naturally extended to the case when instead of ALCreg we have any sublogic of ALCreg that extends ALC.
Our work di ers signi cantly from all of [
The rest of this paper is structured as follows. In Section 2 we recall notation
and semantics of DLs, including the notion of positive concepts [
Our languages use a nite set C of concept names (atomic concepts), a nite set R of role names (atomic roles), and a nite set I of individual names. Let = C [ R [ I . We denote concept names by letters like A and B, role names by letters like r and s, and individual names by letters like a and b.
We consider some DL-features denoted by I (inverse), O (nominal), Q (quanti ed number restriction), U (universal role), Self (the local re exivity of a role). A set of DL-features is a set consisting of some or zero of these names. We sometimes abbreviate sets of DL-features, writing, e.g., IOQ instead of fI; O; Qg. From now on, if not stated otherwise, let be any set of DL-features and let L stand for ALCreg.
De nition 2.1. The DL language L tively as follows:
allows roles and concepts de ned induc{ if r 2 R then r is a role of L { if A 2 C then A is a concept of L { if R and S are roles of L and C is a concept of L then ", R S, R t S, R and C? are roles of L >, ?, :C, C t D, C u D, 9R:C and 8R:C are concepts of L if I 2 then R is a role of L if O 2 and a 2 I then fag is a concept of L if Q 2 , r 2 R and n is a natural number then n r:C and n r:C are concepts of L if fQ; Ig then if U 2 if Self 2
, r 2 R and n is a natural number n r :C and n r :C are concepts of L then U is a role of L
and r 2 R then 9r:Self is a concept of L .
The following de nition introduces positive concepts of L .
De nition 2.2. Let Lpos be the smallest set of concepts and Lpo;9s, Lpo;8s be the smallest sets of roles de ned recursively as follows: { if r 2 R then r is a role of Lpo;9s and Lpo;s , {{ iiff IR2andaSndarre2roleRs othfeLnpo;rs ainsdaCroilse aofcLo8npco;9sepatnodf LLppoo;8ss,
9 { itfhRena"n,dRS aSr,eRrotleSs,ofRLpao;nsdanCd? Caries raolceosnocfepLtpo;o9sf, Lpos
8 { itfhAen2", RC thSe,nRAtiSs,aRconacnedpt(:ofCL)?poasr,e roles of Lpo;8s, {{ iiff SOel2f 2andanad2r 2I thRenthfeang9irs:SaeclofnicsepatcoofncLeppots ,of Lpos , { if C>is, aCctonDce,pCt uofDL,po9sR, :RC iasnadr8oSle:Cof aLrepo;c9soanncdepStsiosfaLrpoolse, of Lpo;8s then if Q 2 , r 2 R and n is a natural number then n r:C and n r:(:C) are concepts of Lpos , if fQ; Ig , r 2 R and n is a natural number then n r :C and n r :(:C) are concepts of Lpos , if U 2 then 8U:C and 9U:C are concepts of Lpos .
A concept of Lpos is called a positive concept of L .
We introduce both Lpo;8s and Lpo;9s due to the test constructor of roles. The concepts 9(A?):B and 8((:A)?):B are positive concepts. As we will see, they are equivalent to A u B and A t B, respectively.1
If is empty then we abbreviate L by L. We use letters like R and S to denote arbitrary roles, and use letters like C and D to denote arbitrary concepts. We refer to elements of R also as atomic roles. Let R = R [ fr j r 2
Rg. From now on, by basic roles we refer to elements of R if the considered language allows inverse roles, and refer to elements of R otherwise. In general, the language decides whether inverse roles are allowed in the considered context.
An interpretation I = h I ; I i consists of a non-empty set I , called the domain of I, and a function I , called the interpretation function of I, which maps every concept name A to a subset AI of I , maps every role name r to a binary relation rI on I , and maps every individual name a to an element aI of I . The interpretation function I is extended to complex roles and complex concepts as shown in Figure 1, where # stands for the cardinality of the set . We write CI (x) to denote x 2 CI , and write RI (x; y) to denote hx; yi 2 RI . 1 That the concept alent to 0 R:(:A).
n R:(:A) is positive should not be a surprise, as 8R:A is equiv2 (R
S)I = RI SI (R t S)I = RI [ SI (R )I = (RI) (C?)I = fhx; xi j CI(x)g
Ig "I = fhx; xi j x 2
U I = I I (R )I = (RI) 1 >I = ?I = ; (:C)I =
fagI = faIg (9r:Self)I = fx 2
I j rI(x; x)g (9R:C)I = fx 2 (8R:C)I = fx 2 ( n R:C)I = fx 2 ( n R:C)I = fx 2
I j 9y [RI(x; y) and CI(y)] I j 8y [RI(x; y) implies CI(y)]g I j #fy j RI(x; y) and CI(y)g I j #fy j RI(x; y) and CI(y)g ng ng
A terminological axiom in L , also called a general concept inclusion (GCI) in L , is an expression of the form C v D, where C and D are concepts of L . An interpretation I validates an axiom C v D, denoted by I j= C v D, if CI DI .
A TBox in L is a nite set of terminological axioms in L . An interpretation I is a model of a TBox T , denoted by I j= T , if it validates all the axioms of T .
An individual assertion in L is an expression of one of the forms C(a) (concept assertion), R(a; b) (positive role assertion), :R(a; b) (negative role assertion), a = b, and a 6= b, where C is a concept and R is a role in L .
Given an interpretation I, de ne that:
I j= a = b if aI = bI , I j= a 6= b if aI 6= bI , I j= C(a) if CI (aI ) holds, I j= R(a; b) if RI (aI ; bI ) holds,
I j= :R(a; b) if RI (aI ; bI ) does not hold.
We say that I satis es an individual assertion ' if I j= '.
An ABox in L is a nite set of individual assertions in L . An interpretation I is a model of an ABox A, denoted by I j= A, if it satis es all the assertions of A. 3
Bisimulation is a very useful notion for DLs. It can be used for analyzing
expressiveness of DLs (as investigated in [
De nition 3.1. Let I and I0 be interpretations. A binary relation Z I I0 is called an L -bisimulation between I and I0 if the following conditions hold for every a 2 I , A 2 C , r 2 R, x; y 2 I , x0; y0 2 I0 : Z(aI ; aI0 ) Z(x; x0) ) [AI (x) , AI0 (x0)] [Z(x; x0) ^ rI (x; y)] ) 9y0 2 [Z(x; x0) ^ rI0 (x0; y0)] ) 9y 2 if I 2 then
I0 [Z(y; y0) ^ rI0 (x0; y0)]
I [Z(y; y0) ^ rI (x; y)]; (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) [Z(x; x0) ^ rI (y; x)] ) 9y0 2 [Z(x; x0) ^ rI0 (y0; x0)] ) 9y 2
I0 [Z(y; y0) ^ rI0 (y0; x0)]
I [Z(y; y0) ^ rI (y; x)]; Z(x; x0) ) [x = aI , x0 = aI0 ]; if Z(x; x0) holds then, for every role name r, there exists a bijection h : fy j rI (x; y)g ! fy0 j rI0 (x0; y0)g such that h Z, if Z(x; x0) holds then, for every role name r, there exists a bijection h : fy j rI (y; x)g ! fy0 j rI0 (y0; x0)g such that h Z, then (additionally) I 9x0 2 I0 9x 2
I0 Z(x; x0)
I Z(x; x0); if O 2 if Q 2 if fQ; Ig if U 2 then then then 8x 2
Z(x; x0) ) [rI (x; x) , rI0 (x0; x0)]:
By (20), (70) and (120) we denote the conditions obtained respectively from (2),
(7) and (12) by replacing equivalence (,) by implication ()). If the conditions
(2), (7) and (12) are replaced by (20), (70) and (120), respectively, then the relation
Z is called an L -comparison between I and I0 [
As shown in [
De nition 3.2. A concept C in L is invariant for L -bisimulation if, for any interpretation I; I0 and any L -bisimulation Z between I and I0, if Z(x; x0) holds then x 2 CI i x0 2 CI0 . A TBox T in L is invariant for L -bisimulation if, for every interpretations I and I0, if there exists an L -bisimulation between I and I0 then I is a model of T i I0 is a model of T . The notion of whether an ABox in L is invariant for L -bisimulation is de ned similarly. 2 De nition 3.3. An interpretation I is said to be unreachable-objects-free (w.r.t. the considered language) if every element of I is reachable from some aI , where a 2 I , via a path consisting of edges being instances of basic roles. 2
The following theorem comes from our joint work [
Theorem 3.4. 1. All concepts in L are invariant for L -bisimulation. 2. If U 2 then all TBoxes in L are invariant for L -bisimulation. 3. Let T be a TBox in L and I, I0 be unreachable-objects-free interpretations (w.r.t. L ) such that there exists an L -bisimulation between I and I0. Then I is a model of T i I0 is a model of T . 4. Let A be an ABox in L . If O 2 or A contains only assertions of the form
C(a) then A is invariant for L -bisimulation.
De nition 3.5. A concept C of L is preserved by L -comparisons if, for any interpretations I, I0 and any L -comparison Z between I and I0, if Z(x; x0) holds and x 2 CI then x0 2 CI0 . 2
The following theorem comes from our joint work [
Theorem 3.6. All concepts of Lpos are preserved by L -comparisons. 4
De nition 4.1. Two concepts C and D are equivalent if, for every interpretation I, CI = DI . Two TBoxes T1 and T2 are equivalent if, for every interpretation I, I is a model of T1 i I is a model of T2. Two ABoxes A1 and A2 are equivalent if, for every interpretation I, I is a model of A1 i I is a model of A2. De nition 4.2. We say that a logic L1 is at most as expressive as a logic L2 w.r.t. concepts (resp. positive concepts, TBoxes, ABoxes), denoted by L1 C L2 (resp. L1 P C L2, L1 T L2, L1 A L2), if every concept (resp. positive concept, TBox, ABox) in L1 has an equivalent concept (resp. positive concept, TBox, ABox) in L2.
We say that a logic L2 is more expressive than a logic L1 (or L1 is less expressive than L2) w.r.t. concepts (resp. positive concepts, TBoxes, ABoxes),
P C L2, L1 L2 6 T L1, L2 6 A L1). denoted by L1 <C L2 (resp. L1 <P C L2, L1 <T L2, L1 <A L2), if L1 C L2 (resp. L1 T L2, L1 A L2) and L2 6 C L1 (resp. L2 6 P C L1, 2
The following proposition clearly holds.
Proposition 4.3. If a logic L1 is at most as expressive as a logic L2 w.r.t. concepts (resp. positive concepts, TBoxes, ABoxes) and a logic L2 is at most as expressive as L3 w.r.t. concepts (resp. positive concepts, TBoxes, ABoxes) then L1 is at most as expressive as L3 w.r.t. concepts (resp. positive concepts, TBoxes, ABoxes).
Lemma 4.4. Let 1 and 2 be sets of DL-features such that 1 2. Denote L1 = L 1 and L2 = L 2 . Let I, I0 be interpretations and Z an L1-bisimulation between I and I0. 1. If L1 C L2, x 2 I ; x0 2 I0 ; Z(x; x0) holds, and there exists a concept C of L2 such that x 2 CI but x0 62 CI0 , then L1 <C L2. 2. Suppose that U 2 1 or both I and I0 are unreachable-objects-free. If L1 T L2 and there exists a TBox T in L2 such that I is a model of T but I0 is not, then L1 <T L2. 3. Suppose O 2 1. If L1 A L2 and there exists an ABox A in L2 such that
I is a model of A but I0 is not, then L1 <A L2.
Proof. Consider the rst assertion. Suppose L1 C L2, x 2 I , x0 2 I0 , Z(x; x0) holds and there exists a concept C of L2 such that x 2 CI but x0 62 CI0 . We prove that L2 6 C L1. For the sake of contradiction, suppose L2 C L1. It follows that there exists a concept C0 of L1 that is equivalent to C. Thus, x 2 C0I but x0 62 C0I0 . Hence, C0 is not invariant for Z, which contradicts Theorem 3.4(1). Therefore, L1 <C L2.
Consider the second assertion. Suppose L1 T L2 and there exists a TBox T in L2 such that I is a model of T but I0 is not. We prove that L2 6 T L1. For the sake of contradiction, suppose L2 T L1. It follows that there exists a TBox T 0 in L1 that is equivalent to T . Thus, I is a model of T 0 but I0 is not, which contradicts Theorem 3.4(2) or Theorem 3.4(3). Therefore, L1 <T L2.
Consider the third assertion. Suppose L1 A L2 and there exists an ABox A in L2 such that I is a model of A but I0 is not. We prove that L2 6 A L1. For the sake of contradiction, suppose L2 A L1. It follows that there exists an ABox A0 in L1 that is equivalent to A. Thus, I is a model of A0 but I0 is not, which contradicts Theorem 3.4(4). Therefore, L1 <A L2. 2 Lemma 4.5. Let 1 and 2 be sets of DL-features such that 1 2. Denote L1 = L 1 and L2 = L 2 . Let I, I0 be interpretations and Z an L1-comparison between I and I0. If L1 P C L2, x 2 I ; x0 2 I0 ; Z(x; x0) holds, and there exists a positive concept C of L2 such that x 2 CI but x0 62 CI0 , then L1 <P C L2. Proof. Suppose L1 P C L2, x 2 I , x0 2 I0 , Z(x; x0) holds and there exists a positive concept C of L2 such that x 2 CI but x0 62 CI0 . We prove that L2 6 P C L1. For the sake of contradiction, suppose L2 P C L1. It follows that there exists a positive concept C0 of L1 that is equivalent to C. Thus, x 2 C0I but x0 62 C0I0 . It follows that C0 is not preserved by Z, which contradicts Theorem 3.6. Hence, L1 <P C L2. 2
From now on, we assume that C and at least two individual names. Let fa; bg R are not empty and I , A 2 C and r 2 1. For any pair hL1; L2i among hLI ; LOQUSelfi; hLQ; LIOUSelfi; hLSelf; LIOQU i, we have that: L1 6 C L2, L1 6 P C L2, L1 6 T L2, L1 6 A L2.
LI vs.
LOQUSelf C = 8r8r 1:A LQ vs.
LIOUSelf C = ( 1r::A) LSelf vs.
LIOQU C = 9r9r:Self LO vs.
LIQUSelf C = fbg LU vs.
LIOQSelf C = 8U:A aI : A u1
I0 aI0 : A v1 v2 I0
I0 aI0 : A
v1 aI0 : A v1
I0 aI0 : A
bI0 v2 bI0 : A
v2 v 2. LO 6 C LIQUSelf, LO 6 P C LIQUSelf, LO 6 T LIQUSelf. 3. LU 6 C LIOQSelf, LU 6 P C LIOQSelf, LU 6 A LIOQSelf.
Proof. Let us compare LI with LOQUSelf. Consider the interpretations I, I0 and the relation Z shown in the rst part of Figure 2. The arrows denote the instances of r in I and I0. The instances of A in I and I0 are explicitly indicated in the gure. Let BI = BI0 = ; for all B 2 C n fAg, sI = sI0 = ; for all s 2 R n frg, and cI = aI , cI0 = aI0 for all c 2 I n fa; bg. The dotted lines in the gure indicate the instances of a binary relation Z I I0 . It can be checked that Z is an LOQUSelf-bisimulation between I and I0. Consider the positive concept C = 8r8r 1:A of LI . Clearly, aI 2 CI but aI0 62 CI0 . By Theorem 3.4(1), C does not have any equivalent concept in LOQUSelf. Hence, LI 6 C LOQUSelf. As Z is also an LOQUSelf-comparison between I and I0, by Theorem 3.6, C does not have any equivalent positive concept in LOQUSelf either. Hence, LI 6 P C LOQUSelf. Consider the TBox T = fA v Cg. Since I j= T but I0 6j= T , by Theorem 3.4(3), T does not have any equivalent TBox in LOQUSelf. Hence LI 6 T LOQUSelf. Consider the ABox A = fC(a)g. Since I j= A but I 6j 0 = A, by Theorem 3.4(4), A does not have any equivalent ABox in LOQUSelf. Hence LI 6 A LOQUSelf.
The proofs for the other pairs of logics can be done similarly, using I, I0, C speci ed in the next parts of Figure 2. For the parts without the presence of b, let bI = aI and bI0 = aI0 . 2 Theorem 4.7. Let
and 0 be subsets of fI; O; Q; U; Selfg.
Proof. Consider the rst assertion and suppose 0. Since every concept (resp. positive concept) of L is also a concept (resp. positive concept) of L 0 , we have that L C L 0 (resp. L P C L 0 ). Since 0 n 6= ;, at least one feature among I, O, Q, U , Self belongs to 0 n . Consider the case I 2 0 n . The cases of other features are similar and omitted. For the sake of contradiction, suppose L 0 C L (resp. L 0 P C L ). Since LI C L 0 (resp. LI P C L 0 ) and L C LOQUSelf (resp. L P C LOQUSelf), it follows that LI C LOQUSelf (resp. LI P C LOQUSelf), which contradicts Lemma 4.6. Therefore, L <C L 0 (resp. L <P C L 0 ).
Consider the second assertion and suppose 6 0. Since n 0 6= ;, at least one feature among I, O, Q, U , Self belongs to n 0. Consider the case I 2 n 0. The cases of other features are similar and omitted. For the sake of contradiction, suppose L C L 0 (resp. L P C L 0 ). Since LI C L (resp. LI P C L ) and L 0 C LOQUSelf (resp. L 0 P C LOQUSelf), it follows that LI C LOQUSelf (resp. LI P C LOQUSelf), which contradicts Lemma 4.6. Therefore, L 6 C L 0 (resp. L 6 P C L 0 ).
Consider the third assertion and suppose 0 and 0 n 6= fU g. At least one feature among I, O, Q, Self belongs to 0 n . Consider the case I 2 0 n . The cases of other features are similar and omitted. Since 0, L T L 0 . For the sake of contradiction, suppose L 0 T L . Since LI T L 0 and L T LOQUSelf, it follows that LI T LOQUSelf, which contradicts Lemma 4.6. Therefore, L <T L 0 .
Consider the fourth assertion and suppose 6 0 and n 0 6= fU g. At least one feature among I, O, Q, Self belongs to n 0. Consider the case I 2 n 0. The cases of other features are similar and omitted. For the sake of contradiction, suppose L T L 0 . Since LI T L and L 0 T LOQUSelf, it follows that LI T LOQUSelf, which contradicts Lemma 4.6. Therefore, L 6 T L 0 .
Consider the fth assertion and suppose 0 and 0 n 6= fOg. At least one feature among I, Q, U , Self belongs to 0 n . Consider the case I 2 0 n . The cases of other features are similar and omitted. Since 0, L A L 0 . For the sake of contradiction, suppose L 0 A L . Since LI A L 0 and L A LOQUSelf, it follows that LI A LOQUSelf, which contradicts Lemma 4.6. Therefore, L <A L 0 .
Consider the last assertion and suppose 6 0 and n 0 6= fOg. At least one feature among I, Q, U , Self belongs to n 0. Consider the case I 2 n 0. The cases of other features are similar and omitted. For the sake of contradiction, suppose L A L 0 . Since LI A L and L 0 A LOQUSelf, it follows that LI A LOQUSelf, which contradicts Lemma 4.6. Therefore, L 6 A L 0 . 2 De nition 4.8. We de ne ALC to be the sublogic of ALCreg such that the role constructors ", R S, R t S, R and C? are disallowed. We say that L is a sublogic of ALCreg that extends ALC, denoted ALC L ALCreg, if it extends ALC with some of those role constructors. For fI; O; Q; U; Selfg and ALC L ALCreg, let L and Lpos be de ned as usual in the spirit of De nitions 2.1 and 2.2. 2 Corollary 4.9. Let L be any sublogic of ALCreg that extends ALC and let and 0 be subsets of fI; O; Q; U; Selfg. 1. If 2. If 3. If 4. If 5. If 6. If 6 6 6 0 then L <C L 0 and L <P C L 0 . 0 then L 6 C L 0 and L 6 P C L 0 . 0 and 0 n 6= fU g then L <T L 0 . 0 and n 0 6= fU g then L 6 T L 0 . 0 and 0 n 6= fOg then L <A L 0 .
0 and n 0 6= fOg then L 6 A L 0 .
Proof. Just observe that the concepts C listed in Figure 2 do not use any of the role constructors ", R S, R t S, R , C?. All the lemmas and theorems given in this paper hold for the case when L is a sublogic of ALCreg that extends ALC. Their proofs do not require any change. 2
Figure 3 illustrates the relationship between the expressiveness of all the DLs that extend L, where ALC L ALCreg, with any non-empty combination of the features I, O, Q, U , Self. Note that the problems whether L <T L 0 when 0 n = fU g and whether L <A L 0 when 0 n = fOg remain open. LIOQU
LIOQSelf
LIOUSelf
LIQUSelf
LOQUSelf LIOQ
LIOU
LIOSelf LIQU
LIO LIQ LIU LISelf LOQ LOU LOSelf LQU
LI
LO
LU
LSelf LQ
L Fig. 3. Comparing the expressiveness of description logics, where ALC L ALCreg. If there is a path from a logic L2 down to a logic L1 that contains either a normal edge or at least two edges then L2 is more expressive than L1 w.r.t. concepts, positive concepts, TBoxes and ABoxes. If the path is a dotted edge then L2 is more expressive than L1 w.r.t. concepts, positive concepts and TBoxes. If the path is a dashed edge then L2 is more expressive than L1 w.r.t. concepts, positive concepts and ABoxes. 5
Analyzing the expressiveness of logics is a theoretical topic that has attracted
a lot of logicians. In this paper we have studied the expressiveness of large classes
of DLs. Namely, we have provided results about separating the expressiveness of
the DLs that extend L, where ALC L ALCreg, with any combination of the
features I, O, Q, U , Self. Our separation results are w.r.t. concepts, positive
concepts, TBoxes and ABoxes. Our work di ers signi cantly from all of [
This work was supported by the Polish National Science Centre (NCN) under Grant No. 2011/01/B/ST6/02759. I am grateful to my supervisor, dr hab. Linh Anh Nguyen, for his guidance. I would also like to thank the anonymous reviewers for comments and suggestions. 22. Stewart, I.: Comparing the expressibility of languages formed using NP-complete operators. J. Log. Comput. 1(3), 305{330 (1991) 23. Toman, D., Niwinski, D.: First-order queries over temporal databases inexpressible in temporal logic. In: Proceedings of EDBT'1996. LNCS, vol. 1057, pp. 307{324.
Springer (1996) 24. Tran, T.L., Ha, Q.T., Hoang, T.L.G., Nguyen, L., Nguyen, H.: Bisimulation-based concept learning in description logics. In: Proceedings of CS&P'2013. CEUR Workshop Proceedings, vol. 1032, pp. 421{433. CEUR-WS.org (2013) 25. Tran, T.L., Ha, Q.T., Hoang, T.L.G., Nguyen, L., Nguyen, H., Szalas, A.: Concept learning for description logic-based information systems. In: Proceedings of KSE'2012. pp. 65{73. IEEE Computer Society (2012) 26. Tran, T.L., Nguyen, L., Hoang, T.L.G.: A domain partitioning method for bisimulation-based concept learning in description logics. In: Proceedings of ICCSAMA'2014. Advances in Intelligent Systems and Computing, vol. 282, pp. 297{ 312. Springer (2014)