Strengthening the Rational Closure for Description Logics: An Overview

Abstract

The paper describes a preferential approach for dealing with exceptions in Description Logics, based on the rational closure. It is well known that the rational closure does not allow an independent handling of the inheritance of di erent defeasible properties of concepts. Several solutions have been proposed to face this problem and the lexicographic closure is the most notable one. In this work, we provide an overview of the closure constructions that have been proposed to strengthen the rational closure.

Introduction

The study of nonmonotonic extensions of DLs is motivated by a problem in standard ontology languages (and, speci cally, in OWL Description Logics) where a class inherits the properties of its superclasses, and where the treatment of exceptions is required in many application domains, from those concerning laws and regulations (where new laws override old ones) to medical ontologies.

Many non-monotonic extensions of DLs have been developed incorporating non-monotonic features from most of the non-monotonic formalisms in the literature, from default [ 3, 4 ] and autoepistemic logics [ 23, 41, 49 ], to circumscription [ 12, 9 ] and preferential logics [ 33, 13, 34, 17, 16, 37, 20, 35, 36 ], including also the approaches based on Answer Set Programming [ 25, 24 ] and, in general, on rule languages [ 43, 40 ]. New constructions and semantics have also been developed speci cally for dealing with exceptions in DLs as, for instance, the logic of overriding DLN in [ 8, 10 ] and the context based CKR framework in [ 11 ]).

The landscape is very rich and the complexity of the di erent approaches has been studied, both for low complexity and for high complexity description logics. The case of description logic is an interesting case study for non-monotonic reasoning, which encompasses a limited treatment of rst order of non-monotonic logics, namely, the treatment of the decidable fragment including only unary and binary predicates. Some undecidability results have also been found in nonmonotonic extensions, for instance, when roles are xed in circumscriptive knowledge bases [ 9 ].

For dealing with big knowledge bases, tractable constructions are especially important. In this paper we focus on the rational closure for DLs [ 17, 20, 16, 37, 15 ] and on its re nements. The rational closure introduced by Lehmann and Magidor [45] is a polynomial construction, and it was rst adapted to DLs by Casini and Straccia [ 17 ]. On the one hand, the rational closure can be computed by exploiting polynomial reductions to standard DLs [ 36, 48 ], and its construction requires a quadratic number of entailments to the underlying DL reasoner. On the other hand, it su ers from di erent problems, one of them being the well known problem called by Pearl [50] \the blocking of property inheritance problem". There are other problems of the rational closure which are speci c to description logics. For logics including some combination of constructs, such as nominals and universal role, the rational closure of a nite knowledge base may be inconsistent. This problem is due to the fact that some DL constructs (or their combination) allow for the speci cation of very general constraints which are not taken into account in the rational closure construction. For this problem there are some partial solutions in [ 38, 22 ] for the low complexity logics of the E L? family, while a new notion of stable rational closure has been proposed by Bonatti [ 7 ] to deal with the wider class of expressive description logics. A further problem of rational closure for DLs is that it disregards defeasible information for existential concepts, a problem which has been addressed by Pensel and Turhan [51], who developed a stronger versions of rational and relevant entailment in E L, which considers defeasible information for quanti ed concepts.

In this paper we focus on the rst problem: if a subclass of a class C is exceptional to C for a given aspect, it is exceptional tout court and does not inherit any of the typical properties of C. Re nements of the rational closure construction, avoiding this problem, have been studied in the literature, the rst prominent one being the lexicographic closure introduced by Lehmann [46] in the context of propositional logic, later extended to the DL ALC by Casini and Straccia [ 19 ]. In the context of description logics, other approaches have been proposed to deal with this problem. In [ 20 ] the same authors have developed an inheritance-based approach for defeasible DLs. In [ 14 ] Casini et al. have introduced the notions of basic Relevant Closure and of minimal Relevant Closure as extensions of the rational closure, where relevance is based on the notion of justi cation. In [ 39 ] Gliozzi has de ned a semantics for defeasible inclusions in which models are equipped with several preference relations, providing a re nement of the rational closure semantics. It has to be mentioned that other defeasible extensions of DLs still based on preferential logics but not on the rational closure, also su er from the blocking of property inheritance problem, for instance, the typicality logic ALC + Tmin [ 35 ] which, di erently from the rational closure, is not based on a non-ranked semantics. A multi-typicality version of this semantics has been studied in [ 26 ] to address this problem. Other approaches, such as the logic of overriding DLN [ 8 ], still build on the rational closure to determine speci city of defaults, but do not su er from this problem. In a sense, when it builds on the rational closure to determine the ranking of concepts (rather than building on the concept hierarchy), also DLN can be regarded as a re nement of the rational closure.

