ALC + TeRxp: beyond most likely scenarios in preferential Description Logics of typicality

Abstract

In this work we continue our investigation about the opportunity of reasoning about alternative, surprising scenarios in preferential Description Logics of typicality. We extend the results provided in [1] and presented at CILC 2015, where a nonmonotonic procedure for preferential Description Logics has been outlined in order to solve a problem coming from sports entertainment. Here we provide complexity results for the Description Logic ALC + TeRxp, extending the Description Logic ALC + TR by allowing inclusions of the form T(C) vd D, where d is a degree of expectedness, and also allowing to reason about surprising extensions of an ABox satisfying cardinality restrictions on concepts. Here we propose a decision procedure for reasoning in ALC + TeRxp, and we exploit it to show that entailment is in EXPTIME, allowing us to conclude that reasoning in ALC + TeRxp is essentially inexpensive.

Introduction

From a semantic point of view, models of ALC + TR are standard models extended by a function f which selects the typical/most normal instances of any concept C, i.e. the extension of T(C) is defined as (T(C))I = f (CI ). The function f satisfies a set of postulates that are a restatement of Kraus, Lehmann, and Magidor’s axioms of rational logic R. This allows the typicality operator to inherit well-established properties of nonmonotonic reasoning.

The logic ALC + TR results to be too weak in several application domains. Indeed, although the operator T is nonmonotonic (T(C) v E does not imply T(C u D) v E), the logic ALC + TR is monotonic, in the sense that if the fact F follows from a given knowledge base KB, then F also follows from any KB’ KB. As a consequence, unless a KB contains explicit assumptions about typicality of individuals, there is no way of inferring defeasible properties about them: in the above example, if KB contains the fact that Kate is a depressed woman, i.e. Depressed (kate) belongs to KB, it is not possible to infer that she has sleep disorders (9HasSympthom:SleepDisorder (kate)). This would be possible only if the KB contained the stronger information that Kate is a typical depressed woman, i.e. T(Depressed )(kate) belongs to (or can be inferred from) KB. In order to overwhelm this limit and perform useful inferences, in [ 14 ] the authors have introduced a nonmonotonic extension of the logic ALC + TR based on a minimal model semantics, corresponding to a notion of rational closure as defined in [ 16 ] for propositional logic. Intuitively, the idea is to restrict our consideration to (canonical) models that maximize typical instances of a concept when consistent with the knowledge base. The resulting logic, call it ALC + TRRaCl, supports typicality assumptions, so that if one knows that Kate is depressed, one can nonmonotonically assume that she is also a typical depressed if this is consistent, and therefore that she has sleep disorders. From a semantic point of view, the logic ALC + TRRaCl is based on a preference relation among ALC + TR models and a notion of minimal entailment restricted to models that are minimal with respect to such preference relation.

The logic ALC + TRRaCl imposes to consider all consistent typicality assumptions that are consistent with a given KB. This seems to be too strong in several application domains, in particular when the need arises of bounding the cardinality of the extension of a given concept, that is to say the number of domain elements being members of such a concept, as introduced in [ 17 ]. As a further example, consider the following KB from the domain of sports entertainment taken from [ 1 ]: T(FaceWrestler ) v

RoyalRumbleWinner , T(Returning ) v RoyalRumbleWinner , T(Predicted ) v

RoyalRumbleWinner . The first inclusion represents that, normally, a face wrestler wins the Royal Rumble match, an annual wrestling event involving thirty athletes. The second one states that, typically, an athlete returning from an injury wins the Royal Rumble match. The third and last inclusion represents that an athlete whose victory has been predicted by wrestling web sites normally wins the Royal Rumble match. If the assertional part of the KB contains the facts: FaceWrestler (dean); Returning (dave); FaceWrestler (roman); Predicted (roman), whose meaning is that Dean is a face athlete, Dave is returning from an injury, and that Roman is a face wrestler who has been predicted to win the Royal Rumble match, respectively, then in ALC + TRRaCl we conclude that: T(FaceWrestler )(dean), T(Returning )(dave), T(FaceWrestler )(roman), T(Predicted )(roman), and then that Dean, Dave and Roman are all winners. This happens in ALC + TRRaCl because it is consistent to make the three assumptions above, that hold in all minimal models, however one should be interested in three distinct scenarios that cannot be captured by ALC + TRRaCl as it is. One could think of extending the logic ALC + TRRaCl by means of cardinality restrictions, in the example by imposing that there is only one member of the extension of the concept RoyalRumbleWinner , however the resulting knowledge base would be inconsistent.

Furthermore, it is sometimes useful to restrict reasoning to surprising scenarios, excluding “trivial”/“obvious” ones. For instance, recently a great attention has been devoted to serendipitous search engines, that must be able to provide results that are “surprising, semantically cohesive, i.e. relevant to some information need of the user, or just interesting” [ 18 ]. In this sense, the scenario (among those satisfying cardinality restrictions) obtained by assuming the largest set of consistent typicality assumptions in ALC + TRRaCl corresponds to the most trivial one, whereas one could be interested in less expected ones, in which some typicality assumptions are discarded.

