Reasoning about plausible scenarios in Description Logics of typicality

Abstract

In some application domains it is sometimes useful to reason about plausible but “not obvious” scenarios, excluding the most trivial ones. In this work we introduce nonmonotonic procedures for preferential Description Logics in order to reason about plausible but – in some sense – “surprising” scenarios. We consider an extension, called $ALC + T_{R}^{\exp}$ , of the nonmonotonic logic of typicality $ALC + T_{R}$ by inclusions of the form T (C) ⊑ _dD, where d is a degree of expectedness. We consider a notion of extension of an ABox, in order to assume typicality assertions about individuals satisfying cardinality restrictions on concepts, then we define a preference relation among such extended ABoxes based on the degrees of expectedness, then we restrict entailment to those extensions that are minimal with respect to this preference relation. We propose a decision procedure for reasoning in $ALC + T_{R}^{\exp}$ and we exploit it to show that entailment is in ExpTime as for the underlying $ALC$ . Last, we introduce a further extension of the proposed approach in order to reason about all plausible extensions of the ABox, by restricting the attention to specific degrees of expectedness ranging from the most surprising scenarios to the most expected ones, and we show that entailment remains in ExpTime also in these cases.

Keywords

Description Logics nonmonotonic reasoning typicality

1 Introduction

Nonmonotonic extensions of Description Logics (from now on, DLs for short) have been actively investigated since the early 90s [4–6 , 28] in order to tackle the problem of representing prototypical properties of classes and to reason about defeasible inheritance. A simple but powerful nonmonotonic extension of DLs is proposed in [16–19 , 21]:in this approach “typical” or “normal” properties can be directly specified by means of a “typicality” operator T enriching the underlying DL. The semantics of the T operator is characterized by the core properties of nonmonotonic reasoning axiomatized by either preferential logic [22] or rational logic [23]. We focus on the Description Logic $ALC + T_{R}$ introduced in [21]. In this logic one can express defeasible inclusions such as “typical depressed persons have sleep disorders”:

T (Depressed) ⊑ ∃ Symptom . SleepDisorder (*)

As a difference with standard DLs, one can consistently express exceptions and reason about defeasible inheritance as well. For instance, a knowledge base can consistently express that “normally, a patient affected by depression is not able to react to positive life events”, whereas “mood reactivity (ability to feel better temporarily in response to positive life events) is a typical symptom of atypical depression” as follows:

AtypicalDepressed ⊑ Depressed

T (Depressed) ⊑ ¬ ∃ Symptom . MoodReactivity

T (AtypicalDepressed) ⊑ ∃ Symptom .

MoodReactivity

In the Description Logic $ALC + T_{R}$ standard models are 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 (C^{I})$ . 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: as an example, the property known as specificity, namely the choice of according preference to more specific information in case of conflicts among inherited properties, results “built-in” in the approach.

The logic $ALC + T_{R}$ itself is too weak in several application domains. Indeed, although the operator T is nonmonotonic (T (C) ⊑ E does not imply T (C ⊓ D) ⊑ E), the logic $ALC + T_{R}$ 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 (∃Symptom . 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 overcome this limit and perform useful inferences, in [21] the authors have introduced a nonmonotonic extension of the logic $ALC + T_{R}$ based on a minimal model semantics, corresponding to a notion of rational closure as defined in [23] 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 + T_{R}^{RaCl}$ , 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 + T_{R}^{RaCl}$ is based on a preference relation among $ALC + T_{R}$ models and a notion of minimal entailment restricted to models that are minimal with respect to such preferencerelation.

The logic $ALC + T_{R}^{RaCl}$ imposes to consider all 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 [1]. As a further example, consider the following KB, representing knowledge about toys and children preferences about them:

T (ActionFigure) ⊑ BoysToy (1)

T (TechToy) ⊑ BoysToy (2)

T (Vehicle) ⊑ BoysToy (3)

T (Dollhouse) ⊑ ¬ BoysToy (4)

representing that, normally, action figures, tech toys and vehicles are toys appreciated by boys, whereas dollhouses are not (last inclusion). Suppose the assertional part of the KB contains the facts:

ActionFigure(techThor) (a)

TechToy(techThor) (b)

Vehicle(garagePlayset) (c)

ActionFigure(yoKaiJibanyan) (d)

Facts (a) and (b) state that the action figure of the Avengers titan hero Thor is also a tech toy, since it really speaks. Fact (c) means that a garage playset is classified in the “vehicle” category, whereas fact (d) states that we can consider the action figure of Yo-kai Watch’s Jibanyan. In the nonmonotonic logic $ALC + T_{R}^{RaCl}$ we are able to infer the following facts:

T (ActionFigure) (techThor)

T (TechToy) (techThor)

T (Vehicle) (garagePlayset)

T (ActionFigure) (yoKaiJibanyan)

and then that techThor, garagePlayset, and yoKaiJibanyan are all boys’ toys. This happens in $ALC + T_{R}^{RaCl}$ because it is consistent to make the three assumptions above, that hold in all minimal models, however one should be interested in selecting only one toy (for instance, for a present), therefore considering three distinct scenarios that cannot be captured by $ALC + T_{R}^{RaCl}$ as it is. One could think of extending the logic $ALC + T_{R}^{RaCl}$ by means of cardinality restrictions, in the example by imposing that there is only one member of the extension of the concept BoysToy, 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, in the above example about toys, one could be interested in selecting an appreciated boys’ toy, but not the most “obvious” one, in order to minimize the risk of duplication of birthday gifts. The ontology engineer could need to represent different degrees of typical properties: action figures and vehicles are both typical boys’ toys, however there are more exceptions of action figures not intended for boys only with respect to vehicles. In this respect, having the need of choosing only one present and of being not “trivial” in this choice, it could be useful to conclude that the action figure of Yo-kai Watch’s Jibanyan has to be preferred to a garage playset as well as to the “less unexpected” action figure of Thor. As another example, 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” [11]. In this sense, the scenario (among those satisfying cardinality restrictions) obtained by assuming the largest set of consistent typicality assumptions in $ALC + T_{R}^{RaCl}$ corresponds to the most trivial one, whereas one could be interested in less expected ones, in which some typicality assumptions are discarded.

In this work we introduce the logic $ALC + T_{R}^{\exp}$ , which is based on the combination of two components. On the one hand, we allow one to express different degrees of expectedness of typicality inclusions, having the form T (C) ⊑ _dD 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 d′ ≤ d: this allows one 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. We then define notions of skeptical and credulous entailment and we describe a sound and complete decision procedure that allows us to show that reasoning in $ALC + T_{R}^{\exp}$ is ExpTime-complete for both skeptical and credulous entailment.

The plan of the paper is as follows. In Section 2 we recall Description Logics of typicality $ALC + T_{R}$ and $ALC + T_{R}^{RaCl}$ , then in Section 3 we introduce the logic $ALC + T_{R}^{\exp}$ , allowing to express degrees of expectedness of typicality inclusions as well as cardinality restrictions, and to reason about surprising scenarios. In Section 4 we provide a decision procedure for checking query entailment in $ALC + T_{R}^{\exp}$ , then we exploit it to show that the complexity of reasoning in $ALC + T_{R}^{\exp}$ is in ExpTime. In Section 5 we extend the proposed approach in order to reason about scenarios “in the middle”, each one characterized by a specific degree of expectedness, ranging from the most surprising to the most expected situations, and we show that reasoning in $ALC + T_{R}^{\exp}$ is in ExpTime also in this case. In Section 6 we mention related works, focusing on the differences between the logic $ALC + T_{R}^{\exp}$ and the closest approaches of DLs allowing the formalization of priorities among inclusions and probabilistic DLs under the DISPONTE semantics: in particular, for the former, we show that priorities among defaults are provided for free by the underlying logic of typicality, and not by means of degrees of expectedness; for the latter, we show that the logic $ALC + T_{R}^{\exp}$ allows one to perform useful reasoning that cannot be captured by reasoning in probabilistic DLs. We conclude in Section 7 with a brief discussion on how we aim at extending our approach in futureresearch.

This work is an extended and improved version of [25], whereas preliminary ideas have been outlined by considering an extension of the lightweight DL-Lite_core for surprising scenarios in [24].

2 Preferential Description Logics

2.1 The monotonic logic $ALC + T_{R}$

The logic $ALC + T_{R}$ is obtained by adding to standard $ALC$ the typicality operator T [16]. 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 ⊑ D), and those that only hold for the normal or typical instances of C (T (C) ⊑ D).

The semantics of the T operator can be given by means of a set of postulates that are a reformulation of axioms and rules of nonmonotonic entailment in rational logic R [23]: in this respect an assertion of the form T (C) ⊑ D is equivalent to the conditional assertion C|~ ∣ ∼ D in R. The basic ideas are as follows: given a domain $Δ^{I}$ and an evaluation function $.^{I}$ , one can define a function $f_{T} : Pow (Δ^{I}) ⟼ Pow (Δ^{I})$ that selects the typical instances of any $S \subseteq Δ^{I}$ ; in case $S = C^{I}$ for a concept C, the selection function selects the typical instances of C, namely: $(T (C))^{I} = f_{T} (C^{I}) .$ f_T has the following properties for all subsets S of $Δ^{I}$ , that are essentially a restatement of the properties characterizing rational logic R:

(f_T - 1) f_T (S) ⊆ S

(f_T - 2) if S ¬ = ∅ , thenalso f_T (S) ¬ = ∅

(f_T - 3) if f_T (S) ⊆ R, then f_T (S) = f_T (S ∩ R)

(f_T - 4) f_T (⋃ S_i) ⊆ ⋃ f_T (S_i)

(f_T - 5) ⋂ f_T (S_i) ⊆ f_T (⋃ S_i)

(f_T - 6) if f_T (S) ∩ R ¬ = ∅ , then f_T (S ∩ R) ⊆ f_T (S)

The semantics of the T operator can be equivalently formulated in terms of rational models [21]: a model $M$ is any structure $〈 Δ^{I}, <, .^{I} 〉$ where $Δ^{I}$ is the domain, < is an irreflexive, transitive, well-founded and modular (for all x, y, z in $Δ^{I}$ , if x < y then either x < z or z < y) relation over $Δ^{I}$ . 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 \in Δ^{I}$ is a typical instance of some concept C if $x \in C^{I}$ and there is no C-element in $Δ^{I}$ more typical than x. In detail, $.^{I}$ is the extension function that maps each concept C to $C^{I} \subseteq Δ^{I}$ , and each role R to $R^{I} \subseteq Δ^{I} \times Δ^{I}$ . For concepts of $ALC$ , $C^{I}$ is defined as usual. For the T operator, we have $(T (C))^{I} = {Min}_{<} (C^{I}),$ where ${Min}_{<} (C^{I}) = {x \in C^{I} ∣ ∄ y \in C^{I} s . t . y < x}$ . A model $M$ can be equivalently defined by postulating the existence of a function $k_{M} : Δ^{I} ⟼ ℕ$ , where $k_{M}$ assigns a finite rank to each domain element: the rank function $k_{M}$ and < can be defined from each other by letting x < y if and only if $k_{M} (x) < k_{M} (y)$ .

Given standard definitions of satisfiability of a KB in a model, we define a notion of entailment in $ALC + T_{R}$ . Given a query F (either an inclusion C ⊑ D or an assertion C (a) or an assertion of the form R (a, b)), we say that F is entailed from a KB, written KB $⊨_{ALC + T_{R}} F$ , if F holds in all $ALC + T_{R}$ models satisfying KB.

2.2 The nonmonotonic logic $ALC + T_{R}^{RaCl}$

