We provide a semantical reconstruction of rational closure. We first consider rational closure as defined by Lehman and Magidor for propositional logic, and we provide a semantical characterization based on minimal models mechanism on rational models. Then, we extend the whole formalism and semantics to Description Logics focusing our attention to the standard ALC: we first naturally adapt to Description Logics Lehman and Magidor's propositional rational closure, starting from an extension of ALC with a typicality operator T that selects the most typical instances of a concept C (hence T(C) stands for typical Cs). Then, we provide for ALC plus T a semantical characterization similar to the one for propositional logic. Last, we extend the notion of rational closure to the ABox.
the properties of R, on the other hand it allows to perform some truthful non-monotonic
inferences, like the one just mentioned (monday ∧ shines |∼ go work). In [
The first problem we tackle in this work is that of giving a purely semantic characterization of the syntactic notion of rational closure. Our semantic characterization has as its main ingredient the modal semantics of logic R, over which we build a minimal models’ mechanism, based on the minimization of the rank of worlds. Intuitively, we prefer the models that minimize the rank of domain elements: the lower the rank of a world, the more normal (or less exceptional) is the world and our minimization corresponds intuitively to the idea of minimizing less-plausible worlds (or maximizing most plausible ones). We show that a semantic reconstruction of rational closure can be given in terms of a specific case of a general semantic framework for non-monotonic reasoning.
In the second part of the paper we consider Description Logics (DLs for short). A
large amount of discussion has recently been done in order to extend the basic
formalism of DLs with non-monotonic reasoning features [
We here extend to ALC the definition of rational closure by Lehmann and Magidor
[
Last, we tackle the problem of extending rational closure to ABox reasoning: in order to ascribe defeasible properties to individuals we maximize their typicality. This is done by minimizing their ranks (that is, their level of exceptionality). Because of the interaction between individuals (due to roles) it is not possible to separately assign a unique minimal rank to each individual and alternative minimal ranks must be considered. We end up with a kind of skeptical inference with respect to the ABox.
The rational closure construction that we propose has not just a theoretical interest
and a simple minimal model semantics, we show that it is also feasible. Its complexity is
EXPTIME in the size of the knowledge base (and the query), the same complexity as
the underlying logic ALC. In this respect it is less complex than other approaches to
non-monotonic reasoning in DLs [
The language of logic R consists just of conditional assertions A |∼ B. Here we consider a richer language which also allows boolean combinations of assertions. Our language L is defined from a set of propositional variablesATM , the boolean connectives and the conditional operator |∼. We assume that the set ATM is finite. We useA, B, C, . . . to denote propositional formulas (that do not contain conditional formulas), whereas F, G, . . . are used to denote all formulas (including conditionals). The formulas of L are defined as follows: ifA is a propositional formula, A ∈ L; if A and B are propositional formulas, A |∼ B ∈ L; if F is a boolean combination of formulas of L, F ∈ L. A knowledge base K is any set of formulas: in this work we restrict our attention to finite knowledge bases.
Here is the axiomatization of logic R [
The logic R enjoys a simple modal semantics, actually it turns out that it is the flat fragment (i.e. without nested conditionals) of the well-known conditional logic VC. The modal semantics is defined by considering a set of worldsW equipped by an accessibility (or preference) relation <. Intuitively the meaning of x < y is that x is more normal/less exceptional than y. We say that a conditional A |∼ B is true in a model if B holds in all most normal worlds where A is true, i.e. in all <-minimal worlds satisfying A. Definition 1. A rational model is a triple M = hW, <, V i where: • W is a non-empty set of worlds; • < is an irreflexive, transitive relation on W satisfying modularity: for all x, y, z, if x < y then either x < z or z < y. < further satisfies the Smoothness condition defined below;• V is a function V : W 7−→ 2ATM , which assigns to every world w the set of atoms holding in that world. If F is a boolean combination of formulas, its truth conditions (M, w |= F ) are defined as for propositional logic. LetA be a propositional formula; we defineMin<M(A) = {w ∈ W | M, w |= A and ∀w0, w0 < w implies M, w0 6|= A}. Hence M, w |= A |∼ B if for all w0, if w0 ∈ Min<M(A) then M, w0 |= B.
We define theSmoothness condition: if M, w |= A, then w ∈ Min<M(A) or there is w0 ∈ Min<M(A) s.t. w0 < w. Validity and satisfiability of a formula are defined as usual. Given a set of formulas K of L and a model M = hW, <, V i, we say that M is a model of K, written M |= K, if for every F ∈ K and every w ∈ W, M, w |= F . K rationally entails a formula F (K |= F ) if F is valid in all rational models of K.
Since in this work we limit our attention to a language containing finitely many atoms, and to finite knowledge bases, we can restrict our attention to finite models, as the logic enjoys the finite model property (observe that in this case the smoothness condition is ensured trivially by the irreflexivity of the <). It is easy to see from Definition 1 that the truth condition of A |∼ B is “global” in a model M = hW, <, V i: given a world w, we have that M, w |= A |∼ B if, for all w0, if w0 ∈ Min<M(A) then M, w0 |= B. It immediately follows that A |∼ B holds in w if and only if A |∼ B is valid in a model, i.e. it holds that M, w0 |= A |∼ B, for all w0 in W; for this reason we will often write M |= A |∼ B. Moreover, when the reference to the model M is unambiguous, we will simply write Min<(A) instead of Min<M(A).
Rational models can be equivalently defined by postulating the existence of a rank function k : W → N, and then letting x < y iff k(x) < k(y). For this reason rational models are also called “ranked models”.
Definition 2 (Rank of a world). Given a model M = hW, <, V i, the rank kM of a world w ∈ W, written kM(w), is the length of the longest chain w0 < · · · < w from w to a minimal w0 (i.e. there is no w0 such that w0 < w0).
i = min{kM(w) : M, w |= F }. If there is no w : M, w |= F , F has no rank in M. Proposition 1. For any M = hW, V, <i and any w ∈ W, we have M |= A |∼ B iff k (A ∧ B) < k (A ∧ ¬B) or A has no rank in M.
M M
As already mentioned, although the operator |∼ is non-monotonic, the notion of logical
entailment just defined is itself monotonic. In order to strengthen R and to obtain
non-monotonic entailment, Lehmann and Magidor in [
Let K be a knowledge base (i.e. a finite set of positive conditional assertions) andA a propositional formula. A is said to be exceptional for K if and only if K |= > |∼ ¬A. A conditional formula A |∼ B is exceptional for K if its antecedent A is exceptional for K. The set of conditional formulas which are exceptional for K will be denoted as E(K). It is possible to define a non increasing sequence of subsets of K, C0 ⊇ C1, . . . by letting C0 = K and, for i > 0, Ci = E(Ci−1). Observe that, being K finite, there is a n ≥ 0 such that for all m > n, Cm = Cn or Cm = ∅.
Definition 5 (Rank of a formula).Let K be a knowledge base and let A be a propositional formula. A has rank i (for K) if and only if i is the least natural number for which A is not exceptional for Ci. If A is exceptional for all Ci then A has no rank. Definition 5 above allows to define the rational closure of a knowledge baseK. Definition 6 (Rational closure K¯ of K). Let K be a conditional knowledge base. The rational closure K¯ of K is the set of all A |∼ B such that either (1) the rank of A is strictly less than the rank of A ∧ ¬B (this includes the case A has a rank and A ∧ ¬B has none), or (2) A has no rank.
This mechanism, which is now well-established, allows to overcome some weaknesses of R . First of all it is closed under rational monotonicity (RM): if (A |∼ B) ∈ K¯ and (A |∼ ¬C) 6∈ K¯ then (A ∧ C) |∼ B ∈ K¯. Furthermore, rational closure supports some of the wanted inferences that R does not support. For instance rational closure allows to deal with irrelevance: from monday |∼ go work, it does support the non-monotonic conclusion that monday ∧ shines |∼ go work.
We provide a semantical reconstruction of rational closure in terms of a minimal models’
mechanism, thus providing an instantiation of the following general recipe for
nonmonotonic reasoning:
(i) fix an underlying modal semantics for conditionals (here we concentrate onR but
another possible choice could have been the weaker P as in [
In the next proposition we will use Mi defined as follows. Let M = hW, <, V i be any rational model of K. Let M0 = M and, for all i, let Mi = hWi, <i, Vii be the rational model obtained from M by removing all the worlds w with k (w) < i, i.e., M Wi = {w ∈ W : kM(w) ≥ i}.
Proposition 2. Let M = hW, <, V i be any rational model of K. For any propositional formula A, if rank(A) ≥ i, then 1) kM(A) ≥ i, and 2) if A |∼ B is entailed by Ci, then Mi satisfiesA |∼ B.
The semantics we propose is a fixed interpretations minimal semantics, for short FIMS . In some respects our approach is similar in spirit to minimal models approaches to non-monotonic reasoning, such as circumscription4.
Definition 7 (FIMS ). Given M = hW, <, V i and M0 = hW0, <0, V 0i we say that M is preferred to M0 with respect to the fixed interpretations minimal semantics, and we write M <FIMS M0, if W = W0, V = V 0, and for all x, kM(x) ≤ kM0 (x) whereas there exists x0 : kM(x0) < kM0 (x0). We say that M is minimal w.r.t. <FIMS in case there is no M0 such that M0 <FIMS M. We say that K minimally entails a formula F w.r.t. FIMS , and we write K |=FIMS F , if F is valid in all models of K which are minimal w.r.t. <FIMS .
Can we capture rational closure within the semantics of Definition 7 above? We are soon forced to recognize that this is not the case. For instance, consider the following: Example 1. Let K = {penguin |∼ bird, penguin |∼ ¬f ly, bird |∼ f ly}. We derive that K 6|=FIMS penguin ∧ black |∼ ¬f ly. Indeed in FIMS there can be a model M in which W = {x, y, z}, V (x) = {penguin, bird, f ly, black}, V (y) = {penguin, bird}, V (z) = {bird, f ly}, and z < y < x. M is a model of K, and it is minimal with respect to FIMS (indeed once fixedV (x), V (y), V (z) as above, it is not possible to lower the rank of x nor of y nor of z unless we falsify K). Furthermore, in M, x is a typical world in which “it flies” and “it is black” hold (since there is no other world satisfying the same propositions which is preferred to it). Therefore, K 6|=FIMS penguin ∧ black |∼ ¬f ly. We have that {penguin |∼ bird, penguin |∼ ¬f ly, bird |∼ f ly} 6|=FIMS penguin ∧ black |∼ ¬f ly. On the contrary, it can be verified thatpenguin ∧ black |∼ ¬f ly is in the rational closure of {penguin |∼ bird, penguin |∼ ¬f ly, bird |∼ f ly}. Therefore, FIMS as it is does not allow us to define a semantics corresponding to rational closure. Things change if we consider FIMS applied to models that contain all possible valuations compatible (see Definition 8 below) with a given knowledge baseK. We call these models canonical models.
Example 2. Consider Example 1 above. If we restrict our attention to models that also contain a w with V (w) = {penguin, bird, black} which satisfies “it is a penguin”, “it is black” and “it does not fly” in which w is a typical world satisfying “it is a penguin”, we are able to conclude that typically it holds that if it is a penguin and it is black then it does not fly, as in rational closure. Indeed, in all minimal models of K that also contain w with V (w) = {penguin, bird, black}, it holds that penguin ∧ black |∼ ¬f ly. 4 As for circumscription, there are mainly two ways of comparing models with the same domain: by keeping the valuation function fixed (only comparingM and M0 if V and V 0 in the two models respectively coincide); or by also comparing M and M0 in case V 6= V 0. In this work we consider the latter alternative. We are led to the conjecture that FIMS restricted to canonical models could be the right semantics for rational closure. Canonical models are defined w.r.t. the language L. A truth assignment v : ATM −→ {true, f alse} is compatible with K, if there is no formula A ∈ L such that v(A) = true and K |= A |∼ ⊥.
Definition 8. A model M = hW , <, V i satisfying a knowledge base K is said to be canonical if it contains (at least) a world associated to each truth assignment compatible with K, that is to say: if v is compatible with K, then there exists a world w in W , such that for all propositional formulas B M, w |= B iff v(B) = true.
It can be shown that for any knowledge base a minimal canonical model exists: this is any canonical model in which every possible world w has the rank associated to the conjunction of all atoms and negated atoms in L that it satisfies. We can also prove that the canonical models that are minimal with respect to FIMS are an adequate semantic counterpart of rational closure.
Theorem 1. Let K be a knowledge base and M be a canonical model of K minimal w.r.t. <FIMS . We show that, for all conditionals A |∼ B, M |= A |∼ B if and only if A |∼ B ∈ K, where K is the rational closure of K.
As mentioned, the interest towards non-monotonic reasoning in DLs has grown in the
last years. In this section, we extend to ALC the notion of rational closure proposed
by Lehmann and Magidor [
To express defeasible inclusions, ALC is extended with a typicality operator T,
following the approach in [
Our starting point is therefore the extension of logic ALC with a typicality operator T. The intuitive idea is to extend the standard ALC allowing concepts of the form T(C) whose intuitive meaning is that T(C) selects the typical instances of a concept C. We can therefore distinguish between the properties that hold for all instances of concept C (C v D), and those that only hold for the typical such instances (T(C) v D). Definition 9. We consider an alphabet of concept names C, of role names R, and of individual constants O. Given A ∈ C and R ∈ R, we defineCR := A | > | ⊥ | ¬CR | CR u CR | CR t CR | ∀R.CR | ∃R.CR, and CL := CR | T(CR). A KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusionsCL v CR. ABox contains assertions of the form CL(a) and R(a, b), where a, b ∈ O.
The T operator satisfies a set of postulates that are essentially a reformulation of rational logic R: in this respect, the T-assertion T(C) v D is equivalent to the conditional assertion C |∼ D in R.
A first semantic characterization ofT can be given by means of a set of postulates that are essentially a restatement of axioms and rules of non-monotonic entailment in rational logic R. Given a domain Δ and a valuation function I one can define the function fT(S) that selects the typical instances of S, and in case S = CI for a concept C, it selects the typical instances of C. In this semantics, (T(C))I = fT(CI ), and fT has the following intuitive properties for all subsets S of Δ: (fT − 1) enforces that typical elements of S belong to S. (fT − 2) enforces that if there are elements in S, then there are also typical such elements. (fT − 3) expresses a weak form of monotonicity, namely cautious monotonicity. The next properties constraint the behavior of fT wrt ∩ and ∪ in such a way that they do not entail monotonicity. Last, (fT − R) corresponds to rational monotonicity, and forces again a form of monotonicity: if there is a typical S having the property R, then all typical S and Rs inherit the properties of typical Ss.
The semantics of ALCRT can be equivalently formulated in terms of rational
models: models of ALC are equipped by a preference relation < on the domain, whose
intuitive meaning is to compare the “typicality” of domain elements, that is to say x < y
means that x is more typical than y. Typical members of a concept C, that is members of
T(C), are the members x of C that are minimal with respect to this preference relation
(s.t. there is no other member of C more typical than x). This semantics with one single
preference relation < is the one that, as we will show, corresponds to rational closure5.
Definition 10 (Semantics ofALCRT). A model M of ALCRT is any structure hΔ, <
, I i where: Δ is the domain; < is an irreflexive, transitive and modular relation over
Δ (< is modular if, for all x, y, z ∈ Δ, if x < y then either x < z or z < y); I
is the extension function that maps each concept C to CI ⊆ Δ, and each role R to
RI ⊆ ΔI × ΔI . For concepts of ALC, CI is defined in the usual way. For the T
operator, we have (T(C))I = Min <(CI ), where Min <(S) = {u : u ∈ S and @z ∈ S
5 One may think of considering a sharper semantics with several preference relations. We aim to
explore this possibility in future works, for the moment, we just notice that (i) the definition
of such a semantics is not straightforward (what does differentiate one preference relation
from another? What are the dependencies between the different preference relations? Has
the typicality operator to be made parametric?) (ii) it cannot be expected that the resulting
semantics, being stronger than the one just proposed, can correspond to rational closure below.
s.t. z < u}. Furthermore, < satisfies theSmoothness Condition, i.e., for all concepts C,
CI is smooth. For S ⊆ Δ, we say that S is smooth iff for all x ∈ S, either x ∈ Min<(S)
or ∃y ∈ Min<(S) such that y < x,
Theorem 2. [Theorem 1 in [
In the following, we will refer to the definition of the semantics given in Definition 10.
to assign a distinct element aI of Δ to each individual constant a of O (i.e. we assume the unique name assumption).
We say that: a model M satisfies an inclusionC v D if it holds CI ⊆ DI ; M satisfies an assertion C(a) if aI ∈ CI ; and M satisfies an assertionR(a, b) if (aI , bI ) ∈ RI . We say that: M satisfies a knowledge baseK=(TBox,ABox), if it satisfies both its TBox and its ABox, where: M satisfies TBox ifM satisfies all inclusions in TBox andM satisfies ABox ifM satisfies all assertions in ABox.
From now on, in this section, we restrict our attention to ALCRT and to finite models. Given a knowledge base K and an inclusion CL v CR, we say that the inclusion is derivable from K (we write K |=ALCRT CL v CR) if CLI ⊆ CRI holds in all models M = hΔ, <, Ii satisfying K.
model M is the length of the longest chain x0 < · · · < x from x to a minimal x0 (s.t. for no x0, x0 < x0).
Finite ALCRT models can be equivalently defined by postulating the existence of a function k : Δ → N, and then letting x < y iff k(x) < k(y).
Definition 13 (Rank of a concept).Given a model M = hΔ, <, Ii, the rank kM(CR) of a concept CR in the model M is i = min{kM(x) : x ∈ CRI}. If CRI = ∅, then CR has no rank and we write kM(CR) = ∞.
Proposition 3. For any M = hΔ, <, Ii, we have that M satisfies T(C) v D iff k (C u D) < k (C u ¬D).
M M As already mentioned, although the typicality operator T itself is non-monotonic (i.e. T(C) v D does not imply T(C uE) v D), the logics ALC +T and ALCRT are monotonic: what is inferred from K can still be inferred from any K0 with K ⊆ K0. This is a clear limitation in DLs. As a consequence of non-monotonicity in ALCRT one cannot deal with irrelevance for instance. So one cannot derive from K = {Penguin v Bird , T(Bird ) v Fly , T(Penguin) v ¬Fly } that K |=min T(Penguin u Black ) v ¬Fly , even if the property of being black is irrelevant with respect to flying. In the same way if we added to K the information that jim is a bird (Bird(jim)), in ALCRT one cannot non-monotonically derive that it is a typical bird and therefore flies ( T(Bird)(jim) and F ly(jim) ). We investigate the possibility of overcoming this weakness by extending to ALCRT the notion of rational closure. We first consider the rational closure of the TBox alone. Next we will consider rational closure that also takes into account the ABox. 3.2 Rational Closure of the TBox in ALCRT Let us first define the notion ofquery. Intuitively, a query is either an inclusion relation or an assertion of the ABox; we want to check whether it is entailed from a given KB. Definition 14 (Query).A query F is either an assertion CL(a) or an inclusion relation CL v CR. Given a model M = hΔ, <, Ii, a query F holds in M if M satisfiesF . Definition 15. Let TB be a TBox and C a concept. C is said to be exceptional for TB iff TB |=ALCRT T(>) v ¬C. A T-inclusion T(C) v D is exceptional for TB if C is exceptional for TB. The set of T-inclusions of TB which are exceptional in TB will be denoted as E (TB).
Given a DL knowledge base K=(TBox,ABox), it is possible to define a sequence of non-increasing subsets of TBox E0 ⊇ E1, . . . by letting E0 = TBox and, for i > 0, Ei = E (Ei−1) ∪ {C v D ∈ TBox s.t. T does not occurr in C}. Observe that, being K finite, there is ann ≥ 0 such that for all m > n, Em = En or Em = ∅. Observe also that the definition of theEi’s is the same as the definition of theCi’s in Lehmann and Magidor’s definition of rational closure in Section 2.2, except for the fact that here, at each step, we also add all the strict inclusions.
Definition 16. A concept C has rank i (denoted by rank (C) = i) for K=(TBox,ABox), iff i is the least natural number for which C is not exceptional for Ei. If C is exceptional for all Ei then rank (C) = ∞, and we say that C has no rank.
As for propositional logic, the notion of rank of a formula allows to define the rational closure of the TBox of a knowledge base K.
Definition 17 (Rational closure of TBox). Let K=(TBox,ABox) be a DL knowledge base. We define,TBox , the rational closure of TBox, as
TBox = {T(C) v D | either rank (C) < rank (C u ¬D)
or rank (C) = ∞} ∪ {C v D | K |=ALC C v D} It can be easily seen that the rational closure of TBox is a non-monotonic strengthening of ALCRT. For instance it allows to deal with irrelevance. If TBox = {Penguin v Bird , T(Bird ) v Fly , T(Penguin) v ¬Fly }, then it can be verified thatT(Bird u Black ) v Fly ∈ TBox . This is a non-monotonic inference that does no longer follow if we knew that indeed black birds are non typical birds that do not fly: in this case from TBox’= TBox ∪{T(Bird u Black ) v ¬Fly } (in this case T(Bird u Black ) v Fly 6∈ TBox 0). Similarly, as for the propositional case, rational closure is closed under rational monotonicity: from T(Bird ) v Fly ∈ TBox and T(Bird ) v ¬LivesEurope 6∈ TBox it follows that T(Bird u LivesEurope) v Fly ∈ TBox .
As for the propositional case, in order to semantically characterize the rational closure, we first restrict our attention to minimal rational models that minimizethe rank of domain elements. Informally, given two models of K, one in which a given domain element x has rank 2 (because for instance z < y < x) , and another in which it has rank 1 (because only y < x), we would prefer the latter, as in this model the element x is “more normal” than in the former.
From now on, we restrict our attention to canonical minimal models. First, we define a set of concepts S closed under negation and subconcepts. We assume that all the concepts in K and in the query F belong to S. In order to define canonical models, we consider all the sets of concepts {C1, C2, . . . , Cn} ⊆ S that are consistent with K, i.e., s.t. K 6|=ALC C1 u C2 u · · · u Cn v ⊥.
Definition 18 (Canonical model w.r.t. S). Given K=(TBox,ABox) and a query F , a model M = hΔ, <, Ii satisfying K is canonical w.r.t. S if it contains at least a domain element x ∈ Δ s.t. x ∈ (C1 u C2 u · · · u Cn)I , for each set of concepts {C1, C2, . . . , Cn} ⊆ S that are consistent with K.
Definition 19 (Minimal canonical models (w.r.t. S)). Consider two models M = hΔ, <, Ii and M0 = hΔ0, <0, I0i, canonical w.r.t. S. We say that M is preferred to M0 (M < M0) if Δ = Δ0, and for all x ∈ Δ, kM(x) ≤ kM0 (x) whereas there exists y ∈ Δ such that kM(y) < kM0 (y). Given a knowledge base K, we say that M is a minimal canonical model of K if it is a canonical model satisfying K and there is no canonical model M0 satisfying K such that M0 < M.
The following results hold (more details and proofs can be found in [
K =(TBox,ABox), the problem of deciding whether T(C) v D ∈ TBox is in EXPTIME.
In this section we extend the notion of rational closure defined in the previous section in order to take into account the individual constants in the ABox. We address this question by first considering the semantic aspect, in order to treat individuals explicitly mentioned in the ABox in a uniform way with respect to the other domain elements: as for all the domain elements we would like to attribute to each individual constant named in the ABox the lowest possible rank. So we further refine Definition 19 of minimal canonical models with respect to TBox by taking into account the interpretation of individual constants of the ABox: given two minimal canonical models M and M0, we prefer M to M0 if there is an individual constant b occurring in ABox such that kM(bI ) < kM(bI0 ) (whereas kM(aI ) ≤ kM(aI0 ) for all other individual constants occurring in ABox).
K=(TBox,ABox), let M = hΔ, <, Ii and M0 = hΔ0, <0, I0i be two canonical models of K which are minimal w.r.t. Definition 19. We say thatM is preferred to M0 with respect to ABox (M <ABox M0) if for all individual constants a occurring in ABox, kM(aI ) ≤ kM(aI0 ) and there is at least one individual constant b occurring in ABox such that kM(bI ) < kM(bI0 ). Theorem 6. For any K = (T Box, ABox) there exists a minimal canonical model of K minimally satisfying ABox.
In order to see the power of the above semantic notion, consider the standard birds and penguins example.
Example 3. Suppose we have a knowledge base K where TBox = {T(Bird) v F ly, T(P enguin) v ¬F ly, P enguin v Bird}, and ABox = {P enguin(pio), Bird(tweety )}. Knowing that tweety is a bird and pio is a penguin, we would like to be able to assume, in the absence of other information, that tweety is a typical bird, whereas pio is a typical penguin, and therefore tweety flies whereas pio does not. Consider any minimal canonical model M of K. Being canonical, M will contain, among other elements: – x ∈ (Bird)I , x ∈ (F ly)I , x ∈ (¬P enguin)I , kM(x) = 0; – y ∈ (Bird)I , y ∈ (¬F ly)I , y ∈ (¬P enguin)I , kM(y) = 1; – z ∈ (P enguin)I , z ∈ (Bird)I , z ∈ (¬F ly)I , kM(z) = 1; – w ∈ (P enguin)I , w ∈ (Bird)I , w ∈ (F ly)I , kM(w) = 2; Notice that in the definition of minimal canonical model there is no constraint on the interpretation of the ABox constants tweety and pio. As far as Definition 19 is concerned for instance tweety can be mapped onto x ((tweety )I = x) or onto y ((tweety )I = y): the minimality of M with respect to Definition 19 is not affected by this choice. However in the first case it would hold that tweety is a typical bird, in the second tweety is not a typical bird. We want to prefer the first case, and this is what derives from Definition 20: if in M tweety I = x whereas in M1 (which for the rest is identical to M) it holds that tweety I = y, then M is preferred to M1. The same for pio. As a result in all models of K minimal with respect to both TBox and ABox (Definition 20), it holds what we wanted: that tweety is a typical bird (T (Bird)(tweety )), and therefore it flies, whereas pio is a typical penguin (T (P enguin)(pio)), and therefore it does not fly.
We conclude this section by providing an algorithmic construction for the rational closure of ABox, whose idea is that of considering all the possible minimal consistent assignments of ranks to the individuals explicitly named in the ABox. Each assignment adds some properties to named individuals which can be used to infer new conclusions. We adopt a skeptical view of considering only those conclusions which hold for all assignments. The equivalence with the semantics shows that the minimal entailment captures a skeptical approach when reasoning about the ABox.
More formally, in order to calculate the rational closure of ABox (ABox ) for all individual constants of the ABox we find out what is the lowest possible rank they can have in minimal canonical models w.r.t. Definition 19, with the idea that an individual constant ai can have a given rank (kj (ai)) just in case it is compatible with all the inclusions of the TBox whose antecedent A’s rank is ≥ kj (ai) (the inclusions whose antecedent A’s rank is < kj (ai) do not matter. The minimal possible rank assignment kj for all ai is computed in the algorithm below: μij computes all the concepts that ai would need to satisfy in case it had the rank attributed by kj (kj (ai)). The algorithm verifies whetherμij is compatible with (TBox , ABox) and whether it is minimal. Notice that in this phase all constants are considered simultaneously (indeed the possible ranks of different individual constants depend on each other). For this reason μj takes into account the ranks attributed to all individual constants, being the union of all μij for all ai, and the consistency of this union with (TBox , ABox) is verified (instead of the consistency of all separate μij ). Once computed the minimal rank assignments these are used to defineABox ) as the set of all assertions derivable in ALC from ABox ∪μj for all minimal consistent rank assignments kj .
Definition 21 (ABox : rational closure of ABox). Let a1, . . . , am be the individuals explicitly named in the ABox. Let k1, k2, . . . , kh be all the possible rank assignments (ranging from 1 to n) to the individuals occurring in ABox. • Given a rank assignment kj we define: – for each ai: μij = {(¬C t D)(ai) s.t. C, D ∈ S, T(C) v D in TBox , and kj (ai) ≤ rank(C)} ∪ {(¬C t D)(ai) s.t. C v D in TBox }; – let μj = μ1 ∪ · · · ∪ μjm for all μj1 . . . μjm just calculated for all a1, . . . , am in the j
ABox • kj is minimal and consistent with (TBox , ABox) if: – ABox ∪μj is consistent in ALC; – there is no ki consistent wih (TBox , ABox) s.t. for all ai, ki(ai) ≤ kj (ai) and for some b, ki(b) < kj (b). • The rational closure of ABox (ABox ) is the set of all assertions derivable in ALC from ABox ∪μj for all minimal consistent rank assignments kj , i.e:
ABox = Tkjminimal consistent{C(a) : ABox ∪μj |=ALC C(a)}
The following theorems hold (again, see [
K =(TBox,ABox), an individual constant a and a concept C, the problem of deciding whether C(a) ∈ ABox is EXPTIME-complete. 4
In [
Casini and Straccia [
In the first part of the paper we have provided a semantic reconstruction of the well known rational closure, in detail a minimal model semantics based on the idea that preferred rational models are those ones in which the height of the worlds is minimized. Adding suitable possibility assumptions to a knowledge base, such a minimal model semantics corresponds to rational closure.
The correspondence between the proposed minimal model semantics and rational
closure suggests the possibility of defining variants of rational closure by varying the
ingredients underlying our approach, namely: (i) the properties of the preference relation
<: for instance just preorder, or multi-linear or weakly-connected; (ii) the comparison
relation on models: based for instance on the rank of the worlds or on the inclusion
between the relations <, or on negated boxed formulas satisfied by a world, as in the
logic Pmin [
In the second part of the paper we have defined a rational closure construction for the Description Logic ALC extended with a typicality operator and provided a minimal model semantics for it, based on the idea of minimizing the rank of objects in the domain, that is their level of “untypicality”. This semantics corresponds to a natural extension to DLs of Lehmann and Magidor’s notion of rational closure. We have also extended the notion of rational closure to the ABox, by providing an algorithm for computing it that is sound and complete with respect to the minimal model semantics. Last, we have shown an EXPTIME upper bound for the algorithm.
In future work, concerning Description Logics, we will consider further ingredients
in the recipe for non-monotonic DLs. First, we aim to study stronger versions of rational
closure that allow to overcome the weaknesses of the basic one, for instance the fact
that we cannot reason separately on the inheritance of different properties. Furthermore,
non-monotonic extensions of low complexity DLs based on the T operator have been
recently provided [