In the following, we give an overview of the lexicographic closure and of other re nements of the rational closure, comparing their outcomes on some examples. In particular, we consider the MP-closure and the Skeptical closure, which are weaker variants of the lexicographic closure, as well as the multi-preference semantics [ 39 ], the relevant closure [ 14 ], and DLN . The multi-preference closure was rst introduced in [ 30 ] as a sound approximation of Gliozzi's multi-preference semantics [ 39 ]. As the lexicographic closure, it builds over the rational closure but it de nes a preferential, not necessarily ranked, semantics, using a di erent lexicographic order to compare sets of defaults.

The MP-closure construction generates a superset of the basis generated by the lexicographic closure and, therefore, entailment under the MP-closure (capturing the typicality inclusions which hold from all the MP-closure bases) is weaker than entailment under the lexicographic closure. Unfortunately, both the MP-closure and the lexicographic closure require an exponential number of possible bases to be considered. Having a single base would make reasoning about exceptions in the ontology much faster. The pattern followed by the skeptical closure [ 27, 28 ], as by the logic of overriding DLN [ 8 ], is that of building a single basis which, in essence, is a subset of the intersection of all the basis (soundly approximating the MP-closure), and can be constructed in a polynomial number of steps. Entailment in the skeptical closure is neither weaker nor stronger than entailment in DLN . On the other hand, the multi-preference semantics, although stronger than the MP-closure (and than the skeptical closure), is incomparable with the lexicographic closure. In the following, we rst introduce the rational closure and then we compare the di erent approaches through some examples. 2

The rational closure for ALC In this section we recall the extension of ALC with a typicality operator introduced in [ 34, 36 ] under the preferential and ranked semantics. In particular, we recall the logic ALC + TR which is at the basis of a rational closure construction proposed in [ 36 ] for ALC. The general idea is that of extending the description logic ALC with concepts of the form T(C), whose instances are the typical instances of concept C, thus distinguishing between the properties that hold for all instances of concept C (given by strict inclusions C v D), and the properties that only hold for the typical instances of C (given by the defeasible inclusions T(C) v D). The extended language is de ned as follows:

CR := A j > j ? j :CR j CR u CR j CR t CR j 8R:CR j 9R:CR

CL := CR j T(CR), where A is a concept name and R a role name. A knowledge base K is a pair (T ; A), where the TBox T contains a nite set of concept inclusions CL v CR, and the ABox A contains a nite set of assertions of the form CR(a) and R(a; b), for a; b individual names, and R role name. Less constrained languages have been considered, in which the typicality operator may also occur on the right hand side of inclusions, for instance, in extensions with typicality of the very expressive logic SROIQ [ 36 ] and of the low complexity logic SROEL(u; ) [ 38 ] For simplicity, however, here we restrict our consideration to inclusions, which are either strict inclusions, or typicality inclusions of the form T(C) v D (where C and D are ALC concepts), which in essence correspond to KLM defeasible inclusions C j D.

The semantics of ALC with typicality is de ned in terms of preferential models, extending to ALC the preferential semantics by Kraus, Lehmann and Magidor in [44, 45]: ordinary models of ALC are equipped with a preference relation < on the domain, whose intuitive meaning is to compare the \typicality" of domain elements: x < y means that x is more typical than y. The instances of T(C) are the instances of concept C that are minimal with respect to <. < is further assumed to be well-founded3 (i.e., there is no in nite <-descending chain, so that, if S 6= ;, also min<(S) 6= ;) and, in ranked models, which characterize ALC + TR, < is also assumed to be modular (i.e., for all x; y; z 2 , if x < y then either x < z or z < y). Let us shortly recap the de nition of preferential and ranked models of a nite DL knowledge base K = (T ; A).