Even if the typicality operator T itself is nonmonotonic (i.e. T (C) ⊑ E does not imply T (C ⊓ D) ⊑ E), what is inferred from a KB can still be inferred from any KB’ with KB ⊆ KB’, i.e. the logic $ALC + T_{R}$ is monotonic. In order to perform useful nonmonotonic inferences, in [21] 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 + T_{R}^{RaCl}$ and it corresponds to a notion of rational closure on top of $ALC + T_{R}$ . Such a notion is a natural extension of the rational closure construction provided in [23] for the propositional logic.

The nonmonotonic semantics of $ALC + T_{R}^{RaCl}$ 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 KB. A model $M$ is a minimal canonical model of KB if it satisfies KB, it is minimal and it is canonical 1 . A query F is minimally entailed from a KB, written KB $⊨_{ALC + T_{R}^{RaCl}} F$ , if it holds in all minimal canonical models of KB. In [21] it is shown that query entailment in $ALC + T_{R}^{RaCl}$ is in ExpTime. The construction of the rational closure and the correspondence between semantics and construction is recalled in Section 4.2.

3 Between $ALC + T_{R}$ and $ALC + T_{R}^{RaCl}$ : The logic $ALC + T_{R}^{\exp}$

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 [16], 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 alternative, plausible, but not obvious scenarios. 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 extensions: intuitively, an extension is preferred to another one if it represents a more surprising scenario.

The logic $ALC + T_{R}^{\exp}$ allows one to express cardinality restrictions in the TBox. More expressive DLs allow one 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 one to express that a student attends to 3 courses. Number restrictions are therefore “localized to the fillers of one particular role” [1], for instance we can have Student ⊑ = 3 Attends. 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 + T_{R}^{\exp}$ , cardinality restrictions on concepts are added to the TBox: they are assertions of the form either (≥ n C) or (≤ n C) or (= n C), where n is a positive integer and C is a concept, as proposed in [1]. This is formally defined in the next definition, where, given a set S, ♯S is the cardinality of S.

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

C : = A ∣ ⊤ ∣ ⊥ ∣ ¬ C ∣ C ⊓ C ∣ C ⊔ C ∣ ∀ R . C ∣ ∃ R . C

An $ALC + T_{R}^{\exp}$ knowledge base is a pair ( $T, A$ ). $T$ contains axioms of the form:

C ⊑ C;

T (C) ⊑ _dC, where $d \in ℕ^{+}$ is called the degree of expectedness;

(⊙ n C), where ⊙ ∈ {= , ≤ , ≥} and $n \in ℕ^{+}$ .

$A$ contains assertions of the form C (a) and R (a, b), where $a, b \in O$ .

Given an inclusion T (C) ⊑ _dD, the higher the degree of expectedness the more the inclusion is, in some sense, “obvious”/not surprising. Given another inclusion T (C′) ⊑ _d′D′, with d′ < 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) ⊑ ₄SocialNetworkUser and T (Student) ⊑ ₂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 known that axioms expressing cardinality restrictions are even more expressive than inclusions C ⊑ D or C ≐ D, the last one shortening for the pair of inclusions C ⊑ D and D ⊑ C (thus expressing that the concepts C and D have the same extensions, i.e. $C^{I} = D^{I}$ ). 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 ⊓ ¬ D) ⊔ (¬ C ⊓ D))). The same for an inclusion of the form C ⊑ D, whose meaning is that every C element is also a D element, that can be expressed by (= 0 (C ⊓ ¬ D)) (the intersection of $C^{I}$ and the complement of $D^{I}$ is empty). Therefore, we could restrict our language to TBoxes only containing cardinality restrictions, however we have decided to consider the extended language of Definition 1 for the sake of readability.

Before introducing technical details and formal definitions (sections 3.1 and 3.2), we provide an example in order to give an intuitive idea of what we mean for reasoning about not obvious scenarios in the logic $ALC + T_{R}^{\exp}$ .

Example 1. (Mysterious medical diagnosis) Let KB = ( $T, \emptyset$ ) where $T$ is as follows:

Depressed ⊑ Condition

ProstateCancerPatient ⊑ Condition

Bipolar ⊑ Condition

AtypicalDepressed ⊑ Depressed

T (Depressed) ⊑ ₂ ¬ ∃ Symptom . MoodReactivity

T (Bipolar) ⊑ ₅ ∃ Symptom . MoodReactivity

T (AtypicalDepressed) ⊑ ₄ ∃ Symptom . MoodReactivity

T (ProstateCancerPatient) ⊑ ₂ ∃ Symptom . MoodReactivity

(≥1 Condition)

(≤2 Condition)

the last ones stating that we want to focus on at least one/at most two conditions determining patient’s symptoms. We have that

(*) T (Depressed ⊓ AcromegalicGiant) ⊑ ¬ ∃ Symptom . MoodReactivity

follows 2 from KB, and this is a wanted inference, since being affected by acromegaly, a rare syndrome that results when the anterior pituitary gland produces excess growth hormone, is irrelevant with respect to mood reactivity as far as we know. This is a nonmonotonic inference that does no longer follow if it is discovered that typical depressed people also affected by acromegaly are subject to mood reactivity: given $T^{'}$ = $T \cup {T (Depressed ⊓ AcromegalicGiant) ⊑ \exists Symptom . MoodReactivity}$ , we have that the inclusion (*) does no longer follow from the KB with $T^{'}$ in the logic $ALC + T_{R}^{\exp}$ . As for rational closure, the set of facts/inclusions that are entailed from a $ALC + T_{R}^{\exp}$ KB is closed under the property known as rational monotonicity: for instance, from KB and the fact that $T (Depressed) ⊑ \neg Elder$ is not entailed from KB in $ALC + T_{R}^{\exp}$ , it follows that the inclusion $T (Depressed ⊓ Elder) ⊑ \neg \exists Symptom . MoodReactivity$ is entailed in $ALC + T_{R}^{\exp}$ . Concerning ABox reasoning, we can think of exploiting the logic $ALC + T_{R}^{\exp}$ in order to find a mysterious medical diagnosis to explain patients’ symptoms and signs, a set of formulas of the form C_r (a) that we call $P$ . For instance, let $P$ describe Greg’s symptom, in particular that he has mood reactivity: $P = {\exists Symptom . MoodReactivity (greg)} .$

We have that $P$ is not entailed by KB, but KB $\cup P$ is consistent. We are then interested in finding a diagnosis for Greg’s symptoms, that is to say a set of assertions $D$ such that $P$ follows from KB $\cup D$ . The most trivial scenario suggests that Greg is affected by the bipolar disorder, i.e. $D = {Bipolar (greg)}$ , however this scenario is discarded in the logic $ALC + T_{R}^{\exp}$ : in this context, the condition that is taken into consideration is prostatic cancer, i.e. $D = {ProstateCancerPatient (greg)},$ and such a non trivial diagnosis could be confirmed by an evaluation of other typical symptoms of such a disease (e.g. nocturia).

One could object that no one would be interested in a medical diagnosis support system that discards the most likely explanation for a medical problem, however, as mentioned in the Introduction, the idea underlying the proposed approach is not to ignore the most expected explanation, rather to “go beyond” it in order to find (unexpected) alternative ones in case of a failure with the standard diagnosis. In other words: if the most likely explanation does not provide a solution, the logic $ALC + T_{R}^{\exp}$ tries to provide less obvious alternatives that could be taken into account for further investigations.

3.1 Extensions of ABox

Given a KB, we define the finite set $ℂ$ of concepts occurring in the scope of the typicality operator, i.e. $ℂ = {C ∣ T (C) ⊑_{d} D \in KB}$ . 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 + T_{R}^{RaCl}$ , with $C \in ℂ$ . We then consider an ordered set $ℂ_{A}$ of pairs (a, C) of all possible assumptions T (C) (a), for all concepts $C \in ℂ$ and all individual constants a occurring in the ABox.

