Minimal Model Semantics and Rational Closure in Description Logics

Abstract

We define the notion of rational closure in the context of Description Logics. We start from an extension of ALC with a typicality operator T allowing to express concepts of the form T(C), whose meaning is to select the “most normal” instances of a concept C. The semantics we consider is based on rational models and exploits a minimal models mechanism based on the minimization of the rank of domain elements. We show that this semantics captures exactly a notion of rational closure which is a natural extension to Description Logics of Lehmann and Magidor's one. We also extend the notion of rational closure to the ABox, by providing an EXPTIME algorithm for computing it that is sound and complete with respect to the minimal model semantics.

1 Introduction

Recently, in the domain of Description Logics (DLs) a large amount of work has been done in order to extend the basic formalism with nonmonotonic reasoning features. The aim of these extensions is to reason about prototypical properties of individuals or classes of individuals. In these extensions one can represent, for instance, knowledge expressing the fact that the heart is usually positioned in the left-hand side of the chest, with the exception of people with situs inversus, that have the heart positioned in the right-hand side. Also, one can infer that an individual enjoys all the typical properties of the classes it belongs to. So, for instance, in the absence of information that someone has situs inversus, one would assume that it has the heart positioned in the left-hand side. A further objective of these extensions is to allow to reason about defeasibile properties and inheritance with exceptions. Consider the standard penguin example, in which typical birds fly, however penguins are birds that do not fly: nonmonotonic extensions of DLs allow to attribute to an individual the typical properties of the most specific class it belongs to. In this example, when knowing that Tweety is a bird, one would conclude that it flies, whereas when discovering that it is also a penguin, the previous inference is retracted, and the fact that Tweety does not fly is concluded.

In the literature of DLs, several proposals have appeared [ 22, 2, 1, 7, 16, 5, 14, 3, 18, 8, 21 ]. However, finding a solution to the problem of extending DLs for reasoning about prototypical properties seems far from being solved. In this paper, we take into consideration the well known notion of rational closure, as introduced by Lehmann and Magidor [ 19 ], and we extend it to DLs in a natural way. We first provide a definition of rational closure for DLs based on the concept of exceptionality, as in Lehmann and Magidor’s work [ 19 ]. Second, we give an equivalent model theoretic characterization of rational closure which extends the one introduced in [ 15 ] within a propositional context.

Our semantical characterization is based on a minimal model mechanism (in the spirit of circumscription). Rational closure being one of the most well established nonmonotonic mechanisms, we believe that the extension of rational closure to DLs and its semantical characterization are important per se. Furthermore, this can be a first step towards the exploration of more refined versions of rational closure, that can overcome some of the known weaknesses of this mechanism. A different approach to the definition of rational closure for DLs has been proposed by Casini and Straccia in [ 5 ], who define a rational closure for ALC based on a construction previously proposed by [ 9 ] for the propositional calculus. In the propositional case, this construction is proved to be equivalent with the notion of rational closure in [ 19 ].

Our starting point is the Description Logic ALC extended with a typicality operator T. The operator T, first introduced in [ 10 ], allows to directly express typical properties such as T(HeartPosition) v Left , T(Bird ) v Fly , and T(Penguin) v :Fly , whose intuitive meaning is that normally, the heart is positioned in the left-hand side of the chest, that typical birds fly, whereas penguins do not. In this paper, the T operator is intended to enjoy the well-established properties of rational logic, described by Kraus, Lehmann and Magidor (henceforth KLM) in their seminal work [ 17, 19 ]. Even if T is a nonmonotonic operator (so that for instance T(HeartPosition) v Left does not entail that T(HeartPosition u SitusInversus ) v Left ) the logic itself is monotonic. Indeed, in this logic it is not possible to infer from T(Bird ) v Fly , in the absence of information to the contrary, that also T(Bird uBlack ) v Fly . Nor it can be inferred from Bird (tweety), in the absence of information to the contrary, that T(Bird )(tweety).

In this paper, nonmonotonicity is achieved first by adapting to ALC with T the propositional construction of rational closure. This nonmonotonic extension allows to infer defeasible subsumptions from the TBox (TBox reasoning). Intuitively the rational closure construction amounts to assigning a rank (a level of exceptionality) to every concept; this rank is used to evaluate defeasible inclusions of the form T(C) v D: the inclusion is supported by the rational closure whenever the rank of C is strictly smaller than the one of C u :D. Second, we tackle the problem of extending the rational closure to ABox reasoning: we would like to ascribe defeasible properties to individuals. The idea is to maximize the typicality of an individual: the more it is “typical”, the more it inherits the defeasible properties of the classes it belongs too (being a typical member of them). We obtain this by minimizing its rank (that is, its level of exceptionality), however, 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. Last but not least, we give a model theoretic characterization of rational closure by restricting entailment to minimal models: they are those ones which minimize the rank of domain elements by keeping fixed the extensions of concepts and roles. We can obtain an exact correspondence between the two characterizations of rational closure if we further restrict the minimal model semantics to canonical models: these are models that satisfy each intersection (C1 u : : : u Cn) of concepts drawn from the knowledge base that is satisfiable with respect to the TBox.