In [ 1 ] we have moved a first step towards the definition of an extension of Description Logics of typicality allowing to reason about surprising scenarios in presence of cardinality restrictions. In that work, an extension of DL-Litecore has been introduced in order to tackle a problem coming from sports entertainment, namely to find a plausible but surprising outcome of a wrestling event. However, neither decision procedures nor complexity results are provided, being that work only a preliminary contribution in this field. Here we try to move a further step by extending our approach to the more expressive Description Logic ALC. Moreover, whereas the approach in [ 1 ] is based on a nonmonotonic extension of DLs based on preferential logic P [ 15 ], here we exploit the nonmonotonic extension of ALC called ALC + TRRaCl, based on rational models [ 16 ] and corresponding to a notion of rational closure for Description Logics introduced in [ 14 ]. The approach we propose in this work is based on the combination of two components. On the one hand, we allow to express different degrees of expectedness of typicality inclusions: this allows to describe several plausible scenarios by considering different combinations of typicality assumptions about individuals named in the ABox. Such degrees introduce a rank of expectedness among plausible scenarios, ranging from surprising to obvious ones. On the other hand, TBoxes are extended to allow restrictions about the cardinality of concepts, in order to “filter” such plausible scenarios. Finally, reasoning tasks are restricted to reasonable but “surprising enough” (or “not obvious”) scenarios satisfying cardinality restrictions. In detail, the original contribution of this work can be summarized as follows: - we introduce a new Description Logic of typicality, called ALC + TeRxp, allowing to express a degree of expectedness of typicality inclusions and cardinality restrictions on concepts: TBoxes are extended by (i) inclusions of the form T(C) vd D where d is a positive integer, such that an inclusion with degree d is more “trivial” (or “obvious”) with respect to another one with degree d0 d, as well as by (ii) restrictions on the cardinality of concepts of the form ( n C), where 2 f ; ; =g and n 2 N+; - we introduce a notion of extension of an ABox for the logic ALC + TeRxp, corresponding to a set of typicality assumptions that can be performed in ALC + TRRaCl for individual constants, then we introduce an order relation among extensions whose basic idea is to prefer extensions representing more surprising scenarios; - we define notions of skeptical and credulous entailment in ALC + TeRxp, relying on reasoning in ALC + TR, but allowing to restrict our concern to “non trivial” scenarios, corresponding to minimal extensions with respect to the order relation among extensions of the previous point; - we describe a procedure for reasoning in ALC + TeRxp, that can be used to estimate the complexity of entailment (EXPTIME for both skeptical and credulous entailment). It is worth noticing that the proposed logic ALC + TeRxp is not intended to replace existing extensions of DLs for representing and reasoning about prototypical properties and defeasible inheritance. The idea is that, in some applications, the need of reasoning about surprising scenarios could help domain experts to achieve their goals, wherever standard reasoning is not enough to do it: as an example, in medical diagnosis, the most likely explanation for a set of symptoms is not always the solution to the problem, whereas reasoning about surprising scenarios could help the medical staff in taking alternative explanations into account. In other words, the Description Logic ALC + TeRxp is not intended to replace existing nonmonotonic DLs, but to tile them in order to reason about alternative, plausible scenarios when it is needed to go beyond most likely solutions. 2 2.1

Description Logics of Typicality

The monotonic logic ALC + TR

The logic ALC + TR is obtained by adding to standard ALC the typicality operator T [ 14 ]. The intuitive idea 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 normal or typical instances of C (T(C) v D).

The semantics of the T operator can be formulated in terms of rational models: a model M is any structure h I ; <; :I i where I is the domain, < is an irreflexive, transitive, well-founded and modular (for all x; y; z in , if x < y then either x < z or z < y) relation over . In this respect, x < y means that x is “more normal” than y, and that the typical members of a concept C are the minimal elements of C with respect to this relation. An element x 2 is a typical instance of some concept C if x 2 CI and there is no C-element in more typical than x. In detail, :I is the extension function that maps each concept C to CI , and each role R to RI . For concepts of ALC, CI is defined as usual. For the T operator, we have (T(C))I = M in<(CI ). A model M can be equivalently defined by postulating the existence of a function kM : 7 ! N, where kM assigns a finite rank to each world: the rank function kM and < can be defined from each other by letting x < y iff kM(x) < kM(y).

Given standard definitions of satisfiability of a KB in a model, we define a notion of entailment in ALC + TR. Given a query F (either an inclusion C v D or an assertion C(a) or an assertion of the form R(a; b)), we say that F is entailed from a KB in ALC + TR, written KB j=ALC+TR F , if F holds in all ALC + TR models satisfying KB. Even if the typicality operator T itself is nonmonotonic (i.e. T(C) v E does not imply T(C u D) v E), what is inferred from a KB can still be inferred from any KB’ with KB

KB’, i.e. the logic ALC +TR is monotonic. In order to perform useful nonmonotonic inferences, in [ 14 ] the authors have strengthened the above semantics by restricting entailment to a class of minimal models. Intuitively, the idea is to restrict entailment to models that minimize the untypical instances of a concept. The resulting logic is called ALC + TRRaCl and it corresponds to a notion of rational closure on top of ALC + TR. Such a notion is a natural extension of the rational closure construction provided in [ 16 ] for the propositional logic. Here below we recall the semantics of the DL ALC + TRRaCl: details about the construction of the rational closure and the correspondence between semantics and construction can be found in [ 14 ].

