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.
In the last years it has become apparent the need for the introduction of forms of
uncertain 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
reasoning. Indeed, there have been various proposals for the introduction of non-monotonic
reasoning in DLs and similarly structured logics, mostly ranging from preferential
approaches [
The preferential approach, that has been formalized for the propositional languages
mainly in the 90’s [
In what follows we are going to present the adaptation for the ABox of a
classical nonmonotonic form of reasoning, Lehmann and Magidor’s Rational Closure.
Elsewhere [
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 j :C j C u C j 9r:C j >. Concepts built with the constructors t and 8, 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 2 NC into subsets AI of I , and mapping role names r 2 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 following way: (:C)I = I n CI , (C u D)I = CI \ DI , and (9r:C)I = fx 2 I j for some y; (x; y) 2 rI and y 2 CI g.
Given C; D 2 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 CI DI . C v D is (classically) entailed by a TBox T , denoted T j= 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 2 T . An ABox A is a set of assertions about individuals. Let D be a set of individuals fa; b; c; : : :g, that are interpreted in h I ; I i as elements of the domain I , i.e. aI 2 I . The admissible assertions in ALC have the form C(a) and r(a; b), where I C(a) if and only if aI 2 CI and I r(a; b) if and only if haI ; bI i 2 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
concept D’ [
Step 1. Let D (resp., T ) be the set containing the materializations of the axioms in D (resp., T ), i.e. D = f:C t D j C < D 2 Dg (resp., T = f:C t D j C v D 2 T g); 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
j= l T u l 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 function E that gives back the exceptional axioms in D (E(D) = fC < D j j= d T u d D v :Cg).1 Given hT ; Di we can construct a sequence E0; E1; : : : starting with E0 = 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: r(C < D) = i if C < D 2 Ei and C < D 2= Ei+1 1 if C < D 2 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; D1, for some n, and with D1 possibly empty. It is possible to define a new knowledge base hT 0; D0i, with T 0 = T [fC v D j C < D 2 D1g and D0 = D=D1. The only difference between hT ; Di and hT 0; D0i 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 1 as ranking value. We shall indicate with i the default concept obtained from the conjunction of all the materializations of rank i or higher ( i = d(Si 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 iff j= d T 0 u i u C v D, where i is the first element of the sequence h 0; : : : ; ni s.t. 6j= d T 0 u i v :C; if there is no such element, hT ; Di `rat C < D iff j= d 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
characterizing 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 [
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. [
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 2 X, x y iff rk(x) < rk(y).
Definition 2 (Ranked Interpretation). A ranked interpretation is a structure R = h R; R; Ri, where h R; Ri is a DL interpretation (which we denote by IR), and R is a modular order on R satisfying the smoothness condition (for every C 2 L, min R (CR) 6= ;).
As in the propositional case [
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 2 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 j=R the consequence relation defined in the classical way using all the ranked models of hT ; Di, that is, hT ; Di j=R C < D if and only if C < D is satisfied in all the ranked models satisfying hT ; Di.
compatible if and only if hT ; Di 6j=R C < ? for every C 2 L s.t. x 2 CI . 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 2 L, x 2 CI iff y 2 CJ . 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 interpretations R; R0 2 RhI;hT ;Dii, R I R0 iff for every x 2 I hR(x) hR0 (x). Based on such an ordering of the interpretations, we can define the consequence relation . R
if R C < D, where R is the I -minimum ranked interpretation of some hT ; Dicompatible interpretation I. If hT ; Di is unsatisfiable then every defeasible subsumption statement C < D is in the ranked entailment of hT ; Di.
Such a consequence relation corresponds to `rat. tion C < D, hT ; Di `rat C < D iff hT ; Di
C < D. R 3
Here we consider the extension of the above procedure to knowledge bases
containing also an ABox: given information about particular individuals, we want to derive
what presumably holds about such individuals. Our knowledge base will have a
classical 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
presumably falls under the concept C. A first attempt for this kind of procedure is presented
in [
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, D1 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 axioms, i.e. the sets Di and the default concepts i.
Hence, given D = SfD0; : : : ; Dng, we end up with the sequence of default concepts = h 0; : : : ; ni, as specified in Section 2 at the Step 2 of the Rational Closure procedure. It is easy to see that i j= i+1 for 1 i n, and we want to be able to associate to each individual a 2 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 Ke = 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 D1 = ;), 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 2 O, C(a) 2 AD n A iff C = i for some i and for every h, h < i, hT ; AD [ f h(a)gi j= ?
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 = fr(a; b)g and D = D0 = f> < A u 8R::Ag (hence we have = h 0i = hA u 8r::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]
AD = AD [ f i(aj )g.
j = j + 1 – Consider the set S of all the linear orders of the individuals in O; – For each s = ha1; : : : ; ami in S do:
Set j = 1 Set AD = A Repeat until j = m + 1:
such that hAD [ f i(aj )g; T gi 6j= > v ?.
return hAsD; T i
Hence, the procedure returns a knowledge base hAsD; T i for each s 2 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 rational 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 `rs C(a)’, iff hAD s ; T i is the rational extension generated from K using the s ; T i j= C(a), where hAD 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.
relation `rs satisfies the following properties:
Example 2. We define a DL-variation of the penguin example. Let K = fA; T ; Dg be a knowledge base where A = fP (a); B(b); Hunt(a; c); Hunt(b; c)g, T = fP v B; I v :F ig, D = fB < F; P < :F; B < 8Hunt:I; P < 8Hunt:F ig, 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 8Hunt:I) u (:P t :F ) u (:P t 8Hunt:F i) and 1 = (:P t :F ) u (:P t 8Hunt: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.
`rs has the same complexity result of the classical ABox consistency decision problem
in ALC [
s Proposition 3. Deciding hA; T ; Di `r lem.
In the presence of multiple rational ABox extensions, we can also define the inference relation `r, a more conservative inference relation independent from any order s on the individuals, that corresponds to the intersection of all the inference relations `r modeling a rational extension.
`r=
\f`rsj s is a linear order on the elements of Og
However, there is the possibility that we lose the property of rational monotonicity.
The computational complexity of `r is the same as `rs, i.e., the decision procedure is ExpTime-complete: assuming that the number of individuals named in the ABox is n, we have to decide `rs 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 (probably 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 individual 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.
tional ABox extension, checking the uniqueness of the rational ABox extension and whether hA; T ; Di `rs C(a) is an ExpTime-complete problem in ALC. Example 3. Consider the KB in Example 2, where in A H unt(b; c) is replaced with H unt(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 extension. 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.
Lemma 1. A knowledge base hA; T ; Di is consistent iff hA; T i 6j= ? and 6j= d T u d 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.
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 RhR=0 (faI0 ) for each object a in O. The minimal ABox models of hA; T ; Di ; ; Rg and R0 = f ; 0; Rg (note that IR = IR0 ), R A R0 iff hR(aI ) are the minimal elements of the order A.
Definition 7 (Minimal ABox model). R = f ; ; Rg 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 = f ; 0; Rg 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 with MhhA;T ;Di 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 j=h as hA; T ; Di j=h C(a) iff M
C(a) for each M 2 MhhA;T ;Di and we indicate with j= the consequence relation defined by all the minimal ABox models of hA; T ; Di.
hA; T ; Di j=
C(a) iff M
C(a) for each M 2 M hA;T ;Di;
There is a correspondence between the inference relations `rs and `r and, respectively, the consequence relations j=h and j= .
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 individual 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 individuals 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 transitive closure of all the roles in our vocabulary, i.e., the symmetric and transitive closure of S R, and with Q the set of the pairs of individuals named in A that are connected by Q.
an individual a 2 O, we call the cluster of a the set [a] of the individuals connected to a through Q.
[a] = fb 2 O j Q(a; b)g
Hence, in order to know what we can presumably conclude about a, it is sufficient to determine `rs 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].
the individuals in A[a].
If we have a query about an individual a s.t. a is not named in the ABox (a 62 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 62 O, we can derive that presumably C(a) holds iff hAa; T i j= C(a), where Aa = A [ f 0(a)g. 4
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. [
The proposal by Bonatti et al. [
Closer to our approach is the work by Giordano et al. [
We have started from a previous proposal that models Lehmann and Magidor’s
Rational 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 [
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.
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 rational 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 consistent 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 `rs satisfies the following properties: Proof. For REFDL, LLEDL and RWDL the proof is quite immediate. For CTDL and CMDL, assume hA; T ; Di `rs D(y), that is hAsD; T i D(y). Hence, for every i 2 and every individual z 2 O, i(z) is consistent with hA; T i iff it is consistent with hA [ fD(y)g; T i, and the procedure associates to each individual the same default formula s either we start with A or with A [ fD(y)gC. (Sxo)wifef hh(aAve[tfhDat (hyA)gD)[sDf;TDi(y)g; T i = h(A [ fD(y)g)sD; T i and hAsD [fD(y)g; T i C(x). Since satisfies CT and CM , we have that hAsD; T i C(x) iff h(A [ fD(y)g)sD; T i C(x), that is, hA; T ; Di `rs C(x) iff hA [ fD(y)g; T ; Di `rs C(x).
For ORDL, assume that hA [ fD(y)g; T ; Di `rs C(x), hA [ fE(y)g; T ; Di `rs 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 [ fD(y)g; T ; Di, hA [ fE(y)g; T ; Di, and hA [ fD t E(y)g; T ; Di are completed exactly with the same defaults, obtaining, s = A0 [ fD(y)g, (A [ fE(y)g)s ; = A0 [ rfeEsp(eyc)tgiv,ealnyd, t(hAe A[BfoDxets (EA(y[)gf)DsD(y=)gA)D0 [ fD t E(y)g, for some ABox DA0. So we have that A0 [ fD(y)g C(x) and A0 [ fE(y)g C(x), and, since satisfies OR, we obtain A0 [ fD t E(y)g C(x), that is, h(A [ fy : D t Eg)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 [ fD t E(y)g; T ; Di will entail the same formulae as hA [ fD(y)g; T ; Di. Analogously, if j i, the default-assumption extension of hA [ fD t E(y)g; T ; Di will correspond to the one of hA [ fE(y)g; T ; Di. s ; T i, so the presence of D(y) in the
Finally, for RMDL, D(y) is consistent with hAD knowledge base does not influence the association of the defaults to the individuals, and AsD (A [ fD(y)g)sD. Eventually, hAsD; T i C(x) implies h(A [ fD(y)g)sD; T i C(x), i.e. hA [ fy : Dg; T ; Di `rs C(x).
s
Proposition 3. Deciding hA; T ; Di `r 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 (jOj = m). Given a sequence s of the individuals in O, to decide if hA; T ; Di `rs 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 ExpTimecomplete.
Proof. Consider the knowledge base hA; Di s.t. A = fr(a; b)g and D = D0 [ D1, with D0 = f> < A u 8r::A; > < Bg and D1 = f:A < :B; :8r::A < Bg. We can define two sequences on the individuals, s = ha; bi and s0 = hb; ai, each of them defining a different rational extension, with `r=`rs \ `rs0 . We have that hA; Di `r B(a), since in both the extensions B(a) holds (in `rs because of the axiom > < B and in `rs0 for the axiom :8r::A < B) while we have hA; Di 6`r A(a), since hA; Di 6`rs0 A(a). However, hA [ f:A(a)g; Di 6`r B(a), since hA [ f:A(a)g; Di 6`rs B(a).
tional ABox extension, checking the unicity of the rational ABox extension and whether hA; T ; Di `rs 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 1. A knowledge base hA; T ; Di is consistent iff hA; T i 6j= d T u d D v ?. > v ? and 6j= Proof. ): Assume hA; T ; Di is consistent i.e. there is a ranked model R = f ; ; Rg satisfying hA; T ; Di. Moreover, assume that hA; T i j= > v ?. Clearly cannot be the case.
Then assume that hA; T i 6j= > v ? but j= d T u d D v ?. Hence there is no object x in s.t. d T u d D(x) is satisfied. Consider o to be one of the minimal objects in R w.r.t. : since R :(d T u d D)(o) there is whether a strict inclusion axiom C v D 2 T s.t. C u :D(o) (impossible, since R is a model of T ) or a defeasible inclusion axiom C < D 2 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; T ; Di.
(: Assume hA; T i 6j= > v ? and 6j= d T u d D v ?. Then there can be an object o satisfying d T u d D, and we construct a model of hA; T ; Di using such an object in the following way. Since hA; T i 6j= > v ?, hA; T i has a model; add to such a model an object o s.t. d T u d 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 2 O=fog.
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 no such individual, do nothing, otherwise create a new individual o0 s.t. C uD(o0), and d T u d D(o0). The existence of an object satisfying C u D is guaranteed: if 6j= C v ? and 6j= :C t D v ?, then we have also that 6j= C u D v ?. It’s easy to see that that is the case. Assume that 6j= C v ?, 6j= :C t D v ?, but j= C u D v ?. It means that j= C v :D, that in turn implies that C < ? is a preferential consequence of C < D, i.e. C < D 2 D1, while we assume D1 = 1.
Now define a preference relation in which o is preferred to all the just created individuals 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.
Proof. Let M = f ; ; I g be a minimal ranked model of hT ; Di and M0 = f 0; I0 g be a model of hA; T i (we assume that \ 0 = ;, otherwise rename the objects appropriately). Now define a model M where the domain is [ 0 and the interpretation is I [ I0 . 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.
by a sequence s on the elements of O corresponds to the consequence relation j=h for some h, and the other way around. The inference relation `r, corresponding to the intersection of all `rs generated by hA; T ; Di, corresponds to the consequence relation j= .
Proof. In the proofs for Section 5 in [
The correspondence between `r and j= is an immediate consequence.
the individuals in A[a].
Proof. Assume hA[a]; T ; Di 6`rs C(a) for some s. Let s0 be a sequence of the individuals named in A obtained using s as initial segment. Hence we have that hA; T ; Di 6`rs0 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`rs C(a). Let s0 be a restriction of s to the individuals named in A[a]; then we have that hA; T ; Di 6`rs0 C(a).