=Paper=
{{Paper
|id=Vol-1193/paper_20
|storemode=property
|title=Rational Closure in SHIQ
|pdfUrl=https://ceur-ws.org/Vol-1193/paper_20.pdf
|volume=Vol-1193
|dblpUrl=https://dblp.org/rec/conf/dlog/GiordanoGOP14
}}
==Rational Closure in SHIQ==
<pdf width="1500px">https://ceur-ws.org/Vol-1193/paper_20.pdf</pdf>
<pre>
                               Rational closure in SHIQ

        Laura Giordano1 , Valentina Gliozzi2 , Nicola Olivetti3 , and Gian Luca Pozzato2
          1
            DISIT - U. Piemonte Orientale, Alessandria, Italy - laura@mfn.unipmn.it
    2
         Dip. di Informatica - Univ. di Torino, Italy - {gliozzi,pozzato}@di.unito.it
        3
          Aix-Marseille Université, CNRS, France nicola.olivetti@univ-amu.fr

              Abstract. We define a notion of rational closure for the logic SHIQ, which
              does not enjoys the finite model property, building on the notion of rational
              closure introduced by Lehmann and Magidor in [24]. We provide a semantic
              characterization of rational closure in SHIQ in terms of a preferential semantics,
              based on a finite rank characterization of minimal models. We show that the
              rational closure of a TBox can be computed in E XP T IME using entailment in
              SHIQ.


1       Introduction
Recently, a large amount of work has been done in order to extend the basic formalism of
Description Logics (for short, DLs) with nonmonotonic reasoning features [27, 1, 10, 11,
13, 17, 21, 4, 2, 6, 26, 23]; the purpose of these extensions is that of allowing reasoning
about prototypical properties of individuals or classes of individuals. In these extensions
one can represent, for instance, knowledge expressing the fact that the hematocrit level
is usually under 50%, with the exceptions of newborns and of males residing at high
altitudes, that have usually much higher levels (even over 65%). Furthermore, one can
infer that an individual enjoys all the typical properties of the classes it belongs to. As an
example, in the absence of information that Carlos and the son of Fernando are either
newborns or adult males living at a high altitude, one would assume that the hematocrit
levels of Carlos and Fernando’s son are under 50%. This kind of inferences apply to
individual explicitly named in the knowledge base as well as to individuals implicitly
introduced by relations among individuals (the son of Fernando).
     In spite of the number of works in this direction, finding a solution to the problem of
extending DLs for reasoning about prototypical properties seems far from being solved.
The most well known semantics for nonmonotonic reasoning have been used to the
purpose, from default logic [1], to circumscription [2], to Lifschitz’s nonmonotonic logic
MKNF [10, 26], to preferential reasoning [13, 4, 17], to rational closure [6, 9].
     In this work, we focus on rational closure and, specifically, on the rational closure
for SHIQ. The interest of rational closure in DLs is that it provides a significant
and reasonable nonmonotonic inference mechanism, still remaining computationally
inexpensive. As shown for ALC in [6], its complexity can be expected not to exceed
the one of the underlying monotonic DL. This is a striking difference with most of
the other approaches to nonmonotonic reasoning in DLs mentioned above, with some
exception such as [26, 23]. More specifically, we define a rational closure for the logic
SHIQ, building on the notion of rational closure in [24] for propositional logic. This is
a difference with respect to the rational closure construction introduced in [6] for ALC,
which is more similar to the one by Freund [12] for propositional logic (for propositional
logic, the two definitions of rational closure are shown to be equivalent [12]). We provide
a semantic characterization of rational closure in SHIQ in terms of a preferential
semantics, by generalizing to SHIQ the results for rational closure in ALC presented
in [18]. This generalization is not trivial, since SHIQ lacks a crucial property of ALC,
the finite model property [20]. Our construction exploits an extension of SHIQ with a
typicality operator T, that selects the most typical instances of a concept C, T(C). We
define a minimal model semantics and a notion of minimal entailment for the resulting
logic, SHIQR T, and we show that the inclusions belonging to the rational closure of a
TBox are those minimally entailed by the TBox, when restricting to canonical models.
This result exploits a characterization of minimal models, showing that we can restrict to
models with finite ranks. We also show that the rational closure construction of a TBox
can be done exploiting entailment in SHIQ, without requiring to reason in SHIQR T,
and that the problem of deciding whether an inclusion belongs to the rational closure of
a TBox is in E XP T IME.
    Concerning ABox reasoning, because of the interaction between individuals (due to
roles) it is not possible to separately assign a unique minimal rank to each individual
and alternative minimal ranks must be considered. We end up with a kind of skeptical
inference with respect to the ABox, whose complexity in E XP T IME as well.
    For an extended version of this paper with the proofs of the results see [19].