The nonmonotonic semantics of ALC + TRRaCl relies on minimal rational models that minimize the rank of domain elements. Informally, given two models of KB, 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 prefer the latter, as in this model the element x is assumed to be “more typical” than in the former. Query entailment is then restricted to minimal canonical models. The intuition is that a canonical model contains all the individuals that enjoy properties that are consistent with the knowledge base. This is needed when reasoning about the rank of the concepts: it is important to have them all represented. A model M is a minimal canonical model of KB if it satisfies KB, it is minimal and it is canonical1. Finally, a query F is minimally entailed from a KB (or, equivalently, F belongs to the rational closure of KB), written KB j=ALC+TRRaCl F , if it holds in all minimal canonical models of KB minimally satisfying A. In [ 14 ] it is shown that query entailment in ALC + TRRaCl, i.e. the problem of checking whether a query F is in the rational closure of KB, namely that KB j=ALC+TRRaCl F , is in EXPTIME. 3

The Logic ALC + TeRxp: Reasoning About Surprising Scenarios

In this section we define an alternative semantics that allows us to express a degree of expectedness for the typicality inclusions and to limit the number of typicality assumptions in the ABox in order to obtain less predictable scenarios. The basic idea is similar to the one proposed in [ 10 ], where a completion of an ALC+T ABox is proposed in order to assume that every individual constant of the ABox is a typical element of the most specific concept he belongs to, if this is consistent with the knowledge base. Here we propose a similar, algorithmic construction in order to compute only some assumptions of typicality of domain elements/individual constants, in order to describe an alternative, surprising but plausible scenario. Constraints about the cardinality of the extensions of concepts are also introduced in order to filter scenarios, allowing to define eligible extensions of the ABox satisfying such constraints, and entailment is restricted to minimal scenarios, called perfect extensions, with respect to an order relation among 1 In Theorem 10 in [ 14 ] the authors have shown that for any KB there exists a finite minimal canonical model of KB minimally satisfying the ABox. extensions: intuitively, an extension is preferred to another one if it represents a more surprising scenario.

As mentioned above, the logic ALC +TeRxp allows to express cardinality restrictions in the TBox. More expressive DLs allow to specify (un)qualified number restrictions, in order to specify the number of possible elements filling a given role R. As an example, number restrictions allow to express that a student attends to 3 courses. Number restrictions are therefore “localized to the fillers of one particular role” [ 17 ], for instance we can have Student v= 3Attends:Course as a restriction on the number of role fillers of the role Attends. However one could need to express global restrictions on the number of domain elements belonging to a given concept, for instance to express that in the whole domain there are exactly 3 courses. In DLs not allowing cardinality restrictions one can only express that every student must attend to three courses, but not that all must attend to the same ones. In the logic ALC + TeRxp, cardinality restrictions on concepts are added to the TBox as in Definition 1. They are expressions of the form either ( n C) or ( n C) or (= n C), where n is a positive integer and C is a concept. This is formally defined in the next definition, where, given a set S, we write ]S to mean the cardinality of S.

Let us first define the language L of this new Description Logic called ALC + TeRxp. It is known that axioms expressing cardinality restrictions are even more expressive than : inclusions C v D or C = D, the last one shortening for the pair of inclusions C v D and D v C (thus expressing that the concepts C and D have the same extensions, i.e.

: CI = DI ). Indeed, C = D means that the set of domain elements that are Cs but not Ds is empty, and viceversa (the set of domain elements that are Ds but not Cs is empty). This can be expressed by the following cardinality restriction: (= 0 ((C u:D)t(:C u D))). The same for an inclusion of the form C v D, whose meaning is that every C element is also a D element, that can be expressed by (= 0 (C u :D)) (the intersection of CI and the complement of DI is empty). Therefore, we could restrict our language to TBoxes only containing cardinality restriction, however we have decided to consider the extended language of Definition 1 for the sake of readability.

Definition 1. We consider an alphabet of concept names C, of role names R, and of individual constants O. Given A 2 C and R 2 R, we define:

C := A j > j ? j :C j C u C j C t C j 8R:C j 9R:C An ALC + TeRxp knowledge base is a pair (T ; A). T contains axioms of the form: – C v C; – T(C) vd C, where d 2 N+ is called the degree of expectedness; – ( n C), where 2 f=; ; g and n 2 N+; A contains assertions of the form C(a) and R(a; b), where a; b 2 O.

Given an inclusion T(C) vd D, the higher the degree of expectedness the more the inclusion is, in some sense, “obvious”/not surprising. Given another inclusion T(C0) vd0 D0, with d0 < d, we assume that this inclusion is less “obvious”, more surprising with respect to the other one. As an example, let KB contain:

T(Student ) v4 SocialNetworkUser T(Student ) v2 PartyParticipant

representing that typical students make use of social networks, and that normally they go to parties; however, the second inclusion is less obvious with respect to the first one. In other words, one can think of representing the fact that both are properties of a prototypical student, however there are more exceptions of students not taking part to parties with respect to the number of exceptions of students not being part of the social media ecosphere.

It is worth noticing that using positive integers for expressing degrees of expectedness is only a way of formalizing a partial order among typicality inclusions, however all properties expressed by typicality inclusions of the form T(C) vd D are typical properties, even if n is high: the ontology engineer has still to distinguish between properties that are prototypical (even with some exceptions) and those that are not and do not deserve to be represented by a typicality inclusion. It is also worth noticing that degrees of expectedness are not intended to represent priorities among inclusions (as in circumscribed KBs), since specificity is provided for free by the preferential semantics of the logic ALC + TRRaCl. 3.1