Definition 2. (Assumptions in $ALC + T_{R}^{\exp}$ ) Given an $ALC + T_{R}^{\exp}$ KB=( $T \cup T_{card}, A$ ), where $T_{card}$ is a set of cardinality restrictions and $T$ does not contain cardinality restrictions, let $T^{'}$ be the set of inclusions of $T$ without degrees of expectedness, namely $T^{'} = {T (C) ⊑ D ∣ T (C) ⊑_{d} D \in T} \cup {C ⊑ D \in T}$ . Given a finite set of concepts $ℂ$ , we define, for each individual name a occurring in $A$ : $ℂ_{a} = {C \in ℂ ∣ (T^{'}, A) ⊨_{ALC + T_{R}^{RaCl}} T (C) (a)}$

We also define $ℂ_{A}$ : $ℂ_{A} = {(a, C) ∣ C \in ℂ_{a} and a occurs in A}$ and we impose an order on the elements of $ℂ_{A}$ : $ℂ_{A} = [(a_{1}, C_{1}), (a_{2}, C_{2}), \dots, (a_{n}, C_{n})] .$ Furthermore, we define the ordered multiset $d_{A} = [d_{1}, d_{2}, \dots, d_{n}]$ , respecting the order imposed on $ℂ_{A}$ , where $d_{i} = avg ({d \in ℕ^{+} ∣ T (C_{i}) ⊑_{d} D \in T})$ .

Intuitively, the ordered multiset $d_{A}$ is a tuple of the form [d₁, d₂, …, d_n], where d_i is the degree of expectedness of the assumption T (C) (a), such that $(a, C) \in ℂ_{A}$ at position i. d_i corresponds to the average 3 of all the degrees d of typicality inclusions T (C) ⊑ _dD 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 $d_{A} = [d_{1}, d_{2}, \dots, d_{n}]$ , the first step is to build all alternative tuples where 0 is used in place of some d_i 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). To give an intuitive idea, before introducing the formal definitions, let us consider the following example:

Example 2. Given a KB= $(T, A)$ , let the only typicality inclusions in $T$ be T (C) ⊑ ₁D and T (E) ⊑ ₂F. Let a and b be the only individual constants occurring in $A$ . Suppose also that T (C) (a), T (C) (b), and T (E) (b) are entailed in $ALC + T_{R}^{RaCl}$ , more precisely:

let KB’ be the knowledge base obtained by replacing T (C) ⊑ ₁D and T (E) ⊑ ₂F in $T$ by T (C) ⊑ D and T (E) ⊑ F, respectively;

suppose that:

KB’ $⊨_{ALC + T_{R}^{RaCl}} T (C) (a)$

KB’ $⊨_{ALC + T_{R}^{RaCl}} T (C) (b)$

KB’ $⊨_{ALC + T_{R}^{RaCl}} T (E) (b)$

We have that $ℂ_{A} = {(a, C), (b, C), (b, E)} and d_{A} = [1, 1, 2]$ The other possible tuples (strings) are:

- [0, 0, 2], corresponding to extending $A$ with the only assumption T (E) (b);

- [0, 1, 0], corresponding to extending $A$ with the only assumption T (C) (b);

- [1, 0, 0], corresponding to extending $A$ with the only assumption T (C) (a);

- [0, 1, 2], corresponding to extending $A$ with the assumptions T (C) (b) and T (E) (b);

- [1, 0, 2], corresponding to extending $A$ with the assumptions T (C) (a) and T (E) (b);

- [1, 1, 0], corresponding to extending $A$ with the assumptions T (C) (a) and T (C) (b)-

- [0, 0, 0], corresponding to not extending $A$ (the set of typicality assumptions is empty).

Let us now introduce formal definitions for the above mentioned notions of string of assumptions and of extension of an ABox corresponding to a string.

Definition 3. (Strings of possible assumptions $𝕊$ ) Given a KB=( $T, A$ ), let the set $ℂ_{A}$ and $d_{A} = [d_{1}, d_{2}, \dots, d_{n}]$ be as in Definition 2. We define the set $𝕊$ of all the strings of possible assumptions with respect to KB as $𝕊 = {[s_{1}, s_{2}, \dots, s_{n}] ∣$

∀i = 1, 2, …, n either s_i = d_i or s_i = 0}

Definition 4. (Extension of the ABox) Let KB = ( $T, A$ ) and let $ℂ_{A} = [(a_{1}, C_{1}), (a_{2}, C_{2}), \dots, (a_{n}, C_{n})]$ as in Definition 2. Given a string of possible assumptions $[s_{1}, s_{2}, \dots, s_{n}] \in 𝕊$ of Definition 3,we define the extension $\hat{A}$ of $A$ with respect to $ℂ_{A}$ and $𝕊$ as: $\hat{A} = {T (C_{i}) (a_{i}) ∣ (a_{i}, C_{i}) \in ℂ_{A} and s_{i} \neq 0}$

It can be observed that, in $ALC + T_{R}^{RaCl}$ , the set of typicality assumptions that can be inferred from a KB corresponds to the extension of $A$ corresponding to the string $d_{A}$ (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 + T_{R}$ , no typicality assumptions 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 + T_{R}^{\exp}$ 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 = 〈 Δ^{I}, <, .^{I} 〉$ , itsatisfies:

(TBox)

an inclusion C ⊑ D if $C^{I} \subseteq D^{I}$ ;

a typicality inclusion T (C) ⊑ _dD if Min_< (C^ℐ) ⊆ D^ℐ;

a cardinality restriction of the form (⊙ n C) if $♯ C^{I} ⊙ n$ , where ⊙ ∈ {≤ , ≥ , =} and $n \in ℕ^{+}$ .

(ABox)

an assertion of the form C (a) if $a^{I} \in C^{I}$ ;

an assertion of the form R (a, b) if $(a^{I}, b^{I}) \in R^{I}$ .

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

Definition 6. (Eligible extension $\hat{A}$ ) Given an $ALC + T_{R}^{\exp}$ KB=( $T, A$ ) and an extension $\hat{A}$ of $A$ as in Definition 4, we say that $\hat{A}$ is eligible if there exists an $ALC + T_{R}^{\exp}$ model $M$ as in Definition 5 that satisfies KB’=( $T, A \cup \hat{A}$ ).

Definition 7. (Order between eligible extensions) Given KB=( $T, A$ ) and the set $𝕊$ of Definition 3, let s = [s₁, s₂, …, s_n] and r = [r₁, r₂, …, r_n], with $s, r \in 𝕊$ . Let $\hat{A_{s}}$ and $\hat{A_{r}}$ 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 (s_i, r_j) ∈ δ, it holds that s_i ≤ r_j, and there is at least one (s_i, r_j) ∈ δ such that s_i < r_j. We say that $\hat{A_{s}}$ is more surprising (or less trivial) than $\hat{A_{r}}$ 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 again the knowledge base of Example 2: given the strings s = [1, 1, 0] and r = [1, 0, 2], we have that s < r, because there exists a bijection {(1, 1), (0, 0), (1, 2)}. 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] ≮ [0, 0, 2] and [0, 0, 2] notlessthan [1, 1, 0]. In order to choose between two incomparable situations, we introduce the following notion of weak order: intuitively, given two incomparable extensions $\hat{A_{s}}$ and $\hat{A_{r}}$ , we assume that $\hat{A_{s}}$ is weakly less trivial than $\hat{A_{r}}$ if $\hat{A_{r}}$ is strictly included in another eligible extension $\hat{A_{u}}$ more trivial than $\hat{A_{s}}$ , i.e. $\hat{A_{r}} \subset \hat{A_{u}}$ and s < u. As an example, consider the KB whose TBox is {T (Bird) ⊑ ₂Fly} and whose ABox is: ${T (Bird) (tweety), T (Bird) (jim), T (Bird) (mike)}$ and the tuples:

s₁ = [2, 2, 0]

s₂ = [2, 0, 0]

s₃ = [0, 0, 2]

corresponding to the following extensions:

$\hat{A_{1}} = {T (Bird) (tweety), T (Bird) (jim)}$

$\hat{A_{2}} = {T (Bird) (tweety)}$

$\hat{A_{3}} = {T (Bird) (mike)}$

we have that the extensions $\hat{A_{2}}$ and $\hat{A_{3}}$ are not comparable, however $\hat{A_{2}}$ is a proper subset of $\hat{A_{1}}$ , which is more “obvious” than $\hat{A_{3}}$ (indeed, s₃ < s₁). Therefore, we assume that the scenario represented by $\hat{A_{3}}$ is weakly less trivial than the one represented by $\hat{A_{2}}$ .

This is formally stated in next definition:

Definition 8. (Weak preference) Given a KB =( $T, A$ ), let $\hat{A_{s}}$ and $\hat{A_{r}}$ be two eligible extensions of $A$ such that neither $\hat{A_{s}}$ is more surprising than $\hat{A_{r}}$ nor $\hat{A_{r}}$ is more surprising than $\hat{A_{s}}$ . We say that $\hat{A_{s}}$ is (weakly) more surprising (or (weakly) less trivial) than $\hat{A_{r}}$ if there exists an eligible extension $\hat{A_{u}}$ of $A$ such that (i) $\hat{A_{s}}$ is more surprising than $\hat{A_{u}}$ (Definition 7)and (ii) $\hat{A_{r}} \subset \hat{A_{u}}$ .

Definition 9. (Minimal (perfect) extensions) Given a KB=( $T, A$ ) and the set $𝕊$ of strings of possible assumptions (Definition 3), we say that an eligible extension $\hat{A_{s}}$ is minimal if there is no other eligible extension $\hat{A_{r}}$ which is (weakly) more surprising (or (weakly) less trivial) than $\hat{A_{s}}$ .

Given the above definitions, we can define a notion of entailment in $ALC + T_{R}^{\exp}$ . Intuitively, given a query F, we distinguish two cases:

if F is a TBox inclusion C ⊑ D (even if it is a typicality inclusion, i.e. C has the for T (C′)), we rely on reasoning in the nonmonotonic logic $ALC + T_{R}^{RaCl}$ and we say that F is entailed by KB if it is minimally entailed in $ALC + T_{R}^{RaCl}$ from KB or, equivalently, F is in the rational closure of KB;

if F is an ABox fact C (a), we check whether F follows in the monotonic logic $ALC + T_{R}$ from a given KB, whose ABox is augmented with extensions that are minimal (perfect) as in Definition 9. 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 definitions:

Definition 10. (Skeptical entailment in $ALC + T_{R}^{\exp}$ ) Given a KB=( $T, A$ ) and given $ℂ$ a set of concepts, let $ε$ the set of all extensions of $A$ that are minimal as in Definition 9. Given a query F, we say that F is skeptically entailed from KB in $ALC + T_{R}^{\exp}$ , written KB $⊨_{ALC + T_{R}^{\exp}}^{sk} F$ :

if F is a TBox inclusion C ⊑ D, if it holds that KB $⊨_{ALC + T_{R}^{RaCl}} F$ ;

if F is an ABox fact C (a), where $a \in O$ , if ( $T, A \cup \hat{A}$ ) $⊨_{ALC + T_{R}} F$ for all $\hat{A} \in ε$ .

Definition 11. (Credoulous entailment in $ALC + T_{R}^{\exp}$ ) Given a KB=( $T, A$ ) and given $ℂ$ a set of concepts, let $ε$ the set of all extensions of $A$ that are minimal as in Definition 9. Given a query F, we say that F is credulously entailed from KB in $ALC + T_{R}^{\exp}$ , written KB $⊨_{ALC + T_{R}^{\exp}}^{cr} F$ :

if F is a TBox inclusion C ⊑ D, if it holds that KB $⊨_{ALC + T_{R}^{RaCl}} F$ ;

if F is an ABox fact C (a), where $a \in O$ , if there exists $\hat{A} \in ε$ such that ( $T, A \cup \hat{A}$ ) $⊨_{ALC + T_{R}} F$ .

At a first glance, one could have the impression that the notions of rank in the semantics of $ALC + T_{R}^{RaCl}$ , where elements with lowest rank are the most typical ones, and the semantics of expectedness of Definitions 7 and 9, 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 extensions of typicality concepts, and this is also considered in the expectation semantics to select plausible typicality assumptions. The rank among extensions is rather used in order to choose less trivial 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 this section by recalling the example inspired by sports entertainment taken from [24].

Example 3. (Better Royal Rumble Match) The term sports entertainment is usually associated to professional wrestling, a combat sport combining athletics with theatrical performance. As a difference with typical athletics and games, which are conducted for competition, the main objective of sports entertainment is to entertain an audience. Wrestling matches are driven by storylines provided by a creative team, and their outcomes are predetermined: duration, sequence of athletic moves and, obviously, winners of the contests. One of the most attractive events in professional wrestling is the WWE Royal Rumble match: thirty athletes are involved in this competition, and the winner receives a title shot in the main annual event of the company. The objective of each participant is to eliminate all the other competitors by tossing them over the top rope of the ring; an athlete is eliminated if both his feet touch the floor outside the ring. The match starts with the two participants who have drawn entry numbers one and two, with the remaining competitors entering the ring at regular timed intervals, usually 90 seconds, according to their entrance number assigned by means of a lottery. On the contrary, the assignment of entrance numbers to the participants, the sequence of eliminations (who eliminates who), the last man being eliminated, as well as the winner himself are determined by the choices of a creative team and scheduled in all the details. In the last years, the Royal Rumble match has been marked by an extremely negative audience reaction: the trivial sequence of eliminations, as well as the fact that the winners have been predicted before the match by professional wrestling web sites, lead the people in the arena to “boo” every single action of the show. In this example we exploit the logic $ALC + T_{R}^{\exp}$ in order to tackle the problem of defining a better script for the Royal Rumble match, focusing on the selection of the winner. Let the TBox be as follows:

T (FaceWrestler) ⊑ ₁RoyalRumbleWinner (T1)

T (Returning) ⊑ ₃RoyalRumbleWinner (T2)

T (Predicted) ⊑ ₂RoyalRumbleWinner (T3)

(= 1 RoyalRumbleWinner) (T4)

the last one stating that there could be only one winner. Concerning typicality inclusions, we represent the facts that normally, a face wrestler wins the Royal Rumble match (T1), however this admits more exceptions with respect to the fact that, typically, an athlete whose victory has been predicted by wrestling web sites normally wins the Royal Rumble match (T3), which is in turn more surprising than the most “obvious” inclusion, namely that an athlete returning from an injury wins the Royal Rumble match (T2). Let the ABox be:

FaceWrestler(dean)

Returning(seth)

FaceWrestler(roman)

Predicted(roman)

In the logic $ALC + T_{R}^{\exp}$ , we can infer that Dean is the winner of the Royal Rumble match:

KB $⊨_{ALC + T_{R}^{\exp}}^{sk} RoyalRumbleWinner (dean)$

KB $⊨_{ALC + T_{R}^{\exp}}^{cr} RoyalRumbleWinner (dean)$

since there is only one perfect extension. Let $ℂ = {FaceWrestler, Predicted, Returning}$ . By Definition 2 above, we have that: $ℂ_{dean} = {FaceWrestler}$ , $ℂ_{roman} = {FaceWrestler, Predicted}$ , $ℂ_{seth} =$ {Returning}. Furthermore, consider $ℂ_{A} = ℂ_{dean} \cup ℂ_{roman} \cup ℂ_{seth}$ in this order. Concerning the degrees of expectedness, we have $d_{A} = [1, 1, 2, 3]$ . As mentioned, in $ALC + T_{R}^{RaCl}$ the minimal model semantics forces all the consistent typicality assumptions, namely we are considering an ABox extended with the following facts:

T (FaceWrestler) (dean)

T (FaceWrestler) (roman)

T (Predicted) (roman)

T (Returning) (seth)

corresponding (in the sense of Definition 4) to the multiset [1, 1, 2, 3]. However, in $ALC + T_{R}$ we obtain that Dean, Roman and Seth are all winners, against the fact that we want to have only one winner: the extension corresponding to [1, 1, 2, 3] is indeed not eligible in the sense of Definition 6. In order to find only one winner and to obtain a non-trivial outcome of the match, we consider the set $𝕊$ of all possible strings of typicality assumptions (Definition 3). The only eligible extensions of the ABox are:

$\hat{A_{1}} = {T (Returning) (seth)}$ , by [0, 0, 0, 3]

$\hat{A_{2}} = {T (Predicted) (roman)}$ , by [0, 0, 2, 0]

$\hat{A_{3}} = {T (FaceWrestler) (dean)}$ , by [1, 0, 0, 0]

$\hat{A_{4}} = {T (FaceWrestler) (roman)}$ , by [0, 1, 0, 0]

$\hat{A_{5}} = {T (FaceWrestler) (roman),$

T (Predicted) (roman)}, corresponding to [0, 1, 2, 0]

We have that $\hat{A_{3}}$ and $\hat{A_{4}}$ are less trivial than $\hat{A_{5}}$ , because [1, 0, 0, 0] < [0, 1, 2, 0] and [0, 1, 0, 0] < [0, 1, 2, 0]. Furthermore, $\hat{A_{3}}$ and $\hat{A_{4}}$ are less trivial than $\hat{A_{1}}$ (again, [1, 0, 0, 0] < [0, 0, 0, 3] and [0, 1, 0, 0] < [0, 0, 0, 3]). Moreover, $\hat{A_{3}}$ and $\hat{A_{4}}$ are less trivial than $\hat{A_{2}}$ (again, [1, 0, 0, 0] < [0, 0, 0, 2] and [0, 1, 0, 0] < [0, 0, 0, 2]). The strings [1, 0, 0, 0] and [0, 1, 0, 0] are not comparable, however $\hat{A_{3}}$ is weakly less trivial than $\hat{A_{4}}$ , since $\hat{A_{4}} \subset \hat{A_{5}}$ and [1, 0, 0, 0] < [0, 1, 2, 0]. This allows one to conclude that $\hat{A_{3}}$ is minimal (the perfect extension) and to suggest that Dean has to be chosen as the winner of the Royal Rumble match.

4 A decision procedure for $ALC + T_{R}^{\exp}$

In this section we describe a decision procedure for reasoning in the logic $ALC + T_{R}^{\exp}$ . 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 + T_{R}^{\exp}$ 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 [2].

The procedure performs the following steps:

compute the set $ℂ_{a}$ of all typicality assumptions that are minimally entailed from the KB in the nonmonotonic logic $ALC + T_{R}^{RaCl}$ ;

compute all possible extensions of the ABox and select perfect extensions;

check whether the query F is entailed from at least one extension/all the extensions of KB in the monotonic logic $ALC + T_{R}$ plus cardinality restrictions.

Step 3 is based on reasoning in the monotonic logic $ALC + T_{R}$ : to this aim, the procedure relies on a polynomial encoding of $ALC + T_{R}$ into $ALC$ introduced in [20] and then on reasoning with cardinality restrictions. Step 1 is based on reasoning in the nonmonotonic logic $ALC + T_{R}^{RaCl}$ : in this case, the procedure computes the rational closure of an $ALC + T_{R}$ knowledge base by means of the algorithm introduced in [21], 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 + T_{R}$ , 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 [29], namely that reasoning in $ALCO$ , extending $ALC$ with qualified number restrictions, is ExpTime-complete also with cardinality restrictions. Before introducing the overall procedure for reasoning in $ALC + T_{R}^{\exp}$ and analyze its complexity, we briefly recall procedures for reasoning in $ALC + T_{R}$ and $ALC + T_{R}^{RaCl}$ .

4.1 Reasoning in $ALC + T_{R}$

In order to reason in $ALC + T_{R}$ , in [20] the authors provide the following polynomial encoding in standard $ALC$ of KB 4 . The idea on which the encoding is based exploits the definition of the typicality operator T in terms of a Gödel-Löb modality □ as follows: T (C) is defined as C ⊓ □ ¬ C where the accessibility relation of the modality □ is the preference relation < in $ALC + T_{R}$ models.

Let KB=( $T, A$ ) be a knowledge base where $A$ does not contain positive typicality assertions on individuals of the form T (C) (a). We define the encoding KB’=( $T^{'}, A^{'}$ ) of KB in $ALC$ as follows. First of all, we let $A^{'} = \emptyset$ . Then, for each $A ⊑ B \in T$ , not containing T, we introduce A ⊑ B in $T^{'}$ . For each T (A) occurring in $T$ , we introduce a new atomic concept Box_¬A and, for each inclusion $T (A) ⊑_{d} B \in T$ , we add to $T^{'}$ the inclusion $A ⊓ {Box}_{\neg A} ⊑ B .$

In order to capture the properties of the □ modality, a new role R is introduced to represent the relation < in preferential models, and the following inclusions are introduced in $T^{'}$ :

Box_¬A ⊑ ∀ R. (¬A ⊓ Box_¬A)

¬Box_¬A ⊑ ∃ R . (A ⊓ Box_¬A)

The first inclusion accounts for the transitivity of <. The second inclusion accounts for the well-foundedness, namely the fact that if an element is not a typical A element then there must be a typical A element preferred to it. For the encoding of the inclusions, if C_l ⊑ C_r is not a typicality inclusion, then $C_{l}^{'} = C_{l}$ and $C_{r}^{'} = C_{r}$ ; if C_l ⊑ C_r is a typicality inclusion T (A) ⊑ C_r, then $C_{l}^{'} = A ⊓ {Box}_{\neg A}$ and $C_{r}^{'} = C_{r}$ .

The size of KB’ is polynomial in the size of the KB. The same for $C_{l}^{'}$ and $C_{r}^{'}$ , assuming the size of C_l and C_r be polynomial in the size of KB.

Given the above encoding, in [20] it is shown that (we write KB $⊨_{ALC} F$ to mean that F holds in all $ALC$ models of KB): KB $⊨_{ALC + T_{R}} C_{l} ⊑ C_{r}$ if and only if KB’ $⊨_{ALC} C_{l}^{'} ⊑ C_{r}^{'}$

and, as a consequence, that the problem of deciding entailment in $ALC + T_{R}$ is in ExpTime, since reasoning in $ALC$ is ExpTime-complete. ExpTime-hardness follows from the fact that $ALC + T_{R}$ includes $ALC$ . In conclusion, the problem of deciding entailment in $ALC + T_{R}$ is ExpTime-complete. This also holds if cardinality restrictions are taken into account: in [29], it is shown that reasoning in the logic $ALCO$ , extending $ALC$ with qualified number restrictions, is ExpTime-complete also with cardinality restrictions. Therefore, we can again conclude that reasoning in $ALC + T_{R}$ with cardinality restrictions is ExpTime-complete. However, as far as we know, the only “concrete” decision procedure for $ALCO$ with cardinality restrictions is the set of transformation rules described in [1], which is in NexpTime.

4.2 Reasoning in $ALC + T_{R}^{RaCl}$

We have mentioned that the semantics of the logic $ALC + T_{R}^{RaCl}$ corresponds to the rational closure of an $ALC + T_{R}$ knowledge base introduced in [21]. Here we recall this machinery, essentially an extension to $ALC + T_{R}$ of the definition of rational closure introduced by Lehmann and Magidor in [23] for the propositional case. We first consider the rational closure with respect to the TBox, in which essentially we only consider which inclusions belong to the rational closure of KB. Next we will consider rational closure with respect to the ABox, in which we consider the individuals explicitly named in the ABox itself.

Definition 12. (Exceptionality) Let KB=( $T, A$ ) be a knowledge base. A concept C is said to be exceptional for KB if and only if KB $⊨_{ALC + T_{R}} T (⊤) ⊑ \neg C$ . An inclusion T (C) ⊑ D is exceptional for KB if C is exceptional for KB. The set of typicality inclusions of KB which are exceptional in KB are denoted as $ε (KB)$ .

Similarly to the rational closure for propositional logic in [23], we introduce a sequence of knowledge bases, starting from the initial one, KB, in order to iteratively use exceptionality in the construction of the rational closure. At each step, in order to reason about the following exceptional subset of KB, we remove the inclusions T (C) ⊑ D of KB that are not exceptional for KB. Before we do this, if there is an assertion $T (C) (a) \in A$ , we add to a all the typical properties of C that we are removing. In order to reason in the same way for equivalent concepts, we need the slightly more complicated formulation of $A_{i}$ below.

Definition 13. Given KB=( $T, A$ ), it is possible to define a sequence of knowledge bases E₀, …, E_i, …, E_n by letting $E_{0} = (T_{0}, A_{0})$ where $T_{0} = T$ and $A_{0} = A$ and, for i > 0, $E_{i} = (T_{i}, A_{i})$ where

$T_{i} = ε (E_{i - 1}) \cup {C ⊑ D \in T ∣$ T does not occur in C}

$A_{i} = A_{i - 1} \cup {(\neg C ⊔ D) (a) ∣$ T (C) ⊑ D in (E_i-1 - E_i) and there is a $T (B) (a) \in A$ such that $E_{i - 1} ⊭_{ALC + T_{R}} T (⊤) ⊑ \neg B$ and $E_{j} ⊨_{ALC + T_{R}} T (⊤) ⊑ \neg B$ for all j < i - 1}

(as a consequence of the next Definition 14, these are the Bs such that rank (B) = i - 1).

Clearly $T_{0} \supseteq T_{1} \supseteq T_{2}, \dots$ , while $A_{0} \subseteq A_{1} \subseteq A_{2}, \dots$ Observe that, being KB finite, there is a least n ≥ 0 such that, for all $m > n, T_{m} = T_{n}$ or $T_{m} = \emptyset$ . We take $(T_{n}, A_{n})$ as the last element of the sequence of knowledge bases starting from KB.

Informally, for the definition of $A_{i}$ , if $T (B) (a) \in A$ (i.e., a is a typical B-element), and B has rank i - 1,then, for all the inclusions T (C) ⊑ D in (E_i-1 - E_i), since C has also rank i - 1 we have that: if a is a C-element, then it is a typical C-element and the assertion (¬ C ⊔ D) (a) must hold.

Definition 14. (Rank of a concept) A concept C has ranki (denoted by rank(C)=i) for KB=( $T, A$ ), if and only if 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)=∞, and we say that C has no rank.

Consider the least n ≥ 0 such that, for all $m > n, T_{m} = T_{n}$ or $T_{m} = \emptyset$ . Then from the above definition it follows that if a concept C has a rank, its highest possible value is n. The notion of rank of a formula allows one to define the rational closure of a knowledge base KB with respect to the TBox.

Definition 15. (Rational closure of TBox) Given KB= (𝒯, 𝒜), we define the rational closure $\bar{T}$ of $T$ , as $\bar{T} = {T (C) ⊑ D ∣ either rank (C) < rank (C ⊓ \neg D) or rank (C) = \infty} \cup {C ⊑ D ∣ KB ⊨_{ALC + T_{R}} C ⊑ D}$ .

Let us now consider the rational closure of the ABox as defined in [21]:

Definition 16. (Rational closure of ABox) Given KB= (𝒯, 𝒜), let a₁, …, a_m be the individuals explicitly named in $A$ . Let k₁, k₂, …, k_h be all the possible rank assignments to the individuals occurring in $A$ .

Given a rank assignment k_j we define:

for each a_i: $μ_{i}^{j} = {(\neg C ⊔ D) (a_{i})$ s.t. T (C) ⊑ D in $\bar{T}$ , and k_j (a_i) = rank (C)} ∪ {(¬ C ⊔ D) (a_i) s.t. $C ⊑ D \in T}$ ;

let $μ^{j} = μ_{1}^{j} \cup \dots \cup μ_{m}^{j}$ for all $μ_{1}^{j} \dots μ_{m}^{j}$ just calculated for all a₁, …, a_m in $A$

We say that k_j is consistent with ( $\bar{T}, A$ ) if:

if $T (C) (a_{i}) \in A$ , then k_j (a_i) = rank(C);

$T \cup A \cup μ^{j}$ is consistent in $ALC + T_{R}$ ;

We say that k_j is minimal and consistent with ( $\bar{T}, A$ ) if k_j is consistent with ( $\bar{T}, A$ ) and there is no k_i consistent with ( $\bar{T}, A$ ) s.t. for all a_i, k_i (a_i) ≤ k_j (a_i) and for some b, k_i (b) < k_j (b).

The rational closure of $A$ ( $\bar{A}$ ) is the set of all assertions derivable in $ALC + T_{R}$ from $T \cup A \cup μ^{j}$ for all minimal consistent rank assignments k_j: $\bar{A} = ⋂_{k_{j} minimal consistent} {C (a) ∣ T \cup A \cup μ^{j} ⊨_{ALC + T_{R}} C (a)}$ .

In [21] it is shown that, given a knowledge base KB=( $T, A$ ), the semantics based on rational models of Section 2.2 is equivalent with the above notion of rational closure of KB, namely:

given an inclusion C ⊑ D, KB $⊨_{ALC + T_{R}^{RaCl}} C ⊑ D$ if and only if $C ⊑ D \in \bar{T}$

given an ABox fact C (a), KB $⊨_{ALC + T_{R}^{RaCl}} C (a)$ if and only if $C (a) \in \bar{A}$ .

Moreover, it is shown that the problem of deciding whether $T (C) ⊑ D \in \bar{T}$ is in ExpTime and that an individual constant a and a concept C, the problem of deciding whether $C (a) \in \bar{A}$ is ExpTime-complete.

Algorithm 1 Skeptical entailment in $ALC + T_{R}^{\exp}$ : KB $⊨_{ALC + T_{R}^{\exp}}^{sk} F$

1: Procedure SKEPTICALENTAILMENT( $T \cup T_{card}, A), T^{'}$ , F, $ℂ$

2: $ℂ_{A} \leftarrow \emptyset$ ▹ build the set $𝕊$ of possible assumptions

3: for each $C \in ℂ$ do

4: for each individual $a \in A$ do ▹Reasoning in $ALC + T_{R}^{RaCl}$

5: if $(T^{'}, A) ⊨_{ALC + T_{R}^{RaCl}} T (C) (a)$ $ℂ_{A} \leftarrow ℂ_{A} \cup {T (C) (a)}$

6: $d_{A} \leftarrow$ build the ordered multiset of avg degrees of Definition 2 given $T$ and $ℂ_{A}$

7: $𝕊 \leftarrow$ build strings of possible assumptions as in Definition 3 given $ℂ_{A}$ and $d_{A}$

8: $A_{pl} \leftarrow \emptyset$ ▹build plausible extensions of $A$

9: for each $d_{i} \in 𝕊$ do

10: build the extension ${\hat{A}}_{i}$ corresponding to d_i

11: $A_{pl} \leftarrow A_{pl} \cup {\hat{A}}_{i}$

12: $A_{el} \leftarrow \emptyset$ ▹select eligible extensions checking cardinality restrictions

13: for each ${\hat{A}}_{i} \in A_{pl}$ do ▹Reasoning in $ALC + T_{R}$ plus cardinality restrictions

14: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) is satisfiable in $ALC + T_{R}$ then

15: $A_{el} \leftarrow A_{el} \cup {\hat{A}}_{i}$

16: for each ${\hat{A}}_{i} \in A_{el}$ do ▹check preference among extensions of $A$

17: for each ${\hat{A}}_{j} \in A_{el}$ do

18: ifd_i ≤ d_j let ${\hat{A}}_{i} < {\hat{A}}_{j}$

19: $ε \leftarrow {{\hat{A}}_{i} ∣ ∄ {\hat{A}}_{j} \in A_{el} such that {\hat{A}}_{j} < {\hat{A}}_{i}}$ ▹select perfect extensions

20: for each ${\hat{A}}_{i} \in ε$ do ▹query entailment in $ALC + T_{R}$ plus cardinality restrictions

21: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) $⊭_{ALC + T_{R}} F$ then

22: return KB $⊭_{ALC + T_{R}^{\exp}}^{sk} F$ ▹a perfect extension not entailing F

23: return KB $⊨_{ALC + T_{R}^{\exp}}^{sk} F$ ▹F is entailed in all perfect extensions

Algorithm 2 Credulous entailment in $ALC + T_{R}^{\exp}$ : KB $⊨_{ALC + T_{R}^{\exp}}^{cr} F$

1: procedure CREDULOUSENTAILMENT( $T \cup T_{card}, A), T^{'}$ , F, $ℂ$

2: $ℂ_{A} \leftarrow \emptyset$ ▹build the set $𝕊$ of possible assumptions

3: for each $C \in ℂ$ do

4: for each individual $a \in A$ do ▹Reasoning in $ALC + T_{R}^{RaCl}$

5: if $(T^{'}, A) ⊨_{ALC + T_{R}^{RaCl}} T (C) (a)$ $ℂ_{A} \leftarrow ℂ_{A} \cup {T (C) (a)}$

6: $d_{A} \leftarrow$ build the ordered multiset of avg degrees of Definition 2 given $T$ and $ℂ_{A}$

7: $𝕊 \leftarrow$ build strings of possible assumptions as in Definition 3 given $ℂ_{A}$ and $d_{A}$

8: $A_{pl} \leftarrow \emptyset$ ▹build plausible extensions of $A$

9: for each $d_{i} \in 𝕊$ do

10: build the extension ${\hat{A}}_{i}$ corresponding to d_i

11: $A_{pl} \leftarrow A_{pl} \cup {\hat{A}}_{i}$

12: $A_{el} \leftarrow \emptyset$ ▹select eligible extensions checking cardinality restrictions

13: for each ${\hat{A}}_{i} \in A_{pl}$ do ▹Reasoning in $ALC + T_{R}$ plus cardinality restrictions

14: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) is satisfiable in $ALC + T_{R}$ then

15: $A_{el} \leftarrow A_{el} \cup {\hat{A}}_{i}$

16: for each ${\hat{A}}_{i} \in A_{el}$ do ▹check preference among extensions of $A$

17: for each ${\hat{A}}_{j} \in A_{el}$ do

18: ifd_i ≤ d_j let ${\hat{A}}_{i} < {\hat{A}}_{j}$

19: $ε \leftarrow {{\hat{A}}_{i} ∣ ∄ {\hat{A}}_{j} \in A_{el} such that {\hat{A}}_{j} < {\hat{A}}_{i}}$ ▹select perfect extensions

20: for each ${\hat{A}}_{i} \in ε$ do ▹query entailment in $ALC + T_{R}$ plus cardinality restrictions

21: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) $⊨_{ALC + T_{R}} F$ then

22: return KB $⊨_{ALC + T_{R}^{\exp}}^{cr} F$ ▹a perfect extension entailing F

23: return KB $⊭_{ALC + T_{R}^{\exp}}^{cr} F$ ▹F is not entailed in any perfect extension

4.3 Reasoning in $ALC + T_{R}^{\exp}$ : the whole procedure

Let KB=( $T \cup T_{card}, A$ ) be an $ALC + T_{R}^{\exp}$ knowledge base, where $T_{card}$ is a set of cardinality restrictions and $T$ does not contain cardinality restrictions. Let $T^{'}$ be the set of inclusions of $T$ without the degrees of expectedness: $T^{'} = {C ⊑ D ∣ C ⊑_{n} D \in T}$ , that the procedure will take into account in order to reason in $ALC + T_{R}$ and $ALC + T_{R}^{RaCl}$ for checking query entailment and finding all plausible typicality assumptions, respectively. Other inputs of the procedure are a finite set of concepts $ℂ$ and a query F. If F is an inclusion C ⊑ D (even with typicality, i.e. C has the form T (C′)), by Definitions 10 and 11 we just need to reason in $ALC + T_{R}^{RaCl}$ to check whether KB $⊨_{ALC + T_{R}^{RaCl}} C ⊑ D$ . If F is an ABox formula of the form C (a), then we exploit Algorithms 1 and 2. Algorithm 1 checks whether F is skeptically entailed from the KB in the logic $ALC + T_{R}^{\exp}$ , namely whether KB $⊨_{ALC + T_{R}^{\exp}}^{sk} F$ . Algorithm 2 is used to check whether F is credulously entailed from the KB, that is to say KB $⊨_{ALC + T_{R}^{\exp}}^{cr} F$ .

By exploiting the procedures described by Algorithms 1 and 2, we can estimate the complexity of reasoning in the logic $ALC + T_{R}^{\exp}$ :

Theorem 1. (Complexity of skeptical entailment) Given a KB in $ALC + T_{R}^{\exp}$ 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 whether KB $⊨_{ALC + T_{R}^{\exp}}^{sk} F$ is ExpTime-complete.

proof. If F is an inclusion C ⊑ D, we check whether KB $⊨_{ALC + T_{R}^{RaCl}} F$ , and we immediately conclude since entailment in $ALC + T_{R}^{RaCl}$ is in ExpTime. Otherwise, let n be the size of KB, i.e. the length of the string representing it. Consider the operations computed by Algorithm 1:

lines 2-5: the algorithm checks, for each concept $C \in ℂ$ and for each individual name a of the ABox whether T (C) (a) is minimally entailed from the KB (without cardinality restrictions and degrees of expectedness) in the nonmonotonic logic $ALC + T_{R}^{RaCl}$ . The number of individual names in the ABox is O (n). We have assumed that $ℂ$ contains only concepts belonging to KB, therefore also the size of $ℂ$ is O (n). It follows that the number of different T (C) (a) considered is O (n²). For each T (C) (a) the algorithm relies on reasoning in $ALC + T_{R}^{RaCl}$ , which is in ExpTime, therefore we make a polynomial number of computation in ExpTime;

line 6: the algorithm builds the ordered multiset $d_{A}$ of Definition 2: obviously, this operation consists in computing the average of the degrees of expectedness of the inclusions $T (C) ⊑_{n} D \in T$ , which are O (n), for each $C \in ℂ$ , again O (n). Therefore, this problem can be solved with O (n²) operations, i.e. in polynomial time;

line 7: the algorithm builds the set $𝕊$ of possible assumptions (Definition 3). We have to consider all possible strings obtained by assuming (or not) each typicality assumption T (C) (a), that are O (n²). Consider a generic string 〈d₁, d₂, …, d_{n
²}〉. For each d_i, we have two options: we can choose either to not include the corresponding typicality assumption, then d_i = 0, or to include it, then d_i corresponds to the average of degrees of expectedness for that concept. So we can build 2 × 2 × … ×2 different strings, therefore O (2^{n
²}), that is to say the multiset $𝕊$ has exponential size in n;

lines 8-11: the algorithm builds the extensions of the ABox corresponding to strings of $𝕊$ , again an exponential number of extensions (O (2^{n
²}));

lines 12-15: the algorithm checks, for each extension of the ABox, whether it satisfies cardinality constraints in $T_{card}$ : therefore, the algorithm makes O (2^{n
²}) calls to a procedure checking the satisfiability of a knowledge base in $ALC + T_{R}$ plus cardinality restrictions, that is in ExpTime. Therefore, these problems are in ExpTime;

lines 17-18: the algorithm compares each pair of strings (d_i, d_j) of possible assumptions, in order to check whether d_i < d_j and, therefore, conclude that the extension ${\hat{A}}_{i}$ is more surprising than ${\hat{A}}_{j}$ . To this aim, we consider the following procedure. First, elements (integers) of d_i and d_j are ordered, and since they are O (n²), this can be done in O (n²logn²) steps. Call $d_{i}^{'}$ and $d_{j}^{'}$ the ordered strings. Then, we proceed as follows: an index k is used to scan elements in $d_{i}^{'}$ and $d_{j}^{'}$ ; at each step, if $d_{i}^{'} [k]$ (integer in position k of $d_{i}^{'}$ ) is ≤ of $d_{j}^{'} [k]$ , then k is incremented in order to index the subsequent integer in $d_{i}^{'}$ and $d_{j}^{'}$ , otherwise the procedure answers that $d_{i}^{'} ≮ d_{j}^{'}$ . If the scan of k is completed, and all integers of the strings have been considered, the procedure answers that $d_{i}^{'} < d_{j}^{'}$ . The procedure requires O (n²) steps, and since there are O (2^{n
²}) strings in $𝕊$ , these operations are performed in ExpTime;

line 19: the algorithm builds the set $ε$ of perfect extensions, that is to say extensions of the ABox that are minimal with respect to the relation < introduced in line 18 by the algorithm. The algorithm checks, for each extension ${\hat{A}}_{i}$ , whether it is minimal: to this aim, for each ${\hat{A}}_{j}$ , the algorithm checks whether ${\hat{A}}_{i} ≮ {\hat{A}}_{j}$ , and this can be done in constant time (we could think of implementing the relation < introduced in step 18 by means of a bi-dimensional array, therefore this operation corresponds to a direct access to raw i and column j of such array). For each extension ${\hat{A}}_{i}$ (and they are O (2ⁿ)) the algorithm considers all the other O (2ⁿ) extensions, therefore, since 2ⁿ × 2ⁿ = 2²ⁿ, this step can be solved in ExpTime;

steps 20-23: the algorithm relies on reasoning in monotonic $ALC + T_{R}$ plus cardinality restrictions in order to check whether the query F is entailed in all perfect extensions in $ε$ . Since the size of $ε$ is O (2ⁿ), we have O (2ⁿ) call to query entailment in $ALC + T_{R}$ , which is an ExpTime-complete problem. It is worth noticing that the size of the KB is augmented by the size of the extension ${\hat{A}}_{i}$ , which is however polynomial in n, precisely O (n²). We can conclude that these operations are in ExpTime.

ExpTime hardness immediately follows from the fact that the logic $ALC + T_{R}^{\exp}$ extends standard $ALC$ , which is ExpTime-complete. Indeed, we can consider a knowledge base without the T operator (therefore, without degrees of expectedness), and consider $ℂ = \emptyset$ . ■

We obtain the same result for credulous reasoning:

Theorem 2. (Complexity of credulous entailment) Given a KB in $ALC + T_{R}^{\exp}$ 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 credulously whether KB $⊨_{ALC + T_{R}^{\exp}}^{cr} F$ is ExpTime-complete.

proof. The proof is the same of Theorem 1: the only difference is in steps 20-23, where, in order to check whether F is entailed by any extension of the ABox, the algorithm concludes that KB $⊨_{ALC + T_{R}^{\exp}}^{cr} F$ in line 22. Again, we consider O (2ⁿ) call to query entailment in $ALC + T_{R}$ , which is an ExpTime-complete problem and we conclude as for Algorithm 1.■

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

5 Reasoning about Scenarios “in the middle”

The approach described in the previous sections could be extended in order to take also into account all the extensions of the ABox satisfying cardinality restrictions, that is to say the eligible extensions of Definition 6. The idea is to reason about all plausible scenarios, each one equipped with a degree of expectedness, representing a sort of probability, allowing the user to choose the one he considers more adequate for his application, ranging from the most trivial scenario to the most surprising one.

We iteratively define sets of extensions representing scenarios “in the middle”: intuitively, at each step, we consider the extensions of ABox that are minimal w.r.t. the weak preference among extensions of ABox in Definition 8. At the next step, only remaining eligible extensions are considered, and so on. This is formally stated as follows:

Definition 17. (Extensions “in the middle”) Given a KB=( $T, A$ ), let $𝔼$ be the set of all eligible extensions as in Definition 6. We define extensions “in the middle” as follows:

we let $ε_{0} = ε$ , where $ε \subseteq ε$ is the set of eligible extensions that are minimal as in Definition 9;

while $ε_{i}$ is not empty, let $ε_{i + 1}$ be the extensions in $𝔼 - (ε_{0} \cup ε_{1} \cup \dots \cup ε_{i})$ that are minimal with respect to the order relation of Definition 8.

Definition 17 describes a sequence of sets of eligible extensions $ε_{0}, ε_{1}, \dots, ε_{n}$ with a degree of expectedness i associated to each one. We can formally define what we mean for reasoning in more or less surprising scenarios:

Definition 18. (Entailment in $ALC + T_{R}^{\exp}$ at degree i) Given a KB=( $T, A$ ) and a query F, we say that (i) F is skeptically entailed from KB in $ALC + T_{R}^{\exp}$ at degree i, for $i \in ℕ$ , written KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{i}} F$ , if ( $T, A \cup \hat{A}$ ) $⊨_{ALC + T_{R}} F$ for all $\hat{A} \in ε_{i}$ ; (ii) F is credulously entailed from KB in $ALC + T_{R}^{\exp}$ , written KB $⊨_{ALC + T_{R}^{\exp}}^{{cr}^{i}} F$ , if there exists $\hat{A} \in ε_{i}$ such that ( $T, A \cup \hat{A}$ ) $⊨_{ALC + T_{R}} F$ .

Algorithm 3 Skeptical entailment at degree i in $ALC + T_{R}^{\exp}$ : KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{i}} F$

1: procedure SKEPTICALENTAILMENT( $T \cup T_{card}, A), T^{'}$ , F, $ℂ$ , i

2: … lines 2–18 as in Algorithm 1 …

19: $ε_{0} \leftarrow {{\hat{A}}_{i} ∣ ∄ {\hat{A}}_{j} \in A_{el} such that {\hat{A}}_{j} < {\hat{A}}_{i}}$ ▹select perfect extensions (degree 0)

20: j ← 0

21: while $ε_{j} \neq \emptyset$ do ▹compute set of extensions at different degrees $ε_{1}, ε_{2}, \dots, ε_{n}$

22: $𝔼 \leftarrow A_{el} - {ε_{0}, ε_{1}, \dots, ε_{j}}$

23: $ε_{j + 1} \leftarrow {{\hat{A}}_{i} \in ε ∣ ∄ {\hat{A}}_{j} \in ε such that {\hat{A}}_{j} < {\hat{A}}_{i}}$

24: j ← j + 1

25: $ε \leftarrow ε_{i}$ ▹select the extensions at degree i

26: for each ${\hat{A}}_{i} \in ε$ do ▹query entailment in $ALC + T_{R}$ plus cardinality restrictions

27: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) $⊭_{ALC + T_{R}} F$ then

28: return KB $⊭_{ALC + T_{R}^{\exp}}^{{sk}^{i}} F$ ▹an extension at degree i not entailing F

29: return KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{i}} F$ ▹F is entailed in all extensions of degree i

