Reasoning about exceptions in ontologies is nowadays one of the challenges the description logics community is facing, a challenge which is at the very roots of the development of non-monotonic reasoning in the 80s. Many non-monotonic extensions of Description Logics (DLs) have been developed incorporating non-monotonic features from most of the non-monotonic formalisms in the literature [1,10,12,19,5,4,7,24,11,3,20,6,18,15,16], or defining new constructions and semantics such as in [2].
The abstract describes a preferential approach for dealing with exceptions in description logics [14], where a typicality operator is used to select the typical (or most preferred) instances of a concept. This approach, as well as the preferential approach in [5], has been developed along the lines of the preferential semantics introduced by Kraus, Lehmann and Magidor [21,22].
We focus on the rational closure for DLs [7,9,6,16] and, in particular, on the construction developed in [16], which is semantically characterized by minimal preferential models. While the rational closure provides a simple and efficient approach for reasoning with exceptions, exploiting polynomial reductions to standard DLs [13], the rational closure does not allow an independent handling of the inheritance of different defeasible properties of concepts so that, if a subclass of C is exceptional for a given aspect, it is exceptional tout court and does not inherit any of the typical properties of C.
To cope with this problem Lehmann [23] introduced the notion of the lexicographic closure, which was extended to DLs by Casini and Straccia [8], while in [17] Gliozzi proposed a semantic approach in which models are equipped with several preference relations. The lexicographic closure allows for stronger inferences with respect to rational closure, computing the defeasible consequences in the lexicographic closure may require to compute several alternative bases [23](namely, consistent sets of defeasible inclusions which are maximal with respect to some specificity ordering).
In this extendedabstract we propose an alternative notion of closure, the skeptical closure, which can be regarded as a skeptical variant of the lexicographic closure. It is a refinement of rational closure which allows for stronger inferences, but it is weaker than the lexicographic closure and its computation does not require to generate all the alternative maximally consistent bases. The construction is based on the idea of building a single base, i.e. a single maximal consistent set of defeasible inclusions, starting with the defeasible inclusions with highest rank and progressively adding less specific inclusions, if consistent, but excluding the defeasible inclusions which produce a conflict at a certain stage without considering alternative consistent bases.
We briefly recall the logic ALC + T R which is at the basis of a rational closure construction proposed in [16] for ALC. The idea underlying ALC + T R is that of extending the standard ALC with concepts of the form T(C), whose intuitive meaning is that T(C) selects the typical instances of a concept C, to distinguish between the properties that hold for all instances of concept C (C ⊑ D), and those that only hold for the typical such instances (T(C) ⊑ D). The ALC + T R language is defined as follows:
where A is a concept name and R a role name. A KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusions C L ⊑ C R . ABox contains a finite set of assertions of the form C R (a) and aRb, for a, b individual names. The semantics of ALC + T R is defined in terms of rational models: 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 <. We refer to [16] for a detailed description of the semantics and we denote by
In [16] the rational closure construction has been defined for ALC + T R , extending to DLs the notion of rational closure introduced by Lehmann and Magidor [22]. The definition is based on the notion of exceptionality. Roughly speaking T(C) ⊑ D holds in the rational closure of K if C is less exceptional than C ⊓ ¬D. We shortly recall this construction of the rational closure of a TBox and we refer to [16] for full details.
The set of inclusions in TBox which are exceptional for E will be denoted by E(E).
Given a TBox, it is possible to define a sequence of non increasing subsets of TBox ordered according to the exceptionality of the elements E 0 ⊇ E 1 ⊇ E 2 . . . by letting E 0 = TBox and, for i > 0, E i = E(E i−1 ) ∪ {C ⊑ D ∈ TBox s.t. T does not occurr in C}. Observe that, being KB finite, there is an n ≥ 0 such that, for all m > n, E m = E n or E m = ∅. A concept C has rank i (denoted rank (C) = i) for TBox, iff i is the least natural number for which C is not exceptional for E i . If C is exceptional for all E i then rank (C) = ∞ (C has no rank). Rational closure builds on this notion of exceptionality: Definition 2 (Rational closure of TBox). Let KB = (TBox, ABox) be a DL knowledge base. The rational closure of TBox is defined as:
Exploiting the fact that entailment in ALC + T R can be polynomially encoded into entailment in ALC, it is easy to see that deciding if an inclusion T(C) ⊑ D belongs to the rational closure of TBox is a problem in EXPTIME [16]. expected, to the rational closure of K, as being Italian is irrelevant with respect to being or not a typical student. However, we cannot conclude that T(Student ) ⊑ Y oung: concept WStudent is exceptional w.r.t. Student concerning the property of paying taxes and, hence, it does not inherit any defeasible property of Student.
In the example above the rational closure is too weak to infer that typical working students, as typical student, are young. The lexicographic closure [23] strengthens the rational closure and allows to conclude that typical working students are young. The property of typical students of being toung is inherited by working students, as it is consistent with all the other (strict or defeasible) properties of working students.
3 From the lexicographic to the skeptical closure Given a concept B, one wants to identify the defeasible properties of the B-elements. Assume that the rational closure of the knowledge base K has already been constructed and that k is the rank of concept B in the rational closure. The typical B elements are clearly compatible with all the defeasible inclusions in E k , but they might satisfy further defeasible inclusions with lower ranks, i.e. those included in E 0 , E 1 , . . . , E k−1 . In general, there may be alternative maximal sets of defeasible inclusions compatible with B, among which one would prefer those that maximize the number of defeasible inclusions with higher rank. This is indeed what is done by the lexicographic closure [23], which considers alternative maximally preferred sets of defaults called "bases", which, roughly speaking, maximize the number of defaults of higher ranks with respect to those lower ranks (degree of seriousness), and where situations which violate a number of defaults with a certain rank are considered to be less plausible than situations which violates a lower number of defaults with the same rank. In general, there may be exponentially many alternative sets of defeasible inclusions (bases) which are maximal and consistent for a given concept, and the lexicographic closure has to consider all of them to check if a defeasible inclusion is accepted. Instead, in the following, we aim at defining a construction which skeptically builds a single set of defeasible inclusions compatible with B.
Let S B be the set of typicality inclusions T(C) ⊑ D in K which are individually compatible with B (with respect to E k ), that is
When compatible with B, S B is the unique maximal basis with respect to the seriousness ordering [23]. Let δ(E i ) denote the set of defeasible inclusions in E i . When S B is not compatible with B, we cannot use the defeasible inclusions in S B to derive conclusions about typical B elements. In this case, we can either use just the defeasible inclusions in E k , as in the rational closure, or we can additionally use all the defeasible inclusions in S B k−1 ∈ δ(E k−1 ), with rank k − 1, provided they are compatible with B and E k and, possibly, we can add all the defeasible inclusions in S B k−2 ∈ δ(E k−2 ) (with rank k − 2) provided they are compatible with B, E k and S B k−1 , and so on for lower ranks. This leads to the construction below. For each rank j of the rational closure construction, let S B j be a set of the defeasible inclusions in E j as follows:
j is the set of the defeasible inclusions with rank j, which are not (individually) overridden by defeasible inclusions with higher ranks (from j + 1 to k). Definition 3. Let B be a concept such that rank (B) = k. We define the skeptical closure S sk,B of B as follows:
Intuitively, S sk,B contains, for each rank j, all the defeasible inclusions having rank j which are compatible with B and with the more specific defeasible inclusions (with rank > j). As S B h−1 is not included in the skeptical closure,
, the set S B h−1 contains conflicting defeasible inclusions which are not overridden by more specific ones. The inclusions in S B h−1 (and, similarly, all the defeasible inclusions with rank lower than h − 1) are not added to the skeptical closure of B. Let us now define when a defeasible inclusion is derivable from the skeptical closure of a TBox. The identification of the defeasible inclusions in S sk,B requires a number of entailment checks which is linear in the number of defeasible inclusions in TBox. In Example 1 the inclusion T(WStudent ) ⊑ Young is derivable from the skeptical closure of TBox, as WStudent has rank 1 and inclusion T(Student ) ⊑ Young in E 0 is compatible with WStudent. No other inclusions in δ(E 0 ) are compatible with E 1 . Instead, the inclusion T(WStudent ) ⊑ Young is not derivable from the skeptical closure of the KB K ′ = {T(Student ) ⊑ ¬Pay Taxes, T(Worker ) ⊑ Pay Taxes, T(Student ) ⊑ Young, WStudent ⊑ Student ⊓ Worker }. as S WStudent 0 is not compatible with WStudent (w.r.t. E 1 ), due to the conflicting defaults concerning tax payment for Worker and Student (both with rank 0). Hence, the defeasible property that typical students are young is not inherited by typical working students.
Notice that, the property that typical working students are young is accepted in the lexicographic closure of K ′ , as there are two bases (the one including T(Student ) ⊑ ¬Pay Taxes and the other T(Worker ) ⊑ Pay Taxes), both containing T(Student ) ⊑ Young. The skeptical closure is indeed weaker than the lexicographic closure. Also, while in the logic DL N [2], given the knowledge base K ′ , the concept WStudent has an inconsistent prototype, in the skeptical closure one cannot conclude that T(WStudent) ⊑ ⊥ and, using the terminology in [2], the conflict is "silently removed". In this respect, the skeptical closure appears to be weaker than DL N , although it shares with DL N (and with lexicographic closure) a notion of overriding. Detailed comparisons and the study of the semantics underlying the skeptical closure will be subject of future work.