Defeasible description logics (DDLs) support nonmonotonic reasoning by admitting defeasible concept inclusions in the knowledge base. Early reasoning methods for subsumption did not always use defeasible information for objects in the scope of nested quantifiers and thus neglected un-defeated information. The reasoning approach employing typicality models for the DDL EL⊥ overcomes this efect for existentially quantified objects. In this extended abstract we report on how to lift typicality model-based reasoning to the DDL ELI⊥, which extends EL⊥ with inverse roles. These can capture a form of universal quantification and extend expressivity of the DDL substantially. Reasoning in DDLs often employs rational closure according to the propositional KLM postulates. We can show that the proposed subsumption algorithm yields more entailments than rational propositional entailment.
Description logics (DLs) are knowledge representation relation. For certain applications monotone reasoning
formalisms that are designed to model terminological can be a short-coming and variants of DLs with
nonknowledge. Important notions from an application do- monotonic reasoning have been investigated by the
remain are modeled by concepts, which are essentially search community. A popular nonmonotonic variant are
unary first-order logic predicates. Each DL ofers a set of defeasible description logics (DDLs) which can express
concept constructors which can be used to build complex knowledge that holds until it is defeated by contradictory
concepts. The so-called roles correspond to binary rela- information. DDLs can express what properties typical
tions and can be used in concept constructors to relate members of a concept fulfill by the use of defeasible
conmembers of one concept to members of another. The use cept inclusions (DCIs) . A finite set of GCIS is a DBox D.
of roles and the quantification over the role-successors is A defeasible knowledge base (DKB) is a pair of a TBox and
what sets DLs apart from propositional logic. Concepts a DBox: K = (T , D).
can be related to each other by so-called general concept There are several proposals for semantics of defeasible
inclusions (GCIs), which state material implications for a DLs in the literature, such as [
Reasoning in description logics is usually the classical, other well-investigated approach is supply the semantics
monotone first-order reasoning. Two prominent reason- by materialization-based reasoning, where essentially the
ing problems are satisfiability of a concept w.r.t. an ontol- information from the DCIs is used in conjunction with
ogy and to decide subsumption for two given concepts the (potential) subsumee. This approach has the severe
w.r.t. an ontology. The latter is to test whether mem- short-coming of quantification neglect which means that
bership to the first concept implies membership to the defeasible information is not used for all the elements
second w.r.t. to the GCIs in T and is a classical entailment in the relational neighborhood of the subsumee. Thus
even un-defeated defeasible information can be omitted
NMR’22: 20th International Workshop on Non-Monotonic Reasoning, when performing reasoning over existentially quantified
August 07-09, 2022, Haifa, Israel objects—as it was observed in [
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License supraclassical inference relation. The classical DL EL⊥
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) provides conjunction and a form of existential
quantification called existential restrictions as concept constructors. Horn rules and Horn-ALC enjoys the canonical model
It can also state disjointness of concepts by the use of ⊥. property. To lift the method for EL⊥ to Horn-ALC two
EL⊥ has the canonical model property, i.e. there always extensions of the logic need to be addressed:
exists a model that can be embedded into all other
models. Thus testing whether α is entailed (i.e. holds in all • the more general form of negation and
models) can be done by computing the canonical model • forall quantification
and test whether α is satisfied in it. Reasoning in EL⊥
can be done in polynomial time [
To compute the canonical model in classical EL⊥, the tends EL⊥ by inverse roles which, in turn, can express
ontology is normalized such that complex concepts get value restrictions as consequences.
assigned a name. The domain of the canonical model con- The goal of this paper is to develop a characterization
sists of a representative for each of the named concepts. of defeasible entailment (and thus of defeasible
subsumpThe canonical models are a main building block of the tion) that alleviates quantification neglect and provides
typicality model used for to characterize the semantics reasoning of rational strength. To that end we proceed
of defeasible reasoning in EL⊥. as it was done in [
Typicality interpretations used for defeasible reason- acterization of entailment under rational strength and ing have 2-dimensional domains. One dimension is the propositional coverage. From this we develop a charrepresentative domain, which coincides with the domain acterization of entailment under rational strength and of the classical canonical model. The other dimension is nested coverage. determined by which subsets of the DBox D are “applied” to the elements. Each element of the typicality domain Entailment under rational strength and proposifor EL⊥ is a pair of a concept name and a subset of D. tional coverage in ELI ⊥. The first step to lift the
Now, the use of diferent collections of subsets from technique from [
Reasoning of propositional strength is mainly of inter- the coverage of reasoning. In case of propositional covest to us to be able to compare the resulting inference erage, we extend the minimal typicality models for EL⊥ relation to materialization-based reasoning. Reasoning to the use of inverse roles. under nested coverage results in an inference relation In minimal typicality models, the root element belongthat does not cause quantification neglect. ing to a named concept can have any degree of typicality admitted by the domain, i.e. it can satisfy any subset of The results presented in this extended abstract are DCIs available in the (second dimension of the) typicality initial steps on a longer research path. We want to inves- domain. The elements that are in the relational neighbortigate defeasible reasoning by means of typicality models hood of this root element, however, do not need to satisfy for defeasible Horn-ALC. This DDL is fairly expressive, any of the defeasible information. Therefore every role as (non-Horn) ALC is propositionally complete and ad- successor necessitated by existential restrictions for roles mits the use of both quantifiers. For all quantification or their inverse, are elements from the typicality domain, can be captured by the concept constructor called value where the second component is empty, i.e. where no DCI restriction. Horn-ALC restricts ALC to GCIs that are needs to be satisfied.
We show that defeasible subsumption w.r.t. a ELI ⊥ and that does not omit defeasible information unless a DKB and under rational strength and propositional cov- contradiction is encountered. erage can be decided by testing satisfaction of it in the rational minimal typicality model alone.
Entailment under rational strength and nested cov- ity domain—the full lattice P (D) instead of the
exceperage in ELI ⊥. The characterization of nested ratio- tionality chain—is enough to for this or whether new
nal reasoning for EL⊥ is achieved by means of maximal techniques in comparison to [
Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001 and also by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) and by the AI competence center ScaDS.AI Dresden/Leipzig. 1. identify an edge in the active set of models that can be upgraded to a more typical successor or predecessor and upgrade that edge
only the ones with elements that are maximally typical are kept. From this set the maximal typicality model is obtained as the one model capturing the information common to all models in the set.
The major technical challenge for defining an upgrade method for ELI ⊥ is that here the element that causes an edge in the model and the role predecessor of that edge need no longer coincide as it is the case in EL⊥. This required a much more elaborate technique for upgrading the models.
Our main result is that defeasible subsumption w.r.t. a ELI ⊥ DKB and under rational strength and nested coverage can be decided by testing satisfaction of it in the rational maximal typicality model alone. This establishes the computation of rational maximal typicality models as the main step in the decision procedure for entailment (and subsumption) for ELI ⊥ that does not commit quantification neglect.
We also investigate the relationship between the materialization-based semantics and the one given by nested rational reasoning realized by maximal typicality models. We show that the latter semantics indeed yields consequences that are a superset of the consequences obtained by the materialization-based semantics.
By these results we have provided a method to decide entailment in DDLs that admit the use of both quantifiers