2      A nonmonotonic extension of SHIQ
Following the approach in [14, 17], we introduce an extension of SHIQ [20] with a
typicality operator T in order to express typical inclusions, obtaining the logic SHIQR T.
The intuitive idea is to allow concepts of the form T(C), whose intuitive meaning is that
T(C) selects the typical instances of a concept C. We can therefore distinguish between
the properties that hold for all instances of C (C v D), and those that only hold for the
typical such instances (T(C) v D). Since we are dealing here with rational closure, we
attribute to T properties of rational consequence relation [24]. We consider an alphabet
of concept names C, role names R, transitive roles R+ ⊆ R, and individual constants
O. Given A ∈ C, S ∈ R, and n ∈ N we define:
CR := A | > | ⊥ | ¬CR | CR u CR | CR t CR | ∀S.CR | ∃S.CR | (≥ nS.CR ) | (≤ nS.CR )
CL := CR | T(CR )          S := R | R−
As usual, we assume that transitive roles cannot be used in number restrictions [20]. A
KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusions CL v CR
and role inclusions R v S. ABox contains assertions of the form CL (a) and S(a, b),
where a, b ∈ O.
The semantics of SHIQR T is formulated in terms of rational models: ordinary models
of SHIQ are equipped with a preference relation < on the domain, whose intuitive
meaning is to compare the “typicality” of domain elements, that is to say, x < y means
that x is more typical than y. Typical instances of a concept C (the instances of T(C))
are the instances x of C that are minimal with respect to the preference relation < (so
that there is no other instance of C preferred to x)4 .
 4
     As for the logic ALC R T in [15], an alternative semantic characterization of T can be given
     by means of a set of postulates that are essentially a reformulation of the properties of rational
     consequence relation [24].
Definition 1 (Semantics of SHIQR T). A SHIQR T model M is any structure h∆, <
, Ii where: ∆ is the domain; < is an irreflexive, transitive, well-founded, and modular
(for all x, y, z ∈ ∆, if x < y then x < z or z < y) relation over ∆; I is the extension
function that maps each concept C to C I ⊆ ∆, and each role R to RI ⊆ ∆I × ∆I . For
concepts of SHIQ, C I is defined as usual. For the T operator, we have (T(C))I =
M in< (C I ), where M in< (S) = {u : u ∈ S and @z ∈ S s.t. z < u}.
As for rational models in [24] (see Lemma 14), SHIQR T models can be equivalently
defined by postulating the existence of a function kM : ∆ 7−→ Ord assigning an ordinal
to each domain element, and then letting x < y if and only if kM (x) < kM (y). We
call kM (x) the rank of element x in M. When finite, kM (x) can be understood as the
length of a chain x0 < · · · < x from x to a minimal x0 (an x0 s.t. for no x0 , x0 < x0 ).
Definition 2 (Model satisfying a knowledge base). Given a SHIQR T model M=
h∆, <, Ii, we say that: - a model M satisfies an inclusion C v D if C I ⊆ DI ; similarly
for role inclusions; - M satisfies an assertion C(a) if aI ∈ C I ; and M satisfies an
assertion R(a, b) if (aI , bI ) ∈ RI . Given a KB=(TBox,ABox), we say that: M satisfies
TBox if M satisfies all inclusions in TBox; M satisfies ABox if M satisfies all assertions
in ABox; M is a model of KB if it satisfies both its TBox and its ABox.
The logic SHIQR T, as well as the underlying SHIQ, does not enjoy the finite model
property [20].
    Given a KB, let F be an inclusion or an assertion. We say that F is entailed by KB,
written KB |=SHIQR T F , if for all models M =h∆, <, Ii of KB, M satisfies F .
Let us now introduce the notions of rank of a SHIQ concept.
Definition 3 (Rank of a concept kM (CR )). Given a model M =h∆, <, Ii, we define
the rank kM (CR ) of a concept CR in the model M as kM (CR ) = min{kM (x) | x ∈
CR I }. If CR I = ∅, then CR has no rank and we write kM (CR ) = ∞.
Proposition 1. For any M =h∆, <, Ii, we have that M satisfies T(C) v D if and
only if kM (C u D) < kM (C u ¬D).
It is immediate to verify that the typicality operator T itself is nonmonotonic: T(C) v D
does not imply T(C u E) v D. This nonmonotonicity of T allows to express the
properties that hold for the typical instances of a class (not only the properties that
hold for all the members of the class). However, the logic SHIQR T is monotonic:
what is inferred from KB can still be inferred from any KB’ with KB ⊆ KB’. This is
a clear limitation in DLs. As a consequence of the monotonicity of SHIQR T, one
cannot deal with irrelevance. For instance, KB= {VIP v Person, T(Person) v ≤
1 HasMarried .Person, T(VIP ) v ≥ 2 HasMarried .Person} does not entail KB
|=SHIQR T T(VIP u Tall ) v ≥ 2 HasMarried .Person, even if the property of being
tall is irrelevant with respect to the number of marriages. Observe that we do not want to
draw this conclusion in a monotonic way from SHIQR T, since otherwise we would
not be able to retract it when knowing, for instance, that typical tall VIPs have just one
marriage (see also Example 1). Rather, we would like to obtain this conclusion in a
nonmonotonic way. In order to obtain this nonmonotonic behavior, we strengthen the
semantics of SHIQR T by defining a minimal models mechanism which is similar, in
spirit, to circumscription. Given a KB, the idea is to: 1. define a preference relation
among SHIQR T models, giving preference to the model in which domain elements
have a lower rank; 2. restrict entailment to minimal SHIQR T models (w.r.t. the above
preference relation) of KB.

Definition 4 (Minimal models). Given M =h∆, <, Ii and M0 = h∆0 , <0 , I 0 i we say
                                                                               0
