=Paper=
{{Paper
|id=None
|storemode=property
|title=A Semantics for Rational Closure: Preliminary Results
|pdfUrl=https://ceur-ws.org/Vol-1068/paper-l07.pdf
|volume=Vol-1068
|dblpUrl=https://dblp.org/rec/conf/cilc/GiordanoGOP13
}}
==A Semantics for Rational Closure: Preliminary Results==
<pdf width="1500px">https://ceur-ws.org/Vol-1068/paper-l07.pdf</pdf>
<pre>
 A semantics for Rational Closure: Preliminary Results
    Laura Giordano1 , Valentina Gliozzi2 , Nicola Olivetti3 , and Gian Luca Pozzato2
1
   DISIT - Università del Piemonte Orientale - Alessandria, Italy - laura@mfn.unipmn.it
   2
     Dip. di Informatica - Univ. di Torino - Italy {gliozzi,pozzato}@di.unito.it
 3
   Aix-Marseille Univ. - CNRS, LSIS UMR 7296 - France - {nicola.olivetti}@univ-amu.fr

       Abstract. 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 se-
       mantics 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.


1   Introduction
In [18] Kraus, Lehmann and Magidor (henceforth KLM) proposed a set of natural
properties of non-monotonic reasoning. Plausible inferences are represented by non-
monotonic conditionals of the form A |∼ B, to be read as “typically or normally A
entails B”: for instance monday |∼ go work can be used to represent that “normally
if it is Monday I go to work”. Conditional entailment is non-monotonic since from
A |∼ B one cannot derive A ∧ C |∼ B, in our example from monday |∼ go work one
cannot monotonically derive monday ∧ ill |∼ go work (“normally if it is Monday,
even if I am ill I go to work”). KLM organized the core properties of non-monotonic
reasoning into a hierarchy of systems, from the weakest to the strongest: cumulative
logic C, loop-cumulative logic CL, preferential logic P. Preferential logic has been
strengthened into rational logic R in [20]. In this work, we restrict our attention to the
rational logic R on which rational closure is built.
     KLM system R formalizes desired properties of non-monotonic inference but it
is too weak to perform useful non-monotonic inferences. We have just seen that by
the non-monotonicity of |∼, A |∼ B does not entail A ∧ C |∼ B, and this is a wanted
property of |∼. However, there are cases in which, in the absence of information to
the contrary, we want to be able to tentatively infer that also A ∧ C |∼ B, with the
possibility of withdrawing the inference in case we discovered that it is inconsistent.
For instance, we might want to infer that A ∧ C |∼ B when C is irrelevant with respect
to the property B: we might want to tentatively infer from monday |∼ go work that
monday ∧ shines |∼ go work (“normally if it is Monday, even if the sun shines I go to
work”), with the possibility of withdrawing the conclusion if we discovered that indeed
the sun shining prevents from going to work. R cannot handle irrelevant information in
conditionals, and the inferences just exemplified are not supported.
     Partially motivated by this weakness, Lehmann and Magidor have proposed a true
non-monotonic mechanism on the top of R. Rational closure on the one hand preserves
100            Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 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 [20] the
 authors give a syntactic procedure to calculate the set of conditionals entailed by the
 rational closure as well as a quite complex semantic construction. It is worth noticing
 that a strongly related construction has been proposed by Pearl [22] with his notion of
 1-entailment, motivated by a probabilistic interpretation of conditionals.
     The first problem we tackle in this work is that of giving a purely semantic characteri-
 zation 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 formal-
 ism of DLs with non-monotonic reasoning features [1, 2, 4, 6, 7, 14, 19, 17, 3, 21]; the
 purpose of these extensions is that of allowing reasoning about prototypical properties
 of individuals or classes of individuals. In spite of the load of work in this direction,
 finding a solution to the problem of extending DLs for reasoning about prototypical
 properties seems far from being solved. The best known semantics for non-monotonic
 reasoning have been used to the purpose, from default logic [1], to circumscription [2],
 from Lifschitz’s non-monotonic logic MKNF [6, 21] to KLM logics. Concerning KLM
 logics, in [10] a preferential extension of ALC is defined, based on the logic P, and in
 [14] a minimal model semantics for this logic is proposed; in [3], a defeasible description
 logic based on the logic R is introduced and, in [4], a notion of rational closure is defined
 for ALC through an algorithmic construction similar to the one introduced by Freund
 for the propositional calculus. Although [4] provides axiomatic properties of this notion
 of rational closure, it does not provide a semantics for it.
 We here extend to ALC the definition of rational closure by Lehmann and Magidor
 [20] and define a minimal model semantics for rational closure in ALC by adapting the
 semantics introduced in the propositional case. We start from the extension of the descrip-
 tion logic ALC with a typicality operator T, first proposed in [10], that allows to directly
 express typical properties such as T(HeartPosition) v Left, T(Bird ) v Fly, and
 T(Penguin) v ¬Fly, whose intuitive meaning is that normally, the heart is positioned
 in the left-hand side of the chest, that typical birds fly, whereas penguins do not. In this pa-
 per, the T operator is intended to enjoy the well-established properties of rational logic R.
 Even if T is a non-monotonic operator (so that for instance T(HeartPosition) v Left
 does not entail that T(HeartPosition u SitusInversus) v Left) the logic itself is mono-
 tonic. Indeed, in this logic it is not possible to monotonically infer from T(Bird ) v Fly,
 in the absence of information to the contrary, that also T(Bird u Black ) v Fly. Nor it
 can non-monotonically be inferred from Bird (tweety), in the absence of information to
 the contrary, that T(Bird )(tweety) and that Fly(tweety). Non-monotonicity is achieved,
 from a semantic point of view, by defining, on the top of ALC with typicality, a minimal
