=Paper=
{{Paper
|id=Vol-2211/paper-47
|storemode=property
|title=Computing Standard Inferences under Rational and Relevant Semantics in Defeasible
EL_bot
|pdfUrl=https://ceur-ws.org/Vol-2211/paper-47.pdf
|volume=Vol-2211
|authors=Maximilian Pensel,Anni-Yasmin Turhan
|dblpUrl=https://dblp.org/rec/conf/dlog/PenselT18
}}
==Computing Standard Inferences under Rational and Relevant Semantics in Defeasible
EL_bot==
https://ceur-ws.org/Vol-2211/paper-47.pdf
Computing Standard Inferences under Rational
and Relevant Semantics in defeasible EL⊥
Maximilian Pensel∗ and Anni-Yasmin Turhan
Institute for Theoretical Computer Science, TU Dresden
first-name.last-name @tu-dresden.de
In this extended abstract we report on the results from our paper [1]. De-
feasible DLs (DDLs) provide defeasible concept inclusions (DCIs), which are
statements of the form C @ ∼ D. DCIs should be satisfied for elements of the
interpretation domain as long as no inconsistencies arise, otherwise, DCIs are
defeated for some elements. DCIs are collected in the DBox (denoted D), allow-
ing for defeasible knowledge bases (DKB K = (A, T , D)).
A prominent approach by Casini et al., to compute the specific entailment
relations rational closure and the strictly stronger lexicographic and relevant
closure in defeasible ALC, is materialization. In a nutshell, the materialization-
based approach adds consistent material implications (¬AtX) of DCIs (A @ ∼ X)
as conjuncts. For instance, the left-hand side of a subsumption query may be
augmented this way in order obtain consequences including defeasible informa-
tion. Materialisation-based reasoning, however, disregards defeasible information
for quantified concepts. In our paper, we resolve this issue for rational and rele-
vant closure for TBox and for ABox reasoning. As a side result we showed that
materialisation-based reasoning (using all boolean connectives) over EL⊥ DKBs
can be reduced to classical reasoning in EL⊥ and thus, remains polynomial. The
biggest part of our paper studies TBox and ABox reasoning under different clo-
sures. To this end, we characterise the investigated semantics by two parameters:
(1) the strength of the semantics is either rational (rat) or relevant (rel) and (2)
the coverage is either based on materialisation (mat), of propositional (prop) na-
ture or properly nested (nest), i.e., regarding quantified concepts. E.g. relevant
nested entailment for a DKB: K |=(rel,nest) C @ ∼ D.
Typicality Models. Our approach is to extend classical canonical models for EL⊥
knowledge bases. The new kind of model consists of representatives for concepts
and individuals (as usual), but contains also copies of concept representatives
that have higher typicality, i.e., these copies do satisfy differently large subsets of
the DBox. A domain extending the domain of a classical canonical model in this
way, is called a typicality domain (TD). Intuitively, the more DCIs an element
in a TD satisfies, the more typical this element is considered. Entailments are
determined from the canonical model, i.e., by examining what holds for the
most typical representative of the query concept in a set of models over a fixed
TD. Incidentally, what elements are included in the domain, and which element
is chosen (as most typical) for deciding entailments, determines the strength
of our semantics, whereas the set of models considered to decide entailments,
∗
Supported by DFG in the Research Training Group QuantLA (GRK 1763).
D ∅
A, X A Rational Relevant
A
a Propositional P–compl. in EXP
B Nested co-NP–compl. in co-NEXP
B, Y B
Fig. 1: Example rational typicality model (A @ ∼ X, B @ ∼ Y ∈ D) (left) with upgrades
(dashed), supporting K |=(rat,nest) A @
∼ ∃r.X and K |=(rat,nest)
(∃r.Y )(a); Complexity
results for defeasible subsumption and instance checking under the 4 semantics (right).
determines the coverage of our semantics. For rational (relevant) strength, the
typicality domain is of polynomial (exponential) size in the size of the DKB. To
obtain propositional coverage, all models over the rational (relevant) domain are
considered. It turns out there is a canonical typicality model for all typicality
models over the same TD. We call it the minimal typicality model, since the
range of all roles contains only elements of minimal typicality (not satisfying
any DCIs). We showed consequences based on the minimal typicality model
(rat/rel, prop) to coincide with materialisation-based consequences (rat/rel,
mat). In order to obtain consequences using defeasible information for nested
concepts, we define an iterative procedure upgrading the typicality of role edges,
i.e. creating new edges with more typical elements in the range, unless this
renders the interpretation inconsistent with the DKB. This typicality upgrade
procedure results in a fixpoint, providing a set of maximal typicality models with
distinct sets of upgraded edges. To obtain consequences of nested coverage, i.e.,
to derive defeasible information for role-successors, all maximal typicality models
are considered (cf. Fig. 1). Regarding the different coverage of the semantics, we
show that nest yields more consequences than prop.
Defeasible Instance Checking. Instance checking in DDLs has also been consid-
ered by Casini et al. using materialisation for rational closure. We adopt their
technique of completing the ABox, i.e. adding material implication assertions
for individuals. We also devise the first algorithm for deciding instance relation-
ships under relevant closure. Similar to the classical construction of a canonical
model over an ABox and a TBox, the canonical model of this completed ABox
is connected to typicality interpretations with role edges pointing to anonymous
individuals, i.e. concept representatives (e.g. for (∃r.B)(a)). Using minimal typi-
cality models and the same upgrade procedure as before, we define the reasoning
service of defeasible instance checking for all four of the considered semantics.
Again, we show that the consequences obtained by (rat, prop) coincide with
those from (rat, mat) and that nest yields more consequences than prop.
Complexity. Finally, we investigate complexity of deciding subsumption and
instance checking under all 4 of the presented semantics with the result of a
strict increase of complexity for nested coverage (cf. Fig. 1).
References
1. Pensel, M., and Turhan, A.-Y. Reasoning in the defeasible description logic
EL⊥ —computing standard inferences under rational and relevant semantics. Inter-
national Journal of Approximate Reasoning (IJAR) 103 (2018), 28–70.