=Paper=
{{Paper
|id=Vol-1193/paper_11
|storemode=property
|title=Comparing the Expressiveness of Description Logics
|pdfUrl=https://ceur-ws.org/Vol-1193/paper_11.pdf
|volume=Vol-1193
|dblpUrl=https://dblp.org/rec/conf/dlog/Divroodi14
}}
==Comparing the Expressiveness of Description Logics==
<pdf width="1500px">https://ceur-ws.org/Vol-1193/paper_11.pdf</pdf>
<pre>
              Comparing the Expressiveness of
                   Description Logics

                                 Ali Rezaei Divroodi

                    Institute of Informatics, University of Warsaw
                          Banacha 2, 02-097 Warsaw, Poland
                                 rezaei@mimuw.edu.pl



       Abstract. This work studies the expressiveness of the description log-
       ics that extend ALC reg (a variant of PDL) with any combination of the
       features: inverse roles, nominals, quantified number restrictions, the uni-
       versal role, the concept constructor for expressing the local reflexivity of
       a role. We compare the expressiveness of these description logics w.r.t.
       concepts, positive concepts, TBoxes and ABoxes. Our results about sepa-
       rating the expressiveness of description logics are based on bisimulations
       and bisimulation-based comparisons. They are naturally extended to the
       case when instead of ALC reg we have any sublogic of ALC reg that ex-
       tends ALC.


1    Introduction

Expressiveness (expressive power) is a topic studied in the fields of formal lan-
guages, databases and logics. The Chomsky hierarchy provides fundamental re-
sults on the expressiveness of formal languages. In the field of databases, the
works by Fagin [11, 12], Immerman [15, 16], Abiteboul and Vianu [1] provide
important results on the expressiveness of query languages. Many results on the
expressiveness of logics have also been obtained, e.g. in [13, 15, 3, 17, 22, 18, 23].
    The expressiveness of description logics (DLs) has been studied in a number
of works [2, 5, 6, 19, 20]. In [2] Baader proposed a formal definition of the expres-
sive power of DLs. His definition is liberal in that it allows the compared logics to
have different vocabularies. His work provides separation results for some early
DLs. In [5] Borgida showed that certain DLs have the same expressiveness as the
two or three variable fragment of first-order logic. The class of DLs considered
in [5] is large, but the results only concern DLs without the reflexive and transi-
tive closure of roles. In [6] Cadoli et al. considered the expressiveness of hybrid
knowledge bases that combine a DL knowledge base with Horn rules. The used
DL is ALCN R. The work [19] by Kurtonina and de Rijke is a comprehensive
work on the expressiveness of DLs that are sublogics of ALCN R. It is based
on bisimulation and provides many interesting results. In [20] Lutz et al. char-
acterized the expressiveness and rewritability of DL TBoxes for the DLs that
are sublogics of ALCQIO. They used semantic notions such as bisimulation,
equisimulation, disjoint union and direct product.
     This work studies the expressiveness of the DLs that extend ALC reg (a vari-
ant of PDL) with any combination of the features: inverse roles, nominals, quan-
tified number restrictions, the universal role, the concept constructor for express-
ing the local reflexivity of a role. We compare the expressiveness of these DLs
w.r.t. concepts, positive concepts, TBoxes and ABoxes. Our results about sep-
arating the expressiveness of DLs are based on bisimulations and bisimulation-
based comparisons studied in our joint works [8–10]. They are naturally extended
to the case when instead of ALC reg we have any sublogic of ALC reg that extends
ALC.
     Our work differs significantly from all of [2, 5, 6, 19, 20], as the class of con-
sidered DLs is much larger than the ones considered in those works (we allow
PDL-like role constructors as well as the universal role and the concept con-
structor ∃r.Self) and our results about separating the expressiveness of DLs are
obtained not only w.r.t. concepts and TBoxes but also w.r.t. positive concepts
and ABoxes.
     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 [10]. In Section 3