Since it computes all the extensions of an ABox, Algorithm 1 can be slightly modified in order to compute the sets of extensions $ε_{0}, ε_{1}, \dots, ε_{n}$ in order to reason in plausible scenarios with a given degree of expectedness, according to Definition 18. Algorithm 3 shows the complete procedure for skeptical reasoning, that can be exploited in order to show that also reasoning about scenarios “in the middle” is ExpTime-complete. The Algorithm for reasoning credulously at degree i can be easily obtained by replacing lines 26 –29 with the following ones:

26: for each ${\hat{A}}_{i} \in ε$ do

27: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) $⊨_{ALC + T_{R}} F$ then

28: return KB $⊨_{ALC + T_{R}^{\exp}}^{{cr}^{i}} F$

29: return KB $⊭_{ALC + T_{R}^{\exp}}^{{cr}^{i}} F$

Theorem 3. (Complexity of reasoning at degree i) Given a KB in $ALC + T_{R}^{\exp}$ , a query F whose size is polynomial in the size of KB, and an integer i, assuming the unary encoding of numbers in cardinality restrictions of KB, the problem of checking skeptically (resp. credulously) whether KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{i}} F$ (resp. KB $⊨_{ALC + T_{R}^{\exp}}^{{cr}^{i}} F$ ) is ExpTime-complete.