that M is preferred to M0 (M <FIMS M0 ) if (i) ∆ = ∆0 , (ii) C I = C I for all
concepts C, and (iii) for all x ∈ ∆, kM (x) ≤ kM0 (x) whereas there exists y ∈ ∆ such
that kM (y) < kM0 (y). Given a KB, we say that M is a minimal model of KB with
respect to <FIMS if it is a model satisfying KB and there is no M0 model satisfying KB
such that M0 <FIMS M.

Proposition 2 (Existence of minimal models). Let KB be a finite knowledge base, if
KB is satisfiable then it has a minimal model.

The minimal model semantics introduced is similar to the one introduced in [17] for
ALC. However, it is worth noticing that the notion of minimality here is based on the
minimization of the ranks of the worlds, rather then on the minimization of formulas of
a specific kind.
    The following theorem says that reasoning in SHIQR T has the same complexity as
reasoning in SHIQ, i.e. it is in E XP T IME. Its proof is given by providing an encoding of
satisfiability in SHIQR T into satisfiability SHIQ, which is known to be an E XP T IME-
complete problem. The proof is omitted due to space limitations

Theorem 1. Satisfiability in SHIQR T is an E XP T IME-complete problem.


3    Rational Closure for SHIQ
In this section, we extend to SHIQ the notion of rational closure proposed by Lehmann
and Magidor [24] for the propositional case. Given the typicality operator, the typicality
inclusions T(C) v D (all the typical C’s are D’s) play the role of conditional assertions
C |∼ D in [24]. Here we define the rational closure of the TBox. In Section 6 we will
discuss an extension of rational closure that also takes into account the ABox.

Definition 5 (Exceptionality of concepts and inclusions). Let TB be a TBox and C a
concept. C is said to be exceptional for TB if and only if TB |=SHIQR T T(>) v ¬C.
A T-inclusion T(C) v D is exceptional for TB if C is exceptional for TB . The set of
T-inclusions of TB which are exceptional in TB will be denoted as E(TB ).

Given a DL KB=(TBox,ABox), it is possible to define a sequence of non increasing
subsets of TBox E0 ⊇ E1 , E1 ⊇ E2 , . . . by letting E0 = TBox and, for i > 0,
Ei = E(Ei−1 ) ∪ {C v D ∈ TBox s.t. T does not occurr in C}. Observe that, being
KB finite, there is an n ≥ 0 such that, for all m > n, Em = En or Em = ∅. Observe
also that the definition of the Ei ’s is the same as the definition of the Ci ’s in Lehmann
and Magidor’s rational closure [22], except for that here, at each step, we also add all the
“strict” inclusions C v D (where T does not occur in C).
Definition 6 (Rank of a concept). A concept C has rank i (denoted by rank (C) = i)
for KB=(TBox,ABox), iff i is the least natural number for which C is not exceptional for
Ei . If C is exceptional for all Ei then rank (C) = ∞, and we say that C has no rank.

The notion of rank of a formula allows to define the rational closure of the TBox of a KB.
Let |=SHIQ be the entailment in SHIQ. In the following definition, by KB |=SHIQ F
we mean KF |=SHIQ F , where KF does not include the defeasible inclusions in KB.

Definition 7 (Rational closure of TBox). Let KB=(TBox,ABox) be a DL knowledge
base. We define, TBox , the rational closure of TBox, as TBox = {T(C) v D |
either rank (C) < rank (C u ¬D) or rank (C) = ∞} ∪ {C v D | KB |=SHIQ C v
D}, where C and D are arbitrary SHIQ concepts.

Observe that, apart form the addition of strict inclusions, the above definition of rational
closure is the same as the one by Lehmann and Magidor in [24]. The rational closure
of TBox is a nonmonotonic strengthening of SHIQR T. For instance, it allows to deal
with irrelevance, as the following example shows.

Example 1. Let TBox = {T(Actor ) v Charming}. It can be verified that T(Actor u
Comic) v Charming ∈ TBox . This is a nonmonotonic inference that does no longer
follow if we discover that indeed comic actors are not charming (and in this respect are
untypical actors): indeed given TBox’= TBox ∪ {T(Actor u Comic) v ¬Charming},
we have that T(Actor u Comic) v Charming 6∈ TBox 0 . Furthermore, as for the
propositional case, rational closure is closed under rational monotonicity [22]: from
T(Actor ) v Charming ∈ TBox and T(Actor ) v Bold 6∈ TBox it follows that
T(Actor u ¬Bold ) v Charming ∈ TBox .

Although the rational closure TBox is an infinite set, its definition is based on the
construction of a finite sequence E0 , E1 , . . . , En of subsets of TBox, and the problem
of verifying that an inclusion T(C) v D ∈ TBox is in E XP T IME. Let us first prove the
following proposition:

Proposition 3. Let KB=(TBox,∅) be a knowledge base with empty ABox. KB |=SHIQR T
CL v CR iff KB 0 |=SHIQ CL0 v CR  0
                                    , where KB 0 , CL0 and CR
                                                            0
                                                              are polynomial encod-
ings in SHIQ of KB, CL and CR , respectively.

