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 EXPTIME using entailment in

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 S HIQ in terms of a preferential semantics, by generalizing to S HIQ the results for rational closure in ALC presented in [ 18 ]. This generalization is not trivial, since S HIQ lacks a crucial property of ALC, the finite model property [ 20 ]. Our construction exploits an extension of S HIQ 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, S HIQRT, 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 S HIQ, without requiring to reason in S HIQRT, and that the problem of deciding whether an inclusion belongs to the rational closure of a TBox is in EXPTIME.

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 EXPTIME as well.

For an extended version of this paper with the proofs of the results see [ 19 ]. 2

A nonmonotonic extension of S HI Q

Following the approach in [ 14, 17 ], we introduce an extension of S HIQ [ 20 ] with a typicality operator T in order to express typical inclusions, obtaining the logic S HIQRT. 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 2 C, S 2 R, and n 2 N we define: CR := A j > j ? j :CR j CR u CR j CR t CR j 8S:CR j 9S:CR j ( CL := CR j T(CR) S := R j 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 2 O.

The semantics of S HIQRT is formulated in terms of rational models: ordinary models of S HIQ 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. nS:CR) j ( nS:CR) 4 As for the logic ALCRT 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 SHIQRT). A SHIQRT model M is any structure h ; <

; Ii where: is the domain; < is an irreflexive, transitive, well-founded, and modular (for all x; y; z 2 , if x < y then x < z or z < y) relation over ; I is the extension function that maps each concept C to CI , and each role R to RI I I . For concepts of SHIQ, CI is defined as usual. For the T operator, we have (T(C))I = M in<(CI ), where M in<(S) = fu : u 2 S and @z 2 S s.t. z < ug.

As for rational models in [ 24 ] (see Lemma 14), SHIQRT 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 SHIQRT model M= h ; <; Ii, we say that: - a model M satisfies an inclusion C v D if CI DI ; similarly for role inclusions; - M satisfies an assertion C(a) if aI 2 CI ; and M satisfies an assertion R(a; b) if (aI ; bI ) 2 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 SHIQRT, 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 j=SHIQRT 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) = minfkM(x) j x 2 CRI g. If CRI = ;, then CR has no rank and we write kM(CR) = 1. 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 SHIQRT 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 SHIQRT, one cannot deal with irrelevance. For instance, KB= fVIP v Person, T(Person) v 1 HasMarried :Person, T(VIP ) v 2 HasMarried :Persong does not entail KB j=SHIQRT 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 SHIQRT, 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 SHIQRT 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 SHIQRT models, giving preference to the model in which domain elements have a lower rank; 2. restrict entailment to minimal SHIQRT models (w.r.t. the above preference relation) of KB.

Definition 4 (Minimal models). Given M =h ; <; Ii and M0 = h 0; <0; I0i we say that M is preferred to M0 (M <FIMS M0) if (i) = 0, (ii) CI = CI0 for all concepts C, and (iii) for all x 2 , kM(x) kM0 (x) whereas there exists y 2 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 SHIQRT has the same complexity as reasoning in SHIQ, i.e. it is in EXPTIME. Its proof is given by providing an encoding of satisfiability in SHIQRT into satisfiability SHIQ, which is known to be an EXPTIMEcomplete problem. The proof is omitted due to space limitations Theorem 1. Satisfiability in SHIQRT is an EXPTIME-complete problem. 3