Proof. Algorithm 3 differs from Algorithm 1 by the while loop at starting at line 21, where the sets $ε_{0}, ε_{1}, \dots, ε_{k}$ of eligible extensions are computed. As in the proof of Theorem 1, we have that the number of different eligible extensions in $A_{el}$ is O (2ⁿ), so is the maximum number of execution of the body of the while loop. At each step, the algorithm only selects the minimal extensions (among those remaining, thus belonging to the set $𝔼$ ) with respect to the order < among extensions introduced in step 18. We proceed similarly to what done in Algorithm 1 to check, for each extension ${\hat{A}}_{i}$ , whether it is minimal: for each ${\hat{A}}_{j}$ , the algorithm checks whether ${\hat{A}}_{i} ≮ {\hat{A}}_{j}$ , and this can be done in constant time (we could think of implementing the relation < by means of a bi-dimensional array, therefore this operation corresponds to a direct access to raw i and column j of such array). For each extension ${\hat{A}}_{i}$ (and they are O (2ⁿ)) the algorithm considers all the other O (2ⁿ) extensions, therefore the algorithm computes 2ⁿ × 2ⁿ = 2²ⁿ steps. In the worst case, there is a total order among eligible extensions, and at each step only one extension is added to the corresponding $ε_{i}$ . In this case, the body of the while loop is executed O (2ⁿ) times, each one performing 2²ⁿ steps, then we have 2ⁿ × 2²ⁿ = 2³ⁿ, thus in ExpTime. ExpTime hardness again follows from the fact that the logic $ALC + T_{R}^{\exp}$ extends standard $ALC$ , which is ExpTime-complete: as for the proof of Theorem 1, we can consider a knowledge base without the T operator and consider $ℂ = \emptyset$ .■