Proof. (Sketch) First of all, let us remember that rational entailment is equivalent to
preferential entailment for a knowledge base only containing positive non-monotonic
implications A |∼ B (see [24]).The same holds in preferential description logics with
typicality. Let SHIQP T be the logic that we obtain when we remove the requirement
of modularity in the definition of SHIQR T. In this logic the typicality operator has
a preferential semantics [22], based on the preferential models of P rather then on
the ranked models of R [22]. It is possible to prove that entailment in SHIQR T and
entailment in SHIQP T are equivalent if we restrict to KBs with empty ABox, as TBox
contains inclusions (positive non-monotonic implications). Hence, to prove the thesis
it suffices to show that for all inclusions CL v CR in SHIQR T: KB |=SHIQP T
CL v CR iff KB 0 |=SHIQ CL0 v CR       0
                                         , for some polynomial encoding KB 0 , CL0 , CR
                                                                                      0
                                                                                        in
SHIQ .
    The idea of the encoding exploits the definition of the typicality operator T intro-
duced in [14] (for ALC), in terms of a Gödel -Löb modality 2 as follows: T(C) is
defined as C u 2¬C where the accessibility relation of the modality 2 is the preference
relation < in preferential models.
    We define the encoding KB’=(TBox’, ABox’) of KB in SHIQ as follows. First,
ABox’=∅. For each A v B ∈ TBox, not containing T, we introduce A v B in TBox’.
For each T(A) in occurring in the TBox, we introduce a new atomic concept 2¬A and,
for each inclusion T(A) v B ∈ TBox, we add to TBox’ the inclusion: A u 2¬A v B.
Furthermore, to capture the properties of the 2 modality, a new role R is introduced
to represent the relation < in preferential models, and the following inclusions are
introduced in TBox’: 2¬A v ∀R.(¬A u 2¬A ) and ¬2¬A v ∃R.(A u 2¬A ).
                                             0
    For the inclusion CL v CR , we let CR      = CR . For a strict inclusion (CL 6= T (A)),
we let CL = CL , while for a defeasible inclusion (CL = T (A)), we let CL0 = A u 2¬A .
          0

    It is clear that the size of KB’ is polynomial in the size of the KB. Given the above
encoding, it can be proved that: KB |=SHIQP T CL v CR iff KB 0 |=SHIQ CL0 v CR           0
                                                                                           .
                                                                                        2

Theorem 2 (Complexity of rational closure over TBox). Given a TBox, the problem
of deciding whether T(C) v D ∈ TBox is in E XP T IME.
Proof. Checking if T(C) v D ∈ TBox can be done by computing the finite sequence
E0 , E1 , . . . , En of non increasing subsets of TBox inclusions in the construction of
the rational closure. Note that the number n of the Ei is O(|KB|), where |KB| is the
size of the knowledge base KB. Computing each Ei = E(Ei−1 ), requires to check, for
all concepts A occurring on the left hand side of an inclusion in the TBox, whether
Ei−1 |=SHIQR T T(>) v ¬A. Regarding Ei−1 as a knowledge base with empty ABox,
by Proposition 3 it is enough to check that Ei−1   0
                                                      |=SHIQ > t 2¬> v ¬A, which
                                                 0
requires an exponential time in the size of Ei−1 (and hence in the size of KB). If not
already checked, the exceptionality of C and of C u ¬D have to be checked for each
Ei , to determine the ranks of C and of C u ¬D (which can be computed in SHIQ as
well). Hence, verifying if T(C) v D ∈ TBox is in E XP T IME.                          2
The above proof also shows that the rational closure of a TBox can be computed simply
using the entailment in SHIQ.

4   Infinite Minimal Models with finite ranks
In the following we provide a characterization of minimal models of a KB in terms of
their rank: intuitively minimal models are exactly those where each domain element has
rank 0 if it satisfies all defeasible inclusions, and otherwise has the smallest rank greater
than the rank of any concept C occurring in a defeasible inclusion T(C) v D of the KB
falsified by the element. Exploiting this intuitive characterization of minimal models,
we are able to show that, for a finite KB, minimal models have always a finite ranking
function, no matter whether they have a finite domain or not. This result allows us to
provide a semantic characterization of rational closure of the previous section to logics,
like SHIQ, that do not have the finite model property.
    Given a model M = h∆, <, Ii, let us define the set SxM of defeasible inclusions
falsified by a domain element x ∈ ∆, as SxM = {T(C) v D ∈ KD | x ∈ (C u¬D)I }}.
Proposition 4. Let M = h∆, <, Ii be a model of KB and x ∈ ∆, then: (a) if kM (x) =
0 then SxM = ∅; (b) if SxM 6= ∅ then kM (x) > kM (C) for every C such that, for some
D, T(C) v D ∈ SxM .

Let us define KF = {C v D ∈ T Box : T does not occur in C} ∪ ABox and KD =
{T(C) v D ∈ T Box}, so that KB = KF ∪ KD .

Proposition 5. Let KB = KF ∪ KD and M = h∆, <, Ii be a model of KF ; suppose
that for any x ∈ ∆ it holds that: - if kM (x) = 0 then SxM = ∅; - if SxM 6= ∅ then
kM (x) > kM (C) for every C s.t., for some D, T(C) v D ∈ SxM . Then M |= KB.

From Propositions 4 and 5, we obtain the following characterization of minimal models.

Theorem 3. Let KB = KF ∪ KD , and let M = h∆, <, Ii be a model of KF . The
following are equivalent:
    – M is a minimal model of KB
    – For every x ∈ ∆ it holds: (a) SxM = ∅ iff kM (x) = 0 (b) if SxM 6= ∅ then
      kM (x) = 1 + max{kM (C) | T(C) v D ∈ SxM }.