Rational Closure for SHI Q

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 j 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 j=SHIQRT 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) [ fC v D 2 TBox s.t. T does not occurr in Cg. 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) = 1, 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 j=SHIQ be the entailment in SHIQ. In the following definition, by KB j=SHIQ F we mean KF j=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 = fT(C) v D j either rank (C) < rank (C u :D) or rank (C) = 1g [ fC v D j KB j=SHIQ C v Dg, 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 SHIQRT. For instance, it allows to deal with irrelevance, as the following example shows.

Example 1. Let TBox = fT(Actor ) v Charming g. It can be verified that T(Actor u Comic) v Charming 2 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 [ fT(Actor u Comic) v :Charming g, we have that T(Actor u Comic) v Charming 62 TBox 0. Furthermore, as for the propositional case, rational closure is closed under rational monotonicity [ 22 ]: from T(Actor ) v Charming 2 TBox and T(Actor ) v Bold 62 TBox it follows that T(Actor u :Bold ) v Charming 2 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 2 TBox is in EXPTIME. Let us first prove the following proposition: Proposition 3. Let KB=(TBox,;) be a knowledge base with empty ABox. KB j=SHIQRT CL v CR iff KB0 j=SHIQ CL0 v CR0, where KB0, CL0 and CR0 are polynomial encodings in SHIQ of KB, CL and CR, respectively.

SHIQ .

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 j 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 SHIQRT. 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 SHIQRT 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 SHIQRT: KB j=SHIQP T CL v CR iff KB0 j=SHIQ CL0 v CR0, for some polynomial encoding KB0, CL0, CR0 in

The idea of the encoding exploits the definition of the typicality operator T introduced in [ 14 ] (for ALC), in terms of a Go¨del -Lo¨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 2 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 2 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 8R:(:A u 2:A) and :2:A v 9R:(A u 2:A).

For the inclusion CL v CR, we let CR0 = CR. For a strict inclusion (CL 6= T (A)), we let CL0 = CL, while for a defeasible inclusion (CL = T (A)), we let CL0 = A u 2:A.

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 j=SHIQP T CL v CR iff KB0 j=SHIQ CL0 v CR0. 2

Theorem 2 (Complexity of rational closure over TBox). Given a TBox, the problem

of deciding whether T(C) v D 2 TBox is in EXPTIME.

Proof. Checking if T(C) v D 2 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(jKBj), where jKBj 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 j=SHIQRT T(>) v :A. Regarding Ei 1 as a knowledge base with empty ABox, by Proposition 3 it is enough to check that Ei0 1 j=SHIQ > t 2:> v :A, which requires an exponential time in the size of Ei0 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 2 TBox is in EXPTIME. 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 2 , as SxM = fT(C) v D 2 KD j x 2 (C u :D)I gg. Proposition 4. Let M = h ; <; Ii be a model of KB and x 2 , 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 2 SxM.

Let us define KF = fC v D 2 T Box : T does not occur in Cg [ ABox and KD = fT(C) v D 2 T Boxg, 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 2 it holds that: - if kM(x) = 0 then SxM = ;; - if SxM 6= ; then kM(x) > k (C) for every C s.t., for some D, T(C) v D 2 SxM. Then M j= KB.

M From Propositions 4 and 5, we obtain the following characterization of minimal models. Theorem 3. Let KB = KF [ KD, and let M following are equivalent: = h ; <; Ii be a model of KF . The – M is a minimal model of KB – For every x 2 it holds: (a) SxM = ; iff kM(x) = 0 (b) if SxM 6= ; then kM(x) = 1 + maxfkM(C) j T(C) v D 2 SxMg.

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 2 , 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 SHI Q

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 SHIQRT 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 SHIQRT models of KB w.r.t. Definition 4. Indeed there can be a model M = h ; <; Ii in which = fx; y; zg, VIP I = fx; yg, PersonI = fx; y; zg, ( 1 HasMarried : Person)I = fx; zg, ( 2 HasMarried :Person)I = fyg, Tall I = fxg, 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 2 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 SHIQRT 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 fC1; C2; : : : ; Cng S that are consistent with KB, i.e., s.t. KB 6j=SHIQRT 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 2 s.t. x 2 (C1 u C2 u u Cn)I , for each set of concepts fC1; C2; : : : ; Cng 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 closure of a TBox, we need to introduce some propositions. The next one concerns all SHIQRT models. Given a SHIQRT 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 SHIQRT 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 SHIQRT 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 correspondence 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 2 S, if rank (C) = i, then: 1. there is a fC1 : : : Cng S maximal and consistent with KB such that C 2 fC1 : : : Cng 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 2 TBox if and only if C v D holds in all minimal canonical models of KB with respect to S.

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; I0i 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 M0) if, for all individual constants a occurring in ABox, kM(aI ) kM0 (aI0 ) and there is at least one individual constant b occurring in ABox such that kM(bI ) < kM0 (bI0 ). 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=fT(Person) v 1 HasMarried :Person; T(VIP ) v 2 HasMarried :Person; VIP v Persong; and ABox = fVIP (demi ); Person(marco)g. 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 2 (Person)I , x 2 ( 1 HasMarried :Person)I , x 2 (:VIP )I , kM(x) = 0; y 2 (Person)I , y 2 ( 2 HasMarried :Person)I , y 2 (:VIP )I , kM(y) = 1; z 2 (VIP )I , z 2 (Person)I , z 2 ( 2 HasMarried :Person)I , kM(z) = 1; w 2 (VIP )I , w 2 (Person)I , w 2 ( 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: ij 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: ij = f(:C t D)(ai) s.t. C; D 2 S, T(C) v D in TBox , and kj (ai) rank(C)g [ f(:C t D)(ai) s.t. C v D in TBox g; – 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 SHIQRT; (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 SHIQRT from TBox [ ABox [ j for all minimal consistent rank assignments kj , i.e:

ABox = Tkjminimal consistentfC(a) : TBox [ ABox [ j j=SHIQRT C(a)g 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) 2 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 SHIQRT, an individual constant a and a concept C, the problem of deciding whether C(a) 2 ABox is EXPTIME-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 construction 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 EXPTIME algorithm in order to compute the rational closure of a given TBox in ALC. In [ 25 ] a plug-in for the Prote´ge´ 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 EXPTIME 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. , Niemela¨, 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 Description 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 nonmonotonic reasoning . In: Luis Farin˜as del Cerro , Andreas Herzig , J.M. (ed.) Logics in Artificial 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 Intelligence 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, Chambe´ry, France ( August 1993 )