Algorithm 4 Skeptical entailment at degrees n . . m in $ALC + T_{R}^{\exp}$ : KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{n . . m}} F$

1: procedure SKEPTICALENTAILMENT( $T \cup T_{card}, A), T^{'}$ , F, $ℂ$ , n, m

2: … lines 2–18 as in Algorithm 1 …

19: $ε_{0} \leftarrow {{\hat{A}}_{i} ∣ ∄ {\hat{A}}_{j} \in A_{el} such that {\hat{A}}_{j} < {\hat{A}}_{i}}$ ▹select perfect extensions (degree 0)

20: j ← 0

21: while $ε_{j} \neq \emptyset$ do ▹compute set of extensions at different degrees $ε_{1}, ε_{2}, \dots, ε_{n}$

22: $𝔼 \leftarrow A_{el} - {ε_{0}, ε_{1}, \dots, ε_{j}}$

23: $ε_{j + 1} \leftarrow {{\hat{A}}_{i} \in ε ∣ ∄ {\hat{A}}_{j} \in ε such that {\hat{A}}_{j} < {\hat{A}}_{i}}$

24: j ← j + 1

25: $ε \leftarrow \emptyset$

26: i ← n

27: whilei ≤ mdo ▹select the extensions between degrees n and m

28: $ε \leftarrow ε \cup ε_{i}$

29: i ← i + 1

30: for each ${\hat{A}}_{i} \in ε$ do ▹query entailment in $ALC + T_{R}$ plus cardinality restrictions

31: if ( $T^{'} \cup T_{card}, A \cup {\hat{A}}_{i}$ ) $⊭_{ALC + T_{R}} F$ then

32: return KB $⊭_{ALC + T_{R}^{\exp}}^{{sk}^{n . . m}} F$ ▹an extension at a degree i ∈ n, …, m not entailing F

33: return KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{n . . m}} F$ ▹F is entailed in all extensions of degrees between n and m

It is easy to observe that reasoning in perfect extensions, corresponding to the most “surprising” scenarios, as in Definitions 10 and 11, is an instance of entailment at degree i, namely checking whether a query F is entailed in perfect extensions $ALC + T_{R}^{\exp}$ corresponds to checking whether F is entailed at degree i = 0 with respect to entailment inDefinition 18.

A further generalization of the reasoning procedure allows us also to define (credulous and skeptical) entailment in combinations of plausible scenarios. As an example, one could be interested in reasoning in all scenarios $ε_{i}$ such that i < k for a given and fixed k. As a general case, we define a notion of entailment restricted to scenarios with degrees of expectations between n and m, as in the followingdefinition:

Definition 19. (Entailment at degrees n . . m) Given a KB=( $T, A$ ) and a query F, we say that (i) F is skeptically entailed from KB in $ALC + T_{R}^{\exp}$ at degrees n . . m ( $n, m \in ℕ$ with n ≤ m) written KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{n . . m}} F$ , if ( $T, A \cup \hat{A}$ ) $⊨_{ALC + T_{R}} F$ for all $\hat{A} \in ε_{i}$ , for all i such that n ≤ i ≤ m; (ii) F is credulously entailed from KB in $ALC + T_{R}^{\exp}$ , written KB $⊨_{ALC + T_{R}^{\exp}}^{{cr}^{n . . m}} F$ , if there exists i such that n ≤ i ≤ m such that for all $\hat{A} \in ε_{i}$ we have that ( $T, A \cup \hat{A}$ ) $⊨_{ALC + T_{R}} F$ .

The resulting procedure is formally stated by Algorithm 3k, and such a procedure again allows us to show that the complexity of reasoning in the logic $ALC + T_{R}^{\exp}$ remains ExpTime-complete.

Theorem 4. (Complexity at degrees n . . m) Given a KB in $ALC + T_{R}^{\exp}$ , a query F whose size is polynomial in the size of KB, and two integers n ≤ m, assuming the unary encoding of numbers in cardinality restrictions of KB, the problem of checking skeptically (resp. credulously) whether KB $⊨_{ALC + T_{R}^{\exp}}^{{sk}^{n . . m}} F$ (resp. KB $⊨_{ALC + T_{R}^{\exp}}^{{cr}^{n . . m}} F$ ) is ExpTime-complete.

Proof. The proof is straightforward, since Algorithm 3k differs from Algorithm 3 only because the eligible extensions taken into account are no longer restricted to those belonging to a single $ε_{i}$ , but extended to those belonging to degrees between n and m. To this aim, the while loop starting at line 27 is executed, however it only adds eligible extensions (already computed by the Algorithm) to the set $ε$ . ■

6 Related works

The need for representing prototypical properties and to reason about inheritance with exceptions in DLs has motivated the study of nonmonotonic extensions of DLs. Several nonmonotonic extensions of DLs have been proposed in the literature, essentially based on the integration of DLs with well established nonmonotonic reasoning mechanisms. Here we focus on the approaches that can be considered more similar to the peculiarities of the logic $ALC + T_{R}^{\exp}$ introduced in this work, whereas we refer to [16, 19] for a detailed discussion about other extensions of DLs for defeasible inheritance. We consider:

approaches allowing degrees/priorities among TBox inclusions;

probabilistic extensions of DLs, allowing to label inclusions (and facts) with degrees representing probabilities.

In [3] an extension of DL with Reiter’s default logic is proposed. Being based on a minimal models mechanism, our approach is strongly related to the one based on circumscription 5 [6–8 , 10] and to the semantics proposed in [5], where defeasible inclusions are allowed besides classical concept inclusions. The problem of conflicting defaults and of priorities among inclusions has been studied since seminal works in the context of inheritance networks [12]. In the field of nonmonotonic extensions of DLs, in order to overcome the problem of modeling inheritance with exceptions, extensions of DLs with prioritized defaults have been studied in [4, 28], whereas priorities among defeasible inclusions are allowed in [5].

In the logic $ALC + T_{R}^{\exp}$ , degrees of expectedness are not intended to represent priorities among inclusions, since dealing with conflicting inclusions is provided for free by the preferential semantics of the typicality operator which allows one to give preference to the most specific information, without the need of any additional machinery. As a further example, if TBox is:

SumoWrestler ⊑ Athlete

T (Athlete) ⊑ ₁ ¬ Fat

T (SumoWrestler) ⊑ ₁Fat

and the ABox is {Athlete (chad)}, then the fact ¬Fat (chad) is entailed in the logic $ALC + T_{R}^{\exp}$ , whereas it is no longer entailed if we add to the ABox the fact SumoWrestler(chad), from which the fact Fat(chad) is rather entailed. It is easy to observe that the degree of expectedness in the two inclusions does not play any role in this, as a difference with priorities on defaults of the above mentioned approaches.

The use of positive integers for expressing degrees of expectedness in the logic $ALC + T_{R}^{\exp}$ is only a way of formalizing a partial order among typicality inclusions, however all properties expressed by typicality inclusions of the form T (C) ⊑ _dD are typical properties, even if d is low: 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. As far as we know, this is not taken into account in the other existing proposals for extensions of DLs for prototypical reasoning, even if, in principle, it could be considered in order to reason about plausible scenarios.

The extension of DLs highlighted in this work suggests a relation with probabilistic Description Logics under the distribution semantics [26]. In this approach, called DISPONTE, the authors propose the integration of probabilistic information with DLs based on the distribution semantics for probabilistic logic programs [27]. The basic idea is to label inclusions of the TBox as well as facts of the ABox with a real number between 0 and 1, representing their probabilities, assuming that each axiom is independent from each others. The resulting knowledge base defines a probability distribution over worlds: roughly speaking, a world is obtained by choosing, for each axiom of the KB, whether it is considered as true of false. The distribution is further extended to queries and the probability of a query is obtained by marginalizing the joint distribution of the query and the worlds.

As an example, consider the following variant of the knowledge base inspired by the people and pets ontology in [26]:

0.3 : : ∃ hasAnimal . Pet ⊑ NatureLover (1)

0.6 : : Cat ⊑ Pet (2)

0.9 : : Cat (tom) (3)

hasAnimal(kevin, tom) (4)

The inclusion (1) expresses that individuals that own a pet are nature lovers with a 30% probability, whereas (2) is used to state that cats are pets with probability 60%. The ABox fact (3) represents that Tom is a cat with probability 90%. Inclusions (1), (2) and (3) are probabilistic axioms, whereas (4) is a certain axiom, that must always hold. The KB has the following eight possible worlds:

{((1), 0), ((2), 0), ((3), 0)}

{((1), 0), ((2), 0), ((3), 1)}

{((1), 0), ((2), 1), ((3), 0)}

{((1), 0), ((2), 1), ((3), 1)}

{((1), 1), ((2), 0), ((3), 0)}

{((1), 1), ((2), 0), ((3), 1)}

{((1), 1), ((2), 1), ((3), 0)}

{((1), 1), ((2), 1), ((3), 1)}

representing all possible combinations of considering/not considering each probabilistic axiom. For instance, the world {((1), 1), ((2), 0), ((3), 1)} represents the situation in which we have that (1) and (3) hold, i.e. ∃hasAnimal . Pet ⊑ NatureLover and Cat(tom), whereas (2) does not. The query

NatureLover(kevin)

is true only in the last world, i.e. having that (1), (2) and (3) are all true, whereas it is false in all the other ones. The probability of such a query is P (NatureLover (kevin)) =0.3 × 0.6 × 0.9 = 0.162.

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 corresponding, for instance, to worlds where corresponding probabilities are lower than a given threshold. However, as mentioned above, degrees in the logic $ALC + T_{R}^{\exp}$ are used in order to represent a level of expectedness in typicality inclusions, whereas in DISPONTE KBs we can express inclusions like (1) above that cannot express prototypical properties: in $ALC + T_{R}^{\exp}$ we would not have something like T (∃ hasAnimal . Pet) ⊑ NatureLover, in the sense that it does not seem to be the case to consider as typical a property having a low probability (0.3). Therefore, the query NatureLover(kevin) is not entailed neither skeptically nor credulously. Such a difference is further emphasized by the presence of cardinality restrictions.

Let us recall the example from sports entertainment at the end of Section 3: we can think of representing the typicality inclusions

T (FaceWrestler) ⊑ ₁RoyalRumbleWinner (T1)

T (Returning) ⊑ ₃RoyalRumbleWinner (T2)

T (Predicted) ⊑ ₂RoyalRumbleWinner (T3)

with the following ones in the language of probabilistic DLs:

0.6: : FaceWrestler ⊑ RoyalRumbleWinner (a)

0.8: : Returning ⊑ RoyalRumbleWinner (b)

0.7: : Predicted ⊑ RoyalRumbleWinner (c)

The ABox facts $\begin{matrix} FaceWrestler (dean) & FaceWrestler (roman) \\ Predicted (roman) & Returning (seth) \end{matrix}$ are all certain axioms, therefore differences among worlds are only introduced by the choices about (a), (b) and (c). Given the cardinality constraint (= 1 RoyalRumbleWinner), it can be observed that all the worlds where (a) is considered as true are inconsistent, since both Roman and Dean are face wrestlers. The world {((a), 0), ((b), 0), ((c), 0)} excludes all the TBox inclusions, whereas the world {((a), 0), ((b), 1), ((c), 1)} does not allow to fulfill the cardinality restriction too (from (b) and Returning(seth) we conclude RoyalRumbleWinner(seth) and from (c) and Predicted(roman) we have RoyalRumbleWinner (roman)). The only worlds satisfying the restriction about a single Royal Rumble winner are ${((a), 0), ((b), 0), ((c), 1)} and {((a), 0), ((b), 1), ((c), 0)} .$

In the first case, we have that the predicted winner, Roman, wins the match, whereas in the second one the winner is the returning athlete Seth. In none of them, the most surprising outcome in which Dean wins the Royal Rumble match is taken into account. As an alternative, one can think of formalizing the initial TBox with certain axioms, as follows:

FaceWrestler ⊑ RoyalRumbleWinner

Returning ⊑ RoyalRumbleWinner

Predicted ⊑ RoyalRumbleWinner

and to capture degrees of expectedness with the following probabilistic ABox: $\begin{matrix} (i) 0.1 : : FaceWrestler (dean) & (ii) 0.1 : : FaceWrestler (roman) \\ (iii) 0.2 : : Predicted (roman) & (iv) 0.3 : : Returning (seth) \end{matrix}$ In this case, we have 16 different worlds, representing all possibile combinations of ABox facts. Only the following worlds satisfy the cardinality constraint of having only one winner:

{((i), 1), ((ii), 0), ((iii), 0), ((iv), 0)}

{((i), 0), ((ii), 1), ((iii), 0), ((iv), 0)}

{((i), 0), ((ii), 0), ((iii), 1), ((iv), 0)}

(*) {((i), 0), ((ii), 1), ((iii), 1), ((iv), 0)}

{((i), 0), ((ii), 0), ((iii), 0), ((iv), 1)}

In the first world, Dean is the winner with a probability of 10%, whereas in the last one Seth is the winner with a probability of 30%. In all other worlds, Roman is the winner. It is worth noticing that, with this knowledge base, in order to reason about typicality we need to “weaken” certain facts of the ABox to probabilistic ones, losing the opportunity to reason about them with respect to other properties. For instance, if the TBox further contains FaceWrestler ⊑ KidsFavourite, then in the logic $ALC + T_{R}^{\exp}$ we are still able to infer that kids are fans of both Dean and Roman, since eligible extensions select only typicality assumptions: only one of them is a typical face wrestler, but both are face wrestlers, then obtaining support by the kids. On the contrary, in the DLs with DISPONTE semantics with the above formulation, Dean and Roman are face wrestlers with a certain probability, and this also affects the probabilities of being kids’ favourites or not.

7 Conclusions and future issues

In this work we have provided a nonmonotonic procedure for preferential Description Logics in order to reason about surprising scenarios in presence of cardinality restrictions on concepts. We have introduced the Description Logic of typicality $ALC + T_{R}^{\exp}$ , an extension of $ALC$ with a typicality operator T allowing to (i) express typicality inclusions of the form T (C) ⊑ _dD, where d is a positive integer representing a degree of expectedness; (ii) reason in presence of restrictions on the cardinality of concepts. It is worth noticing that the proposed logic $ALC + T_{R}^{\exp}$ 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 plausible but unexpected 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 logic $ALC + T_{R}^{\exp}$ 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.

We have also described a procedure for reasoning in $ALC + T_{R}^{\exp}$ exploiting reasoning mechanisms in the logics $ALC + T_{R}$ and $ALC + T_{R}^{RaCl}$ , the last one relying on a notion of rational closure for Description Logics. This procedure allowed us to show that entailment in $ALC + T_{R}^{\exp}$ is ExpTime-complete as the underlying $ALC$ , therefore it is essentially inexpensive, once unary encoding of numbers in cardinality restrictions is assumed. We have also provided an extension of our framework in order to reason about alternative scenarios “in the middle”, ranging from the most surprising to the most expected ones; we have proposed reasoning procedures and ExpTime completeness results also for this extension.

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 plausible scenarios of the logic $ALC + T_{R}^{\exp}$ , but directly applied to the nonmonotonic semantics of $ALC + T_{R}^{RaCl}$ . 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 those underlying the standard language for ontology engineering OWL. As a first step, in [20] the logic with the typicality operator and the rational closure construction have been applied to the logic $SHIQ$ .

Footnotes

In Theorem 10 in [] the authors have shown that for any consistent KB there exists a finite minimal canonical model of KB.

As mentioned, at this point of the presentation we only want to give an intuition of the inferences characterizing the logic $ALC + T_{R}^{\exp}$ . Formal definitions of nonmonotonic entailment in $ALC + T_{R}^{\exp}$ will be provided in Definitions 10 and 11.

Other aggregation functions could be used to define d_i (e.g. maximum/minimum degree). We aim at studying the impact of this choice on the reasoning machinery in future research.

The results provided in [] are extended to the more expressive logic $SHIQ$ . Here we focus our attention on the basic $ALC$ .

A formal and precise comparison between the logics with the typicality operator T and circumscribed knowledge bases can be found in [].

References

Baader

, Buchheit

and Hollunder

, Cardinality restrictions on concepts, Artificial Intelligence88(1-2) (1996), 195–213.

Baader

, Calvanese

, McGuinness

D.L.

, Nardi

, Patel-Schneider

P.F.

, The Description Logic Handbook - Theory, Implementation, and Applications, 2nd edition. Cambridge, 2007.

Baader

and Hollunder

, Embedding defaults into terminological knowledge representation formalisms, Journal of Automated Reasoning (JAR)14(1) (1995), 149–180.

Baader

and Hollunder

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

Bonatti

P.A.

, Faella

, Petrova

and Sauro

, A new semantics for overriding in description logics, Artificial Intelligence222 (2015), 1–48.

Bonatti

P.A.

, Faella

and Sauro

, Defeasible inclusions in low-complexity dls, Journal of Artificial Intelligence Research (JAIR)42 (2011), 719–764.

Bonatti

P.A.

, Faella

and Sauro

, On the complexity of EL with defeasible inclusions. In Walsh

Toby

, editor, Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), Barcelona, Spain, July 2011, pp. 762–767. Morgan Kaufmann.