Extensions of ABox Given a KB, we define the finite set C of concepts occurring in the scope of the typicality operator, i.e. C = fC j T(C) vd D 2 KBg. These are the concepts whose atypical instances we want to minimize.

Given an individual a explicitly named in the ABox, we define the set of “plausible” typicality assumptions T(C)(a) that can be minimally entailed from KB without cardinality restrictions in the logic ALC + TRRaCl, with C 2 C. We then consider an ordered set of pairs (a; C) of all possible assumptions T(C)(a), for all concepts C 2 C and all individual constants a occurring in the ABox. This is formally stated in the next definition: Definition 2 (Assumptions in ALC+TeRxp). Given an ALC+TeRxp KB=(T [ Tcard ; A), where Tcard is a set of cardinality restrictions and T does not contain cardinality restrictions, let T 0 be the set of inclusions of T without degrees of expectedness. Given a finite set of concepts C, we define, for each individual name a occurring in A:

Ca = fC 2 C j (T 0; A) j=ALC+TRRaCl T(C)(a)g We also define CA = f(a; C) j C 2 Ca and a occurs in Ag and we impose an order on the elements of CA = [(a1; C1); (a2; C2); : : : ; (an; Cn)]: Furthermore, we define the ordered multiset dA = [d1; d2; : : : ; dn] respecting the order imposed on CA, where di = avg(fd 2 N+ j T(Ci) vd D 2 Tcard g).

Intuitively, the ordered multiset dA is a tuple of the form [d1; d2; : : : ; dn], where di is the degree of expectedness of the assumption T(C)(a), such that (a; C) 2 CA at position i. di corresponds to the average2 of all the degrees d of typicality inclusions T(C) vd D in the TBox.

In order to define alternative scenarios, where not all plausible assumptions are taken into account, we consider different extensions of the ABox and we introduce an order among them, allowing to range from unpredictable to trivial ones. Starting from dA = [d1; d2; : : : ; dn], the first step is to build all alternative tuples where 0 is used in place of some di to represent that the corresponding typicality assertion T(C)(a) is no longer assumed (Definition 3). Furthermore, we define the extension of the ABox corresponding to a string so obtained (Definition 4).

Definition 3 (Strings of plausible assumptions S). Given a KB=(T ; A) and the set CA, let dA = [d1; d2; : : : ; dn] be as in Definition 2. We define the set S of all the strings of plausible assumptions with respect to KB as

S = f[s1; s2; : : : ; sn] j 8i = 1; 2; : : : ; n either si = di or si = 0g Definition 4 (Extension of the ABox). Let KB=(T ; A) and let CA = [(a1; C1); (a2; C2); : : : ; (an; Cn)] as in Definition 2. Given a string of plausible assumptions [s1; s2; : : : ; sn] 2 S of Definition 3, we define the extension Ab of A with respect to CA and S

Ab = fT(Ci)(ai) j (ai; Ci) 2 CA and si 6= 0g It is easy to observe that, in ALC + TRRaCl, the set of typicality assumptions that can be inferred from a KB corresponds to the extension of A corresponding to the string dA, that is to say no element is set to 0: all the typicality assertions of individuals occurring in the ABox, that are consistent with the KB, are assumed. On the contrary, in ALC + TR, no typicality assumption can be derived from a KB, and this corresponds to extending A by the assertions corresponding to the string [0; 0; : : : ; 0], i.e. by the empty set. 3.2 Cardinality restrictions and perfect extensions Let us now introduce models of the Description Logic ALC + TeRxp taking cardinality restrictions into account, as well as the notion of eligible extension of the ABox as a set of typicality assumptions satisfying cardinality restrictions.

Definition 5. Given a model M = h I ; <; :I i, it satisfies: – (TBox) an inclusion C v D if CI DI ; a typicality inclusion T(C) vd D if Min<(CI ) a cardinality restriction of the form ( n C) if ]CI and n 2 N+; DI ; n, where 2 f ; ; =g 2 Other aggregation functions could be used in order to define di (maximun degree, minimum degree). We aim at studying the impact of the choice on the reasoning machinery in future research. – (ABox) an assertion of the form C(a) if aI 2 CI ; an assertion of the form R(a; b) if (aI ; bI ) 2 RI .

Given a KB=(T ; A), we say that a model M satisfies KB if it satisfies all the inclusions in T and all the assertions in A.