A semantics for Rational Closure: Preliminary Results                                      101


 model semantics which is similar to the one in [14], with the difference that the notion
 of minimality is based on the minimization of the ranks of the worlds, rather than on the
 minimization of specific formulas, as in [14]. This semantics provides a characterization
 to the rational closure construction for ALC, which assigns a rank (a level of exception-
 ality) to every concept; this rank is used to evaluate defeasible inclusions of the form
 T(C) v D: the inclusion is supported by the rational closure whenever the rank of C is
 strictly smaller than the one of C u ¬D.
      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
 E XP T IME 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 [14, 2] and comparable with the approaches in [4, 21],
 and thus a good candidate to define effective non-monotonic extensions of DLs.


 2    Propositional rational closure: a semantic characterization
 2.1 KLM rational system R
 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 variables ATM , the boolean connectives and
 the conditional operator |∼. We assume that the set ATM is finite. We use A, 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: if A 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 [11]. We use `P C (resp. |=P C ) to denote
 provability (resp. validity) in the propositional calculus:
     • All axioms and rules of propositional logic
     • A |∼ A                                                                     (REF)
     • if `P C A ↔ B then (A |∼ C) → (B |∼ C),                                    (LLE)
     • if `P C A → B then (C |∼ A) → (C |∼ B)                                      (RW)
     • ((A |∼ B) ∧ (A |∼ C)) → (A ∧ B |∼ C)                                        (CM)
     • ((A |∼ B) ∧ (A |∼ C)) → (A |∼ B ∧ C)                                      (AND)
     • ((A |∼ C) ∧ (B |∼ C)) → (A ∨ B |∼ C)                                         (OR)
     • ((A |∼ B) ∧ ¬(A |∼ ¬C)) → ((A ∧ C) |∼ B)                                    (RM)
 The axiom (CM) is called cumulative monotony and it is characteristic of all KLM
 logics, axiom (RM) is called rational monotony and it characterizes the logic of rational
 entailment R (it is what distinguishes rational from the weaker preferential entailment). R
102            Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 seems to capture the core properties of non-monotonic reasoning, as shown by Friedman
 and Halpern these properties are quite ubiquitous being characterized by different
 semantics (all of them being instances of so-called plausibility structures [8]).
     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 worlds W 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. Let A be a
 propositional formula; we define Min M    < (A) = {w ∈ W | M, w |= A and ∀w , w < w
                                                                                     0   0

 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 the Smoothness condition: if M, w |= A, then w ∈ Min M            < (A) or there is
 w0 ∈ Min M   < (A) s.t. w 0
                             < 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, w |= B. It
                                                                                  0

 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 ).
 Definition 3 (Rank of a formula). The rank kM (F ) of a formula F in a model M is
 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
 kM (A ∧ B) < kM (A ∧ ¬B) or A has no rank in M.
A semantics for Rational Closure: Preliminary Results                                   103


 2.2 Lehmann and Magidor’s definition of rational closure
 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 [20] propose the well-known
 mechanism of rational closure. Since in rational closure no boolean combinations of
 conditionals are allowed, in the following, the knowledge base K is just a finite set of
 positive conditional assertions of the form A |∼ B.
 Definition 4 (Exceptionality of propositional formulas and conditional formulas).
 Let K be a knowledge base (i.e. a finite set of positive conditional assertions) and A 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 proposi-
 tional 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 base K.
 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.

 2.3 A semantical characterization of rational closure
 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 non-
 monotonic reasoning:
 (i) fix an underlying modal semantics for conditionals (here we concentrate on R but
 another possible choice could have been the weaker P as in [12]),
 (ii) obtain non-monotonic inference by restricting semantic consequence to a class of
 minimal models. These minimal models should be chosen on the basis of semantic con-
 siderations, independent from the language and from the set of conditionals (knowledge
 base) whose non-monotonic consequences we want to determine.
 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 , Vi i be the
104              Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 rational model obtained from M by removing all the worlds w with kM (w) < i, i.e.,
 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 satisfies A |∼ 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 = hW 0 , <0 , V 0 i we say that M
 is preferred to M0 with respect to the fixed interpretations minimal semantics, and we
 write M <FIMS M0 , if W = W 0 , 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 fixed V (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 that penguin ∧ 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 base K. 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 comparing M 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.
A semantics for Rational Closure: Preliminary Results                                   105


 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.

 3    Rational closure in Description Logics
 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 [20], recalled in Section 2.2, and we define a semantic
 characterization of this notion of rational closure by introducing a minimal model
 semantics for ALC with defeasible inclusions. This semantics is a direct generalization
 of the minimal (canonical) model semantics introduced in Section 2.3
     To express defeasible inclusions, ALC is extended with a typicality operator T,
 following the approach in [10, 14]. Differently from [14], here we consider special
 kinds of preferential models, namely, rational models, to define the semantics of the
 T operator, and we use a different notion of preference between models, namely, the
 preference relation <F IM S , introduced in Section 2.3. Given the typicality operator,
 the defeasible assertion T(C) v D (all the typical C’s are D’s) plays the role of the
 conditional assertion C |∼ D in R.

 3.1 The logic ALC R T
 Similarly to rational closure which is a non-monotonic mechanism built over R, our
 application of rational closure to DLs is done in two steps. First, similarly to what done
 in [10], we extend the standard ALC by a typicality operator T that allows to single out
 the typical instances of a concept T. Since we are dealing here with rational closure (that
 builds over R), we attribute to T properties related to R. The resulting logic is called
 ALC R T. As a second step, we build over ALC R T a rational closure mechanism.
     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).
106               Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 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 define CR := 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 inclusions CL 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 of T 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 = C I for a concept
 C, it selects the typical instances of C. In this semantics, (T(C))I = fT (C I ), 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 ALC R T 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 of ALC R T). A model M of ALC R T is any structure h∆, <
 , Ii 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 C I ⊆ ∆, and each role R to
 RI ⊆ ∆I × ∆I . For concepts of ALC, C I is defined in the usual way. For the T
 operator, we have (T(C))I = Min < (C I ), 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.
A semantics for Rational Closure: Preliminary Results                                    107


 s.t. z < u}. Furthermore, < satisfies the Smoothness Condition, i.e., for all concepts C,
 C I 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 [9]] A KB=(TBox,ABox) is satisfiable in a model described
 in Definition 10 iff it is satisfiable in a model h∆, I, fT i where fT satisfies (fT − 1) −
 (fT − 5) and (fT − R), and (T(C))I = fT (C I ).
 In the following, we will refer to the definition of the semantics given in Definition 10.
 Definition 11 (Model satisfying a Knowledge Base). Given a model M, I is extended
 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 inclusion C v D if it holds C I ⊆ DI ; M satisfies
 an assertion C(a) if aI ∈ C I ; and M satisfies an assertion R(a, b) if (aI , bI ) ∈ RI .
 We say that: M satisfies a knowledge base K=(TBox,ABox), if it satisfies both its TBox
 and its ABox, where: M satisfies TBox if M satisfies all inclusions in TBox and M
 satisfies ABox if M satisfies all assertions in ABox.
 From now on, in this section, we restrict our attention to ALC R T 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 |=ALC R T CL v CR ) if CLI ⊆ CR      I
                                                                     holds in all models
 M = h∆, <, Ii satisfying K.
 Definition 12 (Rank of a domain element). The rank kM of a domain element x in a
 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 ALC R T 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 CR
                                                                   I
                                                                     = ∅, 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
 kM (C u D) < kM (C u ¬D).
 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 ALC R T are mono-
 tonic: what is inferred from K can still be inferred from any K 0 with K ⊆ K 0 . This is a
 clear limitation in DLs. As a consequence of non-monotonicity in ALC R T 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 ALC R T 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 ALC R T 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.
108            Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 3.2 Rational Closure of the TBox in ALC R T
 Let us first define the notion of query. Intuitively, a query is either an inclusion relation
 or an assertion of the ABox; we want to check whether it is entailed from a given KB.

 Definition 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 satisfies F .

 Definition 15. Let TB be a TBox and C a concept. C is said to be exceptional for TB
 iff TB |=ALC R T 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 an n ≥ 0 such that for all m > n, Em = En or Em = ∅. Observe also
 that the definition of the Ei ’s is the same as the definition of the Ci ’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 ALC R T. 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 that T(Bird uBlack ) 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 minimize the 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.
A semantics for Rational Closure: Preliminary Results                                       109


      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 , I 0 i, 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 [15, 16]):
 Theorem 3. For any K there exists a minimal canonical model w.r.t. TBox.
 Theorem 4. Let K=(TBox,ABox) be a knowledge base and C v D a query. We have
 that C v D ∈ TBox if and only if C v D holds in all minimal canonical models of K
 with respect to S.
 Theorem 5 (Complexity of rational closure over the TBox). Given a knowledge base
 K =(TBox,ABox), the problem of deciding whether T(C) v D ∈ TBox is in E XP T IME.

 3.3 Rational Closure Over the ABox
 In this section we extend the notion of rational closure defined in the previous section
 in order to take into account the individual constants in the ABox. We 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
                     0                               0
 kM (bI ) < kM (bI ) (whereas kM (aI ) ≤ kM (aI ) for all other individual constants
 occurring in ABox).
 Definition 20 (Minimal canonical model of K minimally satisfying ABox). Given
 K=(TBox,ABox), let M = h∆, <, Ii and M0 = h∆0 , <0 , I 0 i be two canonical models
 of K which are minimal w.r.t. Definition 19. We say that M is preferred to M0 with
 respect to ABox (M <ABox M0 ) if for all individual constants a occurring in ABox,
                   0
 kM (aI ) ≤ kM (aI ) and there is at least one individual constant b occurring in ABox
                           0
 such that kM (b ) < kM (bI ).
                I
110            Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 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 typ-
 ical 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: µji 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 µji 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
A semantics for Rational Closure: Preliminary Results                                           111


 account the ranks attributed to all individual constants, being the union of all µji for
 all ai , and the consistency of this union with (TBox , ABox) is verified (instead of the
 consistency of all separate µji ). Once computed the minimal rank assignments these are
 used to define ABox ) 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 : µji = {(¬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 = µj1 ∪ · · · ∪ µjm for all µj1 . . . µjm just calculated for all a1 , . . . , am in the
     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:
                      T
            ABox = kj minimal consistent {C(a) : ABox ∪µj |=ALC C(a)}

 The following theorems hold (again, see [15, 16] for details and proofs):

 Theorem 7 (Soundness and Completeness of ABox ). Given K=(TBox, ABox), for
 all individual constant a in ABox, we have that C(a) ∈ ABox if and only if C(a) holds
 in all minimal canonical models of K minimally satisfying ABox.

 Theorem 8 (Complexity of rational closure over the ABox). Given a knowledge base
 K =(TBox,ABox), an individual constant a and a concept C, the problem of deciding
 whether C(a) ∈ ABox is E XP T IME-complete.


 4    Related work
 In [14] non-monotonic extensions of DLs based on the T operator have been proposed.
 In these extensions, the semantics of T is based on preferential logic P. Non-monotonic
 inference is obtained by restricting entailment to minimal models, where minimal models
 are those that minimize the truth of formulas of a special kind. In this work, we have
 presented an alternative approach. First, the semantics underlying the T operator is R .
 Moreover and more importantly, we have adopted a minimal model semantics, where, as
 a difference with [14], the notion of minimal model is completely independent from the
 language and is determined only by the relational structure of models.
     Casini and Straccia [4] study the application of rational closure to DLs. They extend
 to ALC the algorithmic construction proposed by Freund for capturing the rational
 closure in the propositional calculus. While in the propositional calculus this construction
 is proved to be equivalent with the notion of rational closure in [20], the equivalence
112           Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato


 is not known to hold for the case of ALC. While Casini and Straccia prove axiomatic
 properties of their notion of rational closure, here we focus on an extension of Lehmann
 and Magidor definition of rational closure for ALC and we define a semantics for it. [4]
 also keeps the ABox into account, and defines closure operations over individuals. It
 introduces a consequence relation among a knowledge base K and assertions, under
 the requirement that the TBox is unfoldable and the ABox is closed under completion
 rules, such as, for instance, that if a : ∃R.C ∈ ABox, then both aRb and b : C (for some
 individual constant b) must belong to the ABox too. Under such restrictions they are
 able to define a procedure to compute the rational closure of the ABox assuming that the
 individuals explicitly named are linearly ordered, and different orders determine different
 sets of consequences. The authors show that, for each order s, the consequence relation
   s is rational and can be computed in PS PACE . In a subsequent work [5], the authors
 introduce an approach based on the combination of rational closure and Defeasible
 Inheritance Networks (INs).


 5    Conclusions
 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 [12]. The systems obtained by various combinations of these ingredients are
 largely unexplored and may give rise to useful non-monotonic logics.
     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 E XP T IME 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 [13]. In future works, we aim to study the application of the proposed
 semantics to DLs of the EL and DL-Lite families, in order to define a rational closure
 for low complexity DLs.
A semantics for Rational Closure: Preliminary Results                                           113


 References
  1. F. Baader and B. Hollunder. Priorities on defaults with prerequisites, and their application in
     treating specificity in terminological default logic. J. Autom. Reasoning, 15(1):41–68, 1995.
  2. Piero A. Bonatti, Carsten Lutz, and Frank Wolter. The Complexity of Circumscription in DLs.
     Journal of Artificial Intelligence Research (JAIR), 35:717–773, 2009.
  3. Katarina Britz, Johannes Heidema, and Thomas Meyer. Semantic preferential subsumption.
     In G. Brewka and J. Lang, editors, KR 2008, pages 476–484, 2008. AAAI Press.
  4. G. Casini and U. Straccia. Rational Closure for Defeasible Description Logics. In T. Janhunen
     and I. Niemelä, editors, Proc. of JELIA 2010, LNAI 6341, pages 77–90, 2010. Springer.
  5. Giovanni Casini and Umberto Straccia. Defeasible Inheritance-Based Description Logics. In
     Proc of IJCAI 2011, pages 813–818, 2011. Morgan Kaufmann.
  6. F. M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation
     as failure. ACM Transactions on Computational Logic (ToCL), 3(2):177–225, 2002.
  7. T. Eiter, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining Answer Set Program-
     ming with Description Logics for the Semantic Web. In KR 2004, pages 141–151, 2004.
  8. N. Friedman and J. Y. Halpern. Plausibility measures and default reasoning. Journal of the
     ACM, 48(4):648–685, 2001.
  9. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Preferential vs Rational Description
     Logics: which one for Reasoning About Typicality? ECAI 2010, pp. 1073 - 1074, IOS Press.
 10. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. ALC+T: a preferential extension of
     Description Logics. Fundamenta Informaticae, 96:1–32, 2009.
 11. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Analytic Tableaux Calculi for KLM
     Logics of Nonmonotonic Reasoning. ACM Trans. on Comput. Logics (TOCL), 10(3), 2009.
 12. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. A nonmonotonic extension of KLM
     preferential logic P. In LPAR 2010, LNCS 6397, pages 317–332, 2010. Springer-Verlag.
 13. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Reasoning about typicality in low
     complexity DLs: the logics EL⊥ Tmin and DL-Litec Tmin . In Proc. of IJCAI 2011, pages
     894–899, 2011. Morgan Kaufmann.
 14. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. A NonMonotonic Description Logic
     for Reasoning About Typicality. Artificial Intelligence, pages 165–202, 2012.
 15. Laura Giordano, Valentina Gliozzi, Nicola Olivetti, and Gian Luca Pozzato. Preliminary
     result on the definition of a minimal model semantics for Rational Closure . Technical report,
     Dipartimento di Informatica, Università degli Studi di Torino, 2013.
 16. Laura Giordano, Valentina Gliozzi, Nicola Olivetti, and Gian Luca Pozzato. Minimal model
     semantics and rational closure in description logics. In Informal Proc. of DL2013), CEUR
     1014, pages 168–180, 2013.
 17. P. Ke and U. Sattler. Next Steps for Description Logics of Minimal Knowledge and Negation
     as Failure. In Proc. of DL2008, CEUR 353, 2008. CEUR-WS.org.
 18. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and
     cumulative logics. Artificial Intelligence, 44(1-2):167–207, 1990.
 19. Adila Alfa Krisnadhi, Kunal Sengupta, and Pascal Hitzler. Local closed world semantics:
     Keep it simple, stupid! In Proc. of DL2011, CEUR 745, 2011.
 20. Daniel Lehmann and Menachem Magidor. What does a conditional knowledge base entail?
     Artificial Intelligence, 55(1):1–60, 1992.
 21. Boris Motik and Riccardo Rosati. Reconciling Description Logics and rules. Journal of the
     ACM, 57(5), 2010.
 22. J. Pearl. System Z: A natural ordering of defaults with tractable applications to nonmonotonic
     reasoning. In TARK, pages 121–135,1990. Morgan Kaufmann.

</pre>