=Paper=
{{Paper
|id=Vol-1645/paper_22
|storemode=property
|title=ALC + Texp: Beyond most likely Scenarios in Preferential Description Logics of Typicality
|pdfUrl=https://ceur-ws.org/Vol-1645/paper_22.pdf
|volume=Vol-1645
|authors=Gian Luca Pozzato
|dblpUrl=https://dblp.org/rec/conf/cilc/Pozzato16
}}
==ALC + Texp: Beyond most likely Scenarios in Preferential Description Logics of Typicality==
https://ceur-ws.org/Vol-1645/paper_22.pdf
ALC + TexpR : beyond most likely scenarios in
preferential Description Logics of typicality
Gian Luca Pozzato1
Dip. Informatica - Università di Torino - Italy
gianluca.pozzato@unito.it
Abstract. In this work we continue our investigation about the opportunity of
reasoning about alternative, surprising scenarios in preferential Description Log-
ics of typicality. We extend the results provided in [1] and presented at CILC
2015, where a nonmonotonic procedure for preferential Description Logics has
been outlined in order to solve a problem coming from sports entertainment.
exp
Here we provide complexity results for the Description Logic ALC + TR , ex-
tending the Description Logic ALC + TR by allowing inclusions of the form
T(C) vd D, where d is a degree of expectedness, and also allowing to reason
about surprising extensions of an ABox satisfying cardinality restrictions on con-
exp
cepts. Here we propose a decision procedure for reasoning in ALC + TR , and
we exploit it to show that entailment is in E XP T IME, allowing us to conclude that
exp
reasoning in ALC + TR is essentially inexpensive.
1 Introduction
Nonmonotonic extensions of Description Logics (from now on, DLs for short) have
been actively investigated since the early 90s [2–9] in order to tackle the problem of
representing prototypical properties of classes and to reason about defeasible inheri-
tance. A simple but powerful nonmonotonic extension of DLs is proposed in [10–14]:
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 opera-
tor is characterized by the core properties of nonmonotonic reasoning axiomatized by
either preferential logic [15] or rational logic [16]. We focus on the Description Logic
ALC + TR introduced in [14]. In this logic one can express defeasible inclusions such
as “normally, depressed people have sleep disorders”:
T(Depressed ) v ∃HasSympthom.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”:
AtypicalDepressed v Depressed
T(Depressed ) v ¬∃HasSympthom.MoodReactivity
T(AtypicalDepressed ) v ∃HasSympthom.MoodReactivity
From a semantic point of view, models of ALC + TR are standard models extended
by a function f which selects the typical/most normal instances of any concept C, i.e.
the extension of T(C) is defined as (T(C))I = f (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.
The logic ALC + TR results to be too weak in several application domains. Indeed,
although the operator T is nonmonotonic (T(C) v E does not imply T(C u D) v E),
the logic ALC + TR is monotonic, in the sense that if the fact F follows from a given
knowledge base KB, then F also follows from any KB’ ⊇ KB. As a consequence, un-
less 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 (∃HasSympthom.SleepDisorder (kate)).
This would be possible only if the KB contained the stronger information that Kate is a
typical depressed woman, i.e. T(Depressed )(kate) belongs to (or can be inferred from)
KB. In order to overwhelm this limit and perform useful inferences, in [14] the authors
have introduced a nonmonotonic extension of the logic ALC + TR based on a minimal
model semantics, corresponding to a notion of rational closure as defined in [16] for
propositional logic. Intuitively, the idea is to restrict our consideration to (canonical)
models that maximize typical instances of a concept when consistent with the knowl-
edge base. The resulting logic, call it ALC + TRaCl
R , 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 + TRaCl R is based on a preference relation
among ALC + TR models and a notion of minimal entailment restricted to models that
are minimal with respect to such preference relation.
The logic ALC + TRaCl R imposes to consider all consistent typicality assumptions
that are consistent with a given KB. This seems to be too strong in several application
domains, in particular when the need arises of bounding the cardinality of the exten-
sion of a given concept, that is to say the number of domain elements being members
of such a concept, as introduced in [17]. As a further example, consider the follow-
ing KB from the domain of sports entertainment taken from [1]: T(FaceWrestler ) v
RoyalRumbleWinner , T(Returning) v RoyalRumbleWinner , T(Predicted ) v
RoyalRumbleWinner . The first inclusion represents that, normally, a face wrestler
wins the Royal Rumble match, an annual wrestling event involving thirty athletes. The
second one states that, typically, an athlete returning from an injury wins the Royal
Rumble match. The third and last inclusion represents that an athlete whose victory has
been predicted by wrestling web sites normally wins the Royal Rumble match. If the
assertional part of the KB contains the facts: FaceWrestler (dean), Returning(dave),
FaceWrestler (roman), Predicted (roman), whose meaning is that Dean is a face ath-
lete, Dave is returning from an injury, and that Roman is a face wrestler who has been
predicted to win the Royal Rumble match, respectively, then in ALC + TRaCl R we con-
clude that: T(FaceWrestler )(dean), T(Returning)(dave), T(FaceWrestler )(roman),
T(Predicted )(roman), and then that Dean, Dave and Roman are all winners. This hap-
pens in ALC + TRaCl R because it is consistent to make the three assumptions above, that
hold in all minimal models, however one should be interested in three distinct scenar-
ios that cannot be captured by ALC + TRaCl R as it is. One could think of extending the
logic ALC + TRaCl R by means of cardinality restrictions, in the example by imposing
that there is only one member of the extension of the concept RoyalRumbleWinner ,
however the resulting knowledge base would be inconsistent.
Furthermore, it is sometimes useful to restrict reasoning to surprising scenarios,
excluding “trivial”/“obvious” ones. For instance, recently a great attention has been
devoted to serendipitous search engines, that must be able to provide results that are
“surprising, semantically cohesive, i.e. relevant to some information need of the user,
or just interesting” [18]. In this sense, the scenario (among those satisfying cardinality
restrictions) obtained by assuming the largest set of consistent typicality assumptions
in ALC + TRaClR corresponds to the most trivial one, whereas one could be interested in
less expected ones, in which some typicality assumptions are discarded.
In [1] we have moved a first step towards the definition of an extension of Descrip-
tion Logics of typicality allowing to reason about surprising scenarios in presence of
cardinality restrictions. In that work, an extension of DL-Litecore has been introduced
in order to tackle a problem coming from sports entertainment, namely to find a plausi-
ble but surprising outcome of a wrestling event. However, neither decision procedures
nor complexity results are provided, being that work only a preliminary contribution in
this field. Here we try to move a further step by extending our approach to the more ex-
pressive Description Logic ALC. Moreover, whereas the approach in [1] is based on a
nonmonotonic extension of DLs based on preferential logic P [15], here we exploit the
nonmonotonic extension of ALC called ALC + TRaCl R , based on rational models [16]
and corresponding to a notion of rational closure for Description Logics introduced in
[14]. The approach we propose in this work is based on the combination of two com-
ponents. On the one hand, we allow to express different degrees of expectedness of
typicality inclusions: this allows to describe several plausible scenarios by considering
different combinations of typicality assumptions about individuals named in the ABox.
Such degrees introduce a rank of expectedness among plausible scenarios, ranging from
surprising to obvious ones. On the other hand, TBoxes are extended to allow restrictions
about the cardinality of concepts, in order to “filter” such plausible scenarios. Finally,
reasoning tasks are restricted to reasonable but “surprising enough” (or “not obvious”)
scenarios satisfying cardinality restrictions. In detail, the original contribution of this
work can be summarized as follows:
- we introduce a new Description Logic of typicality, called ALC + Texp R , allowing to
express a degree of expectedness of typicality inclusions and cardinality restrictions on
concepts: TBoxes are extended by (i) inclusions of the form T(C) vd D where d is
a positive integer, such that an inclusion with degree d is more “trivial” (or “obvious”)
with respect to another one with degree d0 ≤ d, as well as by (ii) restrictions on the
cardinality of concepts of the form ( n C), where ∈ {≤, ≥, =} and n ∈ N+ ;
- we introduce a notion of extension of an ABox for the logic ALC + Texp R , corre-
sponding to a set of typicality assumptions that can be performed in ALC + TRaCl R for
individual constants, then we introduce an order relation among extensions whose basic
idea is to prefer extensions representing more surprising scenarios;
- we define notions of skeptical and credulous entailment in ALC + Texp R , relying on
reasoning in ALC + TR , but allowing to restrict our concern to “non trivial” scenarios,
corresponding to minimal extensions with respect to the order relation among exten-
sions of the previous point;
- we describe a procedure for reasoning in ALC + Texp R , that can be used to estimate
the complexity of entailment (E XP T IME for both skeptical and credulous entailment).
It is worth noticing that the proposed logic ALC + Texp R is not intended to replace
existing extensions of DLs for representing and reasoning about prototypical properties
and defeasible inheritance. The idea is that, in some applications, the need of reasoning
about surprising scenarios could help domain experts to achieve their goals, wherever
standard reasoning is not enough to do it: as an example, in medical diagnosis, the
most likely explanation for a set of symptoms is not always the solution to the problem,
whereas reasoning about surprising scenarios could help the medical staff in taking
alternative explanations into account. In other words, the Description Logic ALC +
Texp
R is not intended to replace existing nonmonotonic DLs, but to tile them in order to
reason about alternative, plausible scenarios when it is needed to go beyond most likely
solutions.
2 Description Logics of Typicality
2.1 The monotonic logic ALC + TR
The logic ALC + TR is obtained by adding to standard ALC the typicality operator T
[14]. The intuitive idea is that T(C) selects the typical instances of a concept C. We
can therefore distinguish between the properties that hold for all instances of concept C
(C v D), and those that only hold for the normal or typical instances of C (T(C) v D).
The semantics of the T operator can be formulated in terms of rational models:
a model M is any structure h∆I , <, .I i where ∆I is the domain, < is an irreflexive,
transitive, well-founded and modular (for all x, y, z in ∆, if x < y then either x < z or
z < y) relation over ∆. In this respect, x < y means that x is “more normal” than y, and
that the typical members of a concept C are the minimal elements of C with respect to
this relation. An element x ∈ ∆ is a typical instance of some concept C if x ∈ C I and
there is no C-element in ∆ more typical than x. In detail, .I is the extension function
that maps each concept C to C I ⊆ ∆, and each role R to RI ⊆ ∆ × ∆. For concepts
of ALC, C I is defined as usual. For the T operator, we have (T(C))I = M in< (C I ).
A model M can be equivalently defined by postulating the existence of a function
kM : ∆ 7−→ N, where kM assigns a finite rank to each world: the rank function kM
and < can be defined from each other by letting x < y iff kM (x) < kM (y).
Given standard definitions of satisfiability of a KB in a model, we define a notion of
entailment in ALC + TR . Given a query F (either an inclusion C v D or an assertion
C(a) or an assertion of the form R(a, b)), we say that F is entailed from a KB in
ALC + TR , written KB |=ALC+TR F , if F holds in all ALC + TR models satisfying
KB.
2.2 The nonmonotonic logic ALC + TRaCl
R
Even if the typicality operator T itself is nonmonotonic (i.e. T(C) v E does not imply
T(C uD) v E), what is inferred from a KB can still be inferred from any KB’ with KB
⊆ KB’, i.e. the logic ALC +TR is monotonic. In order to perform useful nonmonotonic
inferences, in [14] the authors have strengthened the above semantics by restricting
entailment to a class of minimal models. Intuitively, the idea is to restrict entailment to
models that minimize the untypical instances of a concept. The resulting logic is called
ALC + TRaCl R and it corresponds to a notion of rational closure on top of ALC + TR .
Such a notion is a natural extension of the rational closure construction provided in [16]
for the propositional logic. Here below we recall the semantics of the DL ALC + TRaCl R :
details about the construction of the rational closure and the correspondence between
semantics and construction can be found in [14].
The nonmonotonic semantics of ALC + TRaCl R relies on minimal rational models
that minimize the rank of domain elements. Informally, given two models of KB, one
in which a given domain element x has rank 2 (because for instance z < y < x), and
another in which it has rank 1 (because only y < x), we prefer the latter, as in this model
the element x is assumed to be “more typical” than in the former. Query entailment is
then restricted to minimal canonical models. The intuition is that a canonical model
contains all the individuals that enjoy properties that are consistent with the knowledge
base. This is needed when reasoning about the rank of the concepts: it is important to
have them all represented. A model M is a minimal canonical model of KB if it satisfies
KB, it is minimal and it is canonical1 . Finally, a query F is minimally entailed from a
KB (or, equivalently, F belongs to the rational closure of KB), written KB |=ALC+TRaCl
R
F , if it holds in all minimal canonical models of KB minimally satisfying A. In [14] it
is shown that query entailment in ALC + TRaCl R , i.e. the problem of checking whether
a query F is in the rational closure of KB, namely that KB |=ALC+TRaCl F , is in
R
E XP T IME.
3 The Logic ALC + Texp
R : Reasoning About Surprising Scenarios
In this section we define an alternative semantics that allows us to express a degree
of expectedness for the typicality inclusions and to limit the number of typicality as-
sumptions in the ABox in order to obtain less predictable scenarios. The basic idea is
similar to the one proposed in [10], where a completion of an ALC+T ABox is proposed
in order to assume that every individual constant of the ABox is a typical element of
the most specific concept he belongs to, if this is consistent with the knowledge base.
Here we propose a similar, algorithmic construction in order to compute only some as-
sumptions of typicality of domain elements/individual constants, in order to describe
an alternative, surprising but plausible scenario. Constraints about the cardinality of the
extensions of concepts are also introduced in order to filter scenarios, allowing to define
eligible extensions of the ABox satisfying such constraints, and entailment is restricted
to minimal scenarios, called perfect extensions, with respect to an order relation among
1
In Theorem 10 in [14] the authors have shown that for any KB there exists a finite minimal
canonical model of KB minimally satisfying the ABox.
extensions: intuitively, an extension is preferred to another one if it represents a more
surprising scenario.
As mentioned above, the logic ALC +Texp R allows to express cardinality restrictions
in the TBox. More expressive DLs allow to specify (un)qualified number restrictions, in
order to specify the number of possible elements filling a given role R. As an example,
number restrictions allow to express that a student attends to 3 courses. Number restric-
tions are therefore “localized to the fillers of one particular role” [17], for instance we
can have Student v= 3Attends.Course as a restriction on the number of role fillers of
the role Attends. However one could need to express global restrictions on the number
of domain elements belonging to a given concept, for instance to express that in the
whole domain there are exactly 3 courses. In DLs not allowing cardinality restrictions
one can only express that every student must attend to three courses, but not that all
must attend to the same ones. In the logic ALC + Texp R , cardinality restrictions on con-
cepts are added to the TBox as in Definition 1. They are expressions of the form either
(≥ n C) or (≤ n C) or (= n C), where n is a positive integer and C is a concept. This
is formally defined in the next definition, where, given a set S, we write ]S to mean the
cardinality of S.
Let us first define the language L of this new Description Logic called ALC + Texp R .
It is known that axioms expressing cardinality restrictions are even more expressive than
.
inclusions C v D or C = D, the last one shortening for the pair of inclusions C v D
and D v C (thus expressing that the concepts C and D have the same extensions, i.e.
.
C I = DI ). Indeed, C = D means that the set of domain elements that are Cs but not
Ds is empty, and viceversa (the set of domain elements that are Ds but not Cs is empty).
This can be expressed by the following cardinality restriction: (= 0 ((C u¬D)t(¬C u
D))). The same for an inclusion of the form C v D, whose meaning is that every C
element is also a D element, that can be expressed by (= 0 (C u ¬D)) (the intersection
of C I and the complement of DI is empty). Therefore, we could restrict our language
to TBoxes only containing cardinality restriction, however we have decided to consider
the extended language of Definition 1 for the sake of readability.
Definition 1. We consider an alphabet of concept names C, of role names R, and of
individual constants O. Given A ∈ C and R ∈ R, we define:
C := A | > | ⊥ | ¬C | C u C | C t C | ∀R.C | ∃R.C
An ALC + Texp
R knowledge base is a pair (T , A). T contains axioms of the form:
– C v C;
– T(C) vd C, where d ∈ N+ is called the degree of expectedness;
– ( n C), where ∈ {=, ≤, ≥} and n ∈ N+ ;
A contains assertions of the form C(a) and R(a, b), where a, b ∈ O.
Given an inclusion T(C) vd D, the higher the degree of expectedness the more the in-
clusion is, in some sense, “obvious”/not surprising. Given another inclusion T(C 0 ) vd0
D0 , with d0 < d, we assume that this inclusion is less “obvious”, more surprising with
respect to the other one. As an example, let KB contain:
T(Student) v4 SocialNetworkUser
T(Student) v2 PartyParticipant
representing that typical students make use of social networks, and that normally they
go to parties; however, the second inclusion is less obvious with respect to the first
one. In other words, one can think of representing the fact that both are properties of a
prototypical student, however there are more exceptions of students not taking part to
parties with respect to the number of exceptions of students not being part of the social
media ecosphere.
It is worth noticing that using positive integers for expressing degrees of expected-
ness is only a way of formalizing a partial order among typicality inclusions, however
all properties expressed by typicality inclusions of the form T(C) vd D are typical
properties, even if n is high: the ontology engineer has still to distinguish between
properties that are prototypical (even with some exceptions) and those that are not and
do not deserve to be represented by a typicality inclusion. It is also worth noticing that
degrees of expectedness are not intended to represent priorities among inclusions (as in
circumscribed KBs), since specificity is provided for free by the preferential semantics
of the logic ALC + TRaCl
R .
3.1 Extensions of ABox
Given a KB, we define the finite set C of concepts occurring in the scope of the typicality
operator, i.e. C = {C | T(C) vd D ∈ 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 “plausi-
ble” typicality assumptions T(C)(a) that can be minimally entailed from KB without
cardinality restrictions in the logic ALC + TRaClR , with C ∈ C. We then consider an
ordered set of pairs (a, C) of all possible assumptions T(C)(a), for all concepts C ∈ C
and all individual constants a occurring in the ABox. This is formally stated in the next
definition:
Definition 2 (Assumptions in ALC+Texp exp
R ). Given an ALC+TR KB=(T ∪ Tcard , A),
where Tcard is a set of cardinality restrictions and T does not contain cardinality re-
strictions, let T 0 be the set of inclusions of T without degrees of expectedness. Given a
finite set of concepts C, we define, for each individual name a occurring in A:
Ca = {C ∈ C | (T 0 , A) |=ALC+TRaCl T(C)(a)}
R
We also define CA = {(a, C) | C ∈ Ca and a occurs in A} and we impose an order
on the elements of CA = [(a1 , C1 ), (a2 , C2 ), . . . , (an , Cn )]. Furthermore, we define
the ordered multiset dA = [d1 , d2 , . . . , dn ] respecting the order imposed on CA , where
di = avg({d ∈ N+ | T(Ci ) vd D ∈ Tcard }).
Intuitively, the ordered multiset dA is a tuple of the form [d1 , d2 , . . . , dn ], where di
is the degree of expectedness of the assumption T(C)(a), such that (a, C) ∈ CA at
position i. di corresponds to the average2 of all the degrees d of typicality inclusions
T(C) vd D in the TBox.
In order to define alternative scenarios, where not all plausible assumptions are
taken into account, we consider different extensions of the ABox and we introduce an
order among them, allowing to range from unpredictable to trivial ones. Starting from
dA = [d1 , d2 , . . . , dn ], the first step is to build all alternative tuples where 0 is used
in place of some di to represent that the corresponding typicality assertion T(C)(a) is
no longer assumed (Definition 3). Furthermore, we define the extension of the ABox
corresponding to a string so obtained (Definition 4).
Definition 3 (Strings of plausible assumptions S). Given a KB=(T , A) and the set
CA , let dA = [d1 , d2 , . . . , dn ] be as in Definition 2. We define the set S of all the strings
of plausible assumptions with respect to KB as
S = {[s1 , s2 , . . . , sn ] | ∀i = 1, 2, . . . , n either si = di or si = 0}
Definition 4 (Extension of the ABox). Let KB=(T , A) and let CA = [(a1 , C1 ), (a2 , C2 ),
. . . , (an , Cn )] as in Definition 2. Given a string of plausible assumptions [s1 , s2 , . . . , sn ] ∈
S of Definition 3, we define the extension Ab of A with respect to CA and S
Ab = {T(Ci )(ai ) | (ai , Ci ) ∈ CA and si 6= 0}
It is easy to observe that, in ALC + TRaCl
R , the set of typicality assumptions that can
be inferred from a KB corresponds to the extension of A corresponding to the string
dA , that is to say no element is set to 0: all the typicality assertions of individuals
occurring in the ABox, that are consistent with the KB, are assumed. On the contrary, in
ALC +TR , no typicality assumption can be derived from a KB, and this corresponds to
extending A by the assertions corresponding to the string [0, 0, . . . , 0], i.e. by the empty
set.
3.2 Cardinality restrictions and perfect extensions
Let us now introduce models of the Description Logic ALC + Texp R taking cardinality
restrictions into account, as well as the notion of eligible extension of the ABox as a set
of typicality assumptions satisfying cardinality restrictions.
Definition 5. Given a model M = h∆I , <, .I i, it satisfies:
– (TBox)
• an inclusion C v D if C I ⊆ DI ;
• a typicality inclusion T(C) vd D if Min < (C I ) ⊆ DI ;
• a cardinality restriction of the form ( n C) if ]C I n, where ∈ {≤, ≥, =}
and n ∈ N+ ;
2
Other aggregation functions could be used in order to define di (maximun degree, minimum
degree). We aim at studying the impact of the choice on the reasoning machinery in future
research.
– (ABox)
• an assertion of the form C(a) if aI ∈ C I ;
• an assertion of the form R(a, b) if (aI , bI ) ∈ RI .
Given a KB=(T , A), we say that a model M satisfies KB if it satisfies all the inclusions
in T and all the assertions in A.
Given a KB=(T , A), we say that an extension of A is an eligible extension if it admits
a model as in Definition 5:
Definition 6 (Eligible extension A).b Given an ALC + Texp KB=(T , A) and an exten-
R
sion Ab of A as in Definition 4, we say that Ab is eligible if there exists an ALC + Texp
R
model M as in Definition 5 that satisfies KB’=(T , A ∪ A). b
Let us now introduce an order relation among the strings of S (Definition 3), corre-
sponding to eligible extensions of the ABox:
Definition 7 (Order between eligible extensions). Given KB=(T , A) and the set S of
Definition 3, let s = [s1 , s2 , . . . , sn ] and r = [r1 , r2 , . . . , rn ], with s, r ∈ S. Let A
cs and
Ar be two eligible extensions of A corresponding to s and r (Definition 4). We say that
c
s < r if there exists a bijection δ between s and r such that, for each (si , rj ) ∈ δ, it
holds that si ≤ rj , and there is at least one (si , rj ) ∈ δ such that si < rj . We say that
A
cs is more surprising (or less trivial) than A cr if s < r.
Intuitively, a string s whose elements are “lower” than the ones of another string r cor-
responds to a less trivial ABox. For instance, let us consider a KB whose typicality
inclusions are T(C) v1 D and T(E) v2 F , and such that T(C)(a), T(C)(b), and
T(E)(b) are entailed in ALC + TRaCl R . 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 assump-
tions 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 Defini-
tion 7 is partial: as an example, the strings [1, 1, 0] and [0, 0, 2] are not comparable, in
the sense that [1, 1, 0] 6< [0, 0, 2] and [0, 0, 2] 6< [1, 1, 0]. In order to choose between
two incomparable situations, we introduce the following notion of weak order: given
two incomparable extensions A cs and A cr , we assume that A cs is weakly less trivial than
Ar if Ar is strictly included in another eligible extension A
c c cu more trivial than Acs , i.e.
A
cr ⊂ A cu and s < u.
Definition 8 (Minimal (perfect) extensions). Given a KB=(T , A) and the set S of
strings of plausible assumptions (Definition 3), we say that an eligible extension A
cs is
minimal or perfect if there is no other eligible extension Ar which is (weakly) more
c
surprising (or (weakly) less trivial) than A
cs .
Given the above definitions, we can define a notion of entailment in ALC + Texp R .
Intuitively, given a query F , we check whether F follows in the monotonic logic ALC +
TR from a given KB, whose ABox is augmented with extensions that are minimal
(perfect) as in Definition 8. We can reason either in a skeptical way, by asking that F is
entailed if it follows in all KBs, obtained by considering each minimal extension of the
ABox, or in a credulous way, by assuming that F is entailed if there exists at least one
extension of the ABox allowing such inference. This is stated in a rigorous manner by
the following definition:
Definition 9 (Entailment in ALC + Texp R ). Given a KB=(T , A) and given C a set of
concepts, let E the set of all extensions of A that are minimal as in Definition 8. Given
a query F , we say that (i) F is skeptically entailed from KB in ALC + Texp R , written
KB |=sk exp F , if (T , A ∪ A)
b |= ALC+T R
F for all A
b ∈ E; (ii) F is credulously
ALC+TR
entailed from KB in ALC + Texp cr
R , written KB |= exp F , if there exists A ∈ E such
b
ALC+TR
that (T , A ∪ A)
b |=ALC+T F .
R
At a first glance, one could have the impression that the notions of rank in the seman-
tics of ALC + TRaClR , where elements with lowest rank are the most typical ones, and
the semantics of expectedness of Definitions 7 and 8, where lower ranks correspond to
more surprising scenarios, are in conflict. However, this is not the case: ranks in the
semantics are introduced in order to define the extension of typicality concepts, and
this notion is also considered in the expectation semantics to select plausible typicality
assumptions. The rank among extensions is rather used in order to choose surprising
scenarios, to restrict the number of typicality assumptions to satisfy cardinality restric-
tions: the unexpectedness is the additional ingredient to select surprising scenarios by
fixing cardinality restrictions, where all candidates try to maximize the typicality of
individuals.
Let us conclude by showing an example of reasoning in the logic ALC + Texp R .
Example 1 (Mysterious medical diagnosis). In this example we exploit the logic ALC+
Texp
R in order to provide a mysterious medical diagnosis, as an alternative to the most
likely explanation, for a patient characterized by mood swings. The idea is to support the
medical staff whenever the “standard” diagnosis fails, suggesting surprising alternatives
that could be taken into account for further investigations.
Let KB=(T , A) as follows and let T be:
T(Cancer ) v1 MoodSwingsCause (T1)
T(BrainDisorder ) v3 MoodSwingsCause (T2)
T(MajorDepressionAtypicalFeatures) v2 MoodSwingsCause (T3)
(= 1 MoodSwingsCause) (T4)
the last one stating that we are interested in finding exactly one disease being respon-
sible for mood reactivity. Concerning typicality inclusions, we represent the facts that
normally, cancer causes mood swings (T1), however this admits more exceptions with
respect to the fact that mood reactivity is a typical symptom of depressive disorders
with atypical features (T3), which is in turn more surprising than the most “obvious”
inclusion, namely that brain disorders normally cause changes in the mood of patients
(T2). The cardinality restriction (T4) imposes that exactly one disease is the reason why
the patient’s mood swings. Let A be:
Cancer (prostaticCancer )
BrainDisorder (bipolarDisorder )
MajorDepressionAtypicalFeatures(bipolarDisorder )
MajorDepressionAtypicalFeatures(atypicalDepression)
In the logic ALC + TexpR , we can infer that prostatic cancer is responsible of mood
swings in our patient:
KB |=sk exp MoodSwingsCause(prostaticCancer )
ALC+TR
KB |= cr MoodSwingsCause(prostaticCancer )
exp
ALC+TR
since there is only one perfect extension. Let
C = {Cancer , MajorDepressionAtypicalFeatures, BrainDisorder }.
By Definition 2 above, we have that:
CprostaticCancer = {Cancer },
CatypicalDepression = {MajorDepressionAtypicalFeatures},
CbipolarDisorder = {BrainDisorder , MajorDepressionAtypicalFeatures}
and, obviously, CA = CprostaticCancer ∪ CatypicalDepression ∪ CbipolarDisorder . Con-
cerning the degrees of expectedness, we have dA = [1, 3, 2, 2]. As mentioned above, in
ALC + TRaCl
R the minimal model semantics forces all the consistent typicality assump-
tions, namely we are considering an ABox extended with the following facts:
T(Cancer )(prostaticCancer )
T(BrainDisorder )(bipolarDisorder )
T(MajorDepressionAtypicalFeatures)(bipolarDisorder )
T(MajorDepressionAtypicalFeatures)(atypicalDepression)
corresponding (in the sense of Definition 4) to the multiset [1, 3, 2, 2]. However, in
ALC + TR we obtain that prostatic cancer, bipolar disorder and atypical depression
are all responsible of mood reactivity in the patient, against the fact that we want to fo-
cus on only one disease: the extension corresponding to [1, 3, 2, 2] is indeed not eligible
in the sense of Definition 6. In order to find only one non-trivial diagnosis justifying
mood swings, we consider the set S of all plausible strings of typicality assumptions
(Definition 3). The only eligible extensions of the ABox are:
A
c1 = {T(BrainDisorder )(bipolarDisorder )}, by [0, 3, 0, 0]
A
c2 = {T(MajorDepressionAtypicalFeatures)(atypicalDepression)}, by [0, 0, 0, 2]
A
c3 = {T(Cancer )(prostaticCancer )}, [1, 0, 0, 0]
A
c4 = {T(MajorDepressionAtypicalFeatures)(bipolarDisorder )}, [0, 0, 2, 0]
A
c5 = {T(BrainDisorder )(bipolarDisorder ), T(MajorDepressionAtypicalFeatures)
(bipolarDisorder )}, corresponding to [0, 3, 2, 0]
We have that A c1 , A
c2 and A c4 are less trivial than A
c5 , because [0, 3, 0, 0] < [0, 3, 2, 0],
as well as [0, 0, 0, 2] < [0, 3, 2, 0] and [0, 0, 2, 0] < [0, 3, 2, 0]. However, A c3 is less
trivial than A1 , A2 and A4 , since [1, 0, 0, 0] < [0, 3, 0, 0], as well as [1, 0, 0, 0] <
c c c
[0, 0, 0, 2] and [1, 0, 0, 0] < [0, 0, 2, 0]. This allows to suggest that prostatic cancer
could be a “mysterios diagnosis” for the patient having mood swings, and such a non
trivial diagnosis could be confirmed by an evaluation of other typical symptoms of such
a disease, e.g. nocturia.
4 A Decision Procedure for Reasoning in ALC + Texp
R
In this section we describe a decision procedure for reasoning in the logic ALC +
Texp
R . 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 + Texp R is
in E XP T IME. 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 E XP T IME complete [19].
Following the definitions of nonmonotonic entailment introduced in the previous
section, given an ALC + Texp R KB=(T , A) and a query F , we define a procedure com-
puting the following three steps:
1. compute the set Ca of all typicality assumptions that are minimally entailed from
the knowledge base in the nonmonotonic logic ALC + TRaCl R ;
2. compute all possible extensions of the ABox and select perfect extensions;
3. check whether the query F is entailed from at least one extension/all the extensions
of KB in the monotonic logic ALC + TR plus cardinality restrictions.
Step 3 is based on reasoning in the monotonic logic ALC + TR : to this aim, the proce-
dure relies on a polynomial encoding of ALC + TR into ALC introduced in [20] and
then on reasoning with cardinality restrictions. Step 1 is based on reasoning in the non-
monotonic logic ALC + TRaCl R : in this case, the procedure computes the rational closure
of an ALC + TR knowledge base by means of the algorithm introduced in [14], which
is sound and complete with respect to the minimal model semantics recalled in Section
2.2. Also the algorithm computing the rational closure relies on reasoning in the mono-
tonic logic ALC + TR , then on the above mentioned polynomial encoding in ALC.
We assume unary encoding of numbers in cardinality restrictions in order to exploit the
results in [21], namely that reasoning in ALCO, extending ALC with qualified number
restrictions, is E XP T IME-complete also with cardinality restrictions. Due to space limi-
tations, here we only introduce the overall procedure for reasoning in ALC + Texp R and
we analyze its complexity, whereas we remind to the accompanying report [22] for the
procedures for reasoning in ALC + TR and ALC + TRaCl R .
Let KB=(T ∪ Tcard , A) be an ALC + Texp R knowledge base, where Tcard is a set
of cardinality restrictions and T does not contain cardinality restrictions. Let T 0 be the
set of inclusions of T without the degrees of expectedness: T 0 = {C v D | C vn
D ∈ T }, that the procedure will take into account in order to reason in ALC + TR
and ALC + TRaCl R for checking query entailment and finding all plausible typicality
assumptions, respectively. Other inputs of the procedure are a finite set of concepts C
and a query F . Algorithm 1 checks whether F is skeptically entailed from the KB in
the logic ALC + Texp sk
R , namely whether KB |= exp F .
ALC+TR
Algorithm 1 Skeptical entailment in ALC + Texp sk
R : KB |= exp F
ALC+TR
1: procedure S KEPTICAL E NTAILMENT((T ∪ Tcard , A), T 0 , F , C)
2: CA ← ∅ . build the set S of plausible assumptions
3: for each C ∈ C do
4: for each individual a ∈ A do . Reasoning in ALC + TRaCl R
0 RaCl
5: if (T , A) |=ALC +TR T(C)(a) then CA ← CA ∪ {T(C)(a)}
6: dA ← build the ordered multiset of avg degrees of Definition 2 given T and CA
7: S ← build strings of plausible extensions as in Definition 3 given CA and dA
8: Apl ← ∅ . build plausible extensions of A
9: for each di ∈ S do
10: build the extension Abi corresponding to di
11: Apl ← Apl ∪ Abi
12: Ael ← ∅ . select eligible extensions checking cardinality restrictions
13: for each Abi ∈ Apl do . Reasoning in ALC + TR plus cardinality restrictions
14: if (T 0 ∪ Tcard , A ∪ Abi ) is satisfiable in ALC + TR then
15: Ael ← Ael ∪ Abi
16: for each Abi ∈ Ael do . check preference among extensions of A
17: for each Abj ∈ Ael do
18: if di ≤ dj then let Abi < Abj
19: E ← {Abi |6 ∃Abj ∈ Ael such that Abj < Abi } . select perfect extensions
20: for each Abi ∈ E do . query entailment in ALC + TR plus cardinality restrictions
21: if (T 0 ∪ Tcard , A ∪ Abi ) 6|=ALC+TR F then
22: return KB 6|=sk exp F . a perfect extension not entailing F
ALC+TR
23: return KB |=sk exp F . F is entailed in all perfect extensions
ALC+TR
In order to check whether F is credulously entailed from the KB, that is to say KB
|=cr exp F , the algorithm is obtained by replacing lines 20-23 in Algorithm 1 by
ALC+TR
the following ones:
20: for each Abi ∈ E do
21: if (T 0 ∪ Tcard , A ∪ Abi ) |=ALC+TR F then
22: return KB |=cr exp F
ALC+TR
23: return KB 6|=cr exp F
ALC+TR
By exploiting the procedures above, we show that:
Theorem 1 (Complexity of entailment). Given a KB in ALC + Texp R and a query F
whose size is polynomial in the size of KB, assuming the unary encoding of numbers in
cardinality restrictions of KB, the problem of checking skeptically (resp. credulously)
whether KB |=sk exp F (resp. KB |=
cr
exp F ) is E XP T IME -complete.
ALC+TR ALC+TR
Proof. (sketch, see [22] for the complete proof ) The algorithm checks, for each concept
C ∈ C and for each individual name a whether T(C)(a) is minimally entailed from KB
in the nonmonotonic logic ALC + TRaCl R . By definition, the size of C is O(n). For each
T(C)(a) (they are O(n2 )) the algorithm relies on reasoning in ALC + TRaCl R , which is
in E XP T IME. Building dA can be solved with O(n2 ) operations. For building the set S
of plausible extensions we have to consider all possible strings obtained by assuming
(or not) each typicality assumption T(C)(a), that are O(n2 ): for each di , we have two
options (di = 0 or di 6= 0) , then 2 × 2 × . . . × 2 different strings, thus S has exponen-
tial size in n. Checking, for each extension of A, if it satisfies cardinality constraints
2
requires O(2n ) calls to satisfiability in ALC + TR plus cardinality restrictions, that is
in E XP T IME. Ordering extensions of A and finding perfect extensions can be solved in
E XP T IME, then the algorithm relies on reasoning in monotonic ALC + TR plus cardi-
nality restrictions in order to check whether the query F is entailed in perfect extensions
in E, whose size is O(2n ): we have O(2n ) call to query entailment in ALC +TR , which
is an E XP T IME-complete problem.
Since reasoning in the underlying standard ALC is E XP T IME-complete, we can con-
clude that reasoning about typicality in surprising scenarios is essentially inexpensive.
5 Conclusions
In this work we have provided a nonmonotonic procedure for preferential Description
Logics in order to reason about surprising scenarios. We have introduced the Descrip-
tion Logic of typicality ALC + Texp R , an extension of ALC with a typicality operator
T allowing to (i) express typicality inclusions of the form T(C) vd D, where d is
a positive integer representing a degree of expectedness; (ii) reason in presence of re-
strictions on the cardinality of concepts. We have also described a procedure for rea-
soning in ALC + Texp R exploiting reasoning mechanisms in the logics ALC + TR and
ALC + TRaCl R , the last one relying on a notion of rational closure for Description Log-
ics. This procedure allowed us to show that entailment in ALC + Texp R is E XP T IME
complete as the underlying ALC, therefore it is essentially inexpensive, once unary
encoding of numbers in cardinality restrictions is assumed.
The extension of DLs of typicality with cardinality restrictions is of its own inter-
est, and one can think of considering cardinality restrictions not limited to surprising
scenarios of the logic ALC + Texp R , but directly applied to the nonmonotonic semantics
of ALC + TRaClR . Furthermore, we aim at studying also cardinality restrictions on roles.
In future work we aim at extending this approach to more expressive Description
Logics, in particular the logics underlying the standard language for ontology engineer-
ing OWL. As a first step, in [23] the logic with the typicality operator and the rational
closure construction have been applied to the description logic SHIQ.
A comparison with probabilistic approaches will be also object of further investi-
gations. To the best of our knowledge, the literature lacks a formalization of surprising
scenarios in probabilistic formalizations of knowledge, however it is worth observing
that a surprising scenario could be defined as a set of facts with a low probability, then
one can think of restricting the attention to less probable outcomes.
Acknowledgements
The author is partially supported by the project “ExceptionOWL: Nonmonotonic Ex-
tensions of Description Logics and OWL for defeasible inheritance with exceptions” ,
Progetti di Ateneo Università degli Studi di Torino and Compagnia di San Paolo, call
2014, line “Excellent (young) PI”, project ID: Torino call2014 L1 111.
References
1. Pozzato, G.L.: Preferential description logics meet sports entertainment: cardinality restric-
tions and perfect extensions for a better royal rumble match. In Ancona, D., Maratea, M.,
Mascardi, V., eds.: Proceedings of the 30th Italian Conference on Computational Logic, Gen-
ova, Italy, July 1-3, 2015. Volume 1459 of CEUR Workshop Proceedings., CEUR-WS.org
(2015) 159–174
2. Bonatti, P.A., Lutz, C., Wolter, F.: The complexity of circumscription in dls. Journal of
Artificial Intelligence Research (JAIR) 35 (2009) 717–773
3. Baader, F., Hollunder, B.: Priorities on defaults with prerequisites, and their application in
treating specificity in terminological default logic. Journal of Automated Reasoning (JAR)
15(1) (1995) 41–68
4. Bonatti, P.A., Faella, M., Sauro, L.: Defeasible inclusions in low-complexity dls. Journal of
Artificial Intelligence Research (JAIR) 42 (2011) 719–764
5. Donini, F.M., Nardi, D., Rosati, R.: Description logics of minimal knowledge and negation
as failure. ACM Transactions on Computational Logics (ToCL) 3(2) (2002) 177–225
6. Casini, G., Straccia, U.: Rational closure for defeasible description logics. In Janhunen,
T., Niemelä, I., eds.: Logics in Artificial Intelligence - Proceedings of the12th European
Conference (JELIA 2010). Volume 6341 of Lecture Notes in Computer Science (LNCS).,
Springer (2010) 77–90
7. Casini, G., Straccia, U.: Defeasible Inheritance-Based Description Logics. Journal of Artifi-
cial Intelligence Research (JAIR) 48 (2013) 415–473
8. Straccia, U.: Default inheritance reasoning in hybrid kl-one-style logics. In: Proceedings of
the 13th International Joint Conference on Artificial Intelligence (IJCAI’93), Morgan Kauf-
mann (1993) 676–681
9. Bonatti, P.A., Faella, M., Petrova, I., Sauro, L.: A new semantics for overriding in description
logics. Artificial Intelligence 222 (2015) 1–48
10. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: ALC+T: a preferential extension of
description logics. Fundamenta Informaticae 96 (2009) 341–372
11. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A NonMonotonic Description Logic
for Reasoning About Typicality. Artificial Intelligence 195 (2013) 165 – 202
12. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Preferential vs Rational Description
Logics: which one for Reasoning About Typicality? . In Coelho, H., Studer, R., Wooldridge,
M., eds.: Proceedings of the 19th European Conference on Artificial Intelligence (ECAI
2010). Volume 215 of FAIA (Frontiers in Artificial Intelligence and Applications)., Lisbon,
Portugal, IOS Press (August 2010) 1069 – 1070
13. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Reasoning about typicality in low
complexity DLs: the logics EL⊥ Tmin and DL-Litec Tmin . In Walsh, T., ed.: Proceedings of
the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), Barcelona,
Spain, IOS Press (2011) 894–899
14. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Semantic characterization of Rational
Closure: from Propositional Logic to Description Logics. Artificial Intelligence 226 (2015)
1–33
15. Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and
cumulative logics. Artificial Intelligence 44(1-2) (1990) 167–207
16. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artificial
Intelligence 55(1) (1992) 1–60
17. Baader, F., Buchheit, M., Hollunder, B.: Cardinality restrictions on concepts. Artificial
Intelligence 88(1-2) (1996) 195–213
18. Bordino, I., Mejova, Y., Lalmas, M.: Penguins in sweaters, or serendipitous entity search
on user-generated content. In He, Q., Iyengar, A., Nejdl, W., Pei, J., Rastogi, R., eds.: 22nd
ACM International Conference on Information and Knowledge Management, CIKM’13, San
Francisco, CA, USA, October 27 - November 1, 2013. (2013) 109–118
19. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.: The Descrip-
tion Logic Handbook - Theory, Implementation, and Applications, 2nd edition. Cambridge
(2007)
20. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Minimal model semantics and rational
closure in description logics. In Eiter, T., Glimm, B., Kazakov, Y., Krötzsch, M., eds.: Infor-
mal Proceedings of the 26th International Workshop on Description Logics. Volume 1014 of
CEUR Workshop Proceedings., CEUR-WS.org (2013) 168–180
21. Tobies, S.: The complexity of reasoning with cardinality restrictions and nominals in expres-
sive description logics. Journal of Artificial Intelligence Research (JAIR) 12 (2000) 199–217
22. Pozzato, G.L.: On Reasoning about surprising scenarios in Preferential Description Logics.
In: Technical Report 02/2015, http://www.di.unito.it/∼pozzato/papers/RT022015.pdf, Dip.
di Informatica, Univ. di Torino. (2015)
23. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Rational closure in SHIQ. In: DL
2014, 27th International Workshop on Description Logics. Volume 1193 of CEUR Workshop
Proceedings., CEUR-WS.org (2014) 543–555