The following proposition shows that in any minimal model the rank of each domain
element is finite.

Proposition 6. Let KB = KF ∪ KD and M = h∆, <, Ii a minimal model of KB, for
every x ∈ ∆, kM (x) is a finite ordinal (kM (x) < ω).

The previous proposition is essential for establishing a correspondence between the
minimal model semantics of a KB and its rational closure. From now on, we can assume
that the ranking function assigns to each domain element in ∆ a natural number, i.e. that
kM : ∆ −→ N.

5     A Minimal Model Semantics for Rational Closure in SHIQ
In previous sections we have extended to SHIQ the syntactic notion of rational closure
introduced in [24] for propositional logic. To provide a semantic characterization of
this notion, we define a special class of minimal models, exploiting the fact that, by
Proposition 6, in all minimal SHIQR T models the rank of each domain element is
always finite. First of all, we can observe that the minimal model semantics in Definition
4 as it is cannot capture the rational closure of a TBox.
    Consider the following KB = (TBox, ∅), where TBox contains: VIP v Person,
T(Person) v ≤ 1 HasMarried .Person, T(VIP ) v ≥ 2 HasMarried . Person. We
observe that T(VIP u Tall ) v ≥ 2 HasMarried .Person does not hold in all minimal
SHIQR T models of KB w.r.t. Definition 4. Indeed there can be a model M = h∆, <, Ii
in which ∆ = {x, y, z}, VIP I = {x, y}, Person I = {x, y, z}, (≤ 1 HasMarried .
Person)I = {x, z}, (≥ 2 HasMarried .Person)I = {y}, Tall I = {x}, and z < y < x.
M is a model of KB, and it is minimal. Also, x is a typical tallVIP in M (since there
is no other tall VIP preferred to him) and has no more than one spouse, therefore
T(VIP u Tall ) v ≥ 2 HasMarried .Person does not hold in M. On the contrary, it
can be verified that T(VIP u Tall ) v ≥ 2 HasMarried .Person ∈ TBox .
    Things change if we consider the minimal models semantics applied to models that
contain a domain element for each combination of concepts consistent with KB. We
call these models canonical models. Therefore, in order to semantically characterize
the rational closure of a SHIQR T KB, we restrict our attention to minimal canonical
models. First, we define S as the set of all the concepts (and subconcepts) occurring in
KB or in the query F together with their complements.
    In order to define canonical models, we consider all the sets of concepts {C1 , C2 , . . . ,
Cn } ⊆ S that are consistent with KB, i.e., s.t. KB 6|=SHIQR T C1 u C2 u · · · u Cn v ⊥.

Definition 8 (Canonical model with respect to S). Given KB=(TBox,ABox) and a
query F , a model M =h∆, <, Ii satisfying KB is canonical with respect to S if it
contains at least a domain element x ∈ ∆ s.t. x ∈ (C1 u C2 u · · · u Cn )I , for each set
of concepts {C1 , C2 , . . . , Cn } ⊆ S that is consistent with KB.

Next we define the notion of minimal canonical model.

Definition 9 (Minimal canonical models (w.r.t. S)). M is a minimal canonical model
of KB if it satisfies KB, it is minimal (with respect to Definition 4) and it is canonical (as
defined in Definition 8).

Proposition 7 (Existence of minimal canonical models). Let KB be a finite knowledge
base, if KB is satisfiable then it has a minimal canonical model.

To prove the correspondence between minimal canonical models and the rational clo-
sure of a TBox, we need to introduce some propositions. The next one concerns all
SHIQR T models. Given a SHIQR T model M =h∆, <, Ii, we define a sequence
M0 , M1 , M2 , . . . of models as follows: We let M0 = M and, for all i, we let
Mi = h∆, <i , Ii be the SHIQR T model obtained from M by assigning a rank 0
to all the domain elements x with kM (x) < i, i.e., kMi (x) = kM (x) − i if kM (x) > i,
and kMi (x) = 0 otherwise. We can prove the following:

Proposition 8. Let KB= hT Box, ABoxi and let M =h∆, <, Ii be any SHIQR T
model of TBox. For any concept C, if rank(C) ≥ i, then 1) kM (C) ≥ i, and 2) if
T(C) v D is entailed by Ei , then Mi satisfies T(C) v D.

Let us now focus our attention on minimal canonical models by proving the correspon-
dence between rank of a formula (as in Definition 6) and rank of a formula in a model
(as in Definition 3). The following proposition is proved by induction on the rank i:
Proposition 9. Given KB and S, for all C ∈ S, if rank (C) = i, then: 1. there is a
{C1 . . . Cn } ⊆ S maximal and consistent with KB such that C ∈ {C1 . . . Cn } and
rank (C1 u · · · u Cn ) = i; 2. for any M minimal canonical model of KB, kM (C) = i.
The following theorem follows from the propositions above:
Theorem 4. Let KB=(TBox,ABox) be a knowledge base and C v D a query. We have
that C v D ∈ TBox if and only if C v D holds in all minimal canonical models of KB
with respect to S.
6    Rational Closure over the ABox
The definition of rational closure in Section 3 takes only into account the TBox. We
address the issue of ABox reasoning first by the semantical side: as for any domain
element, we would like to attribute to each individual constant named in the ABox the
lowest possible rank. Therefore we further refine Definition 9 of minimal canonical
models with respect to TBox by taking into account the interpretation of individual
constants of the ABox.

