Reasoning with rules that allow for exceptions has been a longstanding challenge in knowledge representation. The KLM paradigm has been successful for defeasible reasoning in propositional logics, but its application to Description Logics (DLs) has been challenging. Many approaches to terminological reasoning with defeasible inclusions have been proposed, but reasoning about ABoxes is still largely unexplored. In this paper, we consider defeasible inclusions in the expressive DL ℒℐ with closed predicates, but restrict the inclusions in a way that circumvents some of the challenges faced by related approaches. We also consider the data complexity of defeasible reasoning, which, to our knowledge, had not yet been analysed. Unfortunately, our approach is hard for the second level of the polynomial hierarchy, but we identify a restricted fragment that enables tractable reasoning.
Defeasible reasoning, that is, reasoning with rules that allow for exceptions, has been a longstanding
challenge in knowledge representation. The KLM paradigm for defeasible reasoning [
In our recent paper [13], we consider the expressive DL ℒℐ with closed predicates, which already
allows some simple non-monotonic reasoning and which generalizes nominals [14, 15]; this is one
of the most expressive DLs that can be decided in ExpTime. We add defeasible inclusions to ℒℐ
knowledge bases and give them an exceptionality based semantics in the style of Rational Closure [16]
and the equivalent system Z [
Existing defeasible semantics for DLs based on rational closure neglect all defeasible information for the unnamed objects implied by the existential axioms, sometimes leading to counterintuitive inferences. To our knowledge, the only adequate solution so far is limited to the very inexpressive ℰ ℒ. Our approach fully circumvents the issue of typicality of anonymous objects: since defeasible inferences do not allow inferring new facts about unnamed objects, there is no need to decide how to apply the defeasible inclusions to them. While we do not solve the problem, we do avoid its nontransparent and sometimes counterintuitive aspects. We believe this is a reasonable compromise. Unnamed objects in an interpretation intuitively describe structures that should be as general as possible, and we have not seen many realistic examples that really call for defeasible inferences over anonymous objects.
In this section, we formally define our DL knowledge bases with defeasible inclusions which are concept inclusions that hold for typical, but not necessarily all elements of the domain. Unlike a ‘strict’ concept inclusion ⊑ , a defeasible inclusion ⊏ may have exceptions, i.e., in a model ℐ of ⊏ some elements of ℐ may not be in ℐ ; these ar∼e considered exceptional. ∼
Our key design choice is to make sure that defeasible inclusions apply only to objects that are explicitly named in the knowledge base, and therefore anonymous objects whose existence may be implied by concept inclusions can be treated as non-exceptional. This will be ensured by means of rooted concepts, which are concept expressions that are ‘guarded’ by closed predicates. For closed predicates and in NCc ⊆ N C and NRc ⊆ N R, respectively, the term ℐ |= means that ℐ , ℐ only contain an individual if explicitly mentioned. In our formalisms, defeasible inclusions are restricted to have rooted concepts in the antecedents.
Definition 1. A concept is rooted if one the following is satisfied: 1. ∈ NCc , 2. of the form 1 ⊓ 2 and at least one of 1, 2 is rooted, 3. of the form 1 ⊔ 2 and both 1, 2 are rooted, or 4. of the form ∃. with ∈ NRc or − ∈ NRc .
A defeasible concept inclusion (DCI) is an expression ∼⊏ , where , are concepts and is rooted. A knowledge base (KB) is a tuple = ( , , ), where is a TBox, is a set of defeasible inclusions, and is an ABox.
Example 1 (adapted from [
We will now define the semantics of a KB = ( , , ) as the interpretations ℐ where ℐ |= ,
ℐ |= , and ℐ complies with the defeasible inclusions in as much as possible. To properly define
the latter, following the definition of system Z, the first step is to define the notion of tolerance, which
generalizes a similar concept for propositional rules [
Definition 2. We write ℐ, |= ∼⊏ , if ∈ (¬ ⊔ )ℐ . For a set of defeasible inclusions, we write ℐ, |= , if ℐ, |= ∼⊏ for all ∼⊏ ∈ . A defeasible inclusion ∼⊏ is tolerated by a set of defeasible inclusions and a TBox , if there is an interpretation ℐ and an object ∈ ∆ ℐ such that ℐ |= , ∈ ( ⊓ )ℐ and ℐ, |= .
For a set of defeasible inclusions and a TBox construct the following sequence: (i) Let 0 contain all ∼⊏ ∈ such that ∼⊏ is tolerated by and . (ii) Foℓ′r =allℓ ∖>(0,0le∪t · ·· ∪ℓ contℓa−1in)a.ll ∼⊏ ∈ ℓ′ such that ∼⊏ is tolerated by ℓ′ and , where Let be the smallest integer such that +1 = ∅. Then (0, . . . , , ∞) with ∞ = ′+1 is called the tolerance partition of (w.r.t. ).
Let ℐ be an interpretation such that ℐ |= ∞ ∪ and assume ∈ ∆ ℐ . We let rank, (ℐ, ) be defined as follows. If ℐ, |= , then rank, (ℐ, ) = 0. Otherwise, rank, (ℐ, ) is the biggest ∈ {1, . . . , +1} such that ℐ, ̸|= −1 .
Intuitively, rank, (ℐ, ) tells us to what extent the defeasible inclusions are satisfied at in ℐ. If rank, (ℐ, ) = 0, then is non-exceptional and satisfies all inclusions in . If rank, (ℐ, ) = + 1, then is highly exceptional: it violates some inclusion in , which stores the most specific defeasible inclusions of . Note that the rootedness condition guarantees that unnamed objects have rank, (ℐ, ) = 0.
Let ∆ be the set of individuals occurring explicitly in an ABox . We can now compare the extent to which interpretations satisfy defeasible inclusions: Definition 3. Assume a KB = ( , , ). Let (0, . . . , , ∞) be the tolerance partition of w.r.t. . An interpretation ℐ is called -admissible, if ℐ |= , ℐ |= , and ℐ |= ∞. Assume a pair ℐ, of -admissible interpretations. We write ℐ ≺ , if the following holds: • rank, (ℐ, ) ≤ rank , ( , ) for all individuals ∈ ∆ , and • rank, (ℐ, ) < rank, ( , ) for some individual ∈ ∆ .
A -admissible interpretation is called a minimal model of , if there exists no -admissible interpretation ℐ such that ℐ ≺ .
Example 2. Consider from Example 1. The tolerance partition of is (0, 1) with 0 = {RBC ∼⊏ ∃hasNucleus .⊤} and 1 = {MRBC ∼⊏ ¬∃hasNucleus .⊤}.
Let ℐ be an interpretation with ℐ |= ∪ and ℐ |= (∃hasNucleus .⊤)(1), ℐ |= (¬∃hasNucleus .⊤)(2), ℐ |= (∃hasNucleus .⊤)(3). We have rank, (ℐ, 1) = 0, since ℐ, 1 |= . We have rank, (ℐ, 2) = 1, because ℐ violates an inclusion in 0 for 2.
Observe that even KBs that have a canonical model may have more than one minimal model. Therefore, we consider sceptical and credulous entailment of assertions in the minimal models. Sceptical entailment over the minimal models accepts only conclusions that hold in all minimal models, while credulous entailment accepts conclusions that hold in at least one minimal model.
For this formalism, we show the following complexity results.
Theorem 1. Credulous and sceptical entailment of assertions is ExpTime-complete in combined complexity. In data complexity, credulous and sceptical entailment of assertions is Σ 2 -complete and Π 2 -complete, respectively.
This complexity is too high for applications involving large ABoxes, hence we identify a restricted fragment of our formalism that has tractable data complexity.
Definition 4 (Local KBs). A complex concept is closed if all concept and role names occurring in it are closed. An ordinary inclusion ⊑ or a defeasible inclusion ∼⊏ is called local, if every quantified concept of the form ∃. or ∀. occurring in or is closed. A knowledge base = ( , , ) is local if every defeasible inclusion in and every inclusion in is local.
The intuition of local inclusions is that they can only describe an object and its immediate surroundings. While they can use quantifiers on closed roles and predicates, which can be evaluated by looking up the assertions in the ABox, they cannot be afected by the assignment of open concepts in neighbouring nodes. This will allow us to answer queries about an object without the need to consider the assignments of open concepts for all objects in .
Theorem 2. Let be a local KB and be an assertion. Checking whether sceptically (or credulously, resp.) entails () is polynomial in data complexity and in NP in combined complexity. 3. Related Work and Conclusions We have presented a defeasible reasoning framework over ABoxes based on rational closure, identifying a tractable fragment where queries can be eficiently answered.
Despite the many works that extend DLs with defeasible reasoning based on rational closure,
reasoning about ABoxes is still lacking. While rational closure extends well to DLs with the disjoint model
union property [10, 17], it struggles with DLs that include individuals and closed predicates. Stable
rational closure has been proposed for more expressive logics like ℛℐ [
While our method sidesteps the issue of quantification neglect, it does sufer from other limitations of rational closure, like inheritance blocking. Future work includes exploring more general solutions to quantification neglect and how alternative semantics could be adapted for tractable reasoning, potentially inspired by approaches like ℒ [18, 19].
This work was partially supported by the Austrian Science Fund (FWF) projects PIN8884924, P30873 and 10.55776/COE12.
The author(s) have not employed any Generative AI tools.