Reasoning about exceptions in ontologies: a skeptical preferential approach (Extended Abstract) Laura Giordano DISIT, University of Piemonte Orientale “Amedeo Avogadro” - Italy - laura.giordano@uniupo.it 1 Introduction Reasoning about exceptions in ontologies is nowadays one of the challenges the de- scription logics community is facing, a challenge which is at the very roots of the de- velopment 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 de- scription 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 con- struction developed in [16], which is semantically characterized by minimal preferential models. While the rational closure provides a simple and efficient approach for reason- ing with exceptions, exploiting polynomial reductions to standard DLs [13], the rational closure does not allow an independent handling of the inheritance of different defeasi- ble 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 ratio- nal 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 alter- native 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 inclu- sions, if consistent, but excluding the defeasible inclusions which produce a conflict at a certain stage without considering alternative consistent bases. Laura Giordano 2 The rational closure We briefly recall the logic ALC + TR which is at the basis of a rational closure con- struction proposed in [16] for ALC. The idea underlying ALC + TR is that of extend- ing 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 proper- ties 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 + TR language is defined as fol- lows: CR := A | ⊤ | ⊥ | ¬CR | CR ⊓ CR | CR ⊔ CR | ∀R.CR | ∃R.CR , and CL := CR | T(CR ), 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 CL ⊑ CR . ABox con- tains a finite set of assertions of the form CR (a) and aRb, for a, b individual names. The semantics of ALC + TR 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 |=ALC+TR entailment in ALC + TR . In [16] the rational closure construction has been defined for ALC + TR , 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. Definition 1 (Exceptionality of concepts and inclusions). Let E be a TBox and C a concept. C is exceptional for E if and only if E |=ALC+TR T(⊤) ⊑ ¬C. An inclusion T(C) ⊑ D is exceptional for E if C is exceptional for E. 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 E0 ⊇ E1 ⊇ E2 . . . by letting E0 = TBox and, for i > 0, Ei = E(Ei−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, Em = En or Em = ∅. 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 Ei . If C is exceptional for all Ei 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 knowl- edge base. The rational closure of TBox is defined as: TBox = {T(C) ⊑ D | either rank (C) < rank (C ⊓ ¬D) or rank (C) = ∞} ∪ {C ⊑ D | KB |=ALC+TR C ⊑ D}, where C and D are ALC concepts. Exploiting the fact that entailment in ALC + TR 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 E XP T IME [16]. Example 1. Let K = {T(Student ) ⊑ ¬Pay Taxes, T(WStudent ) ⊑ Pay Taxes, T(Student ) ⊑ Young, WStudent ⊑ Student} be a knowledge base stating that typ- ical students do not pay taxes, but typical working students (which are students) do pay Reasoning about exceptions in ontologies taxes and that typical students are young. It is possible to see that E0 = {T(Student ) ⊑ ¬Pay Taxes, T(Student ) ⊑ Young, WStudent ⊑ Student }, E1 = {T(WStudent ) ⊑ Pay Taxes, WStudent ⊑ Student} and that the defeasible inclusions T(Student ⊓ Italian) ⊑ ¬Pay Taxes and T(WStudent ⊓ Italian) ⊑ Pay Taxes both belong, as 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 : con- cept 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 Ek , but they might satisfy further defeasible inclusions with lower ranks, i.e. those included in E0 , E1 , . . . , Ek−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 num- ber 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 Ek ), that is S B = {T(C) ⊑ D ∈ TBox | Ek ∪ {T(C) ⊑ D} 6|=ALC+TR T(⊤) ⊑ ¬B}. Clearly, although each defeasible inclusion in S B is compatible with B, it might be the case that overall set S B is not compatible with B, i.e., Ek ∪S B |=ALC+TR T(⊤) ⊑ ¬B. When compatible with B, S B is the unique maximal basis with respect to the seri- ousness ordering [23]. Let δ(Ei ) denote the set of defeasible inclusions in Ei . 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 Ek , as in the rational closure, or we can additionally use all the defeasible B inclusions in Sk−1 ∈ δ(Ek−1 ), with rank k − 1, provided they are compatible with B Laura Giordano B and Ek and, possibly, we can add all the defeasible inclusions in Sk−2 ∈ δ(Ek−2 ) (with B rank k − 2) provided they are compatible with B, Ek and Sk−1 , and so on for lower ranks. This leads to the construction below. For each rank j of the rational closure con- struction, let SjB be a set of the defeasible inclusions in Ej as follows: SjB = {T(C) ⊑ B B B D ∈ δ(Ej ) | Ek ∪ Sk−1 ∪ Sk−2 ∪ . . . ∪ Sj+1 ∪ {T(C) ⊑ D} 6|=ALC+TR T(⊤) ⊑ ¬B} B Informally, Sj is the set of the defeasible inclusions with rank j, which are not (indi- vidually) 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: S sk,B = Ek ∪ Sk−1 B B ∪ Sk−2 ∪ . . . ∪ ShB , where h is the least integer j such that 0 ≤ j ≤ k − 1 and Ek ∪ Sk−1 ∪ Sk−2 ∪ . . . ∪ SjB 6|=ALC+TR B B T(⊤) ⊑ ¬B, if such a j exists; S sk,B = Ek , otherwise. 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 B B B rank > j). As Sh−1 is not included in the skeptical closure, Ek ∪ Sk−1 ∪ Sk−2 ∪...∪ B B Sh ∪ Sh−1 |=ALC+TR T(⊤) ⊑ ¬B i.e., the set Sh−1 contains conflicting defeasible B inclusions which are not overridden by more specific ones. The inclusions in Sh−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. Definition 4. Let T(B) ⊑ D be a query and let k = rank (B) be the rank of concept B in the rational closure. T(B) ⊑ D is derivable from the skeptical closure of TBox if S sk,B |=ALC+TR T(⊤) ⊑ (¬B ⊔ D). The identification of the defeasible inclusions in S sk,B requires a number of entail- ment checks which is linear in the number of defeasible inclusions in TBox. In Ex- ample 1 the inclusion T(WStudent ) ⊑ Young is derivable from the skeptical clo- sure of TBox, as WStudent has rank 1 and inclusion T(Student ) ⊑ Young in E0 is compatible with WStudent. No other inclusions in δ(E0 ) are compatible with E1 . 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 S0WStudent is not com- patible with WStudent (w.r.t. E1 ), due to the conflicting defaults concerning tax pay- ment 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 DLN [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 DLN , although it shares with DLN (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. Reasoning about exceptions in ontologies 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. P. A. Bonatti, M. Faella, I. Petrova, and L. Sauro. A new semantics for overriding in descrip- tion logics. Artif. Intell., 222:1–48, 2015. 3. P. A. Bonatti, M. Faella, and L. Sauro. Defeasible inclusions in low-complexity dls. J. Artif. Intell. Res. (JAIR), 42:719–764, 2011. 4. P. A. Bonatti, Carsten Lutz, and Frank Wolter. The Complexity of Circumscription in DLs. Journal of Artificial Intelligence Research (JAIR), 35:717–773, 2009. 5. K. Britz, J. Heidema, and T. Meyer. Semantic preferential subsumption. KR 2008, pages 476–484, Sidney, Australia, September 2008. AAAI Press. 6. G. Casini, T. Meyer, I. J. Varzinczak, , and K. Moodley. Nonmonotonic Reasoning in De- scription Logics: Rational Closure for the ABox. DL 2013, CEUR, vol. 1014, pp. 600–615. 7. G. Casini and U. Straccia. Rational Closure for Defeasible Description Logics. JELIA 2010, volume 6341 of LNCS, pages 77–90, Helsinki, Finland, September 2010. Springer. 8. G. Casini and U. Straccia. Lexicographic Closure for Defeasible Description Logics. In Proc. of Australasian Ontology Workshop, vol.969, pages 28–39, 2012. 9. G. Casini and U. Straccia. Defeasible inheritance-based description logics. Journal of Artifi- cial Intelligence Research (JAIR), 48:415–473, 2013. 10. 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. 11. T. Eiter, G. Ianni, T. Lukasiewicz, and R. Schindlauer. Well-founded semantics for descrip- tion logic programs in the semantic web. ACM Trans. Comput. Log., 12(2):11, 2011. 12. 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. 13. L. Giordano and V. Gliozzi. Encoding a preferential extension of the description logic SROIQ into SROIQ. In Proc. ISMIS 2015, volume 9384 of LNCS, pages 248–258. Springer, 2015. 14. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Preferential Description Logics. of LPAR 2007, volume 4790 of LNAI, pages 257–272, Yerevan, Armenia, October 2007. 15. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. A NonMonotonic Description Logic for Reasoning About Typicality. Artificial Intelligence, 195:165–202, 2013. 16. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Semantic characterization of rational closure: from propositional logic to description logics. Artif. Intell., 226:1–33, 2015. 17. V. Gliozzi. A strengthening of rational closure in DLs: reasoning about multiple aspects. DL 2016, CoRR abs/1604.00301, April 22-25, 2016, Cape Town. 18. G. Gottlob, A. Hernich, C. Kupke, and T. Lukasiewicz. Stable model semantics for guarded existential rules and description logics. In Proc. KR 2014, 2014. 19. P. Ke and U. Sattler. Next Steps for Description Logics of Minimal Knowledge and Nega- tion as Failure. In F. Baader, C. Lutz, and B. Motik, editors, DL 2008, CEUR Workshop Proceedings, volume 353, Dresden, Germany, May 2008. CEUR-WS.org. 20. M. Knorr, P. Hitzler, and F. Maier. Reconciling owl and non-monotonic rules for the semantic web. In ECAI 2012, page 474479, 2012. 21. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44(1-2):167–207, 1990. 22. D. J. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial Intelligence, 55(1):1–60, 1992. 23. D. J. Lehmann. Another perspective on default reasoning. Ann. Math. Artif. Intell., 15(1):61– 82, 1995. 24. B. Motik and R. Rosati. Reconciling Description Logics and rules. J. ACM, 57(5), 2010.