The rational closure construction that we propose has not just a theoretical interest and a simple minimal model semantics, we show that it is also feasible since its complexity is “only” EXPTIME in the size of the knowledge base (and the query), thus not worse than the underlying monotonic logic. In this respect it is less complex than other approaches to nonmonotonic reasoning in DLs [ 14, 2 ] and comparable in complexity with the approaches in [ 5, 4, 21 ], and thus a good candidate to define effective nonmonotonic extensions of DLs.

2 The operator T and the General Semantics

Let us briefly recall the DLs ALC + T and ALCRT introduced in [ 10, 11 ], respectively. The intuitive idea is to extend the standard ALC allowing 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 concept C (C v D), and those that only hold for the typical such instances (T(C) v D). Definition 1. We consider an alphabet of concept names C, of role names R, and of individual constants O. Given A 2 C and R 2 R, we define CR := A j > j ? j :CR j CR u CR j CR t CR j 8R:CR j 9R:CR, and CL := CR j T(CR). A KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusions CL v CR. ABox contains assertions of the form CL(a) and R(a; b), where a; b 2 O.

The semantics of ALC + T and ALCRT is defined respectively in terms of preferential and rational models: ordinary models of ALC are equipped by 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 members of a concept C, that is members of T(C), are the members x of C that are minimal with respect to this preference relation (s.t. there is no other member of C more typical than x). Preferential models, in which the preference relation < is irreflexive and transitive, characterize the logic ALC + T, whereas the more restricted class of rational models, so that < is further assumed to be modular, characterizes ALCRT4.

Definition 2 (Semantics of ALC + T). A model M of ALC + T is any structure h ; <; I i where: is the domain; < is an irreflexive and transitive relation over that satisfies the following Smoothness Condition: for all S , for all x 2 S, either x 2 M in<(S) or 9y 2 M in<(S) such that y < x, where M in<(S) = fu : u 2 S and @z 2 S s.t. z < ug; I is the extension function that maps each concept C to CI , and each role R to RI I I . For concepts of ALC, CI is defined in the usual way. For the T operator, we have (T(C))I = M in<(CI ).

Definition 3 (Semantics of ALCRT). A model M of ALCRT is an ALC + T model as in Definition 2 in which < is further assumed to be modular: for all x; y; z 2 , if x < y then either x < z or z < y. 4 This semantics with one single preference relation < is the one that, as we will show, corresponds to rational closure. One may think of considering a sharper semantics with several preference relations. We will do this in future works. For the moment, we just notice that (i) the definition of such a semantics is not straightforward (what differentiates one preference relation from another? What are the dependencies between the different preference relations?) (ii) it is not obvious that the resulting semantics, being stronger than the one just proposed, would correspond to rational closure.

Definition 4 (Model satisfying a Knowledge Base). Given a model M, I is extended

to assign a distinct element5 aI of to each individual constant a of O. M satisfies a knowledge base K=(TBox,ABox), if it satisfies both its TBox and its ABox, where: M satisfies TBox if for all inclusions C v D in TBox, it holds CI DI ; - M satisfies ABox if: (i) for all C(a) in ABox, aI 2 CI , (ii) for all aRb in ABox, (aI ; bI ) 2 RI . In [ 10 ] it is shown that reasoning in ALC + T is EXPTIME complete, that is to say adding the T operator does not affect the complexity of the underlying DL ALC. We are able to extend the same result also for ALCRT (we omit the proof to save space): Theorem 1 (Complexity of ALCRT). Reasoning in ALCRT is EXPTIME complete. From now on, we restrict our attention to ALCRT and to finite models. Given a knowledge base K and an inclusion CL v CR, we say that it is derivable from K (we write K j=ALCRT CL v CR) if CLI CRI holds in all models M = h ; <; I i satisfying K. Definition 5. The rank kM of a domain element x in M is the length of the longest chain x0 < < x from x to a minimal x0 (s.t. for no x0 x0 < x0).

Finite ALCRT models can be equivalently defined by postulating the existence of a function k : ! N, and then letting x < y iff k(x) < k(y).

