In this extended abstract we report on the results from our paper [1]. Defeasible 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), allowing 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 materializationbased 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 information. Materialisation-based reasoning, however, disregards defeasible information for quantified concepts. In our paper, we resolve this issue for rational and relevant 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 closures. 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) nature or properly nested (nest), i.e., regarding quantified concepts. E.g. relevant nested entailment for a DKB: K j=(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).
A B
D A; X B; Y ; A B a Propositional Rational
Relevant in EXP
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 considered 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 relationships 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 (9r:B)(a)). Using minimal typicality 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).