=Paper=
{{Paper
|id=Vol-1645/paper_16
|storemode=property
|title=Reasoning in a Rational Extension of SROEL
|pdfUrl=https://ceur-ws.org/Vol-1645/paper_16.pdf
|volume=Vol-1645
|authors=Laura Giordano,Daniele Theseider Dupré
|dblpUrl=https://dblp.org/rec/conf/cilc/0001D16
}}
==Reasoning in a Rational Extension of SROEL==
https://ceur-ws.org/Vol-1645/paper_16.pdf
Reasoning in a Rational Extension of SROEL
Laura Giordano1 and Daniele Theseider Dupré1
DISIT - Università del Piemonte Orientale, Alessandria, Italy -
laura.giordano@uniupo.it, dtd@di.unipmn.it
Abstract. In this work we define a rational extension SROEL(⊓, ×)R T of
the low complexity description logic SROEL(⊓, ×), which underlies the OWL
EL ontology language. The logic is extended with a typicality operator T, whose
semantics is based on Lehmann and Magidor’s ranked models and allows for the
definition of defeasible inclusions. We consider both rational entailment and min-
imal entailment. We show that deciding instance checking under minimal entail-
ment is a CO NP-hard problem while, under rational entailment, instance checking
can be computed in polynomial time. In particular, we develop a Datalog materi-
alization calculus for instance checking under rational entailment.
1 Introduction
The need for extending Description Logics (DLs) with nonmonotonic features has led,
in the last decade, to the development of several extensions of DLs, obtained by combin-
ing them with the most well-known formalisms for nonmonotonic reasoning [3, 36, 4,
14, 22, 16, 29, 11, 8, 13, 35, 6, 30, 12, 26, 5, 27] to deal with defeasible reasoning and in-
heritance, to allow for prototypical properties of concepts and to combine DLs with non-
monotonic rule-based languages under the answer set semantics [16], the well-founded
semantics [15], the MKNF semantics [35, 30], as well as in Datalog +/- [28]. Systems
integrating Answer Set Programming (ASP) [19, 18] and DLs have been developed,
e.g., the DReW System for Nonmonotonic DL-Programs [37].
In this paper we study a preferential extension of the logic SROEL(⊓, ×), intro-
duced by Krötzsch [32], which is a low-complexity description logic of the EL family
[1] that includes local reflexivity, conjunction of roles and concept products and is at the
basis of OWL 2 EL. Our extension is based on Kraus, Lehmann and Magidor (KLM)
preferential semantics [31], and, specifically, on ranked models [34]. We call the logic
SROEL(⊓, ×)R T and define notions of rational and minimal entailment for it.
The semantics of ranked interpretations for DLs was first studied in [11], where a ra-
tional extension of ALC is developed allowing for defeasible concept inclusions of the
form C⊏D. In this work, following [23, 27], we extend the language of SROEL(⊓, ×)
e
with typicality concepts of the form T(C), whose instances are intended to be the typi-
cal C elements. Typicality concepts can be used to express defeasible inclusions of the
form T(C) ⊑ D (“the typical C elements are D”). Here, however, as in [9, 21], we
allow for typicality concepts to freely occur in concept inclusions. In this respect, the
language with typicality that we consider is more general than the language with typi-
cality in [27], where the typicality operator T(C ) may only occur on the left hand side
2 L. Giordano, D. Theseider Dupré
of inclusions as well as in assertions. For the language in [27], minimal ranked mod-
els have been shown to provide a semantic characterization to rational closure for the
description logic ALC, generalizing to DLs the rational closure by Lehmann and Magi-
dor [34]. Alternative constructions of rational closure for ALC have been proposed in
[13, 12]. All such constructions regard languages only containing strict or defeasible
inclusions.
We show that, for general SROEL(⊓, ×)R T KBs, deciding instance checking un-
der minimal entailment is a CO NP-hard problem. Furthermore, we define a Datalog
translation for SROEL(⊓, ×)R T which builds on the materialization calculus in [32],
and, for typicality reasoning, is based on properties of ranked models, showing that in-
stance checking for SROEL(⊓, ×)R T can be computed in polynomial time under the
rational entailment. This polynomial upper bound also extends to subsumption, with the
consequence that a Rational Closure construction for SROEL(⊓, ×)R T, based on the
definition in [27], can be computed in polynomial time. However, the minimal canoni-
cal model semantics does not provide a general semantic characterization of the rational
closure for the logic SROEL(⊓, ×) with typicality, as a KB may have alternative min-
imal canonical models with incompatible rankings, or no canonical model at all. An
extended abstract of this paper appeared in [20].
2 A rational extension of SROEL(⊓, ×)
In this section we extend the notion of concept in SROEL(⊓, ×) adding typicality
concepts (we refer to [32] for a detailed description of the syntax and semantics of
SROEL(⊓, ×)). We let NC be a set of concept names, NR a set of role names and NI
a set of individual names. A concept in SROEL(⊓, ×) is defined as follows:
C := A | ⊤ | ⊥ | C ⊓ C | ∃R.C | ∃S.Self | {a}
where A ∈ NC and R, S ∈ NR . We introduce a notion of extended concept CE as
follows:
CE := C | T(C) | CE ⊓ CE | ∃S.CE
where C is a SROEL(⊓, ×) concept. Hence, any concept of SROEL(⊓, ×) is also an
extended concept; a typicality concept T(C) is an extended concept and can occur in
conjunctions and existential restrictions, but it cannot be nested.
A KB is a triple (TBox , RBox , ABox ). TBox contains a finite set of general con-
cept inclusions (GCI) C ⊑ D, where C and D are extended concepts; RBox (as in
[32]) contains a finite set of role inclusions of the form S ⊑ T , R ◦ S ⊑ T , role con-
junctions S1 ⊓ S2 ⊑ T , concept product axioms and C × D ⊑ T and R ⊑ C × D,
where C and D are concepts, and R, S, S1 , S2 , T are role names in NR . ABox con-
tains individual assertions of the form C(a) and R(a, b), where a, b ∈ NI , R ∈ NR
and C is an extended concept. Restrictions are imposed on the use of roles as in [32]
(and, in particular, all the roles occurring in Self concepts and in role conjunctions must
be simple roles, roughly speaking, roles which do not include the composition of other
roles).
Reasoning in a Rational Extension of SROEL(⊓, ×) 3
We define a semantics for SROEL(⊓, ×)R T based on ranked models [34]. As
done in [27] for ALC, we define the semantics of SROEL(⊓, ×)R T by adding to
SROEL(⊓, ×) interpretations [32] a preference relation < on the domain, which is
intended to compare the “typicality” of domain elements. The typical instances of a
concept C, i.e., the instances of T(C), are the instances of C that are minimal with re-
spect to <. The properties of the < relation are defined in agreement with the properties
of the preference relation in Lehmann and Magidor’s ranked models in [34]. A seman-
tics for DLs with defeasible inclusions based on ranked models was first proposed in
[11].
Definition 1. A SROEL(⊓, ×)R T interpretation M is any structure h∆, <, ·I i where:
– ∆ is a domain; ·I is an interpretation function that maps each concept name A ∈
NC to a set AI ⊆ ∆, each role name R ∈ NR to a binary relation RI ⊆ ∆ × ∆,
and each individual name a ∈ NI to an element aI ∈ ∆. ·I is extended to complex
concepts as usual:
⊤I = ∆; ⊥I = ∅; {a}I = {aI };
I I I
(C ⊓ D) = C ∩ D ;
(∃R.C)I = {x ∈ ∆ | ∃y ∈ C I : (x, y) ∈ RI };
(∃R.Self )I = {x ∈ ∆ | (x, x) ∈ RI };
and the composition of role interpretations is defined as follows:
R1I ◦ R2I = {(x, z) | (x, y) ∈ R1I and (y, z) ∈ R2I , for some y ∈ ∆}
– < is an irreflexive, transitive, well-founded and modular relation over ∆;
– the interpretation of concept T(C) is defined as follows:
(T(C))I = M in< (C I )
where M in< (S) = {u : u ∈ S and ∄z ∈ S s.t. z < u}.
Furthermore, an irreflexive and transitive relation < is well-founded if, for all S ⊆ ∆,
for all x ∈ S, either x ∈ M in< (S) or ∃y ∈ M in< (S) such that y < x. It is modular
if, for all x, y, z ∈ ∆, x < y implies x < z or z < y. The well-foundedness condition
guarantees that if, for a non-extended concept C, there is a C element in M, then there
is a minimal C element in M (i.e., C I 6= ∅ implies (T(C))I 6= ∅).
In the following, we will refer to SROEL(⊓, ×)R T interpretations as ranked in-
terpretations. Indeed, as in [34], modularity in preferential models can be equivalently
defined by postulating the existence of a rank function kM : ∆ 7−→ Ω, where Ω is a
totally ordered set. The preference relation < can be defined from kM as follows: x < y
if and only if kM (x) < kM (y). Hence, in the following, we will assume that a rank
function kM is always associated with any model M. We also define the rank kM (C)
of a concept C in the model M as kM (C) = min{kM (x) | x ∈ C I } (if C I = ∅, then
C has no rank and we write kM (C) = ∞).
Observe that semantics of the typicality operator defined above is exactly the same
as the one introduced in [27] for the typicality operator in ALC + TR . Similarly to all
other concept constructors, the typicality operator can be used in TBox and ABox with
different restrictions, depending on the description logic. Differently from [27], where
T(C) can only occur on the left-hand side of concept inclusions (namely, in typicality
4 L. Giordano, D. Theseider Dupré
inclusions of the form T(C) ⊑ D) here, as in [9, 21], we do not put restrictions on
the possible occurrences of typicality concepts T(C) in concept inclusions and in as-
sertions. Instead, as in SROEL(⊓, ×), we do not allow negation, union and universal
restriction which are allowed in ALC. In the following, we call simple KBs the ones
which only allow typicality concepts to occur on the left hand side of typicality inclu-
sions. Given an interpretation M the notions of satisfiability and entailment are defined
as usual.
Definition 2 (Satisfiability and rational entailment). An interpretation M = h∆, <
, ·I i satisfies:
• a concept inclusion C ⊑ D if C I ⊆ DI ;
• a role inclusion S ⊑ T if S I ⊆ T I ;
• a generalized role inclusion R ◦ S ⊑ T if RI ◦ S I ⊆ T I
• a role conjunction S1 ⊓ S2 ⊑ T if S1I ∩ S2I ⊆ T I ;
• a concept product axiom C × D ⊑ T if C I × DI ⊆ T I ;
• a concept product axiom R ⊑ C × D if RI ⊆ C I × DI ;
• an assertion C(a) if aI ∈ C I ;
• an assertion R(a, b) if (aI , bI ) ∈ RI .
Given a KB K = (TBox , RBox , ABox ), an interpretation M =h∆, <, ·I i satisfies
TBox (resp., RBox , ABox ) if M satisfies all axioms in TBox (resp., RBox , ABox ),
and we write M |= TBox (resp., RBox , ABox ). An interpretation M = h∆, <, ·I i is
a model of K (and we write M |= K) if M satisfies all the axioms in TBox , RBox
and ABox .
Let a query F be either a concept inclusion C ⊑ D, where C and D are extended
concepts, or an individual assertion. F is rationally entailed by K, written K |=sroelrt
F , if for all models M =h∆, <, ·I i of K, M satisfies F . In particular, the instance
checking problem (under rational entailment) is the problem of deciding whether an
assertion (C(a), T(C)(a) or R(a, b)) is rationally entailed by K.
Given the correspondence of typicality inclusions with conditional assertions C |∼
D, it can be easily seen that each ranked interpretation M satisfies the following seman-
tic conditions, corresponding to Lehmann and Magidor’s postulates of rational conse-
quence relation [34] reformulated in terms of typicality, where, by T(A) ⊑ B we mean
that T(A) ⊑ B is satisfied in M, by T(A) 6⊑ ¬B we mean that T(A) ⊑ ¬B is not
satisfied in M, and by A ⊑ B (or A ≡ B) we mean that A ⊑ B (or A ≡ B ) is satisfied
in M (a similar formulation of the semantic properties in terms of defeasible inclusions
can be found in [11]):
(LLE ) If A ≡ B and T(A) ⊑ C then T(B ) ⊑ C
(RW ) If B ⊑ C and T(A) ⊑ B then T(A) ⊑ C
(Refl ) T(A) ⊑ A
(And ) If T(A) ⊑ B and T(A) ⊑ C then T(A) ⊑ B ⊓ C
(Or ) If T(A) ⊑ C and T(B ) ⊑ C then T(A ⊔ B ) ⊑ C
(CM ) If T(A) ⊑ B and T(A) ⊑ C then T(A ⊓ B ) ⊑ C
(RM ) If T(A) ⊑ C and T(A) 6⊑ ¬B then T(A ⊓ B ) ⊑ C
Reasoning in a Rational Extension of SROEL(⊓, ×) 5
It is easy to see that these semantic properties hold in all the ranked models. In particu-
lar, property (RM), can be reformulated as follows:
if (T(A) ⊓ B )I 6= ∅, then (T(A ⊓ B ))I ⊆ (T(A))I
and, in this form, it is a rephrasing of property (fT − R), in the semantics with selection
function of the operator T studied in [27] (Appendix A) for ALC + TR . This property
has a syntactic counterpart in the axiom ∃U.(T(A) ⊓ B) ⊓ T(A ⊓ B) ⊑ T(A), which
holds in all the ranked models.
Consider the following example of knowledge base, stating that: typical Italians
have black hair; typical students are young; they hate math, unless they are nerd (in
which case they love math); all Mary’s friends are typical students. We also have the
assertions stating that Mary is a student, that Mario is an Italian student, and is a friend
of Mary, Luigi is a typical Italian student, and Paul is a typical young student.
Example 1. TBox :
(a) T(Italian) ⊑ ∃hasHair .{Black }
(b) T(Student ) ⊑ Young
(c) T(Student) ⊑ MathHater
(d) T(Student ⊓ Nerd ) ⊑ MathLover
(e) ∃hasHair .{Black } ⊓ ∃hasHair .{Blond } ⊑ ⊥
(f ) MathLover ⊓ MathHater ⊑ ⊥
(g) ∃friendOf .{mary} ⊑ T(Student)
ABox :
Student(mary), friendOf (mario, mary), (Student ⊓ Italian)(mario),
T(Student ⊓Italian)(luigi), T(Student ⊓Young)(paul), T(Student ⊓Nerd )(tom)
The fact that concepts T(C) can occur anywhere (apart from being nested in a
T operator) can be used, e.g., to state that typical working students inherit proper-
ties of typical students (T(Student ⊓ Worker ) ⊑ T(Student )), in a situation in
which typical students and typical workers have conflicting properties (e.g., as re-
gards paying taxes). Also, we could state that there are typical students who are Italian:
⊤ ⊑ ∃U.T(Student ⊓ Italian), where U is the universal role (⊤ × ⊤ ⊑ U ).
Standard DL inferences hold for T(C) concepts and T(C) ⊑ D inclusions. For
instance, we can conclude that Mario is a typical student (by (g)) and young (by (b)).
However, by the properties of defeasible inclusions, Luigi, who is a typical Italian stu-
dent, and Paul, who is a typical young student, both inherit the property of typical stu-
dents of being math haters, respectively, by rational monotonicity (RM) and by cautious
monotonicity (CM). Instead, as Tom is a typical nerd student, and typical nerd student
are math lovers, this specific property of typical nerd students prevails over the less spe-
cific property of typical students of hating math. So we can consistently conclude that
Tom is a MathLover .
A normal form for SROEL(⊓, ×)R T knowledge bases can be defined. A KB in
SROEL(⊓, ×)R T is in normal form if it admits all the axioms of a SROEL(⊓, ×)
KB in normal form:
C(a) R(a, b) A⊑⊥ ⊤⊑C A ⊑ {c}
A⊑C A⊓B ⊑C ∃R.A ⊑ C A ⊑ ∃R.B
{a} ⊑ C ∃R.Self ⊑ C A ⊑ ∃R.Self
6 L. Giordano, D. Theseider Dupré
R⊑T R◦S ⊑T R⊓S ⊑ T A×B ⊑R R ⊑C×D
(where A, B, C, D ∈ NC , R, S, T ∈ NR and a, b, c ∈ NI ) and, in addition, it admits
axioms of the form: A ⊑ T (B) and T (B) ⊑ C with A, B, C ∈ NC . Extending the
results in [1] and in [32], it is easy to see that, given a SROEL(⊓, ×)R T KB, a seman-
tically equivalent KB in normal form (over an extended signature) can be computed in
linear time. In essence, for each concept T(C) occurring in the KB, we introduce two
new concept names, XC and YC . A new KB is obtained by replacing all the occur-
rences of T(C) with XC in all the inclusions and assertions, and adding the following
additional inclusion axioms:
XC ⊑ T(YC ), T(YC ) ⊑ XC , YC ⊑ C, C ⊑ YC
Then the new KB undergoes the normal form transformation for SROEL(⊓, ×) [32].
The resulting KB is linear in the size of the original one.
Example 2. Considering again the TBox in Example 1, inclusion (a) T(Italian) ⊑
∃hasHair .{Black } is transformed in the following set of inclusions:
(a1 ) XI ⊑ ∃hasHair .{Black }
(a2 ) XI ⊑ T(Italian)
(a3 ) T(Italian) ⊑ XI
Inclusion (d) T(Student ⊓ Nerd) ⊑ MathLover is mapped to the set of inclusions:
(d1 ) XSN ⊑ MathLover
(d2 ) XSN ⊑ T(YSN )
(d3 ) T(YSN ) ⊑ XSN
(d4 ) Student ⊓ Nerd ⊑ YSN
(d5 ) YSN ⊑ Student ⊓ Nerd
Then (a1 ) is transformed further (the normal form transformation for SROEL(⊓, ×))
into: (a′1 ) XI ⊑ ∃hasHair .B (a′′1 ) B ⊑ {Black}
All the other axioms in the TBox, apart from (b) and (c), have to be transformed
in normal form. Assertions are also subject to the normal form transformation. For
instance, T(Student ⊓ Nerd )(tom) becomes XSN (tom), where XSN is one of the
concept names introduced above.
3 Minimal entailment
In Example 1, we cannot conclude that all typical young Italians have black hair (and
that Luigi has black hair) using rational monotonicity, as we do not know whether there
is some typical Italian who is young. To supports such a stronger nonmonotonic infer-
ence, a minimal model semantics is needed to select those interpretations where indi-
viduals are as typical as possible. Among models of a KB, we select the minimal ones
according to the following preference relation ≺ over the set of ranked interpretations.
An interpretation M =h∆, <, Ii is preferred to M′ = h∆′ , <′ , I ′ i (M ≺ M′ ) if:
′
∆ = ∆′ ; C I = C I for all non-extended concepts C; for all x ∈ ∆, kM (x) ≤ kM′ (x),
and there exists y ∈ ∆ such that kM (y) < kM′ (y).
We can see that, in all the minimal models of the KB in Example 1 luigi is an
instance of the concept ∃hasHair .{Black } and the inclusion T(Young ⊓ Italian) ⊑
Reasoning in a Rational Extension of SROEL(⊓, ×) 7
∃hasHair .{Black } is satisfied, as nothing prevents a Young ⊓ Italian individual from
having rank 0.
In particular, we consider the notion of minimal canonical model defined in [27] to
capture rational closure of an ALC KB extended with typicality. The requirement of
a model to be canonical is used to guarantee that models contain enough individuals.
Given a KB K and a query F , let S be the set of all the (non-extended) concepts (and
subconcepts) occurring in K or F together with their complements (S is finite). In the
following, we will assume that all concepts occurring in the query F are included in K.
Definition 3 (Canonical models). A model M = h∆, <, Ii of K is canonical if, for
each set of SROEL(⊓, ×)R T concepts {C1 , C2 , . . . , Cn } ⊆ S consistent with K (i.e.,
s.t. K 6|=sroelrt C1 ⊓C2 ⊓. . .⊓Cn ⊑ ⊥), there exists (at least) a domain element x ∈ ∆
such that x ∈ (C1 ⊓ C2 ⊓ . . . ⊓ Cn )I .
Among canonical models, we select the minimal ones.
Definition 4. M is a minimal canonical model of K if it is a canonical model of K
and it is minimal with respect to the preference relation ≺.
Definition 5 (Minimal entailment). Given a query F , F is minimally entailed by K,
written K |=min F if, for all minimal canonical models M of K, M satisfies F .
We can show that the problem of instance checking in SROEL(⊓, ×)R T under
minimal entailment is CO NP-hard. The proof is based on a reduction from tautology
checking of propositional 3DNF formulae to instance checking in SROEL(⊓, ×)R T
and its structure has similarities with the proof of CO -NP-hardness for F L subsumption
in [2] (Chapter 3, Theorem 3.2). Given an alphabet of propositional variables L =
{p1 , . . . , pk }, let γ = G1 ∨ . . . ∨ Gn be a propositional formula where each disjunct
Gi = li1 ∧ li2 ∧ li3 (i = 1, . . . , n) is the conjunction of three literals and each literal
lij (j = 1, . . . , 3) is either a variable p ∈ L or its negation ¬p. The 3DNF tautology
problem, i.e. the problem of deciding whether γ is a tautology (in the propositional
calculus), is known to be CO NP-complete [17].
Theorem 1. Instance checking in SROEL(⊓, ×)R T under minimal entailment is CO NP-
hard.
Proof. (sketch) Given an alphabet of propositional variables L = {p1 , . . . , pk } and a
propositional formula in 3DNF γ = G1 ∨ . . . ∨ Gn as defined above, we define a KB
K = (TBox , RBox , ABox ) in SROEL(⊓, ×)R T as follows. We introduce in NC
two concept names Ph , P h for each variable ph ∈ L, a concept name Dγ associated
with the formula γ and a new concept name E. Let R ∈ NR be a role name and a ∈ NI
be an individual name. We define K as follows: RBox = {Ph × P h ⊑ R, h = 1 , ..., k },
ABox = {T(Ph ⊓ P h )(a), h = 1, ..., k} ∪ {T(E)(a)}, and TBox contains the follow-
ing inclusions:
(1) T(Ph ) ⊓ T(P h ) ⊑ ⊥,
(2) T(⊤) ⊓ ∃R.T(⊤) ⊑ ⊥
(3) T(E) ⊓ Ci1 ⊓ Ci2 ⊓ Ci3 ⊑ Dγ , for each Gi = li1 ∧ li2 ∧ li3
8 L. Giordano, D. Theseider Dupré
where h = 1, . . . , k and, for each i = 1, . . . , n and j ∈ {1, 2, 3}, Cij is defined as
follows:
T(Ph ) if lij = ph
Cij =
∃U.(T(⊤) ⊓ T(Ph )) if lij = ¬ph
Let us consider any model M= h∆, <, ·I i of K. Observe that, as aI ∈ Ph ⊓ P h , aI
cannot have rank 0, otherwise it would be both a typical Ph and a typical P h , falsifying
(1). By the role inclusions each Ph element is in relation R with any P h element. Also,
by (2), there cannot be a Ph element x and a P h element y both with rank 0, otherwise
x and y would be related by R and axiom (2) excludes that two T(⊤) elements are in
relation R. It is possible that, in a model of K, there are no Ph elements with rank 0
and no P h elements with rank 0. However, if we consider minimal canonical models of
K, there must be either a Ph element or a P h element with rank 0.
Remember that kM (C) is the rank of a concept C in a ranked model M. It can be
seen that, in all the minimal canonical models of K, for all h = 1, . . . , k, the following
conditions hold:
(i) either kM (Ph ) = 0 or kM (P h ) = 0;
(ii) kM (Ph ⊓ P h ) = 1 and kM (aI ) = 1.
As a consequence, aI is either a typical Ph element (when the rank of P h is 0) or a typ-
ical P h (when the rank of Ph is 0). So there are alternative minimal canonical models
in which, for each h, aI is either a T(Ph ), and in this case there exists a typical P h ele-
ment with rank 0; or a is a T(P h ), and in this case there exists a typical Ph element with
rank 0. Therefore, in any minimal canonical models M of K: either aI ∈ (T(Ph ))I
or a I ∈ (∃U .(T(⊤) ⊓ T(Ph )))I (but not both). Then for aI the two concepts in the
definition of Cij are disjoint and complementary and the following can be proved:
K |=min Dγ (a) if and only if γ is a tautology ⊓
⊔
It is an open issue whether a similar proof can be done also for simple knowledge
bases (i.e., for SROEL(⊓, ×)R T knowledge bases where the typicality operator only
occurs on the left hand side of concept inclusions T(C) ⊑ D). For simple KBs, it was
proved for ALC +TR [27] that all minimal canonical models of the KB assign the same
ranks to concepts, namely, the ranks determined by the rational closure construction.
This is clearly true, in particular, for the fragment of SROEL(⊓, ×)R T included in
the language of ALC plus typicality (which however, does not contain nominals, role
inclusions, and other constructs of SROEL(⊓, ×)).
Note that K, in the proof above, has alternative minimal canonical models with in-
comparable rank assignments. The existence of alternative minimal models for a KB
with free occurrences of typicality in the propositional case was observed in [9] for
Propositional Typicality logic (PTL). As an example of a KB in SROEL(⊓, ×)R T
with alternative minimal canonical models with incomparable rank assignments, con-
sider K ′ = (TBox ′ , RBox ′ , ABox ′ ), where RBox ′ = {P × P ⊑ R}, ABox ′ = {T(P
⊓P )(a)} and T Box contains the inclusion T(P )⊓T(P ) ⊑ ⊥ and T(⊤)⊓∃R.T(⊤) ⊑
⊥ (meaning that two elements of rank 0 cannot be related by R). Consider the follow-
ing two canonical models M1 , M2 of K ′ , over the domain ∆ = {x, y, z, w}, where,
Ii
for i = 1, 2, P Ii = {y, z}, P = {z, w}, RIi = {(z, z), (z, w), (y, z), (y, w)} and
Reasoning in a Rational Extension of SROEL(⊓, ×) 9
aIi = z. Furthermore, concerning the rankings, for M1 , kM1 (x) = kM1 (y) = 0,
kM1 (z) = kM1 (w) = 1; for M2 , kM2 (x) = kM2 (w) = 0, kM2 (z) = kM2 (y) = 1.
M1 and M2 are both minimal canonical models of K ′ and have incomparable rank-
ings, with P having rank 0 in M1 and rank 1 in M2 .
4 Deciding rational entailment in polynomial time
While instance checking in SROEL(⊓, ×)R T under minimal entailment is CO NP-
hard, in this section we prove that instance checking under rational entailment can be
decided in polynomial time for normalized KBs, by defining a translation of a normal-
ized KB into a set of Datalog rules, whose grounding is polynomial in the size of the
KB. In particular, we extend the Datalog materialization calculus for SROEL(⊓, ×),
proposed by Krötzsch [32], to deal with typicality concepts and with instance checking
under rational entailment in SROEL(⊓, ×)R T.
The calculus in [32] uses predicates inst (a, C ) (whose meaning includes: the in-
dividual a is an instance of concept name C, see [33] for details), triple(a, R, b) (a is
in relation R with b), self (a, R) (a is in relation R with itself). To map a SROEL(⊓,
×)R T KB to a Datalog program, we add predicates to represent that: an individual
a is a typical instance of a concept name (typ(a, C )); the ranks of two individuals a
and b are the same (sameRank (a, b)); the rank of a is less or equal than the one of b
(leqRank (a, b)).
Besides the constants for individuals in NI (which are assumed to be finitely many),
the calculus in [32] exploits auxiliary constants auxA⊑∃R.C (one for each inclusion of
the form A ⊑ ∃R.C ) to deal with existential restriction. We also need to introduce an
auxiliary constant auxC for any concept T(C) occurring in the KB or in the query,
used as a representative typical C, in case C is non-empty.
Given a normalized KB K = (TBox , RBox , ABox ) and query Q of the form C(a)
or T(C)(a), where C is a concept name in the normalized KB, the Datalog program
for instance checking in SROEL(⊓, ×)R T, i.e. for querying whetherK |=sroelrt Q, is
a program Π(K), the union of:
1. ΠK , the representation of K as a set of Datalog facts, based on the input translation
in [32];
2. ΠIR , the inference rules of the basic calculus in [32];
3. ΠRT , containing the additional rules for reasoning with typicality in
SROEL(⊓, ×)R T.
A query Q of the form T(C)(a), or C(a), is mapped to a goal GQ of the form
typ(a, C ), or inst (a, C ). Observe that restricting queries to concept names is not a
severe restriction as an arbitrary query C(b) can be replaced by a query A(b) with A
new concept name, by adding C ⊑ A to the TBox [1] and, of course, this inclusion is
normalized when normalizing TBox.
We define Π(K) in such a way that GQ is derivable in Datalog from Π(K) (written
Π(K) ⊢ GQ ) if and only if K |=sroelrt Q .
ΠK includes the result of the input translation in section 3 in [32] where nom(a),
cls(A), rol (R) are used for a ∈ NI , A ∈ NC , R ∈ NR , and, for example:
10 L. Giordano, D. Theseider Dupré
– subClass(a, C ), subClass(A, c), subClass(A, C ) are used for C(a), A ⊑ {c},
A ⊑ C;
– subEx (R, A, C ) is used for ∃R.A ⊑ C ;
and similar statements represent other axioms in the normalized KB.
The following is the additional mapping for the extended syntax of the
SROEL(⊓, ×)R T normal form (note that no mapping is needed for assertions T(C)(a),
as they do not occur in a normalized KB):
A ⊑ T(B ) 7→ supTyp(A, B )
T(B ) ⊑ C 7→ subTyp(B , C )
Also, we need to add top(⊤) to the input specification.
ΠIR contains all the inference rules from [32]1 :
(1) inst (x , x ) ← nom(x )
(2) self (x , v ) ← nom(x ), triple(x , v , x )
(3) inst (x , z ) ← top(z ), inst (x , z ′ )
(4) inst (x , y) ← bot (z ), inst (u, z ), inst (x , z ′ ), cls(y)
(5) inst (x , z ) ← subClass(y, z ), inst (x , y)
(6) inst (x , z ) ← subConj (y1 , y2 , z ), inst (x , y1 ), inst (x , y2 )
(7) inst (x , z ) ← subEx (v , y, z ), triple(x , v , x ′ ), inst (x ′ , y)
(8) inst (x , z ) ← subEx (v , y, z ), self (x , v ), inst (x , y)
(9) triple(x , v , x ′ ) ← supEx (y, v , z , x ′ ), inst (x , y)
(10) inst (x ′ , z ) ← supEx (y, v , z , x ′ ), inst (x , y)
(11) inst (x , z ) ← subSelf (v , z ), self (x , v )
(12) self (x , v ) ← supSelf (y, v ), inst (x , y)
(13) triple(x , w , x ′ ) ← subRole(v , w ), triple(x , v , x ′ )
(14) self (x , w ) ← subRole(v , w ), self (x , v )
(15) triple(x , w , x ′′ ) ← subRChain(u, v , w ), triple(x , u, x ′ ), triple(x ′ , v , x ′′ )
(16) triple(x , w , x ′ ) ← subRChain(u, v , w ), self (x , u), triple(x , v , x ′ )
(17) triple(x , w , x ′ ) ← subRChain(u, v , w ), triple(x , u, x ′ ), self (x ′ , v )
(18) triple(x , w , x ) ← subRChain(u, v , w ), self (x , u), self (x , v )
(19) triple(x , w , x ′ ) ← subRConj (v1 , v2 , w ), triple(x , v1 , x ′ ), triple(x , v2 , x ′ )
(20) self (x , w ) ← subRConj (v1 , v2 , w ), self (x , v1 ), self (x , v2 )
(21) triple(x , w , x ′ ) ← subProd (y1 , y2 , w ), inst (x , y1 ), inst (x ′ , y2 )
(22) self (x , w ) ← subProd (y1 , y2 , w ), inst (x , y1 ), inst (x , y2 )
(23) inst (x , z1 ) ← supProd (v , z1 , z2 ), triple(x , v , x ′ )
(24) inst (x , z1 ) ← supProd (v , z1 , z2 ), self (x , v )
(25) inst (x ′ , z2 ) ← supProd (v , z1 , z2 ), triple(x , v , x ′ )
(26) inst (x , z2 ) ← supProd (v , z1 , z2 ), self (x , v )
(27) inst (y, z ) ← inst (x , y), nom(y), inst (x , z )
(28) inst (x , z ) ← inst (x , y), nom(y), inst (y, z )
(29) triple(z , u, y) ← inst (x , y), nom(y), triple(z , u, x )
1
Here, u, v, x, y, z, w, possibly with suffixes, are variables.
Reasoning in a Rational Extension of SROEL(⊓, ×) 11
Note that “statements inst(a, b), with a and b individuals, encode equality of a and b”
[33].
ΠRT , i.e. the set of rules to deal with typicality, is as follows; it contains rules for
supTyp and subTyp axioms, and rules that deal with the rank of domain elements. In
the rules, x, y, z, A, B, C are all Datalog variables.
(SupTyp) typ(x , z ) ← supTyp(y, z ), inst (x , y)
(SubTyp) inst (x , z ) ← subTyp(y, z ), typ(x , y)
(Refl) inst (x , y) ← typ(x , y)
(A0 ) typ(auxC , C ) ← inst (x , C )
(A1 ) leqRank (x , y) ← typ(x , B ), inst (y, B )
(A2 ) sameRank (x , y) ← typ(x , A), typ(y, A)
(A3 ) typ(x , B ) ← sameRank (x , y), inst (x , B ), typ(y, B )
(A4 ) typ(x , B ) ← inst (x , A), supTyp(A, B )
(B1 ) sameRank (x , z ) ← sameRank (x , y), sameRank (y, z )
(B2 ) sameRank (x , y) ← sameRank (y, x )
(B3 ) sameRank (x , x ) ← inst (x , T )
(B4 ) leqRank (x , y) ← sameRank (y, x )
(B5 ) leqRank (x , z ) ← leqRank (x , y), leqRank (y, z )
(B6 ) sameRank (x , y) ← leqRank (x , y), leqRank (y, x )
(B7 ) sameRank (x , y) ← nom(y), inst (x , y)
Rule (Refl ) corresponds to the reflexivity property (see Section 2). Rules (A0 ) − (A4 )
encode properties of ranked models: if there is a C element, there must be a typical C
element (A0 ); a typical B element has a rank less or equal to the rank of any B element
(A1 ); two elements which are both typical A elements have the same rank (A2 ); if x is
a B element and has the same rank as a typical B element, x is also a typical B element
(A3 ); if x is an A element and all A’s are typical B’s, then x is a typical A (A4 ).
(B1 ) − (B7 ) define properties of rank order. In particular, by (B7 ), two constants that
correspond to the same domain element have the same rank.
The semantic properties of rational consequence relation introduced in Section 2
are enforced by the specification above. Consider, for instance, (CM ). Suppose that
subTyp(A, B ) and subTyp(A, C ) are in ΠK (as T(A) ⊑ B , T(A) ⊑ C are in K)
and that D is a concept name defined to be equivalent to A ⊓ B in K. Suppose that
typ(a, D ) holds. One can infer typ(a, A) and hence inst (a, C ), i.e., typical A ⊓ B’s
inherit from typical A’s the property of being C’s (the inference for P aul in Exam-
ple 1). In fact, typ(a, A) is inferred showing that a (who is a typical D and an A,
as it is a D) and auxA (who is a typical A, by (A1 ), and a D, since all the typical
A’s are also B’s and hence A ⊓ B’s) have the same rank. In fact, using(A1 ) twice,
one can conclude both leqRank (a, auxA ) and leqRank (auxA , a) so that, by (B6 ),
sameRank (a, auxA ). Then, by (A3 ), we infer typ(a, A). With rule (subTyp), from
typ(a, A) and subTyp(A, C ), we conclude inst (a, C ).
Reasoning in a similar way, one can see that also the properties (RM ) and (LLE )
are enforced by the rules above. In particular, for (RM), we can show that: from the fact
that there is a domain element a who is a T(A) and a C element (i.e. typ(a, A) and
inst (a, C ) hold), and from the fact that there is a b who is a typical A ⊓ C element
12 L. Giordano, D. Theseider Dupré
(i.e. that typ(b, D ) holds, for some concept D equivalent to A ⊓ C), we can conclude
that b is also a typical A element (i.e. typ(b, A) holds). Inference in SROEL(⊓, ×)
already takes care of the semantic properties of conjunctive consequences (And ) and
right weakening (RW ).
Theorem 2. For a SROEL(⊓, ×)R T KB in normal form K, and a query Q of the
form T(C)(a) or C(a), K |=sroelrt Q if and only if Π(K) ⊢ GQ .
Proof. (sketch) For completeness, we procede by contraposition, similarly to [33]. As-
sume that inst (a, C ) (respectively, typ(a, C )) is not derivable from Π(K). Let J be
the minimal Herbrand model of the Datalog program Π(K); then inst (a, C ) 6∈ J (resp.
typ(a, C ) 6∈ J). From J we build a ranked model M for K such that C(a) (respec-
tively, T(C)(a)) is not satisfied in M. As in [33], we can build the domain ∆ of M
from the set Const including all the name constants c ∈ NI occurring in the ASP pro-
gram Π(K) as well as all the auxiliary constants, then defining an equivalence relation
≈ over constants and the domain ∆ including the equivalence classes and, possibly,
additional domain elements for auxiliary constants, as in the proof of Lemma 3 in [33].
J contains all the details about the interpretation of concepts and roles, from which an
interpretation M can be defined (for instance, for c ∈ NI , [c] ∈ AI iff inst (c, A) ∈ J ,
and similarly for other domain elements and for roles). However, predicates sameRank
and leqRank only provide partial information about the ranks of the domain elements.
We define a relation < over constants, letting x < y iff there is a concept name C, s.t.
typ(x , C ), inst (y, C ) ∈ J and typ(y, C ) 6∈ J and we show that its transitive closure is
a strict partial order. Also, we show that < is compatible with the sameRank predicate
in J and with the ≈ equivalence relation between constants so that < can be extended
to a modular partial order over the domain ∆. First, a partial ordering over elements in
∆ is defined, letting [c] < [d] iff c < d (where the definition does not depend on the
choice of the representative element in a class) and similarly for domain elements cor-
responding to auxiliary constants. Then the elements in ∆ are partitioned into the sets
Rank0 , . . . , Rankn , where Ranki (the set of domain elements of rank i) is defined by
induction on i, as follows: Rank0 contains all the elements x ∈ ∆ such that there is no
y ∈ ∆ with y < x; Ranki contains all the elements x ∈ ∆ − (Rank0 ∪ . . . ∪ Ranki−1 )
such that there is no y ∈ ∆ − (Rank0 ∪ . . . ∪ Ranki−1 ) with y < x. We let n be the
least integer such that ∆ − (Rank0 ∪ . . . ∪ Rankn ) = ∅. It can be shown that M is a
model of K and it does not satisfy C(a) (respectively, T(C)(a)).
Proving the soundness of the Datalog encoding, requires showing that, if Π(K) ⊢
GQ , for a query Q of the form T(C)(a) or C(a), then, Q is a logical consequence of
K. The proof is similar to the proof of Lemma 1 in [33]. First we associate to each
constant c of the Datalog program Π(K) a concept expression κ(c) a follows:
if c ∈ NI then κ(c) = {c};
if c = auxα , for α = A ⊑ ∃R.B, then κ(c) = B ⊓ ∃R− .A;
if c = auxC , then κ(c) = T(C).
The following statements:
- if Π(K) ⊢ inst (c, A), for A ∈ NC , then K |=sroelrt κ(c) ⊑ A;
- if Π(K) ⊢ inst (c, d ), for d ∈ NI , then K |=sroelrt κ(c) ⊑ {d};
- if Π(K) ⊢ typ(a, A), then K |=sroelrt κ(c) ⊑ T(A);
Reasoning in a Rational Extension of SROEL(⊓, ×) 13
- if Π(K) ⊢ triple(c, R, d ), then K |=sroelrt κ(c) ⊑ ∃R.κ(d);
- if Π(K) ⊢ self (c, R), for A ∈ NC , then K |=sroelrt κ(c) ⊑ ∃R.Self ;
- if Π(K) ⊢ sameRank (c, d ) then for all models M of K, kM (cI ) = kM (dI );
- if Π(K) ⊢ leqRank (c, d ) then, for all models M of K, kM (cI ) ≤ kM (dI ).
can be proved by induction on the height of the derivation tree of each atom from the
program Π(K). ⊓
⊔
Π(K) contains a polynomial number of rules and exploits a polynomial number of
concepts in the size of K, hence instance checking in SROEL(⊓, ×)R T can be de-
cided in polynomial time using the calculus in Datalog. The encoding can be processed,
e.g., in an ASP solver such as Clingo or DLV (with the proper capitalization of vari-
ables); computation of the (unique, in this case) answer set takes a negligible time for
KBs with a hundred assertions (half of them with T).
Exploiting the approach presented in [32], a version of the Datalog specification
where predicates inst , typ, triple and self have an additional parameter (and is there-
fore less efficient than the previous one, although polynomial) can be used to check
subsumption for SROEL(⊓, ×)R T.
For simple SROEL(⊓, ×)R T knowledge bases, i.e., for KBs where the typical-
ity operator only occurs on the left hand side of inclusions, the materialization calcu-
lus for subsumption can be used to construct the rational closure of TBox, adopting
the construction in [27] (Definitions 21 and 23). Such construction can be rephrased
replacing the exceptionality check in ALC + TR with the exceptionality check in
SROEL(⊓, ×)R T and the entailment in ALC + TR with the entailment in SROEL
(⊓, ×)R T. In particular, in SROEL(⊓, ×)R T one can define, for a simple KB K, the
notion of exceptionality as follows: C is exceptional wrt K iff K |=sroelrt T(⊤)⊓C ⊑
⊥. This subsumption is not in the language of normalized KBs, but it can be replaced
by the subsumption A ⊑ ⊥, adding T(⊤) ⊑ X and X ⊓ C ⊑ A to K. The construction
requires a quadratic number of subsumption checks (in the number of typicality inclu-
sions in the KB, and, hence, in the size of the KB), each one requiring polynomial time,
using the above mentioned polynomial calculus for subsumption.
The correspondence between the rational closure construction and the canonical
minimal model semantics in [27], does not extend to all the constructs in SROEL(⊓,
×)R T and, specifically, the canonical model semantics is not adequate for dealing with
nominals. In particular, there are knowledge bases with no canonical model and knowl-
edge bases with more than one minimal canonical model (as the knowledge base K ′
at the end of Section 3). However, in many cases, the rational closure of a KB with no
canonical model is still meaningful. What has to be devised is, on the one hand, a less
restrictive semantic requirement to give meaning also to KBs containing nominals; on
the other hand, a syntactic condition to identify the KBs for which the rational closure is
by itself meaningful and corresponds to the semantics. In this paper, we do not address
these issues and we leave them for further work.
5 Related Work
Among the recent nonmonotonic extensions of DLs are the formalisms for combining
DLs with logic programming rules, such as for instance, [16, 15], [35], [30] and Dat-
14 L. Giordano, D. Theseider Dupré
alog +/- [28]. DL-programs in [16, 15] support a loose coupling of DL ontologies and
rule-based reasoning under the answer set semantics and under the well-founded se-
mantics, where rules may contain DL-atoms in their bodies, corresponding to queries
to a DL ontology, which can be modified according to an input list of updates. In [30]
a general DL language is introduced, which extends SROIQ with nominal schemas
and epistemic operators according to the MKNF semantics [35], which encompasses
some of the most prominent nonmonotonic rule languages, including ASP. In [5] a non
monotonic extension of DLs is proposed based on a notion of overriding, supporting
normality concepts and enjoying good computational properties. In particular, it pre-
serves the tractability of low complexity DLs, including EL++ and DL-lite. In [10],
the CKR framework is presented, which is based on SROIQ-RL, allows for defeasible
axioms with local exceptions and a translation to Datalog with negation. It is shown
that instance checking over a CKR reduces to (cautious) inference under the answer
sets semantics.
Preferential extensions of low complexity DLs in the EL and DL-lite families have
been studied In [24, 25], based on preferential interpretations which are not required to
be modular, and tableaux-based proof methods have been developed for them. In [25],
for a preferential extension of EL⊥ based on a minimal model semantics different from
the one in this paper, it is shown that minimal entailment is E XP T IME-hard already for
simple KBs, similarly to what happens for circumscriptive KBs [6].
6 Conclusions
In this paper we defined a rational extension SROEL(⊓, ×)R T of the low complex-
ity description logic SROEL(⊓, ×), which underlies the OWL EL ontology language,
introducing a typicality operator. For general KBs, we have shown that minimal entail-
ment in SROEL(⊓, ×)R T is CO NP-hard. When free occurrences of typicality con-
cepts in concept inclusions are allowed, alternative minimal models may exist with
different rank assignments to concepts. In [9] this phenomenon has been analyzed in
the context of PTL, considering alternative preference relations over ranked interpreta-
tions which coincide over simple KBs but, for general ones, define different notions of
entailment satisfying alternative and possibly incompatible postulates.
Building on the materialization calculus for SROEL(⊓, ×) in Datalog presented
in [32], a calculus for instance checking and subsumption under rational entailment is
defined, showing that these problems can be decided in polynomial time.
This result also provides a polynomial upper bound for the construction of the ra-
tional closure of a knowledge base in SROEL(⊓, ×)R T. Although for the fragment of
SROEL(⊓, ×)R T which is also included in the language of ALC + TR in [27] the ra-
tional closure is semantically characterized by the minimal canonical models of the KB,
a general semantic characterization of the rational closure for the logic SROEL(⊓, ×)
is still missing.
Future work may also include optimizations, based on modularity as in [7], of the
calculus for rational entailment, and the development of rule based inference meth-
ods for SROEL(⊓, ×)R T minimal entailment based on model generation in ASP. An
upper bound on the complexity of minimal entailment for general KBs has to be es-
Reasoning in a Rational Extension of SROEL(⊓, ×) 15
tablished. A further issue to understand is whether a materialization calculus can be
defined also for the preferential extensions of DLs in the EL family in [24, 25], whose
interpretations are not required to be modular.
Apart from providing a complexity upper bound, the Datalog encoding presented
in this paper is intended to provide a way to integrate the use of SROEL(⊓, ×) KBs
under rational entailment with other kinds of reasoning that can be performed in ASP,
and, by extending the encoding to deal with alternative models of the KB, also to allow
the experimentation of alternative notions of minimal entailment, as advocated in [9].
The approach can be possibly integrated with systems like DReW [37], that already
exploits the mapping by Krötzsch for OWL 2 EL.
Acknowledgement. This research has been supported by INDAM - GNCS Project
2016 Ragionamento Defeasible nelle Logiche Descrittive.
References
1. F. Baader, S. Brandt, and C. Lutz. Pushing the EL envelope. In Proc IJCAI 2005, pages
364–369, 2005.
2. F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors.
The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge
University Press, 2003.
3. F. Baader and B. Hollunder. Embedding defaults into terminological knowledge representa-
tion formalisms. In Proceedings of the 3rd International Conference on Principles of Knowl-
edge Representation and Reasoning (KR’92). Cambridge, MA, October 25-29, 1992., pages
306–317, 1992.
4. F. Baader and B. Hollunder. Priorities on defaults with prerequisites, and their application in
treating specificity in terminological default logic. J. of Automated Reasoning, 15(1):41–68,
1995.
5. P. A. Bonatti, M. Faella, I. Petrova, and L. Sauro. A new semantics for overriding in descrip-
tion logics. Artif. Intell., 222:1–48, 2015.
6. P. A. Bonatti, M. Faella, and L. Sauro. Defeasible inclusions in low-complexity dls. J. Artif.
Intell. Res. (JAIR), 42:719–764, 2011.
7. P. A. Bonatti, I. M. Petrova, and L. Sauro. Optimizing the computation of overriding. In
Proc. ISWC 2015, pages 356–372, 2015.
8. Piero A. Bonatti, Carsten Lutz, and Frank Wolter. The Complexity of Circumscription in
DLs. J. of Artificial Intelligence Research, 35:717–773, 2009.
9. R. Booth, G. Casini, T. Meyer, and I. J. Varzinczak. On the entailment problem for a logic
of typicality. In Proc. IJCAI 2015, pages 2805–2811, 2015.
10. L. Bozzato, T. Eiter, and L. Serafini. Contextualized knowledge repositories with justifiable
exceptions. In DL 2014, pages 112–123, 2014.
11. K. Britz, J. Heidema, and T. Meyer. Semantic preferential subsumption. In G. Brewka and
J. Lang, editors, Proc. KR 2008, pages 476–484, 2008.
12. G. Casini, T. Meyer, I. J. Varzinczak, , and K. Moodley. Nonmonotonic Reasoning in De-
scription Logics: Rational Closure for the ABox. In Proc. DL 2013, pages 600–615, 2013.
13. G. Casini and U. Straccia. Rational Closure for Defeasible Description Logics. In Proc.
JELIA 2010, LNAI 6341, pages 77–90. Springer, 2010.
14. F. M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation
as failure. ACM Transactions on Computational Logic (ToCL), 3(2):177–225, 2002.
16 L. Giordano, D. Theseider Dupré
15. T. Eiter, G. Ianni, T. Lukasiewicz, and R. Schindlauer. Well-founded semantics for descrip-
tion logic programs in the semantic web. ACM Trans. Comput. Log., 12(2):11, 2011.
16. T. Eiter, G. Ianni, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining answer set
programming with description logics for the semantic web. Artif. Intell., 172(12-13):1495–
1539, 2008.
17. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman, 1979.
18. M. Gelfond. Handbook of Knowledge Representation, chapter 7, Answer Sets. Elsevier,
2007.
19. M. Gelfond and N. Leone. Logic programming and knowledge representation - the A-Prolog
perspective. Artif. Intell., 138(1-2):3–38, 2002.
20. L. Giordano and Theseider Dupré D. Reasoning in a Rational Extension of SROEL. In
DL2016, volume 1577 of CEUR Workshop Proceedings, 2016.
21. L. Giordano and V. Gliozzi. Encoding a preferential extension of the description logic SROIQ
into SROIQ. In Proc. ISMIS 2015, volume 9384 of LNCS, pages 248–258. Springer, 2015.
22. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Preferential Description Logics. In
Proceedings of LPAR 2007, volume 4790 of LNAI, pages 257–272. Springer-Verlag, 2007.
23. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. ALC+T: a preferential extension of
Description Logics. Fundamenta Informaticae, 96:1–32, 2009.
24. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Prototypical reasoning with low
complexity description logics: Preliminary results. In Proc. LPNMR 2009, pages 430–436,
2009.
25. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Reasoning about typicality in low
complexity DLs: the logics EL⊥ Tmin and DL-Litec Tmin . In Toby Walsh, editor, Proceed-
ings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pages
894–899, Barcelona, Spain, July 2011. Morgan Kaufmann.
26. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. A NonMonotonic Description Logic
for Reasoning About Typicality. Artificial Intelligence, 195:165–202, 2013.
27. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Semantic characterization of rational
closure: From propositional logic to description logics. Artif. Intell., 226:1–33, 2015.
28. G. Gottlob, A. Hernich, C. Kupke, and T. Lukasiewicz. Stable model semantics for guarded
existential rules and description logics. In Proc. KR 2014, 2014.
29. P. Ke and U. Sattler. Next Steps for Description Logics of Minimal Knowledge and Negation
as Failure. In Proc. DL 2008, volume 353 of CEUR Workshop Proceedings, 2008.
30. M. Knorr, P. Hitzler, and F. Maier. Reconciling OWL and non-monotonic rules for the
semantic web. In ECAI 2012, page 474479, 2012.
31. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and
cumulative logics. Artif. Intell., 44(1-2):167–207, 1990.
32. M. Krötzsch. Efficient inferencing for OWL EL. In Proc. JELIA 2010, pages 234–246, 2010.
33. M. Krötzsch. Efficient inferencing for the description logic underlying OWL EL. Tech. Rep.
3005, Institute AIFB, Karlsruhe Institute of Technology, 2010.
34. Daniel Lehmann and Menachem Magidor. What does a conditional knowledge base entail?
Artificial Intelligence, 55(1):1–60, 1992.
35. Boris Motik and Riccardo Rosati. Reconciling Description Logics and rules. J. ACM, 57(5),
2010.
36. U. Straccia. Default inheritance reasoning in hybrid KL-ONE-style logics. In Proc. IJCAI
1993, pages 676–681, 1993.
37. G. Xiao, T. Eiter, and S. Heymans. The DReW system for nonmonotonic dl-programs. In
Proc. CSWS 2012, pages 383–390, 2012.