Definition 10 (Minimal canonical model w.r.t. ABox). Given KB=(TBox,ABox), let
M =h∆, <, Ii and M0 = h∆0 , <0 , I 0 i be two canonical models of KB which are
minimal w.r.t. Definition 9. We say that M is preferred to M0 w.r.t. ABox (M <ABox
                                                                             0
M0 ) if, for all individual constants a occurring in ABox, kM (aI ) ≤ kM0 (aI ) and there
                                                                                      0
is at least one individual constant b occurring in ABox such that kM (bI ) < kM0 (bI ).

As a consequence of Proposition 7 we can prove that:
Theorem 5. For any KB= (T Box, ABox) there exists a minimal canonical model of
KB with respect to ABox.
In order to see the strength of the above semantics, consider our example about marriages
and VIPs.
Example 2. Suppose we have a KB=(TBox,ABox) where: TBox={T(Person) v ≤
1 HasMarried .Person, T(VIP ) v ≥ 2 HasMarried .Person, VIP v Person}, and
ABox = {VIP (demi ), Person(marco)}. Knowing that Marco is a person and Demi
is a VIP, we would like to be able to assume, in the absence of other information, that
Marco is a typical person, whereas Demi is a typical VIP, and therefore Marco has at
most one spouse, whereas Demi has at least two. Consider any minimal canonical model
M of KB. Being canonical, M will contain, among other elements, the following:
x ∈ (Person)I , x ∈ (≤ 1 HasMarried .Person)I , x ∈ (¬VIP )I , kM (x) = 0;
y ∈ (Person)I , y ∈ (≥ 2 HasMarried .Person)I , y ∈ (¬VIP )I , kM (y) = 1;
z ∈ (VIP )I , z ∈ (Person)I , z ∈ (≥ 2 HasMarried .Person)I , kM (z) = 1;
w ∈ (VIP )I , w ∈ (Person)I , w ∈ (≤ 1 HasMarried .Person)I , kM (w) = 2.
so that x is a typical person and z is a typical VIP. According to Definition 10, there is a
unique minimal canonical model w.r.t. ABox in which (marco)I = x and (demi )I = z.
We next provide an algorithmic construction for the rational closure of ABox. The idea
is that of considering all the possible minimal consistent assignments of ranks to the
individuals explicitly named in the ABox. We adopt a skeptical view by considering
only those conclusions which hold for all assignments. In order to calculate the rational
closure of ABox, written ABox , for all individual constants of the ABox we find out
which is the lowest possible rank they can have in minimal canonical models with respect
to Definition 9: the idea is that an individual constant ai can have a given rank kj (ai ) just
in case it is compatible with all the inclusions T(A) v D of the TBox whose antecedent
A’s rank is ≥ kj (ai ) (the inclusions whose antecedent A’s rank is < kj (ai ) do not matter
since, in the canonical model, there will be an instance of A with rank < kj (ai ) and
therefore ai is not a typical instance of A). The algorithm below computes all minimal
rank assignments kj s to all individual constants: µji contains all the concepts that ai
would need to satisfy in case it had the rank attributed by kj (kj (ai )). The algorithm
verifies whether µj is compatible with (TBox , ABox) and whether it is minimal. Notice
that, in this phase, all constants are considered simultaneously (indeed, the possible
ranks of different individual constants depend on each other).

Definition 11 (ABox : rational closure of ABox). Let a1 , . . . , am be the individuals
explicitly named in the ABox. Let k1 , k2 , . . . , kh be all the possible rank assignments
(ranging from 1 to n) to the individuals occurring in ABox.
– Given a rank assignment kj we define:
  – for each ai : µji = {(¬C t D)(ai ) s.t. C, D ∈ S, T(C) v D in TBox , and
    kj (ai ) ≤ rank(C)} ∪ {(¬C t D)(ai ) s.t. C v D in TBox };
  – let µj = µj1 ∪ · · · ∪ µjm for all µj1 . . . µjm just calculated for all a1 , . . . , am in ABox
