Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox Giovanni Casini, Thomas Meyer, Kody Moodley, and Ivan Varzinczak Centre for Artificial Intelligence Research CSIR Meraka Institute and UKZN, South Africa {GCasini,TMeyer,KMoodley,IVarzinczak}@csir.co.za Abstract. The introduction of defeasible reasoning in description logics has been a main research topic in the field in the last years. Despite the fact that various interesting formalizations of nonmonotonic reasoning for the TBox have been proposed, the application of such a kind of reasoning also to ABoxes is more problematic. In what follows we are going to present the adaptation for the ABox of a classical nonmonotonic form of reasoning, namely Lehmann and Magidor’s Rational Closure. We present both a procedural and a semantical characterization, and we conclude the paper with a comparison between our and other analogous proposals. 1 Introduction In the last years it has become apparent the need for the introduction of forms of uncer- tain and non-classical reasoning in the field of formal ontologies; hence, considering the main role of description logics (DLs), endowing DLs with non-monotonic features is an important problem from the point of view of knowledge representation and reason- ing. Indeed, there have been various proposals for the introduction of non-monotonic reasoning in DLs and similarly structured logics, mostly ranging from preferential ap- proaches [8,9,10,13,18,23] to circumscription [2], amongst others [1,3,4,7,11,15]. The preferential approach, that has been formalized for the propositional languages mainly in the 90’s [20,22], turns out to be particularly promising for a number of rea- sons. Firstly, it provides a thorough analysis of the properties that any non-monotonic consequence relation considered ‘well-behaved’ is supposed to satisfy, which plays a central role in assessing how intuitive the obtained results are; secondly, it allows for many decision problems to be reduced to classical entailment checking, sometimes without blowing up the computational complexity with respect to the classical case, and, thirdly, it has a well-known connection with belief revision [16,19]. It is reason- able to expect that most of these features will transfer to extensions for DLs. In what follows we are going to present the adaptation for the ABox of a classi- cal nonmonotonic form of reasoning, Lehmann and Magidor’s Rational Closure. Else- where [6,10] we have taken under consideration the Rational Closure of a defeasible knowledge base composed only of defeasible inclusion axioms, i.e. inclusion axioms C< ∼ D read as ‘an object falling under the concept C typically falls also under the con- cept D’, and we are going to briefly review such a procedure in the following section. Instead, here we are going to take under consideration knowledge bases composed also of an ABox A containing information about specific individuals, as C(a) (‘the individ- ual a falls under the concept C’) or r(a, b) (the individual a is connected to the individ- ual b through the role r): we shall present a procedure defining rational closure for the ABox, giving also a semantic characterization (Section 3). Eventually in Section 4 we shall compare the proposed procedure with other ones in the field. 2 Preliminaries ALC language and semantics. We shall present our work for the description logic ALC, but it is adaptable also to other more expressive description logics. The language of the description logic ALC is built up from a finite set of concept names NC and a finite set of role names NR such that NC ∩ NR = ∅. A concept name is denoted by A and a role name by r. Complex concepts are denoted by C, D, . . ., and are built in the usual way according to the rule: C ::= A | ¬C | C u C | ∃r.C | >. Concepts built with the constructors t and ∀, as well as the concept ⊥, are defined in terms of the others in the usual way. We denote the set of all ALC concepts by L. The semantics of ALC is a standard set theoretic semantics. An interpretation is a structure I := h∆I , ·I i, where ∆I is a non-empty set called the domain, and ·I is an interpretation function mapping concept names A ∈ NC into subsets AI of ∆I , and mapping role names r ∈ NR into binary relations rI over ∆I × ∆I . Given an interpretation I = h∆I , ·I i, ·I is extended to interpret complex concepts in the fol- lowing way: (¬C)I = ∆I \ C I , (C u D)I = C I ∩ DI , and (∃r.C)I = {x ∈ ∆I | for some y, (x, y) ∈ rI and y ∈ C I }. Given C, D ∈ L, C v D is a subsumption statement. C ≡ D is an abbreviation for both C v D and D v C. An ALC knowledge base K is composed by a TBox T and an ABox A. A TBox T is a finite set of subsumption statements. An interpretation I satisfies C v D (denoted I C v D) if and only if C I ⊆ DI . C v D is (classically) entailed by a TBox T , denoted T |= C v D, if and only if I C v D for every I such that I E v F for all E v F ∈ T . An ABox A is a set of assertions about individuals. Let D be a set of individuals {a, b, c, . . .}, that are interpreted in h∆I , ·I i as elements of the domain ∆I , i.e. aI ∈ ∆I . The admissible assertions in ALC have the form C(a) and r(a, b), where I C(a) if and only if aI ∈ C I and I r(a, b) if and only if haI , bI i ∈ rI . Hence, a classical ALC knowledge base K is composed by a finite TBox T and a finite ABox A (K = hA, T i), both of them possibly empty. Rational Closure of the TBox. In order to formalize defeasible reasoning in DLs, we introduce a form of defeasible subsumption statements, indicated as C < ∼ D and read as ‘the individuals falling under the concept C typically fall also under the con- cept D’ [6,10]. Hence, a defeasible knowledge base K is composed also by a DBox D, a finite set of defeasible subsumption statements (K = hA, T , Di). Here we recall the procedure to formalize the Rational Closure of a set of inclusion axioms, without considering the information about the individuals, i.e. we present the procedure to de- termine the Rational Closure of a knowledge base composed only of TBox and Dbox, hT , Di.We shall indicate the inference relation corresponding to the rational closure with `rat . The procedure below, appropriate for deciding `rat , has been originally pre- sented in [13], and the reader should look at such a paper for a better insight on the procedure. Step 1. Let D (resp., T ) be the set containing the materializations of the axioms in D (resp., T ), i.e. D = {¬C t D | C < ∼ D ∈ D} (resp., T = {¬C t D | C v D ∈ T }); by materialization of an inclusion axiom C < ∼ D or C v D we indicate the concept that expresses in the language the same inclusion relation as the one expressed by the axiom (if an object falls under C, then it falls also under D). We determine an exceptionality ranking of the sequents in D using T and D. A concept C is considered exceptional in a knowledge base hT , Di only if l l |= T u D v ¬C. If a concept C is exceptional in hT , Di, also all the defeasible inclusion axioms having C as antecedent are considered exceptional. Given a knowledge base hT , Di, we can define a < D | |= d function E that gives back the exceptional axioms in D (E(D) = {C ∼ T u D v ¬C}).1 Given hT , Di we can construct a sequence E0 , E1 , . . . starting with E0 = D d and setting Ei+1 = E(Ei ). Since D is a finite set, the construction will terminate with a (empty or not-empty) fixed point of E. Step 2 We define a ranking function r that associates to every axiom in D a number, representing its level of exceptionality: i if C < <  ∼ D ∈ Ei and C ∼ D ∈ / Ei+1 r(C < ∼ D) = < ∞ if C ∼ D ∈ Ei for every i . We indicate with Di the set of the defeasible axioms having i as ranking value. Hence a set D is partitioned into the sets D1 , . . . , Dn , D∞ , for some n, and with D∞ possibly empty. It is possible to define a new knowledge base hT 0 , D0 i, with T 0 = T ∪{C v D | C < ∼ D ∈ D∞ } and D0 = D/D∞ . The only difference between hT , Di and hT 0 , D0 i is that the classical knowledge that was ‘implicitly contained’ in D is now moved into T , and the set D0 is partitioned by the ranking function r into D1 , . . . , Dn , without any axiom with ∞ as ranking value. We shall indicate with δi the defaultdconceptS obtained from the conjunction of all the materializations of rank i or higher (δi = ( i≤j≤n Dj )). Step 3. Now, given a knowledge base hT , Di we can define the inference relation `rat . Definition 1. hT , Di `rat C < d 0 diff 0|= T u δi u C v D, where δi is the first element of ∼D the sequence dhδ0 , . . . , δn i s.t. 6|= T u δi v ¬C; if there is no such element, hT , Di `rat C< ∼ D iff |= T 0 u C v D. Moreover, hT , Di `rat C v D iff hT , Di `rat C u ¬D < ∼ ⊥. The inference relation `rat satisfies the DL-translation of the properties character- izing rational consequence relations, and, since the entire procedure consists of a finite number of classical decisions, it is implementable using already existing DL reasoners, and the complexity of the decision problem does not increase w.r.t. the classical one (i.e., the it is ExpTime-complete for ALC). The semantic characterization presented here below strengthens the claim that the above procedure is the DL-correspondent of rational closure. 1 This is the only difference between the present procedure and the original one in [13]. The lat- ter is a syntactical procedure still lacking of a semantics, and the condition for the exception- ality of a concept C is T ∪ Dv |= > v ¬C (Dv = {C v D | C < ∼ D ∈d D}), while d the se- mantics presented in what follows suggests that the correct condition is |= T u D v ¬C. Semantics. We can give a semantic characterization of the Rational Closure for ALC using the notion of minimal ranked model, defined for the propositional logic by Giordano et al. [17], and here we briefly present a reformulation for ALC. More details about the preferential and ranked models for ALC and the notion of minimal ranked entailment can be found in [6]. First of all, we need to define the notion of ranked interpretation, that in turn is based on the notion of modular order. Given a set X, ≺ ⊆ X × X is a modular order if and only if there is a ranking function rk : X −→ N s.t. for every x, y ∈ X, x ≺ y iff rk(x) < rk(y). Definition 2 (Ranked Interpretation). A ranked interpretation is a structure R = h∆R , ·R , ≺R i, where h∆R , ·R i is a DL interpretation (which we denote by IR ), and ≺R is a modular order on ∆R satisfying the smoothness condition (for every C ∈ L, min≺R (C R ) 6= ∅). As in the propositional case [20], the order ≺R is read as a typicality order [3,4,5], in this case defined over the objects in the domain [8], i.e., if we have that, for a, b ∈ ∆R , a ≺R b is in R, then a is considered a more typical object than b in the situation de- picted by R; for each concept C, the set min≺R (C R ) = {x ∈ C R | there is no y ∈ C R s.t. y ≺R x} contains the most typical elements of C in R. A ranked interpreta- tion R = h∆R , ·R , ≺R i satisfies a defeasible subsumption statement C < ∼ D, denoted by R C< R ∼ D, if and only if min≺R (C ) ⊆ D , with C R R and DR being the in- terpretations in R of the concepts C and D. A knowledge base hT , Di is consistent if and only if there is a ranked model that satisfies all the classical inclusion axioms in T and all the defeasible inclusion axioms in D. Given a knowledge base hT , Di, consider the ranked models satisfying hT , Di; in order to define the consequence relation we are interested in, we do not take all of them under consideration, but we select just some of them, respecting the following procedure. For every ranked model R, we can define a function hR that, given an object in ∆R , gives back its height in R, i.e., hR (x) is the length of the longest chain x0 ≺R , . . . , ≺R x, where x0 ∈ min≺R (∆R ); we shall consider only the finitely ranked models, that is, those models in which there is a maximal value for the height of the objects in the domain (actually, we can prove that each ranked model have a preferentially equivalent model that is finitely ranked). First of all, we need to define a notion of D-compatibility of an interpretation w.r.t. a knowledge base hT , Di. We indicate with |=R the consequence relation defined in the classical way using all the ranked models of hT , Di, that is, hT , Di |=R C < ∼ D if and only if C < ∼ D is satisfied in all the ranked models satisfying hT , Di. Definition 3. For an interpretation I and an x ∈ ∆I , the tuple hI, xi is hT , Di- compatible if and only if hT , Di 6|=R C < I ∼ ⊥ for every C ∈ L s.t. x ∈ C . I is said to be hT , Di-compatible if and only if for every hT , Di-compatible tuple hJ , yi there is an x in ∆I such that, for every C ∈ L, x ∈ C I iff y ∈ C J . A ranked interpretation R is hT , Di-compatible if and only if the classical interpretation IR associated with it is hT , Di-compatible. Given a classical interpretation I, we consider the set RhI,hT ,Dii of all the ranked interpretations that agree on I and satisfy hT , Di. If I is hT , Di-compatible, also are the interpretations in RhI,hT ,Dii . We take under consideration as candidate models for our consequence relation exactly the interpretations in all the hT , Di-compatible sets RhI,hT ,Dii . Hence, given a set RhI,hT ,Dii composed of hT , Di-compatible and finitely ranked interpretations, we define an order ≤I on such interpretations s.t., given two interpreta- tions R, R0 ∈ RhI,hT ,Dii , R ≤I R0 iff for every x ∈ ∆I hR (x) ≤ hR0 (x). Based on such an ordering of the interpretations, we can define the consequence relation ≤ R. Definition 4. For a consistent knowledge base hT , Di, hT , Di ≤ < R C ∼ D if and only if R < C ∼ D, where R is the ≤I -minimum ranked interpretation of some hT , Di- compatible interpretation I. If hT , Di is unsatisfiable then every defeasible subsump- tion statement C < ∼ D is in the ranked entailment of hT , Di. Such a consequence relation corresponds to `rat . Theorem 1. For every knowledge base hT , Di and every defeasible subsumption rela- ≤ tion C < < < ∼ D, hT , Di `rat C ∼ D iff hT , Di R C ∼ D. 3 Rational Extensions of an ABox Here we consider the extension of the above procedure to knowledge bases contain- ing also an ABox: given information about particular individuals, we want to derive what presumably holds about such individuals. Our knowledge base will have a classi- cal ABox, composed of concept and role assertions, but, using the defeasible inclusion axioms in D, we will be able to derive defeasible informations about the individuals: we shall indicate with the expression ‘·C(a)’ the conclusion that the individual a presum- ably falls under the concept C. A first attempt for this kind of procedure is presented in [13], and a similar version of the following procedure, specified for a consequence relation different from rational closure, appears in another paper [12], but they both lack of a semantical characterization and the properties of the inference relation are not properly investigated. The procedure for the ABox is built on top of the procedure for the DBox. Hence we work with a knowledge base hA, T , Di, and from now we assume that we have already applied the above procedure to the knowledge base hT , Di, that is, we assume that in the pair hT , Di all the strict information has already been moved into the TBox T , i.e., in D, D∞ is empty and the set has already been partitioned into D0 , . . . , Dn , for some finite n. The basic idea of the following procedure is to consider each individual named in the ABox as much typical as possible, that is, to associate to it all the possible defeasible information that is consistent with the rest of the knowledge base. In order to apply the defeasible information locally to each individual, we encode such information using the materializations of the inclusion S axioms, i.e. the sets Di and the default concepts δi . Hence, given D = {D0 , . . . , Dn }, we end up with the sequence of default con- cepts ∆ = hδ0 , . . . , δn i, as specified in Section 2 at the Step 2 of the Rational Closure procedure. It is easy to see that δi |= δi+1 for 1 ≤ i ≤ n, and we want to be able to associate to each individual a ∈ O (with O being the set of the individuals named in the ABox) the strongest formula δi that is consistent with the knowledge base. In such a way we define a new knowledge base K e = hAD , T i, that we call a rational ABox extension of the knowledge base hA, T , Di. Definition 5 (Rational ABox extension). Given a knowledge base K = hA, T , Di (with hT , Di already modified in such a way that D∞ = ∅), a knowledge base hAD , T i is a rational extension of K = hA, T , Di iff – hAD , T i is classically consistent and A ⊆ AD . – For any a ∈ O, C(a) ∈ AD \ A iff C = δi for some i and for every δh , h < i, hT , AD ∪ {δh (a)}i |= ⊥ The above definition identifies the extensions of the original ABox A s.t. to every individual is associated all the defeasible information that is consistent with the rest of the knowledge base. Using such an approach dealing with the individuals, we remain consistent with the idea behind rational closure: the default information still respects the exceptionality ranking, and we consider each individual as much typical as possible, preserving the general consistency. Also the semantic characterization that is presented here will confirm that the notion of rational ABox extension is consistent with the basic idea of rational closure, that is, ‘pushing’ the individuals as lower as possible in the model. Still, the main problem is that, since the individuals can be related to each other through roles, the possibility of associating a default concept to an individual is often influenced by the default information associated to other individuals, as shown in the following example. Example 1. Consider K = hA, Di, with A = {r(a, b)} and D = D0 = {> < ∼A u ∀R.¬A} (hence we have ∆ = hδ0 i = hA u ∀r.¬Ai). If we associate δ0 to a, we obtain ¬A(b) and we cannot associate δ0 to b; on the other hand, if we apply δ0 to b, we derive A(b) and we are not anymore able to associate δ0 to a. Hence, we define two possible rational extensions of K. 2 This implies that, given a knowledge base hA, T , Di, even if the rational closure of hT , Di is always unique there is the possibility that we have more than one rational ABox extensions. Once we have defined the sequence of default concepts ∆ from D, a simple procedure to obtain all the possible extensions of a knowledge base hA, T , Di, with O the set of the individuals named in A, is the following: Definition 6. [Procedure for rational ABox extensions] – Consider the set S of all the linear orders of the individuals in O; – For each s = ha1 , . . . , am i in S do: • Set j = 1 • Set AD = A • Repeat until j = m + 1: ∗ Find the first default δi ∈ ∆ such that hAD ∪ {δi (aj )}, T }i 6|= > v ⊥. ∗ AD = AD ∪ {δi (aj )}. ∗ j =j+1 • return hAsD , T i Hence, the procedure returns a knowledge base hAsD , T i for each s ∈ S. Now, the following can be proven: Proposition 1. Given a knowledge base K = hA, T , Di and a linear order of O, the above procedure determines a rational ABox extension of K. Contrariwise, every ratio- nal ABox extension of K corresponds to the knowledge base generated by some linear order of the individuals in O. Now, if we fix a priori a linear order s on the individuals, we can say that ·C(a) is a defeasible consequence of K = hA, T , Di w.r.t. the order s, written ‘K `sr ·C(a)’, iff hAsD , T i |= C(a), where hAsD , T i is the rational extension generated from K using the order s. The interesting point of such a consequence relation is that it still satisfies the properties of a rational consequence relation in the following way. Proposition 2. Given K and a linear order s of the individuals in K, the consequence relation `sr satisfies the following properties: (REFDL ) hA, T , ∆i `sr ·C(a) for every C(a) ∈ A Reflexivity hA ∪ {D(b)}, T , Di `sr ·C(a)  D ≡ E (LLEDL ) Left Logical Equivalence hA ∪ {E(b)}, T , Di `sr ·C(a) hA, T , Di `sr ·C(a)  C v D (RWDL ) Right Weakening hA, T , Di `sr ·D(a) hA ∪ {D(b)}, T , Di `sr ·C(a) hA, T , Di `sr ·D(b) (CTDL ) Cautious Transitivity (Cut) hA, T , Di `sr ·C(a) hA, T , Di `sr ·C(a) hA, T , Di `sr ·D(b) (CMDL ) Cautious Monotonicity hA ∪ {D(b)}, T , Di `sr ·C(a) hA ∪ {D(b)}, T , Di `sr ·C(a) hA ∪ {E(b)}, T , Di `sr ·C(a) (ORDL ) Left Disjunction hA ∪ {D t E(b)}, T , ∆i `sr ·C(a) hA, T , Di `sr ·C(a) hA, T , Di 6`sr ·¬D(b) (RMDL ) Rational Monotonicity hA ∪ {D(b)}, T , Di `sr ·C(a) For the explanation of the original propositional rules and their meaning, check the paper by Kraus et al. [20], while, about the DL case, see [6]. Example 2. We define a DL-variation of the penguin example. Let K = {A, T , D} be a knowledge base where A = {P (a), B(b), Hunt(a, c), Hunt(b, c)}, T = {P v B, I v ¬F i}, D = {B < < < < ∼ F, P ∼ ¬F, B ∼ ∀Hunt.I, P ∼ ∀Hunt.F i}, where you can read B as Bird, P as Penguin, F as Flying, I as Insect, F i as Fish, and Hunt as hunts. From D we obtain the default concepts δ0 = (¬B t F ) u (¬B t ∀Hunt.I) u (¬P t ¬F ) u (¬P t ∀Hunt.F i) and δ1 = (¬P t ¬F ) u (¬P t ∀Hunt.F i). Applying our procedure we can identify two possible rational ABox extensions of K: one in which we associate the default concepts first to a and then to b, and the second one in which we consider b before a. In the former case we associate to a the default δ1 , and we derive that a is a typical penguin that hunts fishes (hence we can conclude F i(c)) and does not fly, while, having concluded that c is a fish, we cannot associate anymore δ0 to b, and we have to treat b as an atypical bird, and we are not able to associate to c the typical properties of birds, i.e., that it flies and hunts insects. On the other hand, if we consider b before a, we associate δ0 to b, hence considering b a typical bird that flies and hunts insects, but, being c an insect, we cannot associate with it the concept δ1 , and we have to consider a an atypical penguin. 2 From the point of view of the computational complexity, the decision problem w.r.t. `sr has the same complexity result of the classical ABox consistency decision problem in ALC [14]. Proposition 3. Deciding hA, T , Di `sr ·C(a) in ALC is an ExpTime-complete prob- lem. In the presence of multiple rational ABox extensions, we can also define the infer- ence relation `r , a more conservative inference relation independent from any order on the individuals, that corresponds to the intersection of all the inference relations `sr modeling a rational extension. \ `r = {`sr | s is a linear order on the elements of O} However, there is the possibility that we lose the property of rational monotonicity. Proposition 4. The inference relation `r does not always satisfy (RMDL ). The computational complexity of `r is the same as `sr , i.e., the decision procedure is ExpTime-complete: assuming that the number of individuals named in the ABox is n, we have to decide `sr for each possible sequences s defined on the n individuals. That is, in the worst case we need to do n! ExpTime-complete decision procedures, that, again, gives back an ExpTime-complete decision procedure2 . Yet, we have still to understand if there is the possibility of a decision procedure characterized by a lower computational complexity. Notwithstanding, in many (proba- bly most) of the real-world cases, a knowledge base would have a single rational ABox extension, and in such cases on one hand (RMDL ) is still valid, and on the other hand the decision problem remains ExpTime-complete. To check whether a knowledge base hA, T , Di has a single rational ABox extension, it is sufficient to associate to each in- dividual in O the strongest δi modulo consistency w.r.t hA, T , Di, exactly as in the procedure in Definition 6, but without adding at every step the new default information to A. At the end, add to the knowledge base the default information associated to each individual in A. If the new knowledge base is consistent, that is the only rational ABox extension of hA, T , Di. Proposition 5. In the presence of a knowledge base hA, T , Di that has a single ra- tional ABox extension, checking the uniqueness of the rational ABox extension and whether hA, T , Di `sr ·C(a) is an ExpTime-complete problem in ALC. Example 3. Consider the KB in Example 2, where in A Hunt(b, c) is replaced with Hunt(b, d). Then, whatever is the order on the individuals, we obtain the following association between the default formulae and the individuals: δ1 (a), δ0 (b), δ0 (c), and δ0 (d). Using the information in these defaults, we obtain a unique rational ABox exten- sion. 2 2 See e.g., http://lifecs.likai.org/2012/06/better-upper-bound-for-factorial.html. Semantics. Extending the minimal ranked model approach also to the ABoxes we can characterize from the semantical point of view also the procedure for the rational ABox extension we have just defined. Consider a knowledge base hA, T , Di, where the tuple hT , Di has already been transformed in such a way that all the strict knowledge is in T , and D is partitioned into D1 , . . . , Dn . First of all, we can check if it is a consistent knowledge base by using classical reasoning. A knowledge base hA, T , Di is consistent if there is a ranked interpretation that satisfies all the assertions in A, all the classical subsumption axioms in T and all the defeasible subsumption axioms in D. d Lemma d 1. A knowledge base hA, T , Di is consistent iff hA, T i 6|= ⊥ and 6|= T u D v ⊥. Now that we have a method to decide for the consistency of a knowledge base hA, T , Di, we can prove that the consistency of hA, T , Di guarantees the existence of a minimal ranked model (see Definition 4) of hT , Di satisfying A. Lemma 2. Let hA, T , Di be a consistent knowledge base. Then there is at least a min- imal ranked model of hT , Di satisfying A. Since the consistency of a knowledge base hA, T , Di implies that there is at least a minimal ranked model of hT , Di that satisfies the ABox A, we can define a notion of minimal model in the presence also of an ABox (again, O is the set of the individuals named in A). We define an order ≤A between the minimal models of hT , Di satisfying A s.t., given R = {∆, ≺, ·R } and R0 = {∆, ≺0 , ·R } (note that IR = IR0 ), R ≤A R0 0 iff hR (aI ) ≤ hR0 (aI ) for each object a in O. The minimal ABox models of hA, T , Di are the minimal elements of the order ≤A . Definition 7 (Minimal ABox model). R = {∆, ≺, ·R } is a minimal ABox model of a knowledge base hA, T , Di iff it is a minimal ranked model of hT , Di that satisfies A, and there is not a minimal ranked model R0 = {∆, ≺0 , ·R } of hT , Di that satisfies A s.t. R0 ≤A R and R 6≤A R0 . Given the set MhA,T ,Di of the minimal ABox models of hA, T , Di, we indicate hA,T ,Di with Mh the subclass of MhA,T ,Di composed by the elements of MhA,T ,Di in which each element a of O has a specific height h(a) = n. We define a consequence relation |=≤ h as hA,T ,Di hA, T , Di |=≤ h C(a) iff M C(a) for each M ∈ Mh and we indicate with |=≤ the consequence relation defined by all the minimal ABox models of hA, T , Di. hA, T , Di |=≤ C(a) iff M C(a) for each M ∈ M hA,T ,Di , There is a correspondence between the inference relations `sr and `r and, respec- tively, the consequence relations |=≤ ≤ h and |= . Proposition 6. Given a knowledge base hA, T , Di, each inference relation `sr defined by a sequence s on the elements of O corresponds to the consequence relation |=≤ h for some h, and the other way around. The inference relation `r , corresponding to the intersection of all `sr generated by hA, T , Di, corresponds to the consequence relation |=≤ . Queries. Assume we want to know if a particular individual a presumably falls under a concept C, and we want to draw the safest possible conclusion. In the presence of multiple acceptable extensions, the classical solution is to use a skeptical approach, i.e. to use the inference relation `r , corresponding to the intersection of all the inference relations associated to each possible ordering s of the individuals appearing in A. As we have seen above, in case of multiple rational extensions the computational of the `r decision problem rises w.r.t the classical ALC decision problem. However, in case of multiple extensions,the amount of default information associable to an indi- vidual a can be influenced only by the individuals related to it by means of a role: it is immediate to see that if there is no role-connection in the ABox between two indi- viduals a and b, then the information that is associated to a does not influence at all the amount of defeasible information that we can associate to b. Hence, we can ease the decisions w.r.t. the ABox introducing the notion of cluster, i.e., a set of individuals named in the ABox that are linked by means of a sequence of role connections. To do so, given an ABox A, we indicate with Q the symmetric and transitiveSclosure of all the roles in our vocabulary, i.e., the symmetric and transitive closure of R, and with Q the set of the pairs of individuals named in A that are connected by Q. S Definition 8 (Cluster). Define Q as the symmetric and transitive closure of R. Given an individual a ∈ O, we call the cluster of a the set [a] of the individuals connected to a through Q. [a] = {b ∈ O | Q(a, b)} Hence, in order to know what we can presumably conclude about a, it is sufficient to determine `sr w.r.t. each sequence s of individuals in [a]. Let A[a] be the ABox obtained restricting A to the statements containing individuals in [a]; the query ·C(a) is clearly decidable using only A[a] . Proposition 7. hA, T , Di `r ·C(a) iff hA[a] , T , Di `sr ·C(a) for every ordering s of the individuals in A[a] . If we have a query about an individual a s.t. a is not named in the ABox (a 6∈ O), we do not have any constraints defined in the ABox about a, we only know >(a); hence, for each individual not appearing in the ABox, we can associate with it the strongest default concept consistent with T , that is δ0 : for any a s.t. a 6∈ O, we can derive that presumably C(a) holds iff hAa , T i |= C(a), where Aa = A ∪ {δ0 (a)}. 4 Related Work Two main proposals in the field modeling defeasible reasoning in DLs, and specifically in ALC or analogous languages, and dealing also with the ABox are the works by Bonatti et al. [2] and by Giordano et al. [18]. The proposal by Bonatti et al. [2] is based on circumscription. From the point of view of the quality of the inferences, in such a proposal is more difficult to draw the expected conclusions. For example, assume that our knowledge base contains the infor- mation that mammals typically live on land, but that whales are abnormal mammals that do not live on the land, and the ABox contains the information M ammalu¬W hale(a). Not knowing anything else about the individual a, we would like our reasoning system to assume that we are dealing with a typical mammal (since, moreover, it is specified that a is not a whale) and hence being able to derive that a lives on the land, but in Bonatti’s proposals the conclusions we can draw change w.r.t. which concepts the user decides to keep fixed or varying (a non-trivial choice), and the results can be that we are not able to derive ∃Habitat.Land(a), that we are able to derive it, or we can even derive that whales do not exist ([2], Section 2.1). In our proposal we can formalize the problem with a knowledge base hA, T , Di with A = {M ammal(a)} (we do not need to spec- ify that it is not a whale), T = {W hale v M ammal, W hale v6 ∃Habitat.Land} and D = {M ammal < ∼ ∃Habitat.Land}; without needing any kind of choice from the user, the system can derive automatically ·∃Habitat.Land(a). Moreover, we have seen that in our procedure the computational cost of our procedure is exponential, while in the circumscription case, for languages analogous to ALC, the complexity of the in- stance problem is co-NExpNP ([2, Section 4.1.1]). Closer to our approach is the work by Giordano et al. [18], that is based too on a preferential approach. The conclusions that we can derive using the logic ALC+Tmin are intuitive, but the complexity of the decision problem for the ABox is co-NExpNP ([18, Theorem 13]), and the procedure cannot be reduced to classical entailment. 5 Conclusions We have started from a previous proposal that models Lehmann and Magidor’s Ratio- nal Closure for DLs allowing to reason about defeasible subsumption axioms, and on that we have built a procedure that extends such a kind of reasoning also for ABox information; we have characterized such a procedure also from the semantical point of view. Such a procedure allows to derive intuitive conclusions, the decision procedures are entirely based on a series of classical decision steps. We are actually preparing an implementation of the algorithm, and we are going to define analogous procedures also for other consequence relations, still based on Rational Closure but inferentially more powerful, as Lehmann’s Lexicographic Closure [21]. Acknowledgements This work is based upon research supported by the National Research Foundation (NRF). Any opinion, findings and conclusions or recommendations expressed in this material are those of the authors and therefore the NRF do not accept any liability in regard thereto. This work was partially funded by Project # 247601, Net2: Network for Enabling Networked Knowledge, from the FP7-PEOPLE- 2009-IRSES call. References 1. F. Baader and B. Hollunder. How to prefer more specific defaults in terminological default logic. In Proc. IJCAI, pages 669–674. Morgan Kaufmann Publishers, 1993. 2. P. Bonatti, C. Lutz, and F. Wolter. The complexity of circumscription in description logic. Journal of Artificial Intelligence Research, 35:717–773, 2009. 3. R. Booth, T. Meyer, and I. Varzinczak. PTL: A propositional typicality logic. In Proceedings of the 13th European Conference on Logics in Artificial Intelligence (JELIA), number 7519 in LNCS, pages 107–119. Springer, 2012. 4. R. Booth, T. Meyer, and I. Varzinczak. A propositional typicality logic for extending rational consequence. Accepted, 2013. 5. C. Boutilier. Conditional logics of normality: A modal approach. Artificial Intelligence, 68(1):87–154, 1994. 6. K. Britz, G. Casini, T. Meyer, K. Moodley, and I. Varzinczak. Ordered interpretations and entailment for defeasible description logics. Technical report, CAIR, CSIR Meraka and UKZN, South Africa, 2013. 7. K. Britz, G. Casini, T. Meyer, and I. Varzinczak. Preferential role restrictions. In Proceedings of the 26th International Workshop on Description Logics, 2013. 8. K. Britz, J. Heidema, and T. Meyer. Semantic preferential subsumption. In Proc. KR, pages 476–484. AAAI Press/MIT Press, 2008. 9. K. Britz, T. Meyer, and I. Varzinczak. Preferential reasoning for modal logics. Electronic Notes in Theoretical Computer Science, 278:55–69, 2011. 10. K. Britz, T. Meyer, and I. Varzinczak. Semantic foundation for preferential description log- ics. In Proc. Australasian Joint Conference on AI, number 7106 in LNAI, pages 491–500. Springer, 2011. 11. K. Britz and I. Varzinczak. Defeasible modalities. In Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pages 49–60, 2013. 12. G. Casini and U. Straccia. Defeasible inheritance-based description logics. Submitted work. 13. G. Casini and U. Straccia. Rational closure for defeasible description logics. In Proc. JELIA, number 6341 in LNCS, pages 77–90. Springer-Verlag, 2010. 14. F.M. Donini and F. Massacci. EXPTIME tableaux for ALC. Artificial Intelligence, 124:87– 138, 2000. 15. F.M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation as failure. ACM Transactions on Computational Logic, 3(2):177–225, 2002. 16. P. Gärdenfors and D. Makinson. Nonmonotonic inference based on expectations. Artificial Intelligence, 65(2):197–245, 1994. 17. L. Giordano, N. Olivetti, V. Gliozzi, and G.L. Pozzato. A minimal model semantics for nonmonotonic reasoning. In Proc. JELIA, number 7519 in LNCS, pages 228–241. Springer, 2012. 18. L. Giordano, N. Olivetti, V. Gliozzi, and G.L. Pozzato. A non-monotonic description logic for reasoning about typicality. Artificial Intelligence, 195:165202, 2012. 19. S.O. Hansson. A Textbook of Belief Dynamics: Theory Change and Database Updating. Kluwer Academic Publishers, 1999. 20. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44:167–207, 1990. 21. D. Lehmann. Another perspective on default reasoning. Annals of Mathematics and Artificial Intelligence, 15(1):61–82, 1995. 22. D. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial Intelligence, 55:1–60, 1992. 23. J. Quantz. A preference semantics for defaults in terminological logics. In Proc. KR, pages 294–305, 1992. A Proofs. Proposition 1. Given a knowledge base K = hA, T , Di and a linear order of O, the above procedure determines a rational ABox extension of K. Contrariwise, every ratio- nal ABox extension of K corresponds to the knowledge base generated by some linear order of the individuals in O. Proof. The first statement is quite immediate. For the second statement, assume that there is a rational extension hA0 , T i of hA, T , Di that cannot be generated by any sequence s of the elements of O. A0 associates to every individual x a default concept from ∆, that we indicate as δ x . Assume we have a rational extension hAD , T i of hA, T , Di that can be generated using a sequence of elements of O. The following procedure allows to define a sequence s of the elements of O s.t. hAD , T i can be generated using s, i.e., hAD , T i = hAsD , T i. Take each element of O and associate to it the strongest default concept in ∆ consis- tent with the knowledge base hA, T i (call it γ x ). Look for an individual x s.t. δ x = γ x , and consider x the first element of the sequence s. Update A with δ x (x), and repeat the procedure, until every individual has been associated to a default formula. With this procedure we can generate a sequence over the dominion of the individuals that generates hAD , T i from hA, T , Di. Since there is no sequence s that can generate hA0 , T i, the above procedure has to fail, that is, at some point it will not be possible to associate to any x a default γ x s.t. δ x = γ x . That means that, for all the remaining x, δ x 6= γ x ; for each such x, either δ x  γ x or γ x  δ x . The first case is not possible, since hA0 , T i would be inconsistent (γ x has to be a maximally consistent default). Hence γ x  δ x and δ x 6= γ x for all the remaining x. In such a case, hA0 , T i would not be a rational extension of hAD , T i, since we could have another consistent model with stronger defaults associated to some individuals. Proposition 2. Given K and a linear order s of the individuals in K, the consequence relation `sr satisfies the following properties: (REFDL ) hA, T , ∆i `sr ·C(a) for every C(a) ∈ A Reflexivity hA ∪ {D(b)}, T , Di `sr ·C(a)  D ≡ E (LLEDL ) Left Logical Equivalence hA ∪ {E(b)}, T , Di `sr ·C(a) hA, T , Di `sr ·C(a)  C v D (RWDL ) Right Weakening hA, T , Di `sr ·D(a) hA ∪ {D(b)}, T , Di `sr ·C(a) hA, T , Di `sr ·D(b) (CTDL ) Cautious Transitivity (Cut) hA, T , Di `sr ·C(a) hA, T , Di `sr ·C(a) hA, T , Di `sr ·D(b) (CMDL ) Cautious Monotonicity hA ∪ {D(b)}, T , Di `sr ·C(a) hA ∪ {D(b)}, T , Di `sr ·C(a) hA ∪ {E(b)}, T , Di `sr ·C(a) (ORDL ) Left Disjunction hA ∪ {D t E(b)}, T , ∆i `sr ·C(a) hA, T , Di `sr ·C(a) hA, T , Di 6`sr ·¬D(b) (RMDL ) Rational Monotonicity hA ∪ {D(b)}, T , Di `sr ·C(a) Proof. For REFDL , LLEDL and RWDL the proof is quite immediate. For CTDL and CMDL , assume hA, T , Di `sr D(y), that is hAsD , T i  D(y). Hence, for every δi ∈ ∆ and every individual z ∈ O, δi (z) is consistent with hA, T i iff it is consistent with hA ∪ {D(y)}, T i, and the procedure associates to each individual the same default formula either we start with A or with A∪{D(y)}. So we have that hAsD ∪{D(y)}, T i = h(A∪ {D(y)})sD , T i and hAsD ∪{D(y)}, T i  C(x) iff h(A∪{D(y)})sD , T i  C(x). Since  satisfies CT and CM , we have that hAsD , T i  C(x) iff h(A ∪ {D(y)})sD , T i  C(x), that is, hA, T , Di `sr ·C(x) iff hA ∪ {D(y)}, T , Di `sr ·C(x). For ORDL , assume that hA ∪ {D(y)}, T , Di `sr ·C(x), hA ∪ {E(y)}, T , Di `sr ·C(x), and that y is in the nth position in the sequence s. So, for the first n − 1 elements of s the association with the default-formulae is the same in both the models. For y, assume that the procedure assigns δi (y) in case D(y), and δj (y) in case E(y). We can have δi = δj ,  δi v δj , or  δj v δi . In the first case the procedure for the assignment of the defaults continues in the same way in both the knowledge bases, and is the same also if we have D t E(y), that is, hA ∪ {D(y)}, T , Di, hA ∪ {E(y)}, T , Di, and hA ∪ {D t E(y)}, T , Di are completed exactly with the same defaults, obtaining, respectively, the ABoxes (A ∪ {D(y)})sD = A0 ∪ {D(y)}, (A ∪ {E(y)})sD , = A0 ∪ {E(y)}, and (A ∪ {D t E(y)})sD = A0 ∪ {D t E(y)}, for some ABox A0 . So we have that A0 ∪ {D(y)}  C(x) and A0 ∪ {E(y)}  C(x), and, since  satisfies OR, we obtain A0 ∪ {D t E(y)}  C(x), that is, h(A ∪ {y : D t E})sD , T i  C(x). If δi  δj and D t E(y), the procedure associates to y the strongest of the two defaults, that is, δi . Since δi is not consistent with E(y), in every following consistency check the procedure will be forced to consider that D(y) holds, and the assignment of the defaults to the individuals will proceed as in the case where D(y) holds, and hA ∪ {D t E(y)}, T , Di will entail the same formulae as hA ∪ {D(y)}, T , Di. Analogously, if δj  δi , the default-assumption extension of hA ∪ {D t E(y)}, T , Di will correspond to the one of hA ∪ {E(y)}, T , Di. Finally, for RMDL , D(y) is consistent with hAsD , T i, so the presence of D(y) in the knowledge base does not influence the association of the defaults to the individuals, and AsD ⊆ (A ∪ {D(y)})sD . Eventually, hAsD , T i  C(x) implies h(A ∪ {D(y)})sD , T i  C(x), i.e. hA ∪ {y : D}, T , Di `sr ·C(x). Proposition 3. Deciding hA, T , Di `sr ·C(a) in ALC is an ExpTime-complete problem. Proof. ABox decision in ALC is ExpTime-complete. hA, T , Di is a knowledge base s.t. D is partitioned into D0 , . . . , Dn and in the ABox are named m individuals (|O| = m). Given a sequence s of the individuals in O, to decide if hA, T , Di `sr ·C(a) we need to do for each individual in O at most n ABox consistency checks to decide which default we can associate to that particular individual, and, eventually, once we have associated to each individual the strongest default possible, we have to check if C(a) is a classical consequence of the rational ABox extension. Hence, in the worst case we need (n∗m)+1 classical ALC decision steps, hence the complexity remains ExpTime- complete. Proposition 4. The inference relation `r does not satisfy (RMDL ). Proof. Consider the knowledge base hA, Di s.t. A = {r(a, b)} and D = D0 ∪ D1 , with D0 = {> < < < < ∼ A u ∀r.¬A, > ∼ B} and D1 = {¬A ∼ ¬B, ¬∀r.¬A ∼ B}. We can define 0 two sequences on the individuals, s = ha, bi and s = hb, ai, each of them defining a 0 different rational extension, with `r =`sr ∩ `sr . We have that hA, Di `r B(a), since in 0 both the extensions B(a) holds (in `sr because of the axiom > < ∼ B and in `sr for the 0 axiom ¬∀r.¬A < s ∼ B) while we have hA, Di 6`r A(a), since hA, Di 6`r A(a). However, s hA ∪ {¬A(a)}, Di 6`r B(a), since hA ∪ {¬A(a)}, Di 6`r B(a). Proposition 5. In the presence of a knowledge base hA, T , Di that has a single ra- tional ABox extension, checking the unicity of the rational ABox extension and whether hA, T , Di `sr ·C(a) is an ExpTime-complete problem in ALC. Proof. It works as in Proposition 4. We need at worst n∗m classical decision procedures to associate to each individual a default concept, then another one to check the overall consistency of the new knowledge base, and eventually, in case it is consistent, a last one to decide whether C(a) is a classical consequence of the rational ABox extension just defined. All in all, (n ∗ m) + 2 ExpTime-complete decision procedures. Lemma d d1. A knowledge base hA, T , Di is consistent iff hA, T i 6|= > v ⊥ and 6|= T u D v ⊥. Proof. ⇒: Assume hA, T , Di is consistent i.e. there is a ranked model R = {∆, ≺, ·R } satisfying hA, T , Di. Moreover, assume that hA, T i |= > v ⊥. Clearly cannot be the case. d d Then assume d that hA, d T i 6|= > v ⊥ but |= T u D v ⊥. Hence there is no object x in ∆ s.t. T u D(x) d is satisfied. d Consider o to be one of the minimal objects in R w.r.t. ≺: since R ¬( T u D)(o) there is whether a strict inclusion axiom C v D ∈ T s.t. C u ¬D(o) (impossible, since R is a model of T ) or a defeasible inclusion axiom C < ∼ D ∈ D s.t. C u ¬D(o), and, since o is one of the most preferred objects in R, R cannot be a model of hA,d T , Di.d ⇐: Assumed hA,dT i | 6 = > v ⊥ and | 6 = T u D v ⊥. Then there can be an object o satisfying T u D, and we construct a model of hA, T , Di using such an object in the following way. d Sinced hA, T i 6|= > v ⊥, hA, T i has a model; add to such a model an object o s.t. T u D(o), and add also all the objects which existence is forced by o, and indicate with O the set of all the objects in such a model; impose o ≺ a for every a ∈ O/{o}. Now consider all the axioms C < ∼ D in D. For each of them, do the following. If C u D(o), do nothing, else check if there is some individual satisfying C u ¬D. If there is dno suchd individual, do nothing, otherwise create a new individual o0 s.t. CuD(o0 ), and 0 T u D(o ). The existence of an object satisfying C u D is guaranteed: if 6|= C v ⊥ and 6|= ¬C t D v ⊥, then we have also that 6|= C u D v ⊥. It’s easy to see that that is the case. Assume that 6|= C v ⊥, 6|= ¬C t D v ⊥, but |= C u D v ⊥. It means that |= C v ¬D, that in turn implies that C < < ∼ ⊥ is a preferential consequence of C ∼ D, i.e. C < ∼ D ∈ D ∞ , while we assume D ∞ = ∞. Now define a preference relation in which o is preferred to all the just created indi- viduals o0 , and each o0 is preferred to all the individuals in O/o. If the creation of new individuals is forced by the creation of the individuals o0 , just place them as the less preferred ones. Lemma 2. Let hA, T , Di be a consistent knowledge base. Then there is at least a mini- mal ranked model of hT , Di satisfying A. 0 Proof. Let M = {∆, ≺, ·I } be a minimal ranked model of hT , Di and M0 = {∆0 , ·I } be a model of hA, T i (we assume that ∆ ∩ ∆0 = ∅, otherwise rename the objects appro- priately). Now define a model M∗ where the domain is ∆ ∪ ∆0 and the interpretation 0 is ·I ∪ ·I . About the preference relation, position the individuals from ∆0 according to their ranking w.r.t. hT , Di. This ranked interpretation is hT , Di-compatible, since it is the extension of a hT , Di-compatible ranked interpretation, and it is a minimal model of D that also satisfies A. Proposition 6. Given a knowledge base hA, T , Di, each inference relation `sr defined by a sequence s on the elements of O corresponds to the consequence relation |=≤ h for some h, and the other way around. The inference relation `r , corresponding to the intersection of all `sr generated by hA, T , Di, corresponds to the consequence relation |=≤ . Proof. In the proofs for Section 5 in [6] we prove that, given a knowledge base hT , Di, in the minimal ranked models there is a correspondence between the height of the ob- jects and their ranking, that is, if an object x has a height i, then the model associates to x the default δi . Hence, given all the minimal models of a knowledge base hA, T , Di s.t. all the individuals in O have the same height in each model, i.e., the models defin- ing |=≤ h , we take under consideration all the models that associate to each individual x ∈ O a specific default concept δi , s.t. it is not possible to associate a stronger de- fault to each of them. This corresponds to the notion of rational ABox extension that, by Proposition 1, corresponds to the inference relation `sr generated by some sequence s. In the other direction, given a knowledge base hA, T , Di and an inference relation `sr , it corresponds to a rational ABox extension of hA, T , Di, and we can define the corresponding class of minimal models using the procedure in Lemma 2. The correspondence between `r and |=≤ is an immediate consequence. Proposition 7 hA, T , Di `r ·C(a) iff hA[a] , T , Di `sr ·C(a) for every ordering s of the individuals in A[a] . Proof. Assume hA[a] , T , Di 6`sr ·C(a) for some s. Let s0 be a sequence of the individ- 0 uals named in A obtained using s as initial segment. Hence we have that hA, T , Di 6`sr ·C(a), that implies hA, T , Di 6`r ·C(a). Now assume hA, T , Di 6`r ·C(a). Hence, for some sequence s, hA, T , Di 6`sr ·C(a). Let s0 be a restriction of s to the individuals named in A[a] ; then we have that 0 hA, T , Di 6`sr ·C(a).