De nition 1 (Preferential and ranked interpretations of ALC + T). A preferential interpretation M is any structure M = h ; <; Ii where: is the domain; < is an irre exive, transitive and well-founded relation over . I is an interpretation function that maps each concept name C 2 NC to CI , each role name R 2 NR to RI I I and each individual name a 2 NI to aI 2 . For concepts of ALC, CI is de ned in the usual way in ALC interpetations [ 2 ]. In particular:>I = , ?I = ;, (:C)I = nCI , (C u D)I = CI \ DI , (C t D)I = CI [ DI and (8R:C)I = fx 2 (9R:C)I = fx 2 j for all y 2 j there is a y 2 ; (x; y) 2 RI implies y 2 CI g such that (x; y) 2 RI and y 2 CI g For the T operator, we have (T(C))I = min<(CI ).

When the relation < is modular, I is called a ranked interpretation.

The notion of satis ability of a KB in an interpretation is de ned as usual. Given an ALC interpretation M = h ; <; Ii: - I satis es an inclusion C v D if CI DI ; - I satis es an assertion C(a) if aI 2 CI ; - I satis es an assertion R(a; b) if (aI ; bI ) 2 RI .

De nition 2 (Model of a KB [34]). A preferential (ranked) model of a knowl

edge base K = (T ; A) is a preferential (ranked) interpretation M that satis es all inclusions in T and all assertions in A.

A query F (either an assertion CL(a) or an inclusion relation CL v CR) is preferentially (rationally) entailed by a knowledge base K, written K j=ALC+T F (resp., K j=ALC+TR F ) if F is satis ed in all the models (resp., ranked models) of K. 3 Since ALC + TR has the nite model property, this is equivalent to having the Smoothness Condition, as shown in [ 36 ]. We choose this formulation because it is simpler.

In particular, the de nition of the rational closure for ALC and its semantics in [ 37, 36 ] extends the de nition introduced by Lehmann and Magidor [45] to the language ALC + TR of ALC plus typicality. Roughly speaking T(C) v D holds in the rational closure of K if C is less exceptional than C u :D. We shortly recall this construction of the rational closure of a TBox and we refer to [ 36 ] for full details.

De nition 3 (Exceptionality of concepts and inclusions). Let E be a TBox and C a concept. C is exceptional for E if and only if E j=ALC+TR T(>) v :C. An inclusion T(C) v D is exceptional for E if C is exceptional for E. The set of inclusions which are exceptional for E will be denoted by E(E). Given a TBox T , it is possible to de ne a sequence of non increasing subsets of the TBox T ordered according to the exceptionality of the elements E0 E1 E2 : : : by letting E0 = T and, for i > 0, Ei = E(Ei 1) [ fC v D 2 T s.t. T does not occurr in Cg. Observe that, being knowledge base nite, there is an n 0 such that, for all m > n; Em = En or Em = ;. A concept C has rank i (denoted rank (C) = i) for TBox, i i is the least natural number for which C is not exceptional for Ei. If C is exceptional for all Ei then rank (C) = 1 (C has no rank). The rank of a typicality inclusion T(C) v D is rank (C). The intuition is that, for i < j, Ei contains less speci c defeasible properties then Ej. Consider the following example.

Example 1. Let K be the knowledge base with TBox:

1. T(Student ) v :9has paid :Tax

2.T(Student ) v Young

3. T(EStudent ) v 9has paid :Tax

4. EStudent v Student

stating that typical students have not paid taxes, but typical employed students (which are students) have paid some taxes and that typical students are young. It is possible to see that

E0 = T

E1 = fT(EStudent ) v 9has paid :Tax , EStudent v Student g.

The rank of concept Student is 0, as Student is non-exceptional for E0, while concept EStudent has rank 1, it is exceptional w.r.t. the property that students typically are not taxpayers. The properties of EStudent are more speci c than those of Students.

Rational closure builds on this notion of exceptionality: De nition 4 (Rational closure of TBox). Let K = (T ; A) be a DL knowledge base. The rational closure of TBox is de ned as:

RC(T ) =fT(C) v D 2 T j either rank (C) < rank (C u :D) or rank (C) = 1g [ fC v D 2 T j KB j=ALC+TR C v Dg where C and D are ALC concepts.

In [ 36 ] it is shown that deciding if an inclusion T(C) v D belongs to the rational closure of TBox is a problem in ExpTime and that the semantics corresponding to rational closure can be given in terms of minimal canonical ALC + TR models. In such models the rank of domain elements is minimized to make each domain element as typical as possible. Furthermore, canonical models are considered in which all possible combinations of concepts are represented. We refer to [ 36 ] for a description.

In Example 1, the typicality inclusion T(Student u Italian) v :9has paid :Tax belongs to the rational closure of the TBox, as rank (Student u Italian) = 0 < rank ( Student u Italian u 9has paid :Tax ) = 1. Similarly, T(EStudent u Italian) v 9has paid :Tax belongs to the rational closure.

However, the inclusion T(EStudent ) v Young does not belong to the rational closure. Indeed, the concept EStudent is exceptional for E0, as it violates the defeasible property of students that, normally, they have not paid taxes (T(Student ) v :9has paid : Tax ). For this reason, EStudent does not inherit \any" of the defeasible properties of Student . Indeed, in a language allowing more liberal occurrences of the typicality operator, as the one in [ 38 ] one could have actually inferred that T(EStudent ) v :T(Student ) using preferential (or rational) entailment. 3

Re nements of the rational closure: a comparison

To overcome the weakness of the rational closure, Lehmann introduced the notion of lexicographic closure [46], that has been extended to the description logic ALC by Casini and Straccia in [ 19 ], which strengthens the rational closure by allowing, roughly speaking, a class to inherit as many as possible of the defeasible properties of more general classes, giving preference to the more speci c properties. In the example above, the defeasible property of students of being young should be inherited by employed students, as it is consistent with all other (strict and defeasible) properties of employed students and, by \presumption of independence" [46], even if typicality is lost with respect to one consequent (9has paid :Tax ) we may still presume typicality of EStudent with respect to the property of being

Young .

In Example 1, the set D = f1; 2g of defeasible properties (defaults) from the TBox forms a basis for EStudent . Using Lehmann terminology, a basis D for A is a maximally serious set of defaults whose material counterpart D~ is consistent with A. In our example, following the de nition for ALC in [ 19 ], the materialization of D, D~ = fStudent v Young ; Employee v 9has paid :Tax g, is consistent with EStudent and with the strict part of TBox = fStudent v Young g (i.e., [ D~ 6j= :EStudent ). Since D is the unique set of defaults consistent with EStudent and , D is maximally serious, and is the unique basis for EStudent . Young holds in the basis D, as Young follows from EStudent [ [ D~ . Thus, Young holds in all the basis for EStudent , and (using our notation) the defeasible inclusion T(EStudent ) v Young belongs to the lexicographic closure of the KB.

The notion of seriousness comes into play when there are alternative sets D of consistent defaults. Seriousness of D depends on the ranking of defeasible inclusions in the rational closure. In order to compare alternative sets of defaults, in [46] a seriousness ordering among sets of defaults is de ned by associating with each set of defaults D K a tuple of numbers hn0; n1; : : : ; nkiD, where n0 is the number of defaults in D with rank 1 and, for 1 i k, ni is the number of defaults in D with rank k i (and there is not default with rank k or greater). A modular order among sets of defaults is obtained from the natural lexicographic order over the tuples. This order gives preference to those bases containing more speci c defaults (the highest is the rank, the more speci c is the default). This is essentially the ordering used in [ 19 ] (but for that fact that hidden non-defeasible knowledge is rst moved to the strict part of the KB).

Let us consider the following variant of Example 1.

Example 2. Let K0 be a knowledge base with TBox:

1. T(Student ) v :9has paid :Tax

2. T(Student ) v Young

3. T(Employee) v :Young

4. T(EStudent ) v 9has paid :Tax

5. EStudent v Student u Employee

In the rational closure of K0, concepts Student and Employee have rank 0 and concept EmployedStudent has rank 1. Default 4 has rank 1 and is more speci c than defaults 1, 2 and 3 having rank 0. We want to derive the properties of typical employed students. Clearly, default 4 holds for EStudent , as its rank is 1. The property that typical employed students are taxpayers (default 4), overrides the property that students are typically not taxpayers (default 1). Instead, the two defaults 2 and 3 are each one compatible with with the property that employed students have paid taxes (default 4). In the lexicographic closure there are two alternative bases (sets of defaults) for EStudent , namely, D = f2; 4g and E = f3; 4g, which are not comparable (no one is more serious than the other), while the strict inclusion 5 holds for all bases. In fact, the corresponding tuples h0; 1; 1iD (D contains no default with rank 1, 1 default with rank 1 and 1 default with rank 0) and, similarly, h0; 1; 1iE. As the two tuples are incomparable, neither D E nor E D. As Young does not hold from basis E, in the lexicographic closure one cannot conclude that T(EStudent ) v Young. Similarly, one cannot conclude that T(EStudent ) v :Young.

Concerning Examples 1 and 2 above, similar results can be obtained when reasoning with the MP-closure, with the Skeptical closure and with the logic EDxLaNm.pNleo2nethoef tlohgeimc ocfaonvceorrnidcliundgeDtLhaNt tynpdiscaoluetmthpalotytehdersetuidseantcsonareictyobuentwg.eeInn the defaults 2 and 3, none of which is overridden by more speci c properties. In this case the prototype of concept EStudent is said to be inconsistent.

In Example 2 the MP-closure and the Skeptical closure, as the lexicographic closure, silently eliminate the con ict and neither infer that typical employed students are young, nor that they are not young. In particular, the MP-closure is a variant of the lexicographic closure which has been studied in [ 29 ], and exploits a di erent lexicographic ordering with respect to the one considered by the lexicographic closure. It compares two sets of defaults D and E by considering the tuples of the sets of defaults with di erent ranks rather than the tuples of their cardinality. The natural lexicographic order to compare such tuples of sets exploits strict subset inclusion, and the resulting seriousness ordering among sets of defaults is a strict partial order, but is not modular in general.

In Example 1, there is a single basis in the MP-closure as in the lexicographic closure, as there is a single set of defaults consistent with EStudent (and with the strict inclusions). In Example 2, the two sets D = f2; 4g and E = f3; 4g are incomparable, as neither h;f4g; f2giD is less serious than h;; f4g; f3giE , nor vice-versa. Hence D and E are both bases of the MP-closure and, as in the lexicographic closure, we can neither conclude that T(EStudent ) v Young nor that T(EStudent ) v :Young.

In this same example, the minimal relevant closure [ 14 ] would neither conclude that T(EStudent ) v Young nor that T(EStudent ) v :Young. There are two EStudent -justi cations w.r.t. K0, namely J 1 = f1; 4g and J 2 = f2; 3g. Hence, J m1in = f1g and J m2in = f2; 3g. In particular, both defaults 2 and 3 are relevant for determining the subsumption T(EStudent ) v Young, and both of them are eligible for removal.4 Example 3. Consider the case when the TBox in Example 2 is extended with an additional defeasible inclusion

6. T(Student ) v Bright .

In this case, in both the lexicographic closure and the MP-closure, there are two bases for concept EStudent , D0 = f2; 4; 6g and E0 = f3; 4; 6g, and default 6 belongs to both them. Hence, in both the lexicographic closure and the MP-closure we would conclude that typical employed students are bright, i.e. T(EStudent ) v Bright . This conclusion would not be obtained in DLN , where the prototype of concept EStudent is inconsistent, as before. In the Skeptical closure, the defaults with rank 0 in the two bases, namely D00 = f2; 6g and E00 = f3; 6g are con icting. Hence they are all discarded when constructing the single basis for EStudent , and T(EStudent ) v Bright cannot be concluded as well.

With the approach in [ 14 ], T(EStudent ) v Bright would belong to the minimal relevant closure of the KB, as the defeasible subsumption 6 is not potentially relevant for resolving the con ict among the other defaults for concept EStudent . To see the di erence between the MP-closure and the lexicographic closure, consider the following variant of Example 2: Example 4. Let the TBox be: 4 Using the notation in [ 14 ], defeasible subsumptions would be written C@D rather than T(C) v D, but they rely on the same ranked semantics. e

1. T(Student ) v :9has paid :Tax

2. T(Student ) v Young

3. T(Employee) v :Young ^ 9has paid :Tax

4. T(EStudent ) v Graduate in 4Years

5. EStudent v Student u Employee

Now, defaults 1, 2 and 3 have rank 0 in the rational closure, while default 4 has rank 1. We have still two alternative bases in the MP-closure, f1; 2; 4g and f3; 4g, but there is a single base f1; 2; 4g in the lexicographic closure. The reason is that in the lexicographic order, the set D = f1; 2; 4g (with the associated tuple h0; 1; 2iD) is more serious than E = f3; 4g (with the associated tuple h0; 1; 1iE ) as both bases contain 1 default with rank 1, but D contains two defaults with rank 0, while E contains just one. From the lexicographic closure one can then conclude that T(EStudent ) v Young ^ :9has paid : Tax .

In the MP-closure, instead, the two bases are not comparable as none of the tuples of sets of defaults h;; f4g; f1; 2gi and h;; f4g; f3gi is more serious than the other one, as the two sets of defaults with rank 0, f1; 2g and f3g, are not comparable using subset inclusion.

In this example, the basic relevant closure and the minimal relevant closure would not be able to conclude that T(EStudent ) v :Young, as well. In fact, there are two EStudent -justi cations w.r.t. the KB above namely J 1 = f1; 3g and J 2 = f2; 3g, both of them containing only defaults with rank 0. Hence, J m1in = J 1 and J m2in = J 2. In particular, defaults 1, 2 and 3 are all relevant for determining the subsumption T(EStudent ) v :Young, and all eligible for removal. In this last example the lexicographic closure appears to be too bold, as the reason to accept that typical employed students are not young and have paid taxes may be disputable. Notice also that if we replace default 3 with two defaults

T(Employee) v :Young

T(Employee) v 9has paid :Tax

there would be two bases in the lexicographic closure, and one would not conclude any more that typical employed students are young and have not paid taxes. The MP-closure and the relevant closure are more cautious (and less syntax dependent in this example). In particular, both formulations of Example 4 there are two bases in the MP-closure and nothing can be concluded about typical employed students being young or paying taxes. Similarly, in the relevant closure.

In the Skeptical closure, the set of defaults with rank 0 which are not overridden by more speci c defaults is f1; 2; 3g, but they are altogether incompatible with EStudent and with the strict inclusion 5. Hence, nothing can be concluded about typical employed students except that they graduate in 4 years. In DLN the prototype of concept EStudent is found to be inconsistent, as there are con icting non overridden defaults 1; 2 and 3.

Conclusions and related work

In this paper we have compared the behavior of some re nements of the rational closure, namely the Lexicographic closure [ 46, 19 ], the Relevant closure [ 14 ], the MP-closure [ 29 ] and the Skeptical [ 28 ] closure, through some examples. We have also considered for comparison the logic DLN , proposed by Bonatti et al. in [ 8 ], which captures a form of \inheritance with overriding": a defeasible inclusion is inherited by a more speci c class if it is not overridden by more speci c (con icting) properties. The logic DLN is not necessarily applied starting from the ranking given by the rational closure but, when it does, it provides another approach to deal with the problem of inheritance blocking in the rational closure.

The multi-preference closure (or MP-closure) was rst introduced in [ 30 ] as a sound approximation of Gliozzi's multi-preference semantics [ 39 ]. As the lexicographic closure, it builds over the rational closure but it de nes a preferential, not necessarily ranked, semantics, using a di erent lexicographic order to compare sets of defaults. A semantic characterization of the MP-closure for the description logic ALC was developed in [ 29 ] using bi-preferential (BP) interpretations, preferential interpretations developed along the lines of the preferential semantics introduced by Kraus, Lehmann and Magidor [44, 45], but containing two preference relations, the rst one <1 playing the role of the ranked preference relations in the models of the RC, and the second one <2 representing a preferential re nement of <1. The skeptical closure [ 28 ] was shown to be a weaker variant of the MP-closure in [ 29 ].

The relevant closure [ 14 ] is based on the idea of relevance of subsumptions to a query, to overcome the limitation of the weakness of rational closure. Relevance is determined based on justi cations and, in minimal relevant closure, the idea is that subsumptions with lower ranks are removed rst. It was shown by Casini et al. [ 14 ] that the relevant closure is a weaker closure than the lexicographic closure. In [ 31 ] it was proved that, in the propositional case, the basic and the minimal relevant closure are weaker than the MP-closure, which, in turn, is weaker than the lexicographic closure.

Another re nement of the rational closure, which also deals with this limitation of the rational closure, is the inheritance-based rational closure in [ 18, 20 ], a closure construction which is de ned by combining the rational closure with defeasible inheritance networks.

Fernandez Gil in [ 26 ] developed a multi-typicality version of the typicality logic ALC + Tmin [ 35 ], another defeasible description logic based on preferential extension of ALC with typicality, which, di erently from the rational closure, is not based on the ranked models semantics but, nevertheless, su ers from the blocking of property inheritance problem. [ 26 ] provides a solution to this problem for ALC + Tmin, considering a language with multiple typicality operators.

Other approaches in the literature deal with the problem of inheritance with exceptions. For instance, Bozzato et al. in [ 11 ] present an extension of the CKR framework in which defeasible axioms are allowed in the global context and can be overridden by knowledge in a local context. Exceptions have to be justi ed in terms of semantic consequence. A translation of extended CHRs (with knowledge bases in SROIQ-RL) into Datalog programs under the answer set semantics is also de ned.

Concerning the multipreference semantics introduced in [ 39 ] to provide a semantic strengthening of the rational closure, we have proved in [ 30 ] that the MP-closure provides a sound approximation of such a semantics. As a consequence of the fact that the skeptical closure is weaker than the MP-closure, the skeptical closure is still a sound (a weaker) approximation for the multipreference semantics.

The relationships among the above variants of rational closure for DLs and the notions of rational closure for DLs developed in the contexts of fuzzy logic [ 21 ] and probabilistic logics [47] are also worth being investigated. In the propositional logic case, it has been shown in [ 5 ] that KLM preferential logics and the rational closure [44, 45], the probabilistic approach [ 1 ], the system Z [50], the possibilistic approach [ 6, 5 ] are all related with each other, and another related approach is that of c-representations [42]. Similar relations might be expected to hold among the non-monotonic extensions of description logics as well.

Although the skeptical closure has been de ned based on the preferential extension of ALC, the same construction could be adopted for more expressive description logics, provided that the rational closure can be consistently de ned for the knowledge base under consideration [ 32 ]. Indeed, for a KB in an expressive DL, the consistency of rational closure is not guaranteed and, from the semantic point of view, the knowledge base might have no canonical models. Partial solutions to this problem have been considered in [ 38, 22 ] for the low complexity logics in the E L family, and a notion of stable rational closure is proposed in [ 7 ] to extend the rational closure to a wider class of expressive description logics, which do not satisfy the disjoint model union property.

Acknowledgement: This research is partially supported by INDAM-GNCS Project 2019 \METALLIC #2: METodi di prova per il ragionamento Automatico per Logiche non-cLassIChe". 42. G. Kern-Isberner. Conditionals in Nonmonotonic Reasoning and Belief Revision Considering Conditionals as Agents, volume 2087 of Lecture Notes in Computer Science. Springer, 2001. 43. M. Knorr, P. Hitzler, and F. Maier. Reconciling owl and non-monotonic rules for the semantic web. In ECAI 2012, page 474{479, 2012. 44. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Arti cial Intelligence, 44(1-2):167{207, 1990. 45. D. Lehmann and M. Magidor. What does a conditional knowledge base entail?

Arti cial Intelligence, 55(1):1{60, 1992. 46. D. J. Lehmann. Another perspective on default reasoning. Ann. Math. Artif. Intell., 15(1):61{82, 1995. 47. T. Lukasiewicz. Expressive probabilistic description logics. Artif. Intell., 172:852{ 883, 2008. 48. K. Moodley. Practical Reasoning for Defeasible Description Logics. PhD Thesis,

University of Kwazulu-Natal, 2016. 49. B. Motik and R. Rosati. Reconciling Description Logics and rules. Journal of the

ACM, 57(5), 2010. 50. J. Pearl. System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In R. Parikh, editor, TARK (3rd Conference on Theoretical Aspects of Reasoning about Knowledge), pages 121{135, Paci c Grove, CA, USA, 1990. Morgan Kaufmann. 51. M. Pensel and A. Turhan. Reasoning in the defeasible description logic EL? - computing standard inferences under rational and relevant semantics. Int. J. Approx. Reasoning, 103:28{70, 2018.

References

1. E.W. Adams . The logic of conditionals . D. Reidel, Dordrecht, 1975 .

2. F. Baader , D. Calvanese , D.L. McGuinness , D. Nardi , and P.F. Patel-Schneider. The Description Logic Handbook - Theory , Implementation, and Applications, 2nd edition . Cambridge, 2007 .

3. F. Baader and B. Hollunder . Embedding defaults into terminological knowledge representation formalisms . J. Autom. Reasoning , 14 ( 1 ): 149 { 180 , 1995 .

4. F. Baader and B. Hollunder. Priorities on defaults with prerequisites, and their application in treating speci city in terminological default logic . Journal of Automated Reasoning (JAR) , 15 ( 1 ): 41 { 68 , 1995 .

5. S. Benferhat , D. Dubois , and H. Prade . Nonmonotonic reasoning, conditional objects and possibility theory . Arti cial Intelligence , 92 ( 1-2 ): 259 { 276 , 1997 .

6. Salem Benferhat , Didier Dubois, and Henri Prade. Representing default rules in possibilistic logic . In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR'92) . Cambridge, MA, October 25 - 29 , 1992 ., pages 673 { 684 , 1992 .

7. P. A. Bonatti . Rational closure for all description logics . Artif . Intell., 274 : 197 { 223 , 2019 .

8. P. A. Bonatti , M. Faella , I. Petrova , and L. Sauro . A new semantics for overriding in description logics . Artif . Intell., 222 :1{ 48 , 2015 .

9. P. A. Bonatti , C. Lutz , and F. Wolter . The Complexity of Circumscription in DLs . Journal of Arti cial Intelligence Research (JAIR) , 35 : 717 { 773 , 2009 .

10. P. A. Bonatti and L. Sauro . On the logical properties of the nonmonotonic description logic dln . Artif . Intell., 248 : 85 { 111 , 2017 .

11. L. Bozzato , T. Eiter , and L. Sera ni. Enhancing context knowledge repositories with justi able exceptions . Artif . Intell., 257 : 72 { 126 , 2018 .

12. G. Brewka. The logic of inheritance in frame systems . In Proceedings of the 10th International Joint Conference on Arti cial Intelligence . Milan, Italy, August 23-28 , 1987 , pages 483 { 488 , 1987 .

13. Katarina Britz , Johannes Heidema, and Thomas Meyer. Semantic preferential subsumption . In G. Brewka and J. Lang, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 11th International Conference (KR 2008 ), pages 476 { 484 , Sidney , Australia, September 2008 . AAAI Press.

14. G. Casini, T. Meyer, K. Moodley, and R. Nortje . Relevant closure: A new form of defeasible reasoning for description logics . In JELIA 2014, LNCS 8761 , pages 92 { 106 . Springer, 2014 .

15. G. Casini, T. Meyer, K. Moodley, U. Sattler , and I.J. Varzinczak . Introducing defeasibility into OWL ontologies . In The Semantic Web - ISWC 2015 - 14th International Semantic Web Conference , Bethlehem, PA, USA, October 11 - 15 , 2015 , Proceedings, Part II , pages 409 { 426 , 2015 .

16. G. Casini, T. Meyer, I. J. Varzinczak , , and K. Moodley . Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox . In DL 2013 , 26th International Workshop on Description Logics, volume 1014 of CEUR Workshop Proceedings , pages 600 { 615 . CEUR-WS.org, 2013 .

17. G. Casini and U. Straccia . Rational Closure for Defeasible Description Logics . In T. Janhunen and I. Niemela, editors, Proceedings of the 12th European Conference on Logics in Arti cial Intelligence (JELIA 2010 ), volume 6341 of Lecture Notes in Arti cial Intelligence , pages 77 { 90 , Helsinki, Finland, September 2010 . Springer.

18. G. Casini and U. Straccia . Defeasible Inheritance-Based Description Logics . In Toby Walsh, editor, Proceedings of the 22nd International Joint Conference on Arti cial Intelligence (IJCAI 2011 ), pages 813 { 818 , Barcelona , Spain, July 2011 . Morgan Kaufmann.

19. G. Casini and U. Straccia . Lexicographic Closure for Defeasible Description Logics . In Proc. of Australasian Ontology Workshop , vol. 969 , pages 28 { 39 , 2012 .

20. G. Casini and U. Straccia . Defeasible inheritance-based description logics . Journal of Arti cial Intelligence Research (JAIR) , 48 : 415 { 473 , 2013 .

21. G. Casini and U. Straccia . Towards rational closure for fuzzy logic: The case of propositional godel logic . In Logic for Programming , Arti cial Intelligence, and Reasoning - 19th International Conference, LPAR-19 , Stellenbosch, South Africa, December 14-19 , 2013 . Proceedings, pages 213 { 227 , 2013 .

22. G. Casini, U. Straccia , and T. Meyer. A polynomial time subsumption algorithm for nominal safe ELO under rational closure . Inf. Sci. , 2019 . in press. ?

23. 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 .

24. T. Eiter, G. Ianni, T. Lukasiewicz , and R. Schindlauer . Well-founded semantics for description logic programs in the semantic web . ACM Trans. Comput. Log. , 12 ( 2 ): 11 , 2011 .

25. T. Eiter, G. Ianni, T. Lukasiewicz , R. Schindlauer , and H. Tompits . Combining answer set programming with description logics for the semantic web . Artif . Intell., 172 ( 12 -13): 1495 { 1539 , 2008 .

26. Oliver Fernandez Gil. On the Non-Monotonic Description Logic ALC+Tmin . CoRR, abs/1404.6566, 2014 .

27. L. Giordano . Reasoning about exceptions in ontologies: a skeptical preferential approach (extended abstract) . In Joint Proceedings of the 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic , Naples, Italy, September 26-28 , 2017 , volume 1949 of CEUR Workshop Proceedings , pages 6 { 10 , 2017 .

28. L. Giordano and V. Gliozzi . Reasoning about exceptions in ontologies: from the lexicographic closure to the skeptical closure . In Proceedings of the Second Workshop on Logics for Reasoning about Preferences , Uncertainty, and Vagueness, PRUV@IJCAR 2018 , Oxford, UK, July 19th , 2018 .

29. L. Giordano and V. Gliozzi . Reasoning about exceptions in ontologies: from the lexicographic closure to the skeptical closure . CoRR , abs/ 1807 .02879, 2018 .

30. L. Giordano and V. Gliozzi . Reasoning about multiple aspects in DLs: Semantics and closure construction . CoRR , abs/ 1801 .07161, 2018 .

31. L. Giordano and V. Gliozzi . A reconstruction of the multipreference closure . CoRR , abs/ 1905 .03855, 2019 .

32. L. Giordano , V. Gliozzi , and N. Olivetti . Towards a rational closure for expressive description logics: the case of SHIQ . Fundam. Inform., 159 ( 1-2 ): 95 { 122 , 2018 .

33. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Preferential Description Logics . In Nachum Dershowitz and Andrei Voronkov, editors, Proceedings of LPAR 2007 ( 14th Conference on Logic for Programming , Arti cial Intelligence, and Reasoning) , volume 4790 of LNAI , pages 257 { 272 , Yerevan , Armenia, October 2007 . Springer-Verlag.

34. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . ALC+ T: a preferential extension of Description Logics . Fundamenta Informaticae , 96 :1{ 32 , 2009 .

35. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . A NonMonotonic Description Logic for Reasoning About Typicality . Arti cial Intelligence , 195 : 165 { 202 , 2013 .

36. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Semantic characterization of rational closure: From propositional logic to description logics . Arti cial Intelligence , 226 :1{ 33 , 2015 .

37. L. Giordano , V. Gliozzi , N. Olivetti , and G.L. Pozzato . Minimal Model Semantics and Rational Closure in Description Logics . In 26th International Workshop on Description Logics (DL 2013 ), volume 1014 , pages 168 { 180 , 7 2013 .

38. L. Giordano and D. Theseider Dupre . ASP for minimal entailment in a rational extension of SROEL . TPLP, 16 ( 5-6 ): 738 { 754 , 2016 . DOI: 10 .1017/S1471068416000399.

39. V. Gliozzi . Reasoning about multiple aspects in rational closure for dls . In Proc. AI*IA 2016 - XVth International Conference of the Italian Association for Arti cial Intelligence , Genova, Italy, November 29 - December 1 , 2016 , pages 392 { 405 , 2016 .

40. G. Gottlob, A. Hernich , C. Kupke , and T. Lukasiewicz . Stable model semantics for guarded existential rules and description logics . In Proc. KR 2014 , 2014 .

41. P. Ke and U. Sattler . Next Steps for Description Logics of Minimal Knowledge and Negation as Failure . In F. Baader, C. Lutz , and B. Motik, editors, Proceedings of Description Logics , volume 353 of CEUR Workshop Proceedings , Dresden, Germany, May 2008 . CEUR-WS.org .