Definition 6. Given a model M = h ; <; I i, the rank kM(CR) of a concept CR in M is i = minfkM(x) : x 2 CRIg. If CRI = ;, then CR has no rank and we write kM(CR) = 1.

It is immediate to verify that: Proposition 1. For any M = h ; <; I i, we have that M satisfies T(C) v kM(C u D) < kM(C u :D).

D iff

In order to define a nonmonotonic entailment and to capture rational closure that we will shortly define, we introduce the second ingredient of our minimal model semantics. As in [ 14 ], we strengthen the semantics by restricting entailment to a class of minimal (or preferred) models, more precisely to models that minimize the rank of individuals. Informally, given two models of K, one in which a given x has rank 2 (because for instance z < y < x) , and another in which it has rank 1 (because only y < x), we would prefer the latter, as in this model x is “more normal” than in the former. We call

R the new logic ALCminT.

Let us define the notion of query. Intuitively, a query is either an inclusion relation or an assertion of the ABox; we want to check whether it is entailed from a given KB. Definition 7 (Query). A query F is either an assertion CL(a) or an inclusion relation CL v CR. Given a model M = h ; <; I i, a query F = CL(a) holds in M if aI 2 CLI, whereas a query F = CL v CR holds in M if CLI CRI. 5 We assume the well-established UNA (unique name assumption). UNA is necessary to independently reason about the typicality of distinct individuals. Without UNA, one would be forced to conclude more often than suitable that two non typical individuals coincide. The situation is analogous to other nonmonotonic mechanisms such as circumscription. In analogy with circumscription, there are mainly two ways of comparing models with the same domain: 1) by keeping the valuation function fixed (only comparing M and M0 if I and I0 in the two models respectively coincide); 2) by also comparing M and M0 in case I 6= I0. In this work we consider the semantics resulting from the first alternative, whereas we leave the study of the other one for future work. The semantics we introduce is a fixed interpretations minimal semantics, for short FIMS .

M0 <FIMS M.

Definition 8 (FIMS ). Given M = h ; <; Ii and M0 = h 0; <0; I0i we say that M is preferred to M0 (M <FIMS M0) if = 0, CI = CI0 for all concepts C, and for all x 2 , kM(x) kM0 (x) whereas there exists y 2 such that kM(y) < kM0 (y). Given a knowledge base K, we say that M is a minimal model of K with respect to <FIMS if it is a model satisfying K and there is no M0 model satisfying K such that Next, we extend the notion of minimal model by also taking into account the individuals named in the ABox.

Definition 9 (Model minimally satisfying K). Given K=(TBox,ABox), let M = h ; <; Ii and M0 = h 0; <0; I0i be two models of K which are minimal w.r.t. Definition 8. We say that M is preferred to M0 with respect to ABox (M <ABox M0) if for all individual constants a occurring in ABox, kM(aI ) kM(aI0 ) and there is at least one individual constant b occurring in ABox such that kM(bI ) < kM(bI0 ). M minimally satisfies K in case there is no M0 satisfying K such that M0 <ABox M. We say that K minimally entails a query F (K j=min F ) if F holds in all models that minimally satisfy K.

Observe that, in this minimal model semantics, the extension of concepts is fixed in comparable models. This has some similarities to the semantics of circumscription where all predicates are fixed. However in contrast with circumscription, the interpretation of named individual is not fixed. Moreover we assume that the interpretation of roles is variable and, as we will see in the next section, we restrict our semantics to minimal canonical models. 3

A Semantical Reconstruction of Rational Closure in DLs

In this section we provide a definition of the well known rational closure, described in [ 19 ], in the context of Description Logics. We then provide a semantic characterization of it within the semantics described in the previous section.

Definition 10. Let K be a DL knowledge base and C a concept. C is said to be exceptional for K iff K j=ALCRT T(>) v :C.