– kj is minimal and consistent with (TBox , ABox), i.e.: (i) TBox ∪ ABox ∪µj is consistent
in SHIQR T; (ii) there is no ki consistent with (TBox , ABox) s.t. for all ai , ki (ai ) ≤
kj (ai ) and for some b, ki (b) < kj (b).
– The rational closure of ABox ( ABox ) is the set of all assertions derivable in SHIQR T
from TBox ∪ ABox ∪µj for all minimal consistent rank assignments kj , i.e:
                                                         TBox ∪ ABox ∪ µj |=SHIQR T C(a)}
                     T
           ABox =        kj minimal consistent {C(a) :

The example below is the syntactic counterpart of the semantic Example 2 above.
Example 3. Consider the KB in Example 2. Computing the ranking of concepts we get
that rank(Person) = 0, rank(VIP ) = 1, rank(Person u ≥ 2 HasMarried .Person)
= 1, rank(VIP u ≤ 1 HasMarried .Person) = 2. The set µ1 contains, among the
others, (¬VIP t ≥ 2 HasMarried .Person)(demi ) , (¬Person t ≤ 1 HasMarried .
Person)(marco). It is tedious but easy to check that KB ∪µ1 is consistent and that k1 is
the only minimal consistent assignment, thus both (≥ 2 HasMarried .Person)(demi )
and (≤ 1 HasMarried .Person) (marco) belong to ABox .
Theorem 6 (Soundness and completeness of ABox ). Given KB=(TBox, ABox), for
each individual constant a in ABox, C(a) ∈ ABox if and only if C(a) holds in all
minimal canonical models with respect to ABox of KB.
Theorem 7 (Complexity of rational closure over the ABox). Given a knowledge base
KB=(TBox,ABox) in SHIQR T, an individual constant a and a concept C, the problem
of deciding whether C(a) ∈ ABox is E XP T IME-complete.
The proof is similar to the one for rational closure over ABox in ALC (Theorem 5 [18]).

7    Related Works
There are a number of works which are closely related to our proposal.
    In [14, 17] nonmonotonic extensions of DLs based on the T operator have been
proposed. In these extensions, focused on the basic DL ALC, the semantics of T is
based on preferential logic P[22]. Moreover and more importantly, the notion of minimal
model adopted here is completely independent from the language and is determined only
by the relational structure of models.
    [6] develop a notion of rational closure for DLs based on the construction of rational
closure proposed by Freund [12] at a propositional level. [8] introduces an approach
based on the combination of rational closure and Defeasible Inheritance Networks (INs).
In [7], a semantic characterization of a variant of the notion of rational closure in [6] is
presented, based on a generalization to ALC of our semantics in [16].
    An approach related to ours can be found in [3]. The basic idea of their semantics is
similar to ours, but it is restricted to the propositional case. Furthermore, their construc-
tion relies on a specific representation of models and it provides a recipe to build a model
of the rational closure, rather than a characterization of its properties. Our semantics,
defined in terms of standard Kripke models, can be more easily generalized to richer
languages, as we have done here for SHIQ.
    In [5] the semantics of the logic of defeasible subsumptions is strengthened by a
preferential semantics. Furthermore, the authors describe an E XP T IME algorithm in
order to compute the rational closure of a given TBox in ALC. In [25] a plug-in for
the Protégé ontology editor implementing the mentioned algorithm for computing the
rational closure for a TBox for OWL ontologies is described.
    Recent works discuss the combination of open and closed world reasoning in DLs.
In particular, formalisms have been defined for combining DLs with logic programming
rules (see, for instance, [11] and [26]). A grounded circumscription approach for DLs
with local closed world capabilities has been defined in [23].
8   Conclusions
In this work we have proposed an extension of the rational closure defined by Lehmann
and Magidor to the Description Logic SHIQ, taking into account both TBox and ABox
reasoning. One of the contributions is that of extending the semantic characterization
of rational closure proposed in [16] for propositional logic, to SHIQ, which does not
enjoy the finite model property. We have shown that in all minimal models of a finite KB
in SHIQ the rank of domain elements is always finite, although the domain might be
infinite. We have proved an E XP T IME upper bound for both TBox and ABox reasoning
with the rational closure shown that the rational closure of a TBox can be computed
using entailment in SHIQ.
     The rational closure construction in itself can be applied to any description logic. We
would like to extend its semantic characterization to stronger logics, such as SHOIQ,
for which the notion of canonical model as defined in this paper is too strong due to the
interaction of nominals with number restrictions.
     It is well known that rational closure has some weaknesses that accompany its
well-known qualities. Among the weaknesses is the fact that one cannot separately
reason property by property, so that, if a subclass of C is exceptional for a given aspect,
it is exceptional “tout court” and does not inherit any of the typical properties of C.
Among the strengths there is its computational lightness, which is crucial in Description
Logics. Both the qualities and the weaknesses seems to be inherited by its extension to
Description Logics. To address the mentioned weakness of rational closure, we may think
of attacking the problem from a semantic point of view by considering a finer semantics
where models are equipped with several preference relations; in such a semantics it
might be possible to relativize the notion of typicality, whence to reason about typical
properties independently from each other.
Acknowledgement. We thank the anonymous referees for their helpful comments. This
work has been partially supported by the Compagnia di San Paolo and by the project
“CONDESC: deduzione automatica per logiche CONDizionali e DESCrittive”.
References

 1. Baader, F., Hollunder, B.: Priorities on defaults with prerequisites, and their application in
    treating specificity in terminological default logic. Journal of Automated Reasoning (JAR)
    15(1), 41–68 (1995)
 2. Bonatti, P.A., Lutz, C., Wolter, F.: The Complexity of Circumscription in DLs. Journal of
    Artificial Intelligence Research (JAIR) 35, 717–773 (2009)
 3. Booth, R., Paris, J.: A note on the rational closure of knowledge bases with both positive and
    negative knowledge. Journal of Logic, Language and Information 7, 165–190 (1998)
 4. Britz, K., Heidema, J., Meyer, T.: Semantic preferential subsumption. In: Brewka, G., Lang,
    J. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the 11th
    International Conference (KR 2008). pp. 476–484. AAAI Press, Sidney, Australia (September
    2008)
 5. Britz, K., Meyer, T., Varzinczak, I.J.: Semantic foundation for preferential description logics.
    In: AI 2011: Advances in Artificial Intelligence - 24th Australasian Joint Conference. Lecture
    Notes in Computer Science, vol. 7106, pp. 491–500. Springer (2011)
 6. Casini, G., Straccia, U.: Rational Closure for Defeasible Description Logics. In: Janhunen,
    T., Niemelä, I. (eds.) Proceedings of the 12th European Conference on Logics in Artificial
    Intelligence (JELIA 2010). Lecture Notes in Artificial Intelligence, vol. 6341, pp. 77–90.
    Springer, Helsinki, Finland (September 2010)
 7. Casini, G., Meyer, T., Varzinczak, I.J., Moodley, K.: Nonmonotonic Reasoning in Descrip-
    tion Logics: Rational Closure for the ABox. In: DL 2013, 26th International Workshop on
    Description Logics. CEUR Workshop Proceedings, vol. 1014, pp. 600–615. CEUR-WS.org
    (2013)
 8. Casini, G., Straccia, U.: Defeasible Inheritance-Based Description Logics. In: Walsh, T. (ed.)
    Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI
    2011). pp. 813–818. Morgan Kaufmann, Barcelona, Spain (July 2011)
 9. Casini, G., Straccia, U.: Defeasible inheritance-based description logics. J. Artif. Intell. Res.
    (JAIR) 48, 415–473 (2013)