Bonatti

P.A.

, Lutz

and Wolter

, Description Logics with Circumscription. In Principles of Knowledge Representation and Reasoning: Proceedings of the 10th International Conference (KR 2006), Lake District of the United Kingdom, 2006, pp. 400–410. AAAI Press.

Bonatti

P.A.

, Lutz

and Wolter

, The complexity of circumscription in dls, Journal of Artificial Intelligence Research (JAIR)35 (2009), 717–773.

10.

Bonatti

P.A.

, Lutz

and Wolter

, The complexity of circumscription in DLs, Journal of Artificial Intelligence Research (JAIR)35 (2009), 717–773.

11.

Bordino

, Mejova

and Lalmas

, Penguins in sweaters, or serendipitous entity search on user-generated content. In He

, Iyengar

, Nejdl

, Pei

, and Rastogi

, editors, 22nd ACM International Conference on Information and Knowledge Management, CIKM’13, San Francisco, CA, USA, October 27 - November 1, 2013, pp. 109–118.

12.

Brewka

and Eiter

, Prioritizing default logic. In Hölldobler

, editor, Intellectics and Computational Logic (to Wolfgang Bibel on the occasion of his 60th birthday), volume 19of Applied Logic Series, Kluwer, 2000, pp. 27–45.

13.

Casini