we recall the definitions of bisimulations and bisimulation-based comparisons as
well as some invariance or preservation results of [8–10]. In Section 4 we present
our results on the expressiveness of DLs. Section 5 concludes this work.


2    Notation and Semantics of Description Logics
Our languages use a finite set ΣC of concept names (atomic concepts), a finite
set ΣR of role names (atomic roles), and a finite 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 (quan-
tified number restriction), U (universal role), Self (the local reflexivity of a role).
A set of DL-features is a set consisting of some or zero of these names. We some-
times abbreviate sets of DL-features, writing, e.g., IOQ instead of {I, O, Q}.
From now on, if not stated otherwise, let Φ be any set of DL-features and let L
stand for ALC reg .

Definition 2.1. The DL language LΦ allows roles and concepts defined induc-
tively as follows:
 – if r ∈ ΣR then r is a role of LΦ
 – if A ∈ Σ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, ∃R.C and ∀R.C are concepts of LΦ
     • if I ∈ Φ then R− is a role of LΦ
     • if O ∈ Φ and a ∈ ΣI then {a} is a concept of LΦ
     • if Q ∈ Φ, r ∈ ΣR and n is a natural number
        then ≥ n r.C and ≤ n r.C are concepts of LΦ
       • if {Q, I} ⊆ Φ, r ∈ ΣR and n is a natural number
         then ≥ n r− .C and ≤ n r− .C are concepts of LΦ
       • if U ∈ Φ then U is a role of LΦ
       • if Self ∈ Φ and r ∈ ΣR then ∃r.Self is a concept of LΦ .                    2
The following definition introduces positive concepts of LΦ .
Definition 2.2. Let Lpos                                        pos    pos
                         Φ be the smallest set of concepts and LΦ,∃ , LΦ,∀ be the
smallest sets of roles defined recursively as follows:
 – if r ∈ ΣR then r is a role of Lpos       pos
                                  Φ,∃ and LΦ,∀ ,
 – if I ∈ Φ and r ∈ ΣR then r− is a role of Lpos          pos
                                               Φ,∃ and LΦ,∀ ,
 – if R and S are roles of Lpos
                             Φ,∃ and C is a concept of LΦ
                                                          pos

                           ∗                        pos
   then ε, R ◦ S, R t S, R and C? are roles of LΦ,∃ ,
 – if R and S are roles of Lpos
                             Φ,∀ and C is a concept of LΦ
                                                          pos
                                                        pos
   then ε, R ◦ S, R t S, R∗ and (¬C)? are roles of LΦ,∀ ,
 – if A ∈ ΣC then A is a concept of Lpos
                                       Φ ,
 – if O ∈ Φ and a ∈ ΣI then {a} is a concept of Lpos Φ ,
 – if Self ∈ Φ and r ∈ ΣR then ∃r.Self is a concept of Lpos   Φ ,
 – if C is a concept of Lpos                  pos                    pos
                         Φ , R is a role of LΦ,∃ and S is a role of LΦ,∀ then
                                                               pos
     • >, C t D, C u D, ∃R.C and ∀S.C are concepts of LΦ ,
     • if Q ∈ Φ, r ∈ ΣR and n is a natural number
        then ≥ n r.C and ≤ n r.(¬C) are concepts of Lpos Φ ,
     • if {Q, I} ⊆ Φ, r ∈ ΣR and n is a natural number
        then ≥ n r− .C and ≤ n r− .(¬C) are concepts of Lpos Φ ,
     • if U ∈ Φ then ∀U.C and ∃U.C are concepts of Lpos   Φ .

A concept of Lpos
              Φ is called a positive concept of LΦ .                                 2
    We introduce both Lpos           pos
                          Φ,∀ and LΦ,∃ due to the test constructor of roles. The
