The preferential and rational consequence relations rst studied by Lehmann and colleagues play a central role in non-monotonic reasoning, not least because they provide the foundation for the determination of the important notion of rational closure. Although they can be applied directly to a large variety of logics, these constructions suffer from the limitation that they are largely propositional in nature. One of the main obstacles in moving beyond the propositional case has been the lack of a formal semantics which appropriately generalizes the preferential and ranked models of Lehmann et al. In this paper we propose a semantics to ll that gap for description logics, an important class of decidable fragments of rst-order logic. Our semantics replaces the propositional valuations used in the models of Lehmann et al. with structures we refer to as concept models. We prove representation results for the description logic ALC for both preferential and rational consequence relations. We argue that our semantics paves the way for extending preferential and rational consequence, and therefore also rational closure, to a whole class of logics that have a semantics de ned in terms of rst-order relational structures.
There has by now been quite a substantial number of attempts to incorporate
defeasible reasoning in logics other than propositional logic. One such endeavor,
and the broad focus of this paper, has been to extend the in uential version
of preferential reasoning rst studied by Lehmann et al. [
The central question answered in this paper is how the existing semantics for both preferential and rational propositional non-monotonic consequence relations should be generalized to languages with more structure, and in particular, to ALC. Speci cally, what is the meaning of a preferential (or rational) subsumption statement C @ D | what properties should it have, and what is its corresponding formal semantics? The main results of this paper, and our answers to these questions, are the two representation results presented in Theorems 3 and 4, respectively. Key to the establishment of these results are the notions of a concept model, which gives a reading of the meaning of concepts suitable for our purposes, and a DL preferential model, giving meaning to non-monotonic subsumption statements. The latter generalizes the notion of a propositional preferential model in terms of concept models.
The rest of the paper is structured as follows. In Section 2 we give a brief account of the work on preferential and rational subsumption for the propositional case as developed by Lehmann and colleagues. Section 3 is the heart of the paper in which we de ne the semantics for both preferential and rational subsumption for ALC and prove representation results for both. Importantly, the representation results provided here are with respect to the corresponding propositional properties. From this we conclude that the semantics we present here forms the foundation of a semantics for preferential and rational consequence for a whole class of DLs and related logics and provides a natural and intuitive semantic framework on which to base such work. In Section 4 we use the fundamental results of the previous section to show that the notions of propositional preferential entailment and rational closure can be `lifted' to the case for DLs, speci cally ALC. In Section 5 we discuss related results. We conclude with Section 6 in which we also discuss future work.
We assume that the reader is familiar with description logics. For more details
on description logics in general, and the description logic ALC in particular, the
reader is referred to the DL handbook [
In this section we give a brief introduction to propositional preferential and
rational consequence, as initially de ned by Kraus et al. [
The semantics of (propositional) preferential consequence relations is in terms
of preferential models ; these are partially ordered structures with states labeled
by propositional valuations. We shall make this terminology more precise in
Section 3, but it essentially allows for a partial order on states, with states
lower down in the order being more preferred than those higher up. Given a
preferential model P, a pair j is in the consequence relation de ned by P
i the minimal states (according to the partial order) of all those states labeled
by valuations that are propositional models of , are also labeled by propositional
models of . The representation theorem for preferential consequence relations
then states:
Theorem 1 (Kraus et al. [
6j : ^ j
The semantics of rational consequence relations is in terms of ranked preferential models, i.e., preferential models in which the preference order is modular : De nition 1. Given a set S, S S is modular i is a partial order on S, and there is a ranking function rk : S 7! N s.t. for every s; s0 2 S, s s0 i rk(s) < rk(s0).
The representation theorem for rational consequence relations then states:
Theorem 2 (Lehmann and Magidor [
It has been argued elsewhere that description logics are ideal candidates for the
extension of propositional preferential consequence since the notion of
subsumption in DLs lends itself naturally to defeasibility [
De nition 2. A subsumption relation @ L L is a preferential subsumption relation i it satis es the properties (Ref ), (LLE), (And), (RW), (Or), and (CM), with propositional entailment replaced by classical DL subsumption. @ is a rational subsumption relation i in addition to being a preferential subsumption relation, it also satis es the property (RM).
However, up until now it has not been clear how to best generalize the
propositional semantics for the DL case. Since DLs have a standard rst-order
semantics, the obvious generalization from a technical perspective is to replace the
propositional valuations in preferential models with rst-order interpretations.
Intuitively, this also turns out to be a natural generalization of the
propositional setting, with the notion of normal rst-order interpretation characterizing
a given concept replacing the propositional notion of normal worlds satisfying a
given proposition. Formally, our semantics is based on the notion of a concept
model, which is analogous to that of a Kripke model in modal logic [
Observe that the valuation function V can be viewed as a propositional valuation with propositional atoms replaced by concept names. From the de nition of satisfaction in a concept model below it is then clear that, within the context of a concept model, a world occurring in that concept model is a proper generalization of a propositional valuation.
De nition 4 (Satisfaction). Given M = hW; R; Vi and w 2 W: M ; w M ; w M ; w M ; w M ; w >; A i A 2 V(w); C u D i M ; w C and M ; w D; :C i M ; w 6 C; 9ri:C i there is w0 2 W s.t. (w; w0) 2 Ri and M ; w0
Let U denote the set of all pairs (M ; w) where M = hW; R; Vi is a concept model and w 2 W.
Worlds are, loosely speaking, interpreted DL objects. And while this
correspondence holds technically (from the correspondence between ALC and
multimodal logic K [
Let S be a set, the elements of which are called states. Let ` : S 7! U be a labeling function mapping every state to a pair (M ; w) where M = hW; R; Vi is a concept model s.t. w 2 W. Let be a binary relation on S. Given C 2 L, we say that s 2 S satis es C (written s j C) i `(s) C, i.e., M ; w C. We de ne Cb = fs 2 S j s j Cg. Cb is smooth i each s 2 Cb is either -minimal in Cb, or there is s0 2 Cb s.t. s0 s and s0 is -minimal in Cb. We say that S satis es the smoothness condition i for every C 2 L, Cb is smooth.
We are now ready for our de nition of preferential model.
De nition 5 (Preferential Model). A preferential model is a triple P = hS; `; i where S is a set of states satisfying the smoothness condition, ` is a labeling function mapping states to elements of U , and is a strict partial order on S, i.e., is irre exive and transitive.
These formal constructions closely resemble those of Kraus et al. [
De nition 6 (Preferential Subsumption). Given concepts C; D 2 L and a preferential model P = hS; `; i, we say that C is preferentially subsumed by D in P (denoted C @ P D) i every -minimal state s 2 Cb is s.t. s 2 Db .
We are now in a position to prove one of the central results of this paper. Theorem 3. A defeasible subsumption relation is a preferential subsumption relation i it is de ned by some preferential model.
The signi cance of this is that the representation result is proved with respect to the same set of properties used to characterize propositional preferential consequence. We therefore argue that preferential models, as we have de ned them, provide the foundation for a semantics for preferential (and rational) subsumption for a whole class of DLs and related logics. We do not claim that this is the appropriate notion of preferential subsumption for ALC, but rather that it describes the basic framework within which to investigate such a notion.
In order to obtain a similar result for rational subsumption, we restrict ourselves to those preferential models in which is a modular order on states (cf. De nition 1): De nition 7 (Ranked Model). A ranked model Pr is a preferential model hS; `; i in which is modular.
Since ranked models are preferential models, the notion of rational subsumption is as in De nition 6. We can then state the following result: Theorem 4. A defeasible subsumption relation is a rational subsumption relation i it is de ned by some ranked model.
One of the primary reasons for de ning non-monotonic consequence relations of the kind we have presented above is to get at a notion of defeasible entailment : Given a set of subsumption statements of the form C @ D or C v D, which other subsumption statements, defeasible and classical, should one be able to derive from this? It can be shown that classical subsumption statements of the form C v D can be encoded as defeasible subsumption statements of the form C u :D @ ?. For the remainder of this paper we shall therefore concern ourselves only with nite sets of defeasible subsumption statements, and refer to these as defeasible TBoxes, denoted T . We permit ourselves the freedom to include classical subsumption statements of the form C v D in a defeasible TBox, with the understanding that it is an encoding of the defeasible subsumption statement C u :D @ ?.
Our aim in this section is to show that the results for the propositional
case [
The version of rational closure de ned here provides us with a strict generalization of classical entailment for ALC TBoxes in which the expressivity of ALC is enriched with the ability to make defeasible subsumption statements. For example, consider the defeasible ALC TBox:
Armed with the notion of a preferential model (cf. Section 3) we de ne preferential entailment for ALC as follows.
Firstly, we can show that preferential entailment is well-behaved and coincides with preferential closure under the properties of preferential subsumption (i.e., the intersection of all preferential subsumption relations containing a defeasible TBox). More precisely, let T be a defeasible TBox. Then the set of defeasible subsumption statements preferentially entailed by T , viewed as a binary relation on concepts, is a preferential subsumption relation. Furthermore, a defeasible subsumption statement is preferentially entailed by T i it is in the preferential closure of T .
From this it follows that if we use preferential entailment, the meningitis example can be formalized by letting T = fBM v M V M v M , M @ :F; BM @ :F g. However, V M @ :F is not preferentially entailed by T above (we cannot conclude that viral meningitis is usually not fatal) and preferential entailment is thus generally too weak. We therefore move to rational subsumption relations.
The rst attempt to do so is to use a de nition similar to that employed for preferential entailment: C @ D is rationally entailed by a defeasible TBox T i for every ranked model Pr in which E @ Pr F for every E @ F 2 T , it is also the case that C @ Pr D. However, this turns out to be exactly equivalent to preferential entailment. Therefore, if the set of defeasible subsumption statements obtained as such is viewed as a binary relation on concepts, the result is a preferential subsumption relation and is not, in general, a rational consequence relation.
The above attempt to de ne rational entailment is thus not acceptable. Instead, in order to arrive at an appropriate notion of (rational) entailment we rst de ne a preference ordering on rational subsumption relations, with relations further down in the ordering interpreted as more preferred.
Lemma 1. Let T be a ( nite) defeasible TBox and let R be the class of all rational subsumption relations which include T . There is a unique rational subsumption relation in R which is preferable to all other elements of R w.r.t. .
This puts us in a position to de ne an appropriate form of (rational) entailment for defeasible TBoxes: De nition 10. Let T be a defeasible TBox. The rational closure of T is the (unique) rational subsumption relation which includes T and is preferable (w.r.t. ) to all other rational subsumption relations including T .
It can be shown that V M @ :F is in the rational closure of T (we can conclude viral meningitis is usually not fatal), but that neither F u M @ BM nor F u M @ :BM is.
We conclude this section with a result which can be used to de ne an algorithm for computing the rational closure of a defeasible TBox T . For this we rst need to de ne a ranking of concepts w.r.t. T which, in turn, is based on a notion of exceptionality. A concept C is said to be exceptional for a defeasible TBox T i T preferentially entails > @ :C. A defeasible subsumption statement C @ D is exceptional for T if and only if its antecedent C is exceptional for T .
It turns out that checking for exceptionality can be reduced to classical subsumption checking.
Lemma 2. Given a defeasible TBox T , let T v be its classical counterpart in which every defeasible subsumption statement of the form D @ E in T is replaced by D v E. C is exceptional for T i > v :C is classically entailed by T v.
Let E(T ) denote the subset of T containing statements that are exceptional for T . We de ne a non-increasing sequence of subsets of T as follows: E0 = T , and for i > 0, Ei = E(Ei 1). Clearly there is a smallest integer k s.t. for all j k, Ej = Ej+1. From this we de ne the rank of a concept w.r.t. T : rT (C) = k i, where i is the smallest integer s.t. C is not exceptional for Ei. If C is exceptional for Ek (and therefore exceptional for all E s), then rT (C) = 0. Intuitively, the lower the rank of a concept, the more exceptional it is w.r.t. the TBox T . Theorem 5. Let T be a defeasible TBox. The rational closure of T is the set of defeasible subsumption statements C @ D s.t. either rT (C) > rT (C u :D), or rT (C) = 0 (in which case rT (C u :D) = 0 as well).
From this result it is easy to construct a (nave) decidable algorithm to
determine whether a given defeasible subsumption statement is in the rational closure
of a defeasible TBox T . Also, if checking for exceptionality is assumed to take
constant time, the algorithm is quadratic in the size of T . Given that
exceptionality reduces to subsumption checking in ALC which is ExpTime-complete,
it immediately follows that checking whether a given defeasible subsumption
statement is in the rational closure of T is an ExpTime-complete problem. This
result is closely related to a result by Casini et al. [
Quantz and Ryan [
Q-preferential entailment is concerned with what ought to follow from a set of classical DL statements, together with a set of default subsumption statements, and is parameterised by a xed partial order on (simpli ed) DL interpretations. They prove that any Q-preferential entailment satis es the properties of a preferential consequence relation and, with some restrictions on the partial order, satis es Rational Monotony as well. Q-preferential entailment can therefore be viewed as something in between the notions of preferential consequence and preferential entailment we have de ned for DLs. It is also worth noting that although the Q-preferential entailments satisfy the properties of a preferential consequence relation, Quantz and Ryan do not prove that Q-preferential entailment provides a characterisation of preferential consequence.
Britz et al. [
Casini and Straccia [
The main contribution of this paper is the provision of a natural and intuitive formal semantics for preferential and rational subsumption for the description logic ALC. We claim that our semantics provides the foundation for extending preferential reasoning in at least three ways. Firstly, as we have seen in Section 4, it allows for the `lifting' of preferential entailment and rational closure from the propositional case to the case for ALC. Without the semantics such a lifting may be possible in principle, but will be very hard to prove formally. Secondly, it paves the way for de ning similar results for other DLs, as well as other similarly structured logics, such as logics of action and belief. We are at present investigating similar notions for logics of action. And thirdly, it provides the tools to tighten up the versions of preferential and rational subsumption for ALC presented in this paper in order to truly move beyond the propositional. The latter point is the obvious one to pursue rst when it comes to future work. Below we provide some initial ideas on moving beyond propositional properties. The value added by the semantics is the ability it provides to test whether appropriate constraints on the orderings in ranked models can be found that matches the new properties.
Consider the following defeasible TBox, which is a slightly modi ed version of our previous meningitis example: where BM , M , and F are as before, and cm abbreviates the role causaMortis. The last statement encodes the classical subsumption statement that all causes of death are fatal.
It is easily veri ed that 9pc:BM v 9pc:M is in the rational closure of T (where pc abbreviates the role potentiallyCauses ), and so it should be since it is entailed by BM v M . We would also expect to conclude 9pc:M @ 9pc::F from T since it contains M @ :F . However, there is no propositional property to guarantee the latter. This prompts us to consider the following property:
(Nave Role Introduction)
Arguably, then, if meningitis is usually non-fatal, then potential causes of meningitis are usually potential causes of something non-fatal.
But there are problems with this reasoning. The following example makes this explicit: From M @ :F , Nave Role Introduction also allows us to conclude that 9cm:M @ 9cm::F . So usually, fatal cases of meningitis are fatal cases of something non-fatal. This is clearly counter-intuitive. Intuitively, cm usually relates to an abnormal type of meningitis, such as bacterial meningitis, which is usually fatal. An additional blocking mechanism is therefore needed to prevent the rule from being applied when the entire range of the role r is abnormal with respect to C. In order to provide such a mechanism, we need to go beyond ALC, and include the ability to express role inverses.3 We then have the following Role Introduction property: (RI)
The e ect of the premise C 6 @ 8r :? is to block application of the rule if C is normally disjoint from the range of r. On the other hand, if normally C overlaps with the range of r, it follows that 9r:C @ 9r:D. 3 Given a role name r, the role inverse of r is denoted by r . For an interpretation I, (r )I = f(y; x) j (x; y) 2 rI g.
Now consider again the example above. The intention of role cm is modeled by > v 8cm:F , the intuition being that only something fatal can be the cause of death. It then follows classically that :F v 8cm :?, and by (RW) that M @ 8cm :?. This property (RI) is therefore blocked for the statement M @ :F . Note that (RI) applied to pc is not blocked, as we do not have that M @ 8pc :?. (RI) applied to cm is also not blocked for BM @ F . The interesting thing about (RI) is that it does not hold for the preferential closure of a TBox, whereas it does hold for the rational closure.
This illustrates that there are intuitively appealing properties characterizing rational DL-entailment that merit further investigation.