and Straccia

, Rational closure for defeasible description logics. In Janhunen

Tomi

and Niemelä

Ilkka

, editors, Logics in Artificial Intelligence - Proceedings of the12th European Conference (JELIA 2010), volume 6341of Lecture Notes in Computer Science (LNCS), Springer, 2010, pp. 77–90.

14.

Casini

and Straccia

, Defeasible Inheritance-Based Description Logics, Journal of Artificial Intelligence Research (JAIR)48 (2013), 415–473.

15.

Donini

F.M.

, Nardi

and Rosati

, Description logics of minimal knowledge and negation as failure, ACM Transactions on Computational Logics (ToCL)3(2) (2002), 177–225.

16.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, ALC+T: A p|ntial extension of description logics, Funda menta Informaticae96 (2009), 341–372.

17.

Giordano

, Gliozzi

, Olivetti

, Pozzato

G.L.

, Preferential vs Rational Description Logics: Which one for Reasoning About Typicality? In Coelho

, Studer

, and Wooldridge

, editors, Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), volume 215of FAIA, Lisbon, Portugal, August 2010, pp. 1069–1070. IOS Press.

18.

Giordano

, Gliozzi

, Olivetti

, Pozzato

G.L.

, Reasoning about typicality in low complexity DLs: The logics EL?Tmin and DL-LitecTmin. In Walsh

Toby

, editor, Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), Barcelona, Spain, 2011, pp. 894–899. IOS Press.

19.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, A nonmonotonic description logic for reasoning about typicality, Artificial Intelligence195 (2013), 165–202.

20.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, Rational closure in SHIQ. In DL 2014, 27th International Workshop on Description Logics, volume 1193of CEUR Workshop Proceedings, CEUR-WS.org, 2014, pp. 543–555.

21.

Giordano

, Gliozzi

, Olivetti

and Pozzato

G.L.

, Semantic characterization of Rational Closure: From Propositional Logic to Description Logics, Artificial Intelligence226 (2015), 1–33.

22.

Kraus

, Lehmann

and Magidor

, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence44(1-2) (1990), 167–207.

23.

Lehmann

and Magidor

, What does a conditional knowledge base entail? (1), Artificial Intelligence55 (1992), 1–60.

24.

Pozzato

G.L.

, Preferential description logics meet sports entertainment: Cardinality restrictions and perfect extensions for a better royal rumble match. In Ancona

, Maratea

, and Mascardi

, editors, Proceedings of the 30th Italian Conference on Computational Logic, Genova, Italy, July 1-3, 2015. volume 1459 of CEURWorkshop Proceedings, CEUR-WS.org, pp. 159–174.

25.

Pozzato

G.L.

, Reasoning about surprising scenarios in description logics of typicality. In Adorni

, Cagnoni

, Gori

, and Maratea

, editors, Advances in Artificial Intelligence: Proceedings of the 15th International Conference of the Italian Association for Artificial Intelligence, volume 10037 of Lecture Notes in Artificial Intelligence LNAI, Genova, November 2016, pp. 1–15. Springer.

26.

Riguzzi

, Bellodi

, Lamma

and Zese

, Probabilistic description logics under the distribution semantics, Semantic Web6(5) (2015), 477–501.

27.

Sato

, A statistical learning method for logic programs with distribution semantics. In Sterling

, editor, Logic Programming, Proc. of the 12th International Conference on Logic Programming, MIT Press, 1995, pp. 715–729.

28.

Straccia

, Default inheritance reasoning in hybrid kl-onestyle logics. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI’93), Morgan Kaufmann, 1993, pp. 676–681.

29.

Tobies

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

Reasoning about plausible scenarios in Description Logics of typicality

Abstract

Keywords

1 Introduction

2 Preferential Description Logics

2.1 The monotonic logic ALC + T R

2.2 The nonmonotonic logic ALC + T R RaCl

3 Between ALC + T R and ALC + T R RaCl : The logic ALC + T R exp

3.1 Extensions of ABox

3.2 Cardinality restrictions and perfect extensions

4 A decision procedure for ALC + T R exp

4.1 Reasoning in ALC + T R

4.2 Reasoning in ALC + T R RaCl

4.3 Reasoning in ALC + T R exp : the whole procedure

5 Reasoning about Scenarios “in the middle”

6 Related works

7 Conclusions and future issues

Footnotes

References

2.1 The monotonic logic $ALC + T_{R}$

2.2 The nonmonotonic logic $ALC + T_{R}^{RaCl}$

3 Between $ALC + T_{R}$ and $ALC + T_{R}^{RaCl}$ : The logic $ALC + T_{R}^{\exp}$

4 A decision procedure for $ALC + T_{R}^{\exp}$

4.1 Reasoning in $ALC + T_{R}$

4.2 Reasoning in $ALC + T_{R}^{RaCl}$

4.3 Reasoning in $ALC + T_{R}^{\exp}$ : the whole procedure