concepts ∃(A?).B and ∀((¬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 ∪ {r− | r ∈
                                                                ±
ΣR }. 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 C I (x) to denote x ∈ C I , and write RI (x, y) to denote hx, yi ∈ RI .
1
    That the concept ≤ n R.(¬A) is positive should not be a surprise, as ∀R.A is equiv-
    alent to ≤ 0 R.(¬A).
        (R ◦ S)I = RI ◦ S I                       >I = ∆I
        (R t S)I = RI ∪ S I                       ⊥I = ∅
           (R∗ )I = (RI )∗                     (¬C)I = ∆I \ C I
           (C?)I = {hx, xi | C I (x)}       (C t D)I = C I ∪ DI
              εI = {hx, xi | x ∈ ∆I }       (C u D)I = C I ∩ DI
             U I = ∆I × ∆I                       {a}I = {aI }
          (R ) = (RI )−1
             − I
                                           (∃r.Self)I = {x ∈ ∆I | rI (x, x)}

                (∃R.C)I = {x ∈ ∆I | ∃y [RI (x, y) and C I (y)]
                (∀R.C)I = {x ∈ ∆I | ∀y [RI (x, y) implies C I (y)]}
              (≥ n R.C)I = {x ∈ ∆I | #{y | RI (x, y) and C I (y)} ≥ n}
              (≤ n R.C)I = {x ∈ ∆I | #{y | RI (x, y) and C I (y)} ≤ n}



           Fig. 1. Interpretation of complex roles and complex concepts.


    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 |= C v D, if
C I ⊆ DI .
    A TBox in LΦ is a finite set of terminological axioms in LΦ . An interpretation
I is a model of a TBox T , denoted by I |= 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 as-
sertion), a = b, and a 6= b, where C is a concept and R is a role in LΦ .
    Given an interpretation I, define that:
                   I |= a = b    if aI = bI ,
                   I |= a 6= b   if aI 6= bI ,
                   I |= C(a)     if C I (aI ) holds,
                   I |= R(a, b) if RI (aI , bI ) holds,
                   I |= ¬R(a, b) if RI (aI , bI ) does not hold.
    We say that I satisfies an individual assertion ϕ if I |= ϕ.
    An ABox in LΦ is a finite set of individual assertions in LΦ . An interpretation
I is a model of an ABox A, denoted by I |= A, if it satisfies all the assertions
of A.

3   Bisimulations and Bisimulation-Based Comparisons
Bisimulation is a very useful notion for DLs. It can be used for analyzing ex-
pressiveness of DLs (as investigated in [19] and the current paper), minimizing
interpretations [8–10] and concept learning in DLs [21, 25, 14, 7, 24, 26]. The fol-
lowing definition comes from our joint works [8–10].
Definition 3.1. Let I and I 0 be interpretations. A binary relation
              0
Z ⊆ ∆I × ∆I is called an LΦ -bisimulation between I and I 0 if the following
                                                                              0
conditions hold for every a ∈ ΣI , A ∈ ΣC , r ∈ ΣR , x, y ∈ ∆I , x0 , y 0 ∈ ∆I :
                             0
          Z(aI , aI )                                                                             (1)
                     0                I               I0       0
          Z(x, x ) ⇒ [A (x) ⇔ A (x )]                                                             (2)
                         0        I                        0           I0   0       I0   0   0
          [Z(x, x ) ∧ r (x, y)] ⇒ ∃y ∈ ∆ [Z(y, y ) ∧ r (x , y )]                                  (3)
                         0        I0      0       0                     I       0   I
          [Z(x, x ) ∧ r (x , y )] ⇒ ∃y ∈ ∆ [Z(y, y ) ∧ r (x, y)],                                 (4)
if I ∈ Φ then
                                                                        0            0
          [Z(x, x0 ) ∧ rI (y, x)] ⇒ ∃y 0 ∈ ∆I [Z(y, y 0 ) ∧ rI (y 0 , x0 )]                       (5)
                         0        I0      0       0                     I       0   I
          [Z(x, x ) ∧ r (y , x )] ⇒ ∃y ∈ ∆ [Z(y, y ) ∧ r (y, x)],                                 (6)
if O ∈ Φ then
                                                                   0
          Z(x, x0 ) ⇒ [x = aI ⇔ x0 = aI ],                                                        (7)
if Q ∈ Φ then
          if Z(x, x0 ) holds then, for every role name r, there exists a bijection
                                         0                                                        (8)
          h : {y | rI (x, y)} → {y 0 | rI (x0 , y 0 )} such that h ⊆ Z,
if {Q, I} ⊆ Φ then (additionally)
          if Z(x, x0 ) holds then, for every role name r, there exists a bijection
                                         0                                                        (9)
          h : {y | rI (y, x)} → {y 0 | rI (y 0 , x0 )} such that h ⊆ Z,
if U ∈ Φ then
                                              0
          ∀x ∈ ∆I ∃x0 ∈ ∆I Z(x, x0 )                                                             (10)
             0               I0               I            0
          ∀x ∈ ∆ ∃x ∈ ∆ Z(x, x ),                                                                (11)
if Self ∈ Φ then
                                                           0
          Z(x, x0 ) ⇒ [rI (x, x) ⇔ rI (x0 , x0 )].                                               (12)
      0          0                    0
By (2 ), (7 ) and (12 ) 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 I 0 [10].                                    2
    As shown in [4], the PDL-like role constructors are “safe” for the conditions
(3)-(6). That is, we need to specify these conditions only for atomic roles, and
as a consequence, they also hold for complex roles.
Definition 3.2. A concept C in LΦ is invariant for LΦ -bisimulation if, for any
interpretation I, I 0 and any LΦ -bisimulation Z between I and I 0 , if Z(x, x0 )
                               0
holds then x ∈ C I iff x0 ∈ C I . A TBox T in LΦ is invariant for LΦ -bisimulation
if, for every interpretations I and I 0 , if there exists an LΦ -bisimulation between
I and I 0 then I is a model of T iff I 0 is a model of T . The notion of whether
an ABox in LΦ is invariant for LΦ -bisimulation is defined similarly.               2
Definition 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 ∈ ΣI , via a path consisting of edges being instances of basic roles.         2
    The following theorem comes from our joint work [8].
Theorem 3.4.
1. All concepts in LΦ are invariant for LΦ -bisimulation.
2. If U ∈ Φ then all TBoxes in LΦ are invariant for LΦ -bisimulation.
3. Let T be a TBox in LΦ and I, I 0 be unreachable-objects-free interpretations
   (w.r.t. LΦ ) such that there exists an LΦ -bisimulation between I and I 0 . Then
   I is a model of T iff I 0 is a model of T .
4. Let A be an ABox in LΦ . If O ∈ Φ or A contains only assertions of the form
   C(a) then A is invariant for LΦ -bisimulation.
Definition 3.5. A concept C of LΦ is preserved by LΦ -comparisons if, for any
interpretations I, I 0 and any LΦ -comparison Z between I and I 0 , if Z(x, x0 )
                               0
holds and x ∈ C I then x0 ∈ C I .                                            2
    The following theorem comes from our joint work [10].
Theorem 3.6. All concepts of Lpos
                              Φ   are preserved by LΦ -comparisons.


4    Comparing the Expressiveness of Description Logics
Definition 4.1. Two concepts C and D are equivalent if, for every interpreta-
tion I, C I = DI . Two TBoxes T1 and T2 are equivalent if, for every interpre-
tation I, I is a model of T1 iff I is a model of T2 . Two ABoxes A1 and A2 are
equivalent if, for every interpretation I, I is a model of A1 iff I is a model of A2 .
Definition 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),
denoted by L1 <C L2 (resp. L1 <P C L2 , L1 <T L2 , L1 <A L2 ), if L1 ≤C L2
(resp. L1 ≤P C L2 , L1 ≤T L2 , L1 ≤A L2 ) and L2 6≤C L1 (resp. L2 6≤P C L1 ,
L2 6≤T L1 , L2 6≤A 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, I 0 be interpretations and Z an L1 -bisimulation
between I and I 0 .
                                     0
1. If L1 ≤C L2 , x ∈ ∆I , x0 ∈ ∆I , Z(x, x0 ) holds, and there exists a concept C
                                        0
   of L2 such that x ∈ C I but x0 6∈ C I , then L1 <C L2 .
2. Suppose that U ∈ Φ1 or both I and I 0 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 I 0 is not, then L1 <T L2 .
3. Suppose O ∈ Φ1 . If L1 ≤A L2 and there exists an ABox A in L2 such that
   I is a model of A but I 0 is not, then L1 <A L2 .
                                                                                      0
Proof. Consider the first assertion. Suppose L1 ≤C L2 , x ∈ ∆I , x0 ∈ ∆I ,
                                                                                    0
Z(x, x0 ) holds and there exists a concept C of L2 such that x ∈ C I but x0 6∈ C I .
We prove that L2 6≤C L1 . For the sake of contradiction, suppose L2 ≤C L1 . It
follows that there exists a concept C 0 of L1 that is equivalent to C. Thus, x ∈ C 0I
              0
but x0 6∈ C 0I . Hence, C 0 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 I 0 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 I 0 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 I 0 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 I 0 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, I 0 be interpretations and Z an L1 -comparison
                                                        0
between I and I 0 . If L1 ≤P C L2 , x ∈ ∆I , x0 ∈ ∆I , Z(x, x0 ) holds, and there
                                                                 0
exists a positive concept C of L2 such that x ∈ C I but x0 6∈ C I , then L1 <P C L2 .
                                                   0
Proof. Suppose L1 ≤P C L2 , x ∈ ∆I , x0 ∈ ∆I , Z(x, x0 ) holds and there exists
                                                                  0
a positive concept C of L2 such that x ∈ C I but x0 6∈ C I . 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 C 0 of L1 that is equivalent to C. Thus, x ∈ C 0I
              0
but x0 6∈ C 0I . It follows that C 0 is not preserved by Z, which contradicts Theo-
rem 3.6. Hence, L1 <P C L2 .                                                     2

    From now on, we assume that ΣC and ΣR are not empty and ΣI contains
at least two individual names. Let {a, b} ⊆ ΣI , A ∈ ΣC and r ∈ ΣR .

Lemma 4.6.
1. For any pair hL1 , L2 i among hLI , LOQU Self i, hLQ , LIOU Self i, hLSelf , LIOQU i,
   we have that: L1 6≤C L2 , L1 6≤P C L2 , L1 6≤T L2 , L1 6≤A L2 .
                                      I                                               I0
  LI vs.
  LOQU Self
                                                                           0                          0
                        aI : A                  bI                    aI : A                     bI
              −1
  C = ∀r∀r         .A
                         u1                     u2                         v1



                                            I                         I0
  LQ vs.
                                                            0
  LIOU Self                               aI : A         aI : A

  C = (≤ 1r.¬A)
                                            u               v1                  v2



                                           I                                     I0
  LSelf vs.
                                                                       0
  LIOQU                       aI : A                             aI : A

  C = ∃r∃r.Self
                                     u1          u2                    v1              v2




  LO vs.                         I                                               I0
  LIQU Self
                                                                  0                         0
                         aI = bI : A                            aI : A                 bI : A
  C = {b}

                                 u                                v1                        v2




  LU vs.                              I                                    I0
  LIOQSelf
                                                                  0
  C = ∀U.A                       aI : A                         aI : A                v



                           Fig. 2. An illustration for Lemma 4.6.




2. LO 6≤C LIQU Self , LO 6≤P C LIQU Self , LO 6≤T LIQU Self .
3. LU 6≤C LIOQSelf , LU 6≤P C LIOQSelf , LU 6≤A LIOQSelf .
Proof. Let us compare LI with LOQU Self . Consider the interpretations I, I 0 and
the relation Z shown in the first part of Figure 2. The arrows denote the instances
of r in I and I 0 . The instances of A in I and I 0 are explicitly indicated in the
                       0                                  0
figure. Let B I = B I = ∅ for all B ∈ ΣC \ {A}, sI = sI = ∅ for all s ∈ ΣR \ {r},
                   0     0
and cI = aI , cI = aI for all c ∈ ΣI \ {a, b}. The dotted lines in the figure
                                                            0
indicate the instances of a binary relation Z ⊆ ∆I × ∆I . It can be checked that
Z is an LOQU Self -bisimulation between I and I 0 . Consider the positive concept
                                               0      0
C = ∀r∀r−1 .A of LI . Clearly, aI ∈ C I but aI 6∈ C I . By Theorem 3.4(1), C does
not have any equivalent concept in LOQU Self . Hence, LI 6≤C LOQU Self . As Z is
also an LOQU Self -comparison between I and I 0 , by Theorem 3.6, C does not have
any equivalent positive concept in LOQU Self either. Hence, LI 6≤P C LOQU Self .
Consider the TBox T = {A v C}. Since I |= T but I 0 6|= T , by Theorem 3.4(3),
T does not have any equivalent TBox in LOQU Self . Hence LI 6≤T LOQU Self .
Consider the ABox A = {C(a)}. Since I |= A but I 0 6|= A, by Theorem 3.4(4),
A does not have any equivalent ABox in LOQU Self . Hence LI 6≤A LOQU Self .
    The proofs for the other pairs of logics can be done similarly, using I, I 0 , C
specified in the next parts of Figure 2. For the parts without the presence of b,
                     0     0
let bI = aI and bI = aI .                                                          2
Theorem 4.7. Let Φ and Φ0 be subsets of {I, O, Q, U, Self}.
1. If Φ ⊂ Φ0 then LΦ <C LΦ0 and LΦ <P C LΦ0 .
2. If Φ 6⊆ Φ0 then LΦ 6≤C LΦ0 and LΦ 6≤P C LΦ0 .
3. If Φ ⊂ Φ0 and Φ0 \ Φ 6= {U } then LΦ <T LΦ0 .
4. If Φ 6⊆ Φ0 and Φ \ Φ0 6= {U } then LΦ 6≤T LΦ0 .
5. If Φ ⊂ Φ0 and Φ0 \ Φ 6= {O} then LΦ <A LΦ0 .
6. If Φ 6⊆ Φ0 and Φ \ Φ0 6= {O} then LΦ 6≤A LΦ0 .
Proof. Consider the first 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 \ Φ 6= ∅, at least one
feature among I, O, Q, U , Self belongs to Φ0 \ Φ. Consider the case I ∈ Φ0 \ Φ.
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 LOQU Self (resp. LΦ ≤P C LOQU Self ), it follows that LI ≤C LOQU Self
(resp. LI ≤P C LOQU Self ), 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 Φ \ Φ0 6= ∅, at
least one feature among I, O, Q, U , Self belongs to Φ \ Φ0 . Consider the case
I ∈ Φ \ Φ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 LOQU Self (resp. LΦ0 ≤P C LOQU Self ), it follows
that LI ≤C LOQU Self (resp. LI ≤P C LOQU Self ), 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 \ Φ 6= {U }. At
least one feature among I, O, Q, Self belongs to Φ0 \ Φ. Consider the case
I ∈ Φ0 \ Φ. 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 LOQU Self , it follows that LI ≤T LOQU Self , which contradicts
Lemma 4.6. Therefore, LΦ <T LΦ0 .
    Consider the fourth assertion and suppose Φ 6⊆ Φ0 and Φ \ Φ0 6= {U }. At least
one feature among I, O, Q, Self belongs to Φ \ Φ0 . Consider the case I ∈ Φ \ Φ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 LOQU Self , it follows that
LI ≤T LOQU Self , which contradicts Lemma 4.6. Therefore, LΦ 6≤T LΦ0 .
    Consider the fifth assertion and suppose Φ ⊂ Φ0 and Φ0 \ Φ 6= {O}. At
least one feature among I, Q, U , Self belongs to Φ0 \ Φ. Consider the case
I ∈ Φ0 \ Φ. 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 LOQU Self , it follows that LI ≤A LOQU Self , which contradicts
Lemma 4.6. Therefore, LΦ <A LΦ0 .
    Consider the last assertion and suppose Φ 6⊆ Φ0 and Φ\Φ0 6= {O}. At least one
feature among I, Q, U , Self belongs to Φ \ Φ0 . Consider the case I ∈ Φ \ Φ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 LOQU Self , it follows that
LI ≤A LOQU Self , which contradicts Lemma 4.6. Therefore, LΦ 6≤A LΦ0 .           2


Definition 4.8. We define ALC to be the sublogic of ALC reg such that the
role constructors ε, R ◦ S, R t S, R∗ and C? are disallowed. We say that L
is a sublogic of ALC reg that extends ALC, denoted ALC ≤ L ≤ ALC reg , if it
extends ALC with some of those role constructors. For Φ ⊆ {I, O, Q, U, Self}
and ALC ≤ L ≤ ALC reg , let LΦ and Lpos Φ  be defined as usual in the spirit of
Definitions 2.1 and 2.2.                                                     2

Corollary 4.9. Let L be any sublogic of ALC reg that extends ALC and let Φ
and Φ0 be subsets of {I, O, Q, U, Self}.

1. If Φ ⊂ Φ0 then LΦ <C LΦ0 and LΦ <P C LΦ0 .
2. If Φ 6⊆ Φ0 then LΦ 6≤C LΦ0 and LΦ 6≤P C LΦ0 .
3. If Φ ⊂ Φ0 and Φ0 \ Φ 6= {U } then LΦ <T LΦ0 .
4. If Φ 6⊆ Φ0 and Φ \ Φ0 6= {U } then LΦ 6≤T LΦ0 .
5. If Φ ⊂ Φ0 and Φ0 \ Φ 6= {O} then LΦ <A LΦ0 .
6. If Φ 6⊆ Φ0 and Φ \ Φ0 6= {O} 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 ALC reg 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 ≤ ALC reg , with any non-empty combination of
the features I, O, Q, U , Self. Note that the problems whether LΦ <T LΦ0 when
Φ0 \ Φ = {U } and whether LΦ <A LΦ0 when Φ0 \ Φ = {O} remain open.
                                       LIOQU Self


          LIOQU          LIOQSelf       LIOU Self      LIQU Self         LOQU Self



 LIOQ     LIOU    LIOSelf   LIQU     LIQSelf LIU Self LOQU LOQSelf LOU Self LQU Self




    LIO   LIQ      LIU      LISelf    LOQ        LOU   LOSelf      LQU     LQSelf    LU Self



             LI             LO              LQ           LU                LSelf


                                            L

Fig. 3. Comparing the expressiveness of description logics, where ALC ≤ L ≤ ALC reg .
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     Conclusions
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 ≤ ALC reg , 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 differs significantly from all of [2, 5, 6,
19, 20], as the class of considered DLs is much larger than the ones considered
in those works and our results about separating the expressiveness of DLs are
obtained not only w.r.t. concepts and TBoxes but also w.r.t. positive concepts
and ABoxes.

Acknowledgements
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.
References

 1. Abiteboul, S., Vianu, V.: Expressive power of query languages. In: Theoretical
    Studies in Computer Science. pp. 207–251 (1992)
 2. Baader, F.: A formal definition for the expressive power of terminological knowl-
    edge representation languages. J. Log. Comput. 6(1), 33–54 (1996)
 3. van Benthem, J.: Modal Logic and Classical Logic. Bibliopolis, Naples (1983)
 4. Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. No. 53 in Cambridge Tracts
    in Theoretical Computer Science, Cambridge University Press (2001)
 5. Borgida, A.: On the relative expressiveness of description logics and predicate
    logics. Artif. Intell. 82(1-2), 353–367 (1996)
 6. Cadoli, M., Palopoli, L., Lenzerini, M.: Datalog and description logics: Expressive
    power. In: Proceedings of APPIA-GULP-PRODE’1997. pp. 333–344 (1997)
 7. Divroodi, A., Ha, Q.T., Nguyen, L., Nguyen, H.: On C-learnability in description
    logics. In: Proceedings of ICCCI’2012 (1). LNCS, vol. 7653, pp. 230–238. Springer
    (2012)
 8. Divroodi, A., Nguyen, L.: On bisimulations for description logics. http://arxiv.
    org/abs/1104.1964 (2011)
 9. Divroodi, A., Nguyen, L.: On bisimulations for description logics. In: Proceedings
    of CS&P’2011. pp. 99–110 (2011)
10. Divroodi, A., Nguyen, L.: Bisimulation-based comparisons for interpretations in
    description logics. In: Proceedings of DL’2013. CEUR Workshop Proceedings, vol.
    1014, pp. 652–669. CEUR-WS.org (2013)
11. Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets.
    In: SIAM-AMS Proceedings. vol. 7 (1974)
12. Fagin, R.: Monadic generalized spectra. Zeitschr. f. math. Logik und Grundlagen
    d. Math. 21, 89–96 (1975)
13. Gabbay, D.: Expressive functional completeness in tense logic. In: Monnich, U.
    (ed.) Aspects of Philosophical Logic, pp. 91–117. Reidel, Dordrecht (1981)
14. Ha, Q.T., Hoang, T.L.G., Nguyen, L., Nguyen, H., Szalas, A., Tran, T.L.: A
    bisimulation-based method of concept learning for knowledge bases in description
    logics. In: Proceedings of SoICT’2012. pp. 241–249. ACM (2012)
15. Immerman, N.: Upper and lower bounds for first order expressibility. J. Comput.
    Syst. Sci. 25(1), 76–98 (1982)
16. Immerman, N.: Relational queries computable in polynomial time. Information
    and Control 68(1-3), 86–104 (1986)
17. Immerman, N., Kozen, D.: Definability with bounded number of bound variables.
    In: Proceedings of LICS’1987. pp. 236–244. IEEE Computer Society (1987)
18. Janin, D., Walukiewicz, I.: On the expressive completeness of the propositional
    mu-calculus with respect to monadic second order logic. In: Proceedings of CON-
    CUR’1996. LNCS, vol. 1119, pp. 263–277. Springer (1996)
19. Kurtonina, N., de Rijke, M.: Expressiveness of concept expressions in first-order
    description logics. Artif. Intell. 107(2), 303–333 (1999)
20. Lutz, C., Piro, R., Wolter, F.: Description logic TBoxes: Model-theoretic charac-
    terizations and rewritability. In: Walsh, T. (ed.) Proceedings of IJCAI’2011. pp.
    983–988 (2011)
21. Nguyen, L., Szalas, A.: Logic-based roughification. In: Skowron, A., Suraj, Z. (eds.)
    Rough Sets and Intelligent Systems (To the Memory of Professor Zdzislaw Pawlak),
    Vol. 1, pp. 529–556. Springer (2012)
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 Work-
    shop 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.: Con-
    cept 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 ICC-
    SAMA’2014. Advances in Intelligent Systems and Computing, vol. 282, pp. 297–
    312. Springer (2014)

</pre>