Reasoning About Typicality in Preferential Description Logics: Preferential vs Rational Entailment Laura Giordano1, Valentina Gliozzi2 , Nicola Olivetti3 , and Gian Luca Pozzato2 1 Dipartimento di Informatica - Università del Piemonte Orientale - Alessandria, Italy laura@mfn.unipmn.it 2 Dipartimento di Informatica - Università degli Studi di Torino - Torino, Italy {gliozzi,pozzato}@di.unito.it 3 LSIS-UMR CNRS 6168 - Université “P. Cézanne” - Marseille, France nicola.olivetti@univ-cezanne.fr Abstract. Extensions of Description Logics (DLs) to reason about typicality and defeasible inheritance have been largely investigated. In this paper, we consider two such extensions, namely (i) the extension of DLs with a typicality operator T, having the properties of Preferential nonmonotonic entailment P, and (ii) its variant with a typicality operator having the properties of the stronger Rational entailment R. The first one has been proposed in [1, 2]. Here, we investigate the second one and we show, by a representation theorem, that it is equivalent to the approach to preferential subsumption proposed in [3]. We compare the two extensions, preferential and rational, and argue that the first one is more suitable than the second one to reason about typicality, as the latter leads to unintuitive inferences. 1 Introduction Description logics (DLs) represents one of the most important formalisms of knowledge representation. Their success can be explained by two key advantages characterizing them. On the one hand, DLs have a well-defined semantics based on first-order logic; on the other hand, they offer a good trade-off between expressivity and complexity. DLs have been successfully implemented by a range of systems and they are at the base of languages for the semantic web such as OWL. In a DL framework, a knowledge base (KB) comprises two components: an inten- sional part, called the TBox, containing the definition of concepts (and possibly roles) as well as a specification of inclusion relations among them, and an extensional part, called the ABox, containing instances of concepts and roles. Since the very objective of the TBox is to build a taxonomy of concepts, the need of representing prototypical properties and of reasoning about defeasible inheritance of such properties naturally arises. The traditional approach is to handle defeasible inheritance by integrating some kind of nonmonotonic reasoning mechanism. This has led to study nonmonotonic exten- sions of DLs [4–9]. However, as the same authors have pointed out, all these proposals present some difficulties, and finding a suitable nonmonotonic extension for inheritance with exceptions is far from obvious. To give a brief account, [4] proposes the extension 2 L. Giordano, V. Gliozzi, N. Olivetti, G.L. Pozzato of DL with Reiter’s default logic. However, the same authors have pointed out that this integration may lead to both semantical and computational difficulties. Furthermore, Reiter’s default logic does not provide a direct way of modeling inheritance with ex- ceptions. This has motivated the study of extensions of DLs with prioritized defaults [9, 5]. A more general approach is undertaken in [7], where an extension of DL is proposed with two epistemic operators. This extension, called ALCKN F , allows one to encode Reiter’s default logic as well as to express epistemic concepts and procedural rules. However, this extension has a rather complicated modal semantics, so that the integra- tion with the existing systems requires significant changes to the standard semantics of DLs. [10] extends the work in [7] by providing a translation of an ALCKN F KB to an equivalent flat KB and by defining a simplified tableau algorithm for flat KBs, which includes an optimized minimality check. In [6] an extension of DL with circumscription is proposed to express prototypical properties with exceptions, by introducing “abnor- mality” predicates whose extension is minimized. The authors provide algorithms for checking satisfiability, subsumption and instance checking which are proved to have an optimal complexity, but are based on massive nondeterministic guessing. A calculus for circumscription in DL has not been developed yet. Moreover, the use of circumscription to model inheritance with exceptions is not that straightforward. We refer to Section 5.1 in [1, 2] for a broader discussion on the above mentioned nonmonotonic extensions of DLs. Here, we consider an alternative approach, based on nonmonotonic entailment as defined by Kraus, Lehmann and Magidor (KLM) in [11, 12]. This approach is adopted by [2, 1] and [3]. The main advantage of this approach over previous ones is that the semantics of the resulting description logics is very simple and close to standard se- mantics for DLs. Furthermore, at least for what concerns [1, 2] there is a calculus for the proposed logic, and the logic can be extended in order to deal with inheritance with exceptions. We start by considering the logic ALC + T proposed in [2, 1], that extends the well-known description logic ALC by a typicality operator T. The intended meaning of the operator T, for any concept C, is that T(C) singles out the instances of C that are considered as “typical”. Thus, an assertion like “typical writers are brillant” is represented by T(Writer ) ⊑ Brillant . An ALC + T TBox can consistently contain the above inclusion together with T(Writer ⊓ Depressed ) ⊑ ¬Brillant (typical depressed writers are not brillant). It is worth noticing that, if the same prop- erties were expressed by ordinary inclusions, such as Writer ⊑ Brillant , we would simply get that there are not depressed writers, thus the KB would collapse. This col- lapse is avoided in ALC + T, as it is not assumed that T is monotonic, that is to say C ⊑ D does not imply T(C) ⊑ T(D). Reasoning About Typicality in Preferential DLs: Preferential vs Rational Entailment 3 The semantics of the T operator is defined by a set of postulates that are essentially a restatement of axioms and rules of nonmonotonic entailment in preferential logic P, as defined by KLM. The logic P introduces a nonmonotonic entailment |∼ in order to formalize conditional assertions of the form A |∼ B, whose intuitive meaning is that “normally the As are Bs”. The semantics of T is given by means of a preference relation < on individuals, so that typical instances of a concept C can be defined as the instances of C that are minimal with respect to <. In this modal logic, < works as an accessibility relation R with R(x, y) ≡ y < x, so that T(C) can be defined as C ⊓ 2¬C. The preference relation < does not have infinite descending chains as the so-called Smoothness condition is assumed. As a consequence, the corresponding modal operator 2 has the same properties as in Gödel-Löb modal logic G of arithmetic provability. The family of KLM logics contains other interesting members, notably the stronger logic R, known as Rational Preferential Logic [12]. The axiomatization of the logic R is obtained from the axiomatization of P by adding the following rule, known as rational monotonicity: RM. ((A |∼ B) ∧ ¬(A |∼ ¬C)) → ((A ∧ C) |∼ B) The intuitive meaning of rational monotonicity is as follows: if A |∼ B and ¬(A |∼ ¬C) hold, then one can infer A ∧ C |∼ B. This rule allows a conditional to be inferred from a set of conditionals in absence of other information. More precisely, “it says that an agent should not have to retract any previous defeasible conclusion when learning about a new fact the negation of which was not previously derivable” [12]. In this paper, we consider whether the properties of T in ALC + T are the correct ones, by comparing them with the properties that would result for T if we adopted the stronger logic of nonmonotonic entailment R. We call ALC + TR the resulting Description Logic. We provide some examples to show that P is better suited than R since R would force some inferences that we consider counterintuitive. Using R, for instance, we would be forced to conclude that typical writers are not brillant from the simple fact that there is a certain Mr. John who is a typical brillant person (he has, for instance, a lot of social success), who is a writer but who is not a typical writer (since he has never succeeded in publishing anything). We consider this as an unwanted inference, and therefore argue that the properties of R are too strong for T, and that P must be preferred. In section 4.2 we also show that the logic ALC + TR is equivalent to the logic for defeasible subsumptions in DLs proposed by [3], when considered with ALC as the underlying DL. The idea underlying the approach by [3] is very similar to that underlying ALC + T and ALC + TR : some objects in the domain are more typical than others. In the approach by [3], x is at least as typical as y if x ≥ y. The properties of ≥ in [3] correspond to those of < in ALC + TR . At a syntactic level the two logics differ, so that in [3] one finds the defeasible inclusions C ⊏ D instead of T(C) ⊑ D of ALC + TR . But the idea is the same: in the two cases the e inclusion holds if the most preferred (typical) Cs are also Ds. Indeed, it can be shown that the logic of preferential subsumption can be translated into ALC + TR by replacing C ⊏ D with T(C) ⊑ D. e The approach in [3] therefore inherits the above criticisms for extensions of DLs that use R. 4 L. Giordano, V. Gliozzi, N. Olivetti, G.L. Pozzato 2 The Logic ALC + T In this section we briefly recall the description logic ALC + T introduced in [1]. We consider an alphabet of concept names C, of role names R, and of individuals O. The language L of the logic ALC + T is defined by distinguishing concepts and extended concepts as follows: – Concepts: A ∈ C and ⊤ are concepts of L; if C, D ∈ L and R ∈ R, then C ⊓ D, C ⊔ D, ¬C, ∀R.C, ∃R.C are concepts of L; – Extended concepts: if C is a concept, then C and T(C) are extended concepts, and all the boolean combinations of extended concepts are extended concepts of L. A knowledge base is a pair (TBox,ABox). TBox contains subsumptions C ⊑ D, where C ∈ L is an extended concept of the form either C ′ or T(C ′ ), and D ∈ L is a concept. ABox contains expressions of the form C(a) and aRb where C ∈ L is an extended concept, R ∈ R, and a, b ∈ O. In order to provide a semantics to the operator T, we extend the definition of a model used in “standard” terminological logic ALC: Definition 1 (Semantics of T with selection function). A model is any structure h∆, I, fT i where: – ∆ is the domain; – I is the extension function that maps each extended concept C to C I ⊆ ∆, and each role R to a RI ⊆ ∆ × ∆. I assigns to each atomic concept A ∈ C a set AI ⊆ ∆ and it is extended as follows: • ⊤I = ∆ • ⊥I = ∅ • (¬C)I = ∆\C I • (C ⊓ D)I = C I ∩ DI • (C ⊔ D)I = C I ∪ DI • (∀R.C)I = {a ∈ ∆ | ∀b.(a, b) ∈ RI → b ∈ C I } • (∃R.C)I = {a ∈ ∆ | ∃b.(a, b) ∈ RI } • (T(C))I = fT (C I ) – Given S ⊆ ∆, fT is a function fT : P ow(∆) → P ow(∆) satisfying the following properties: • (fT − 1) fT (S) ⊆ S; • (fT − 2) if S 6= ∅, then also fT (S) 6= ∅; • (fT − 3) if fTS(S) ⊆ R,Sthen fT (S) = fT (S ∩ R); • (fT − 4) T f T ( Si ) ⊆ f T S(Si ); • (fT − 5) fT (Si ) ⊆ fT ( Si ). Intuitively, given the extension of some concept C, fT selects the typical instances of C. (fT − 1) requests that typical elements of S belong to S. (fT − 2) requests that if there are elements in S, then there are also typical such elements. The next proper- ties constraint the behavior of fT wrt ∩ and ∪ in such a way that they do not entail monotonicity. According to (fT − 3), if the typical elements of S are in R, then they coincide with the typical elements of S ∩ R, thus expressing a weak form of mono- tonicity (namely cautious monotonicity). (fT − 4) corresponds to one direction of the Reasoning About Typicality in Preferential DLs: Preferential vs Rational Entailment 5 S S equivalence fT ( Si ) = fT (Si ), soTthat it does T not entail monotonicity. Similar con- siderations T apply Tto the equation f T ( S i ) = fT (Si ), of which only the inclusion fT (Si ) ⊆ fT ( Si ) is derivable. (fT − 5) is a further constraint on the behavior of fT wrt arbitrary unions and intersections; it would be derivable if fT were monotonic. In [1, 2] an alternative semantics for T based on a preference relation is provided. The idea is that there is a global preference relation among individuals and that the typical members of a concept C, i.e. selected by fT (C I ), are the minimal elements of C wrt this preference relation. Observe that this notion is global, that is to say, it does not compare individuals with respect to a specific concept (something like y is more typical than x wrt concept C). In this framework, an object x ∈ ∆ is a typical instance of some concept C, if x ∈ C I and there is no C-element in ∆ more typical than x. The typicality preference relation is partial since it is not always possible to establish which object is more typical than which other. Let us first define the concept of minimal elements of a given set S ⊆ ∆ wrt a relation <: Definition 2 (Minimal elements of S). Given a relation < over a domain ∆, and given any S ⊆ ∆, we define: M in< (S) = {x : x ∈ S and ∄y ∈ S s.t. y < x} Moreover, we say that a relation < over a set ∆ satisfies the Smoothness Condition iff for all S ⊆ ∆, for all x ∈ S, either x ∈ M in< (S) or ∃y ∈ M in< (S) such that y < x. In [1, 2] the following Representation Theorem has been proved: Theorem 1 ([1]). Given any model h∆, I, fT i, fT satisfies postulates (fT − 1) to (fT − 5) iff there exists an irreflexive and transitive relation < over ∆ satisfying the Smoothness Condition, such that for all S ⊆ ∆, fT (S) = M in< (S). The above representation theorem allows to use the following semantics for ALC + T, which is similar to the one of Preferential logic P as defined by KLM. Definition 3 (Semantics of ALC + T). A model M of ALC + T is any structure h∆, I,