10. Donini, F.M., Nardi, D., Rosati, R.: Description logics of minimal knowledge and negation as
    failure. ACM Transactions on Computational Logic (ToCL) 3(2), 177–225 (2002)
11. Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining Answer Set Programming
    with Description Logics for the Semantic Web. In: Dubois, D., Welty, C., Williams, M. (eds.)
    Principles of Knowledge Representation and Reasoning: Proceedings of the 9th International
    Conference (KR 2004). pp. 141–151. AAAI Press, Whistler, Canada (June 2004)
12. Freund, M.: Preferential reasoning in the perspective of poole default logic. Artif. Intell.
    98(1-2), 209–235 (1998)
13. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Preferential Description Logics. In:
    Dershowitz, N., Voronkov, A. (eds.) Proceedings of LPAR 2007 (14th Conference on Logic
    for Programming, Artificial Intelligence, and Reasoning). LNAI, vol. 4790, pp. 257–272.
    Springer-Verlag, Yerevan, Armenia (October 2007)
14. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: ALC+T: a preferential extension of
    Description Logics. Fundamenta Informaticae 96, 1–32 (2009)
15. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Preferential vs Rational Description
    Logics: which one for Reasoning About Typicality? In: Coelho, H., Studer, R., Wooldridge,
    M. (eds.) Proceedings of ECAI 2010 (19th European Conference on Artificial Intelligence).
    Frontiers in Artificial Intelligence and Applications, vol. 215, pp. 1069–1070. IOS Press,
    Lisbon, Portugal (August 16-20 2010)
16. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A minimal model semantics for non-
    monotonic reasoning. In: Luis Fariñas del Cerro, Andreas Herzig, J.M. (ed.) Logics in Artifi-
    cial Intelligence - 13th European Conference, JELIA 2012. LNAI, vol. 7519, pp. 228–241.
    Springer-Verlag, Toulouse, France (Sptember 2012)
17. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A NonMonotonic Description Logic for
    Reasoning About Typicality. Artificial Intelligence 195, 165–202 (2013)
18. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Minimal Model Semantics and Rational
    Closure in Description Logics . In: Eiter, T., Glim, B., Kazakov, Y., Krtzsch, M. (eds.) Informal
    Proceedings of the 26th International Workshop on Description Logics (DL 2013). CEUR
    Workshop Proceedings, vol. 1014, pp. 168 – 180. Ulm, Germany (7 2013)
19. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Rational closure in SHIQ. In:
    arXiv:1406.2023 (2014), http://arxiv.org/abs/1406.2023
20. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for very expressive description logics.
    Logic Journal of the IGPL 8(3), 239–263 (2000)
21. Ke, P., Sattler, U.: Next Steps for Description Logics of Minimal Knowledge and Negation as
    Failure. In: Baader, F., Lutz, C., Motik, B. (eds.) Proceedings of Description Logics. CEUR
    Workshop Proceedings, vol. 353. CEUR-WS.org, Dresden, Germany (May 2008)
22. Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and
    cumulative logics. Artificial Intelligence 44(1-2), 167–207 (1990)
23. Krisnadhi, A.A., Sengupta, K., Hitzler, P.: Local closed world semantics: Keep it simple,
    stupid! In: Proceedings of Description Logics. CEUR Workshop Proceedings, vol. 745.
    Barcelona, Spain (July 2011)
24. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artificial Intelli-
    gence 55(1), 1–60 (1992)
25. Moodley, K., Meyer, T., Varzinczak, I.J.: A protege plug-in for defeasible reasoning. In:
    Description Logics. CEUR Workshop Proceedings, vol. 846. CEUR-WS.org (2012)
26. Motik, B., Rosati, R.: Reconciling Description Logics and rules. Journal of the ACM 57(5)
    (2010)
27. Straccia, U.: Default inheritance reasoning in hybrid kl-one-style logics. In: Bajcsy, R. (ed.)
    Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI 1993).
    pp. 676–681. Morgan Kaufmann, Chambéry, France (August 1993)

</pre>