Let us now extend Lehmann and Magidor’s definition of rational closure to a DL knowledge base. First, we remember that the T operator satisfies a set of postulates that are essentially a reformulation of KLM axioms of rational logic R: in this respect, in [ 10 ] it is shown that the T-assertion T(C) v D is equivalent to the conditional assertion C j D of KLM logic R. We say that a T-inclusion T(C) v D is exceptional for K if C is exceptional for K. The set of T-inclusions which are exceptional for K will be denoted as E (K). It is possible to define a sequence of non-increasing subsets of K E0 E1; : : : by letting E0 = K and, for i > 0, Ei = E (Ei 1) [ fC v D 2 K s.t. T does not occurr in Cg. Observe that, being K finite, there is an n 0 such that for all m > n; Em = En or Em = ;.

Definition 11. A concept C has rank i (denoted by rank (C) = i) for K 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 knowledge base K.

Definition 12. [Rational closure of TBox] Let K=(TBox,ABox) be a DL knowledge base. We define the rational closure TBox of TBox of K where

TBox = fT(C) v D j either rank (C) < rank (C u :D)

or rank (C) = 1g [ fC v D j K j=ALC C v Dg

In the following we show that the minimal model semantics defined in the previous section can be used to provide a semantical characterization of rational closure.

First of all, we can observe that the minimal model semantics as it is cannot capture the rational closure of a TBox. For instance, consider the knowledge base K =(TBox,;) of the penguin example, where TBox contains the following inclusions: Penguin v Bird , T(Bird ) v Fly , T(Penguin) v :Fly . We observe that K 6j=min T(Penguin u Black ) v :Fly . Indeed in the minimal model semantics there can be a model M = h ; <; Ii in which = fx; y; zg, PenguinI = fx; yg, Bird I = fx; y; zg, Fly I = fx; zg, Black I = fxg, and z < y < x. M is a model of K, and it is minimal (indeed it is not possible to lower the rank of x nor of y nor of z unless we falsify K). Furthermore, x is a typical black penguin in M (since there is no other black penguin preferred to it) that flies. On the contrary, it can be verified that T(Penguin u Black ) v :Fly 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 K. We call these models canonical models. In the example, if we restrict our attention to models M = h ; <; Ii that also contain a w 2 which is a black penguin that does not fly, that is to say w 2 PenguinI , w 2 Bird I , w 2 Black I , and w 62 Fly I and can therefore be assumed to be a typical penguin, we are able to conclude that typically black penguins do not fly, as in rational closure. Indeed, in all minimal models of K that also contain w with w 2 PenguinI , w 2 Bird I , w 2 Black I , and w 62 Fly I , it holds that T(Penguin u Black ) v :Fly .

From now on, we restrict our attention to canonical minimal models. First, we define a set of concepts S closed under negation and subconcepts. We assume that all concepts in K and in the query F belong to S. In order to define canonical minimal models, we consider the set of all consistent sets of concepts fC1; C2; : : : ; Cng S that are consistent with K, i.e., s.t. K 6j=ALC C1 u C2 u u Cn v ?.

Definition 13 (Canonical minimal model w.r.t. S). Given K and a query F , a model

M = h ; <; Ii minimally satisfying K is canonical w.r.t. S if it contains at least a domain element x 2 s.t. x 2 CI for each combination C in S consistent with K. Proposition 2. Let M be a minimal canonical model of K. For all concepts C 2 S, it holds that rank(C) = kM(C).

The proof can be done by induction on the rank of concept C, and it is similar to the proof of Proposition 7 of [ 13 ].

Theorem 2. Given K, we have that C v D 2 TBox if and only if C v D holds in all canonical minimal models with respect to S.

This theorem directly follows from Proposition 2. We omit the proofs to save space. 4

Rational Closure Over the ABox

In this section we extend the notion of rational closure defined in the previous section in order to take into account the individual constants in the ABox. We therefore address the question: what does the rational closure of a knowledge base K allow us to infer about a specific individual constant a occurring in the ABox of K? We propose the algorithm below to answer this question and we show that it corresponds to what is entailed by the minimal model semantics presented in the previous section. The idea of the algorithm is that of considering all the possible minimal consistent assignments of ranks to the individuals explicitly named in the ABox. Each assignment adds some properties to named individuals which can be used to infer new conclusions. We adopt a skeptical view of considering only those conclusions which hold for all assignments. The equivalence with the semantics shows that the minimal entailment captures a skeptical approach when reasoning about the ABox.

Definition 14 (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 kj is minimal and consistent with (TBox , ABox) if: - ABox [ j is consistent in ALC; - there is no ki consistent wih (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 ALC from ABox [ j for all minimal consistent rank assignments kj , i.e:

ABox = Tkjminimal consistentfC(a) : ABox [ j j=ALC C(a)g Theorem 3 (Soundness of ABox ). Given K=(TBox, ABox), for each individual constant a in ABox, we have that if C(a) 2 ABox then C(a) holds in all minimal canonical models of K.

Proof (Fact 0). For any minimal canonical model M of K= (TBox, ABox) there is a minimal rank assignment kj consistent with respect to (TBox , ABox), such that for all a in ABox and all C: if ABox [ j j=ALC C(a) then C(a) holds in M. This can be proven as follows. Let M be a minimal canonical model of K. Let kj be the rank assignment corresponding to M: s.t. for all ai in ABox kj (ai) = kM(aiI ). Obviously kj is minimal. Furthermore, M j= ABox [ j . Indeed, M j= ABox by hypothesis. To show that M j= j we reason as follows: for all ai let (:C t D)(ai) 2 ij . If aiI 2 (:C)I clearly (:C t D)(ai) holds in M. On the other hand, if aiI 2 (C)I : by hypothesis rank(C) kj (ai) hence by the correspondence between rank of a formula in the rational closure and in minimal canonical models (see Proposition 2) also kM(C) kM(aiI ), but since aiI 2 (C)I , kM(C) = kM(aiI ), therefore aiI 2 (T(C))I . By definition of i, and since by Theorem 2, M j= TBox , D(ai) holds in M and therefore also aiI 2 (:C t D)I . Hence, if ABox [ j j=ALC C(ai) then C(ai) holds in M.

Let C(a) 2 ABox , and suppose for a contradiction that there is a minimal canonical model M of K s.t. C(a) does not hold in M. By Fact 0 there must be a kj s.t. ABox [ j 6j=ALC C(a), but this contradicts the fact that C(a) 2 ABox . Therefore C(a) must hold in all minimal canonical models of K.

Theorem 4 (Completeness of ABox ). Given K=(TBox, ABox), for all a individual constant in ABox, we have that if C(a) holds in all minimal canonical models of K then C(a) 2 ABox .

Proof. We show the contrapositive. Suppose C(a) 62 ABox , i.e. there is a minimal kj consistent with (TBox , ABox) s.t. ABox [ j 6j=ALC C(a). We build a minimal canonical model M = h ; < Ii of K such that C(ai) does not hold in M as follows. Let = 0 [ 1 where 0 = ffC1; : : : Ckg S : fC1; : : : Ckg is maximal and consistent with Kg and 1 = fai : ai in ABox g. We define the rank kM of each domain element as follows: kM(fC1; : : : Ckg) = rank(C1 u u Ck), and kM(ai) = kj (ai). We then define < in the obvious way: x < y iff kM(x) < kM(y).

We then define I as follows. First for all ai in ABox we let aiI = ai. For the interpretation of concepts we reason in two different ways for 0 and 1. For 0, for all atomic concepts C0, we let fC1; : : : ; Ckg 2 C0I iff C0 2 fC1; : : : ; Ckg. I then extends to boolean combinations of concepts in the usual way. It can be easily shown that for any boolean combination of concepts C0, fC1; : : : ; Ckg 2 C0I iff C0 2 fC1; : : : ; Ckg. For 1, we start by considering a model M0 = h 0; <; I0i such that M0 j= ABox [ j and M0 6j= C(a). This model exists by hypothesis. For all atomic concepts C0, we let ai 2 C0I in M iff (ai)I0 2 C0I0 in M0. Of course for any boolean combination of concepts C0, (ai) 2 C0I iff (ai)I0 2 C0I0 .

In order to conclude the model’s construction, for each role R, we define RI as follows. For X; Y 2 0, (X; Y ) 2 RI iff fC0: 8R:C0 2 Xg Y . For ai; aj 2 1, (ai; aj ) 2 RI iff ((ai)I0 ; (aj )I0 ) 2 RI0 in M0. For ai 2 1, X 2 0, (ai; X) 2 RI iff there is an x 2 0 of M0 such that (aiI0 ; x) 2 RI0 in M0 and, for all concepts C0, we have x 2 C0I0 iff X 2 C0I . I is extended to quantified concepts in the usual way. It can be shown that for all X 2 0 for all (possibly) quantified C0, X 2 (C0)I iff C0 2 X, and that for all ai in 1, for all quantified C0, ai 2 (C0)I iff ai 2 (C0)I0 .

M satisfies ABox: for aiRaj in ABox this holds by construction. For C0(ai), this holds since (ai)I0 2 (C0)I0 in M0, hence (ai)I 2 (C0)I in M.

M satisfies TBox: for elements X 2 0, this can be proven as in Theorem 2. For 1 this holds since it held in M0. For the inclusion Cl v Cj this is obvious. For T(Cl) v Cj , for all ai we reason as follows. First of all, if kj (ai) > rank(Cl) then ai 62 M in<(ClI ) and the inclusion trivially holds. On the other if kj (ai) rank(Cl), (:Cl tCj )(ai) 2 j , and therefore (ai)I0 2 (:Cl t Cj )I0 in M0, hence (ai)I 2 (:Cl t Cj )I in M, and we are done.

C(a) does not hold in M, since it does not hold in M0. Last, M is minimal: if it was not so there would be M0 < M. However it can be shown that we could define a kj0 consistent with (TBox ; ABox) and preferred to kj , thus contradicting the minimality of kj , against the hypothesis. We have then built a minimal canonical model of K in which C(a) does not hold. The theorem follows by contraposition.

Example 1. Consider the standard penguin example. Let K = (TBox, ABox), where TBox = fT(B) v F; T(P ) v :F; P v Bg, and ABox = fP (i); B(j)g.

Computing the ranking of concepts we get that rank(B) = 0, rank(P ) = 1, rank(B u :F ) = 1, rank(P u F ) = 2. It is easy to see that a rank assignment k0 with k0(i) = 0 is inconsistent with K as i0 would contain (:P t B)(i) , (:B t F )(i), (:P t :F )(i) and P (i). Thus we are left with only two ranks k1 and k2 with respectively k1(i) = 1; k1(j) = 0 and k2(i) = k2(j) = 1.

The set 1 contains, among the others, (:P t :F )(i) , (:B t F )(j). It is tedious but easy to check that K [ 1 is consistent and that k1 is the only minimal consistent assignment (being k1 preferred to k2), thus both :F (i) and F (j) belong to ABox . Example 2. This example shows the need of considering multiple ranks of individual constants: normally computer science courses (CS) are taught only by academic members (A), whereas business courses (B) are taught only by consultants (C), consultants and academics are disjoint, this gives the following TBox: T(CS) v 8taught:A, T(B) v 8taught:C, C v :A. Suppose the ABox contains: CS(c1), B(c2), taught(c1; joe), taught(c2; joe) and let K= (TBox, ABox). Computing rational closure of TBox, we get that all atomic concepts have rank 0. Any rank assignment ki with ki(c1) = ki(c2) = 0, is inconsistent with K since the respective i will contain both (:CS t 8taught:A)(c1) and (:B t 8taught:C)(c2), from which both C(joe) and A(joe) follow, which gives an inconsistency.

There are two minimal consistent ranks: k1, such that k1(joe) = 0; k1(c1) = 0; k1(c2) = 1, and k2, such that k2(joe) = 0; k2(c1) = 1; k2(c2) = 0. We have that ABox [ 1 j= A(joe) and ABox [ 2 j= C(joe). According to the skeptical definition of ABox neither A(joe), nor C(joe) belongs to ABox , however (A t C)(joe) belongs to ABox .

Let us conclude this section by estimating the complexity of computing the rational closure of the ABox:

Theorem 5 (Complexity of rational closure over the ABox). Given a knowledge base

K =(TBox,ABox), an individual constant a and a concept C, the problem of deciding whether C(a) 2 ABox is EXPTIME-complete.

Proof. Let jKj be the size of the knowledge base K and let the size of the query be O(jKj). As the number of inclusions in the knowledge base is O(jKj), then the number n of non-increasing subsets Ei in the construction of the rational closure is O(jKj).

Moreover, the number k of named individuals in the knowledge base is O(jKj). Hence, the number kn of different rank assignments to individuals is such that both k and n are O(jKj). Observe that kn = 2Log kn = 2nLog k. Hence, kn is O(2nk), with n and k linear in jKj, i.e., the number of different rank assignments is exponential in jKj.

To evaluate the complexity of the algorithm, observe that: (i) For each j, the number of sets ij is k (which is linear in jKj). The number of inclusions in each ij is O(jKj2), as the size of S is O(jKj) and the number of Tinclusions T(C) v D 2 TBox , with C; D 2 S is O(jKj2). Hence, the size of set j is O(jKj3). (ii) For each kj , the consistency of (TBox , ABox) can be verified by checking the consistency of ABox [ j in ALC, which requires exponential time in the size of the set of formulas ABox [ j (which, as we have seen, is polynomial in the size of K). Hence, the consistency of each kj can be verified in exponential time in the size of K. (iii) The identification of the minimal assignments kj among the consistent ones requires the comparison of each consistent assignment with each other (i.e. k2 comparisons), where each comparison between kj and kj0 requires k steps. Hence, the identification of the minimal assignments requires k3 steps. (iv) To define the rational closure ABox of ABox, for each concept C occurring in K or in the query (there are O(jKj) many concepts), and for each named individual ai, we have to check if C(ai) is derivable in ALC from ABox [ j for all minimal consistent rank assignments kj . As the number of different minimal consistent assignments kj is exponential in jKj, this requires an exponential number of checks, each one requiring exponential time in the size of the knowledge base jKj. The cost of the overall algorithm is therefore exponential in the size of the knowledge base. 5

Conclusions and Related works

We have defined a rational closure construction for the Description Logic ALC extended with a typicality operator and provided a minimal model semantics for it based on the idea of minimizing the rank of objects in the domain, that is their level of “untypicality”. This semantics corresponds to a natural extension to DLs of Lehmann and Magidor’s notion of rational closure. We have also extended the notion of rational closure to the ABox, by providing an algorithm for computing it that is sound and complete with respect to the minimal model semantics. Last, we have shown an EXPTIME upper bound for the algorithm.

In future work, we will consider a further ingredient in the recipe for nonmonotonic DLs. In analogy with circumscription, we can consider a stronger form of minimization where we minimize the rank of domain elements, but we allow to vary the extensions of concepts. Furthermore, as mentioned in the Introduction, we aim at studying stronger versions of rational closure that allows to overcome the weaknesses of the basic one, for instance the fact that we cannot reason separately on the inheritance of different properties. Last, nonmonotonic extensions of low complexity DLs based on the T operator have been recently provided [ 12 ]. In future works, we aim to study the application of the proposed semantics to DLs of the E L and DL-Lite families, in order to define a rational closure for low complexity DLs.

In [ 14, 12 ] nonmonotonic extensions of DLs based on the T operator have been proposed. In these extensions, the semantics of T is based on preferential logic P. Nonmonotonic inference is obtained by restricting entailment to minimal models, where minimal models are those that minimize the truth of formulas of a special kind. In this work, we have presented an alternative approach. First, the semantics underlying the T operator is not fixed once for all: although here we have considered only KLM’s R as underlying semantics, in principle one might choose any other underlying semantics for T based on a modal preference relation. Moreover and more importantly, we have adopted a minimal model semantics, where, as a difference with the previous approach, the notion of minimal model is completely independent from the language and is determined only by the relational structure of models.

Casini and Straccia [ 5 ] study the application of rational closure to DLs. They first propose an alternative construction to compute rational closure R(K) (as defined by Lehmann and Magidor) of a propositional knowledge base K, then they adapt it to the DL ALC, without explicitly defining the rational closure R(K’) of an ALC knowledge base K’. In this work, we have provided a definition of R(K’) of an ALC knowledge base K’, and we conjecture that Casini and Straccia’s algorithm computes R(K’) as defined in this paper. [ 5 ] keeps the ABox into account, and defines closure operations over individuals. They introduce a consequence relation among a KB and assertions, under the requirement that the TBox is unfoldable and the ABox is closed under completion rules, such as, for instance, that if a : 9R:C 2 ABox, then both aRb and b : C (for some individual constant b) must belong to the ABox too. Under such restrictions they are able to define a procedure to compute the rational closure of the ABox assuming that the individuals explicitly named are linearly ordered, and different orders determine different sets of consequences. The authors show that, for each order s, the consequence relation s is rational and can be computed in PSPACE. In a subsequent work [ 6 ], the authors introduce an approach based on the combination of rational closure and Defeasible Inheritance Networks (INs).

The logic ALCRT we consider as our base language is equivalent to the logic for defeasible subsumptions in DLs proposed by [ 3 ], when considered with ALC as the underlying DL. The idea underlying this approach is very similar to that of ALCRT: some objects in the domain are more typical than others. In the approach by [ 3 ], x is more typical than y if x y. The properties of correspond to those of < in ALCRT. At a syntactic level the two logics differ, so that in [ 3 ] one finds the defeasible inclusions C @ D instead of T(C) v D of ALCRT, however it has be shown in [ 11 ] that the logeic of preferential subsumption can be translated into ALCRT by replacing C @ D with T(C) v D. e

In [ 4 ] the semantics of the logic of defeasible inclusions is strenghtened by a preferential semantics. Intuitively, given a TBox, the authors first introduce a preference ordering on the class of all subsumption relations @ including TBox, then they define the rational closure of TBox as the most preferred relaetion @ w.r.t. , i.e. such that there is no other relation @0 such that TBox @0 and @0 e@. Furthermore, the authors describe an EXPTIMeE algorithm in order teo compeute theerational closure of a given TBox. However, they do not address the problem of dealing with the ABox. In [ 20 ] 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.

References

1. F. Baader and B. Hollunder. 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. Piero A. Bonatti , Carsten Lutz, and Frank Wolter . The Complexity of Circumscription in DLs . Journal of Artificial Intelligence Research (JAIR) , 35 : 717 - 773 , 2009 .

3. Katarina Britz , Johannes Heidema, and Thomas Meyer. Semantic preferential subsumption . In G. Brewka and J. Lang, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 11th International Conference (KR 2008 ), pages 476 - 484 , Sidney, Australia, September 2008 . AAAI Press.

4. Katarina Britz , Thomas Meyer, and Ivan Jose´ Varzinczak. Semantic foundation for preferential description logics . In AI 2011: Advances in Artificial Intelligence - 24th Australasian Joint Conference , volume 7106 of Lecture Notes in Computer Science, pages 491 - 500 . Springer, 2011 .

5. G. Casini and U. Straccia . Rational Closure for Defeasible Description Logics . In T. Janhunen and I. Niemela¨, editors, Proceedings of the 12th European Conference on Logics in Artificial Intelligence (JELIA 2010 ), volume 6341 of Lecture Notes in Artificial Intelligence , pages 77 - 90 , Helsinki, Finland, September 2010 . Springer.

6. Giovanni Casini and Umberto Straccia . Defeasible Inheritance-Based Description Logics . In Toby Walsh, editor, Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011 ), pages 813 - 818 , Barcelona, Spain, July 2011 . Morgan Kaufmann.

7. F. M. Donini , D. Nardi , and R. Rosati . Description logics of minimal knowledge and negation as failure . ACM Transactions on Computational Logic (ToCL) , 3 ( 2 ): 177 - 225 , 2002 .

8. T. Eiter , T. Lukasiewicz , R. Schindlauer , and H. Tompits . Combining Answer Set Programming with Description Logics for the Semantic Web . In D. Dubois, C.A. Welty , and M. Williams, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 9th International Conference (KR 2004 ), pages 141 - 151 , Whistler, Canada, June 2004 . AAAI Press.

9. Michael Freund . Preferential reasoning in the perspective of poole default logic . Artif . Intell., 98 ( 1-2 ): 209 - 235 , 1998 .

10. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . ALC+ T: a preferential extension of Description Logics . Fundamenta Informaticae , 96 : 1 - 32 , 2009 .

11. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Preferential vs Rational Description Logics: which one for Reasoning About Typicality ? In Helder Coelho, Rudi Studer, and Michael Wooldridge, editors, Proceedings of ECAI 2010 (19th European Conference on Artificial Intelligence) , volume 215 of Frontiers in Artificial Intelligence and Applications , pages 1069 - 1070 , Lisbon, Portugal, August 16 -20 2010 . IOS Press.

12. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Reasoning about typicality in low complexity DLs: the logics E L?Tmin and DL-Litec Tmin . In Toby Walsh, editor, Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011 ), pages 894 - 899 , Barcelona, Spain, July 2011 . Morgan Kaufmann.

13. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . A minimal model semantics for nonmonotonic reasoning . In Je´roˆme Mengin Luis Farin˜as del Cerro , Andreas Herzig, editor, Logics in Artificial Intelligence - 13th European Conference, JELIA 2012 , volume 7519 of LNAI , pages 228 - 241 , Toulouse, France, Sptember 2012 . Springer-Verlag.

14. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . A NonMonotonic Description Logic for Reasoning About Typicality . Artificial Intelligence , pages 165 - 202 , 2012 .

15. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . A minimal model semantics for rational closure . In R. Rosati and S. Woltran, editors, NMR 2012 (14th International Workshop on Non-Monotonic Reasoning) , Roma, Italy, 2012 .

16. P. Ke and U. Sattler . Next Steps for Description Logics of Minimal Knowledge and Negation as Failure . In F. Baader, C. Lutz , and B. Motik, editors, Proceedings of Description Logics , volume 353 of CEUR Workshop Proceedings , Dresden, Germany, May 2008 . CEUR-WS.org .

17. S. Kraus , D. Lehmann , and M. Magidor . Nonmonotonic reasoning, preferential models and cumulative logics . Artificial Intelligence , 44 ( 1-2 ): 167 - 207 , 1990 .

18. Adila Alfa Krisnadhi, Kunal Sengupta, and Pascal Hitzler . Local closed world semantics: Keep it simple , stupid! In Proceedings of Description Logics , volume 745 of CEUR Workshop Proceedings , Barcelona, Spain, July 2011 .

19. Daniel Lehmann and Menachem Magidor . What does a conditional knowledge base entail? Artificial Intelligence , 55 ( 1 ): 1 - 60 , 1992 .

20. Kodylan Moodley , Thomas Meyer, and Ivan Jose´ Varzinczak. A protege plug-in for defeasible reasoning . In Description Logics , volume 846 of CEUR Workshop Proceedings. CEURWS.org , 2012 .

21. Boris Motik and Riccardo Rosati . Reconciling Description Logics and rules . Journal of the ACM , 57 ( 5 ), 2010 .

22. U. Straccia . Default inheritance reasoning in hybrid kl-one-style logics . In R. Bajcsy, editor, Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI 1993 ), pages 676 - 681 , Chambe´ry, France, August 1993 . Morgan Kaufmann.