Given a KB=(T ; A), we say that an extension of A is an eligible extension if it admits a model as in Definition 5: Definition 6 (Eligible extension Ab). Given an ALC + TeRxp KB=(T ; A) and an extension Ab of A as in Definition 4, we say that Ab is eligible if there exists an ALC + TeRxp model M as in Definition 5 that satisfies KB’=(T ; A [ Ab).

Let us now introduce an order relation among the strings of S (Definition 3), corresponding to eligible extensions of the ABox: Definition 7 (Order between eligible extensions). Given KB=(T ; A) and the set S of Definition 3, let s = [s1; s2; : : : ; sn] and r = [r1; r2; : : : ; rn], with s; r 2 S. Let Acs and Acr be two eligible extensions of A corresponding to s and r (Definition 4). We say that s < r if there exists a bijection between s and r such that, for each (si; rj ) 2 , it holds that si rj , and there is at least one (si; rj ) 2 such that si < rj . We say that Acs is more surprising (or less trivial) than Acr if s < r.

Intuitively, a string s whose elements are “lower” than the ones of another string r corresponds to a less trivial ABox. For instance, let us consider a KB whose typicality inclusions are T(C) v1 D and T(E) v2 F , and such that T(C)(a), T(C)(b), and T(E)(b) are entailed in ALC + TRRaCl. Given the strings s = [1; 1; 0] and r = [1; 0; 2], we have that s < r, because there exists a bijection f(1; 1); (0; 0); (1; 2)g. The assumptions T(C)(a) and T(C)(b) corresponding to s are then considered less trivial than T(C)(a) and T(E)(b) corresponding to r. It is worth noticing that the order of Definition 7 is partial: as an example, the strings [1; 1; 0] and [0; 0; 2] are not comparable, in the sense that [1; 1; 0] 6< [0; 0; 2] and [0; 0; 2] 6< [1; 1; 0]. In order to choose between two incomparable situations, we introduce the following notion of weak order: given two incomparable extensions Acs and Acr, we assume that Acs is weakly less trivial than Acr if Acr is strictly included in another eligible extension Acu more trivial than Acs, i.e. Acr Acu and s < u.

Definition 8 (Minimal (perfect) extensions). Given a KB=(T ; A) and the set S of strings of plausible assumptions (Definition 3), we say that an eligible extension Acs is minimal or perfect if there is no other eligible extension Acr which is (weakly) more surprising (or (weakly) less trivial) than Acs.

Given the above definitions, we can define a notion of entailment in ALC + TeRxp. Intuitively, given a query F , we check whether F follows in the monotonic logic ALC + TR from a given KB, whose ABox is augmented with extensions that are minimal (perfect) as in Definition 8. We can reason either in a skeptical way, by asking that F is entailed if it follows in all KBs, obtained by considering each minimal extension of the ABox, or in a credulous way, by assuming that F is entailed if there exists at least one extension of the ABox allowing such inference. This is stated in a rigorous manner by the following definition: Definition 9 (Entailment in ALC + TeRxp). Given a KB=(T ; A) and given C a set of concepts, let E the set of all extensions of A that are minimal as in Definition 8. Given a query F , we say that (i) F is skeptically entailed from KB in ALC + TeRxp, written KB j=sAkLC+TeRxp F , if (T ; A [ Ab) j=ALC+TR F for all Ab 2 E ; (ii) F is credulously entailed from KB in ALC + TeRxp, written KB j=cArLC+TeRxp F , if there exists Ab 2 E such that (T ; A [ Ab) j=ALC+TR F .

At a first glance, one could have the impression that the notions of rank in the semantics of ALC + TRRaCl, where elements with lowest rank are the most typical ones, and the semantics of expectedness of Definitions 7 and 8, where lower ranks correspond to more surprising scenarios, are in conflict. However, this is not the case: ranks in the semantics are introduced in order to define the extension of typicality concepts, and this notion is also considered in the expectation semantics to select plausible typicality assumptions. The rank among extensions is rather used in order to choose surprising scenarios, to restrict the number of typicality assumptions to satisfy cardinality restrictions: the unexpectedness is the additional ingredient to select surprising scenarios by fixing cardinality restrictions, where all candidates try to maximize the typicality of individuals.

Let us conclude by showing an example of reasoning in the logic ALC + TeRxp. Example 1 (Mysterious medical diagnosis). In this example we exploit the logic ALC+ TeRxp in order to provide a mysterious medical diagnosis, as an alternative to the most likely explanation, for a patient characterized by mood swings. The idea is to support the medical staff whenever the “standard” diagnosis fails, suggesting surprising alternatives that could be taken into account for further investigations.

Let KB=(T ; A) as follows and let T be:

T(Cancer ) v1 MoodSwingsCause

T(BrainDisorder ) v3 MoodSwingsCause

T(MajorDepressionAtypicalFeatures ) v2 MoodSwingsCause (= 1 MoodSwingsCause) (T1) (T2) (T3) (T4) the last one stating that we are interested in finding exactly one disease being responsible for mood reactivity. Concerning typicality inclusions, we represent the facts that normally, cancer causes mood swings (T1), however this admits more exceptions with respect to the fact that mood reactivity is a typical symptom of depressive disorders with atypical features (T3), which is in turn more surprising than the most “obvious” inclusion, namely that brain disorders normally cause changes in the mood of patients (T2). The cardinality restriction (T4) imposes that exactly one disease is the reason why the patient’s mood swings. Let A be:

Cancer (prostaticCancer ) BrainDisorder (bipolarDisorder ) MajorDepressionAtypicalFeatures (bipolarDisorder )

MajorDepressionAtypicalFeatures (atypicalDepression) In the logic ALC + TeRxp, we can infer that prostatic cancer is responsible of mood swings in our patient:

KB j=sk

ALC+TeRxp MoodSwingsCause(prostaticCancer ) KB j=cr

ALC+TeRxp MoodSwingsCause(prostaticCancer ) since there is only one perfect extension. Let

C = fCancer ; MajorDepressionAtypicalFeatures ; BrainDisorder g: By Definition 2 above, we have that:

CprostaticCancer = fCancer g, CatypicalDepression = fMajorDepressionAtypicalFeatures g,

CbipolarDisorder = fBrainDisorder ; MajorDepressionAtypicalFeatures g and, obviously, CA = CprostaticCancer [ CatypicalDepression [ CbipolarDisorder . Concerning the degrees of expectedness, we have dA = [1; 3; 2; 2]. As mentioned above, in ALC + TRRaCl the minimal model semantics forces all the consistent typicality assumptions, namely we are considering an ABox extended with the following facts: T(Cancer )(prostaticCancer ) T(BrainDisorder )(bipolarDisorder ) T(MajorDepressionAtypicalFeatures )(bipolarDisorder )

T(MajorDepressionAtypicalFeatures )(atypicalDepression) corresponding (in the sense of Definition 4) to the multiset [1; 3; 2; 2]. However, in ALC + TR we obtain that prostatic cancer, bipolar disorder and atypical depression are all responsible of mood reactivity in the patient, against the fact that we want to focus on only one disease: the extension corresponding to [1; 3; 2; 2] is indeed not eligible in the sense of Definition 6. In order to find only one non-trivial diagnosis justifying mood swings, we consider the set S of all plausible strings of typicality assumptions (Definition 3). The only eligible extensions of the ABox are:

Ac1 = fT(BrainDisorder )(bipolarDisorder )g, by [0; 3; 0; 0] Ac2 = fT(MajorDepressionAtypicalFeatures )(atypicalDepression)g, by [0; 0; 0; 2] Ac3 = fT(Cancer )(prostaticCancer )g, [1; 0; 0; 0] Ac4 = fT(MajorDepressionAtypicalFeatures )(bipolarDisorder )g, [0; 0; 2; 0] Ac5 = fT(BrainDisorder )(bipolarDisorder ); T(MajorDepressionAtypicalFeatures ) (bipolarDisorder )g, corresponding to [0; 3; 2; 0] We have that Ac1, Ac2 and Ac4 are less trivial than Ac5, because [0; 3; 0; 0] < [0; 3; 2; 0], as well as [0; 0; 0; 2] < [0; 3; 2; 0] and [0; 0; 2; 0] < [0; 3; 2; 0]. However, Ac3 is less trivial than Ac1, Ac2 and Ac4, since [1; 0; 0; 0] < [0; 3; 0; 0], as well as [1; 0; 0; 0] < [0; 0; 0; 2] and [1; 0; 0; 0] < [0; 0; 2; 0]. This allows to suggest that prostatic cancer could be a “mysterios diagnosis” for the patient having mood swings, and such a non trivial diagnosis could be confirmed by an evaluation of other typical symptoms of such a disease, e.g. nocturia. 4

A Decision Procedure for Reasoning in ALC + TeRxp

In this section we describe a decision procedure for reasoning in the logic ALC + TeRxp. We consider skeptical and credulous entailment. In both cases, we exploit the decision procedure to show that the problem of entailment in the logic ALC + TeRxp is in EXPTIME. This allows us to conclude that reasoning about typicality and defeasible inheritance in surprising scenarios is essentially inexpensive, in the sense that reasoning retains the same complexity class of the underlying standard Description Logic ALC, which is known to be EXPTIME complete [ 19 ].

Following the definitions of nonmonotonic entailment introduced in the previous section, given an ALC + TeRxp KB=(T ; A) and a query F , we define a procedure computing the following three steps: 1. compute the set Ca of all typicality assumptions that are minimally entailed from the knowledge base in the nonmonotonic logic ALC + TRRaCl; 2. compute all possible extensions of the ABox and select perfect extensions; 3. check whether the query F is entailed from at least one extension/all the extensions of KB in the monotonic logic ALC + TR plus cardinality restrictions. Step 3 is based on reasoning in the monotonic logic ALC + TR: to this aim, the procedure relies on a polynomial encoding of ALC + TR into ALC introduced in [ 20 ] and then on reasoning with cardinality restrictions. Step 1 is based on reasoning in the nonmonotonic logic ALC + TRRaCl: in this case, the procedure computes the rational closure of an ALC + TR knowledge base by means of the algorithm introduced in [ 14 ], which is sound and complete with respect to the minimal model semantics recalled in Section 2.2. Also the algorithm computing the rational closure relies on reasoning in the monotonic logic ALC + TR, then on the above mentioned polynomial encoding in ALC. We assume unary encoding of numbers in cardinality restrictions in order to exploit the results in [ 21 ], namely that reasoning in ALCO, extending ALC with qualified number restrictions, is EXPTIME-complete also with cardinality restrictions. Due to space limitations, here we only introduce the overall procedure for reasoning in ALC + TeRxp and we analyze its complexity, whereas we remind to the accompanying report [ 22 ] for the procedures for reasoning in ALC + TR and ALC + TRRaCl.

Let KB=(T [ Tcard ; A) be an ALC + TeRxp knowledge base, where Tcard is a set of cardinality restrictions and T does not contain cardinality restrictions. Let T 0 be the set of inclusions of T without the degrees of expectedness: T 0 = fC v D j C vn D 2 T g, that the procedure will take into account in order to reason in ALC + TR and ALC + TRRaCl for checking query entailment and finding all plausible typicality assumptions, respectively. Other inputs of the procedure are a finite set of concepts C and a query F . Algorithm 1 checks whether F is skeptically entailed from the KB in the logic ALC + TeRxp, namely whether KB j=sk ALC+TeRxp F .

Algorithm 1 Skeptical entailment in ALC + TeRxp: KB j=sk ALC+TeRxp F 1: procedure SKEPTICALENTAILMENT((T [ Tcard ; A); T 0, F , C) 2: CA ; . build the set S of plausible assumptions 3: for each C 2 C do 4: . Reasoning in ALC + TRRaCl 5: for eifa(cTh 0in;Adiv)ijd=uAalLaC 2+TARRdaoClT(C)(a) then CA CA [ fT(C)(a)g 6: dA build the ordered multiset of avg degrees of Definition 2 given T and CA 7: S build strings of plausible extensions as in Definition 3 given CA and dA 8: Apl ; . build plausible extensions of A 9: for each di 2 S do 10: build the extension Abi corresponding to di 11: Apl Apl [ Abi 12: Ael ; . select eligible extensions checking cardinality restrictions 13: for each Abi 2 Apl do . Reasoning in ALC + TR plus cardinality restrictions 14: if (T 0 [ Tcard ; A [ Abi) is satisfiable in ALC + TR then 15: Ael Ael [ Abi 16: for each Abi 2 Ael do . check preference among extensions of A 17: for each Abj 2 Ael do 18: if di dj then let Abi < Abj 19: E fAbi j6 9Abj 2 Ael such that Abj < Abig . select perfect extensions 20: for each Abi 2 E do . query entailment in ALC + TR plus cardinality restrictions 21: if (T 0 [ Tcard ; A [ Abi) 6j=ALC+TR F then 22: . a perfect extension not entailing F return KB 6j=sAkLC+TeRxp F 23: return KB j=sAkLC+TeRxp F . F is entailed in all perfect extensions In order to check whether F is credulously entailed from the KB, that is to say KB j=cArLC+TeRxp F , the algorithm is obtained by replacing lines 20-23 in Algorithm 1 by the following ones: By exploiting the procedures above, we show that: Theorem 1 (Complexity of entailment). Given a KB in ALC + TeRxp and a query F whose size is polynomial in the size of KB, assuming the unary encoding of numbers in cardinality restrictions of KB, the problem of checking skeptically (resp. credulously) whether KB j=sk ALC+TeRxp F ) is EXPTIME-complete.

ALC+TeRxp F (resp. KB j=cr Proof. (sketch, see [ 22 ] for the complete proof ) The algorithm checks, for each concept C 2 C and for each individual name a whether T(C)(a) is minimally entailed from KB in the nonmonotonic logic ALC + TRRaCl. By definition, the size of C is O(n). For each T(C)(a) (they are O(n2)) the algorithm relies on reasoning in ALC + TRRaCl, which is in EXPTIME. Building dA can be solved with O(n2) operations. For building the set S of plausible extensions we have to consider all possible strings obtained by assuming (or not) each typicality assumption T(C)(a), that are O(n2): for each di, we have two options (di = 0 or di 6= 0) , then 2 2 : : : 2 different strings, thus S has exponential size in n. Checking, for each extension of A, if it satisfies cardinality constraints requires O(2n2 ) calls to satisfiability in ALC + TR plus cardinality restrictions, that is in EXPTIME. Ordering extensions of A and finding perfect extensions can be solved in EXPTIME, then the algorithm relies on reasoning in monotonic ALC + TR plus cardinality restrictions in order to check whether the query F is entailed in perfect extensions in E , whose size is O(2n): we have O(2n) call to query entailment in ALC +TR, which is an EXPTIME-complete problem.

Since reasoning in the underlying standard ALC is EXPTIME-complete, we can conclude that reasoning about typicality in surprising scenarios is essentially inexpensive. 5

Conclusions

In this work we have provided a nonmonotonic procedure for preferential Description Logics in order to reason about surprising scenarios. We have introduced the Description Logic of typicality ALC + TeRxp, an extension of ALC with a typicality operator T allowing to (i) express typicality inclusions of the form T(C) vd D, where d is a positive integer representing a degree of expectedness; (ii) reason in presence of restrictions on the cardinality of concepts. We have also described a procedure for reasoning in ALC + TeRxp exploiting reasoning mechanisms in the logics ALC + TR and ALC + TRRaCl, the last one relying on a notion of rational closure for Description Logics. This procedure allowed us to show that entailment in ALC + TeRxp is EXPTIME complete as the underlying ALC, therefore it is essentially inexpensive, once unary encoding of numbers in cardinality restrictions is assumed.

The extension of DLs of typicality with cardinality restrictions is of its own interest, and one can think of considering cardinality restrictions not limited to surprising scenarios of the logic ALC + TeRxp, but directly applied to the nonmonotonic semantics of ALC + TRRaCl. Furthermore, we aim at studying also cardinality restrictions on roles.

In future work we aim at extending this approach to more expressive Description Logics, in particular the logics underlying the standard language for ontology engineering OWL. As a first step, in [ 23 ] the logic with the typicality operator and the rational closure construction have been applied to the description logic S HIQ.

A comparison with probabilistic approaches will be also object of further investigations. To the best of our knowledge, the literature lacks a formalization of surprising scenarios in probabilistic formalizations of knowledge, however it is worth observing that a surprising scenario could be defined as a set of facts with a low probability, then one can think of restricting the attention to less probable outcomes.

Acknowledgements

The author is partially supported by the project “ExceptionOWL: Nonmonotonic Extensions of Description Logics and OWL for defeasible inheritance with exceptions” , Progetti di Ateneo Universita` degli Studi di Torino and Compagnia di San Paolo, call 2014, line “Excellent (young) PI”, project ID: Torino call2014 L1 111.

References

1. Pozzato , G.L. : Preferential description logics meet sports entertainment: cardinality restrictions and perfect extensions for a better royal rumble match . In Ancona, D., Maratea , M. , Mascardi , V., eds. : Proceedings of the 30th Italian Conference on Computational Logic, Genova, Italy, July 1-3 , 2015 . Volume 1459 of CEUR Workshop Proceedings., CEUR-WS.org ( 2015 ) 159 - 174

2. Bonatti , P.A. , Lutz , C. , Wolter , F. : The complexity of circumscription in dls . Journal of Artificial Intelligence Research (JAIR) 35 ( 2009 ) 717 - 773

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

4. Bonatti , P.A. , Faella , M. , Sauro , L. : Defeasible inclusions in low-complexity dls . Journal of Artificial Intelligence Research (JAIR) 42 ( 2011 ) 719 - 764

5. Donini , F.M. , Nardi , D. , Rosati , R.: Description logics of minimal knowledge and negation as failure . ACM Transactions on Computational Logics (ToCL) 3 ( 2 ) ( 2002 ) 177 - 225

6. Casini , G. , Straccia , U. : Rational closure for defeasible description logics . In Janhunen, T., Niemela¨, I., eds. : Logics in Artificial Intelligence - Proceedings of the12th European Conference (JELIA 2010 ). Volume 6341 of Lecture Notes in Computer Science (LNCS)., Springer ( 2010 ) 77 - 90

7. Casini , G. , Straccia , U. : Defeasible Inheritance-Based Description Logics . Journal of Artificial Intelligence Research (JAIR) 48 ( 2013 ) 415 - 473

8. Straccia , U. : Default inheritance reasoning in hybrid kl-one-style logics . In: Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI'93) , Morgan Kaufmann ( 1993 ) 676 - 681

9. Bonatti , P.A. , Faella , M. , Petrova , I. , Sauro , L.: A new semantics for overriding in description logics . Artificial Intelligence 222 ( 2015 ) 1 - 48

10. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : ALC+T: a preferential extension of description logics . Fundamenta Informaticae 96 ( 2009 ) 341 - 372

11. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : A NonMonotonic Description Logic for Reasoning About Typicality . Artificial Intelligence 195 ( 2013 ) 165 - 202

12. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Preferential vs Rational Description Logics: which one for Reasoning About Typicality? . In Coelho, H., Studer , R. , Wooldridge , M., eds. : Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010 ). Volume 215 of FAIA (Frontiers in Artificial Intelligence and Applications)., Lisbon, Portugal, IOS Press ( August 2010 ) 1069 - 1070

13. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Reasoning about typicality in low complexity DLs: the logics E L?Tmin and DL-Litec Tmin . In Walsh, T., ed. : Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011 ), Barcelona, Spain, IOS Press ( 2011 ) 894 - 899

14. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Semantic characterization of Rational Closure: from Propositional Logic to Description Logics . Artificial Intelligence 226 ( 2015 ) 1 - 33

15. Kraus , S. , Lehmann , D. , Magidor , M. : Nonmonotonic reasoning, preferential models and cumulative logics . Artificial Intelligence 44 ( 1-2 ) ( 1990 ) 167 - 207

16. Lehmann , D. , Magidor , M. : What does a conditional knowledge base entail? Artificial Intelligence 55 ( 1 ) ( 1992 ) 1 - 60

17. Baader , F. , Buchheit , M. , Hollunder , B. : Cardinality restrictions on concepts . Artificial Intelligence 88 ( 1-2 ) ( 1996 ) 195 - 213

18. Bordino , I. , Mejova , Y. , Lalmas , M.: Penguins in sweaters, or serendipitous entity search on user-generated content . In He, Q. , Iyengar , A. , Nejdl , W. , Pei , J. , Rastogi , R., eds.: 22nd ACM International Conference on Information and Knowledge Management , CIKM'13 , San Francisco, CA, USA, October 27 - November 1 , 2013 . ( 2013 ) 109 - 118

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

20. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Minimal model semantics and rational closure in description logics . In Eiter, T., Glimm , B. , Kazakov , Y. , Kro¨tzsch, M., eds.: Informal Proceedings of the 26th International Workshop on Description Logics. Volume 1014 of CEUR Workshop Proceedings., CEUR-WS.org ( 2013 ) 168 - 180

21. Tobies , S.: The complexity of reasoning with cardinality restrictions and nominals in expressive description logics . Journal of Artificial Intelligence Research (JAIR) 12 ( 2000 ) 199 - 217

22. Pozzato , G.L. : On Reasoning about surprising scenarios in Preferential Description Logics . In: Technical Report 02/2015 , http://www.di.unito.it/spozzato/papers/RT022015.pdf, Dip. di Informatica, Univ. di Torino . ( 2015 )

23. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Rational closure in SHIQ . In: DL 2014 , 27th International Workshop on Description Logics. Volume 1193 of CEUR Workshop Proceedings., CEUR-WS.org ( 2014 ) 543 - 555