In this paper we propose an algorithm that generalises existing procedures for the implementation of defeasible reasoning in the framework of Description Logics (DLs). One of the well-known approaches to defeasible reasoning, the so-called KLM approach, is based on constructing speci c rankings of defeasible information, and using these rankings to determine priorities in case of con icting information. Here we propose a procedure that allows us to input any possible ranking of the defeasible concept inclusions contained in the knowledge base. We analyse and investigate the forms of defeasible reasoning obtained when conclusions drawn are obtained using these rankings.
Members of the Description Logic (DL) community have devoted considerable
time and e ort to the introduction of defeasible forms of reasoning into DLs,
especially in the last decade. Among the di erent proposals [
The main contributions of this paper are showing that, by repurposing an existing defeasible entailment algorithm, it is possible to reason with an arbitrary ranking of defeasible subsumption statements while satisfying the KLM postulates; we provide equivalence and redundancy results of arbitrary rankings, and an optimization procedure that puts these to use to reduce redundant computation; and show that for any arbitrary ranking, there is a defeasible knowledge base the Rational Closure of which is equivalent to that arbitrary ranking. The results are signi cant, as they allow for the alteration or repair of automatically generated rankings (for example, those generated by lexicographic or rational closure) in the case that undesired statements are entailed, without sacri cing any of the KLM postulates when doing so. This should provide ontology engineers with greater control over their knowledge bases. 2
We assume that the reader is familiar with the basic notions of DLs. We base our
work on the DL ALC. Given a nite set of atomic concept names C := fA; B; : : :g
and a nite set of role names R := fr; s; : : :g, the set of complex concepts is
de ned as follows: C := > j ? j C j :C j C u C j C t C j 8r:C j 9r:C. For
C; D 2 C, a General Concept Inclusion (GCI) has the form C v D, with a
TBox T being a nite set of GCIs. The expression C D is an abbreviation of
C v D and D v C. T j= C v D denotes that C v D is classically entailed by
T . Following previous proposals [
Example 1. Suppose we know that Mammals generally are terrestrial, but whales are mammals and marine creatures. Using classical GCIs we would have a TBox as T = fMammal v LandDweller; Whale v Mammal; Whale v WaterDwellers; WaterDwellers v :LandDwellersg, that would classically entail that whales do not exist (T j= Whale v ?). Using DCIs we can convey the information above more accurately, eliminating Mammal v LandDweller from the TBox and adding a DTBox D = fMammal @ LandDwellerg, indicating that Mammals generally are terrestrial, but leaving open the possibility for the existence of exceptions (like whales).
Consider knowledge bases of the form K = (T ; D). We focus here on defeasible
entailment (denoted by j ). That is, we are interested in what it means for GCIs
and DCIs to be entailed by a knowledge base K. It is well-accepted that defeasible
entailment (unlike classical entailment) is not unique. In studying di erent forms
of defeasible entailment, the position we adopt here is to consider the rationality
properties presented in Fig. 2 that any form of defeasible entailment ought to
satisfy. These are referred to as the KLM properties, and are translations of
the propositional properties initially proposed by Kraus et al. [
A number of forms of defeasible entailment have been de ned that satisfy
all the KLM properties [
(And) (RM)
C (LLE) (Or) (CM) presumption of typicality states that we reason assuming that we are in the most typical situation consistent with the information at our disposal. For example, if we only know that manatees are mammals (Manatee v Mammal) and that usually mammals are land dwellers (Mammal @ LandDweller), we assume that manatees are normal mammals, and we would like to conclude that presumably they are land dwellers (Manatee @ LandDweller). The presumption of typicality is clearly a defeasible form of reasoning. If we are later informed that manatees live in the water (Manatee @ WaterDweller), then we want to drop the previously tentative conclusion that manatees are land dwellers (Manatee @ LandDweller).
Rational Closure can be de ned semantically in the DL framework [
Given a KB K = (T ; D), Algorithm 1 returns the elements of D that are exceptional. To do that, the materialization of a set of DCIs is used. De nition 1 (Materialization). The materialization of a set of DCIs D, denoted by D, is de ned as D := f:C t D j C @ D 2 Dg.
That is, the materialisation of a DCI C @ D is the concept :C t D, representing the corresponding material implication.
Using Algorithm 1, we obtain an algorithm (Algorithm 2) which, given K = (T ; D), ranks all the DCIs in D according to their level of exceptionality. In general, in case of con ictual information (e.g., students do not pay taxes, but working students do), the subconcepts that present atypical properties, and the DCIs that have as antecedents such subconcepts, have a higher rank: students,
Algorithm 1 Exceptional 1: procedure Exceptional 2: Input: K = (T ; D) 3: Output: D0 D such that D0 is exceptional w.r.t. D 4: for A @ B 2 D do 5: if T j= FD v :A then 6: D0 := D0 [ fA @ Bg 7: return D0 that typically do not pay taxes, will have rank 0; working students, since they pay taxes, will have rank 1; let there be a rule stating that working students with a family do not have to pay taxes, and so they will have rank 2, and so on.
In addition to the ranking E that Algorithm 2 produces, it also outputs a KB
K0 that, despite not necessarily being the same as the original K, is equivalent
to K [8, Lemma 13]. We refer the reader to the work of Britz et al. [
The next algorithm we consider, Algorithm 3, takes as input a KB K and a ranking E, as well as a query C @ D, and decides whether C @ D is defeasibly entailed by K (given E). Algorithm 3 guarantees that, in case of potential con icts, the information that is higher in the ranking overrides the other pieces of information. For example, if students do not pay takes (Student @ :PayTax) has rank 0, while the rule that working students should pay taxes (Student u Worker @ PayTax) has rank 1, we will conclude that, for example, part-time students that have a job as public servants presumably should pay taxes (PartTimeStudent u PubServ @ PayTax), since, in case of con ict, we rely on the DCI with the higher rank.
Finally, combining Algorithm 3 with Algorithm 2 enables us to de ne an
algorithm for computing Rational Closure [8, Theorem 4]: given a KB K and a
query C @ D, Algorithm 4 takes the ranking created by Algorithm 2 from K and,
calling Algorithm 3, decides whether C @ D is or not in the Rational Closure
of K. DIP? ? ? (Defeasible Inference Platform) is a Protege plugin implementing
Rational Closure for DLs [
As previously noted, Algorithm 2 returns a xed ranking E = (E0; : : : ; En) when presented with a KB K = (T ; D) as input. That is, it orders the elements of D w.r.t. exceptionality. In what follows we will refer to a more general notion of ranking of a KB.
De nition 2 (Ranking). A ranking is a tuple E = (E0; E1; :::; En) de ned relative to a KB K = (T ; D) satisfying the following properties: { for every integer i 2 [0; n], Ei { for every integer i 2 [0; n), Ei+1 { E0 = D
D;
Ei
A rank refers to any of the sets which compose a given ranking E . For all integers i 2 [0; n], Ei is a rank of E . The size of E , denoted jE j, is n where E = (E0; E1; :::; En).
A property of the materialization of ranks of E is shown in the following lemma. ? ? ? https://tinyurl.com/y3cjdznp
Lemma 1. Let E = (E0; :::; En) be a ranking relative to the KB K = (T ; D). For every integer i 2 [0; n), j= FEi v FEi+1.
It follows that if 0 j < i n, then j= FEj v FEi.
What happens if, together with a KB K, with give as input to Algorithm 3 an arbitrary ranking E of K instead of the ranking produced by ComputeRanking? It turns out that IsEntailed still de nes an entailment relation that satis es all the KLM properties. To make this more precise, we de ne defeasible entailment w.r.t a ranking E as follows.
Observe that defeasible entailment for K w.r.t the ranking produced by ComputeRanking is exactly Rational Closure.
Theorem 1. For a KB K = (T ; D) and a ranking E = (E0; :::; En) of K, defeasible entailment for K w.r.t E ( j E ) satis es all the KLM properties.
To motivate reasoning with an arbitrary ranking, note that algorithms like Algorithm 2 determine a ranking of statements based on their logical speci city, wherein more speci c statements are ranked higher; in some cases, we may wish to base our rankings on another principle altogether. Consider the example of country C. C is federal, with every region having a regional code, which is superceded by the federal code of C. Alcohol is considered a narcotic substance, but in region R of C, alcohol consumption is permitted. New laws are introduced to the federal code of C: one states that the consumption of narcotics is a crime unless otherwise indicated in the federal code, while the other states that consumption of narcotics is permitted if medically prescribed. Citizen B is caught drinking grappa in region R, without a medical prescription. To model that Bob is guilty of having broken the law of C, all that is required in the arbitrary ranking framework is to give the laws of the federal code a lower ranking than those of the regional code.
We now investigate the circumstances under which two rankings entail the
same set of statements, that is, when two rankings are equivalent. Results about
the equivalence of rankings are of interest, because as per Lutz [
Lemmas 2 and 3 below allow us to `shrink' a ranking in order to produce a ranking which is smaller but equivalent. For notational convenience, we de ne subrankings, borrowing syntax from the Python programming language.
De nition 5 (Subranking). Let E = (E0; E1; :::; En) be a ranking relative to K = (T ; D). For 0 i j n, the tuple (Ei; Ei+1; :::; Ej ) is an i-to-j subranking of E , denoted E [i : j].
Lemma 2. Let K = (T ; D) be a KB with the statements in D ranked into E =: (E0; :::; En). If there is some i 2 [0::n] for which T j= FEi v ? then E = E [i + 1 : n], where E [i + 1 : n] is the subranking of E relative to KB K0 = (T ; D0) where D0 = Ei+1.
Lemma 3. Let E = (E0; :::; En) be a ranking relative to KB K = (T ; D). Let i 2 [0; n] be the smallest integer such that T j= FEi >. Then E 0 =: E , where E 0 = E [0 : i 1].
These lemmas allow for ranks to be dropped from the top or bottom of a ranking without changing the set of entailed statements, but what about dropping statements from the middle of the ranking? This is discussed further in Section 4, but the following de nition allows us to provide some initial results: De nition 6 (Dense ranking). Let E = (E0; :::; En) be a ranking. E is dense if for all 0 i < n, T 6j= FEi FEi+1.
Dense rankings are signi cant because every rank of a dense ranking is involved in deciding entailment. By contrast, a ranking which is not dense (a sparse ranking) has the property that for some Ei, Ei+1, T j= FEi FEi+1. For any concept A, T j= FEi u A FEi+1 u A; so A is non-empty at i if and only if it is non-empty at i + 1. If FEi u A is non-empty then FEi+1 u A is non-empty, but algorithm 3 will stop at i, so Ei+1 will not be used; and if FEi u A is empty, then
FEi+1 u A is also empty, so it will be passed over for the next highest rank. Ei+1 therefore never contributes to entailment checking. This can be thought of as a `gap' in the ranking that does not alter entailment in a signi cant way, increasing the running time of entailment checking without contributing knowledge.
To this end, algorithm 5, CollapseRanking, takes a KB K and ranking E
aE n0d=: rEe.tuNrontse athraatntkhiengalgEo0 riotfh mthepesrafomremsstlainteemarelyntmsasnuychAtLhCatenEt0aiilsmdenentsceheacnkds
in the size of the ranking. Schmidt-Schau and Smolka prove in [
: : Corollary 1. E = F if and only if CollapseRanking(E) = CollapseRanking(F ). Corollary 2. Every nite ranking E has an equivalent dense ranking.
Another motivation for working with dense rankings is the result of Theorem 3 below, which states that if two dense rankings are equivalent, then the conjunction of the materialization of each of their ranks must be equivalent.
One requirement of the proof of Theorem 3 is that the top rank of the rankings under consideration not have the conjunction of its materialization equivalent to >. But by Lemma 3, it is always possible to transform a ranking into an equivalent ranking for which this is true.
Lemma 4 is split from Theorem 3 because it allows us to prove a slighter stronger result that does not require dense rankings.
Lemma 4. Let E = (E0; :::; Em) and F = (F0; :::; Fn) be rankings relative to the same KB K = (T ; D) with m = n such that for all integers i with 0 i n, : T j= FEi FFi; then E = F .
Theorem 3. Let E = (E0; :::; Em) and F = (F0; :::; Fn) be dense rankings relat?iv,eTto6j=the KFFB0s K?=, (TT ;6j=D) aFEnmd K0 =>,(Tan;dD0T) r6j=especFFtinvely,>su;cthhethnaEt T=: 6j=F ifFEa0nd only if m = n and for all integers i such that 0 i n, T j= FEi FFi.
The following observation summarizes the section on equivalence.
Let E and F be two rankings of statements relative to KBs K = (T ; D) and K0 = (T ; D0) respectively. Let E0 = CollapseRanking(K; E), F 0 = CollapseRanking(K0; F ). Let n = jE0j and m = jF 0j. Assign: :1; T j=
8 FE00 6 ? eh = <n; Let E00 = E0[el : eh] and F 00 = F 0[fl : fh]. Finally, let n0 = jE00j and m0 = jF 00j.
: Corollary 3. E = F if and only if n0 = m0 and for all integers i such that 0 i n0, T j= FEi00 FFi00.
Algorithm 6 Equivalent 1: procedure Equivalent(K; E; K0; F) 2: Input: K = (T ; D) with nite ranking E = (E0; :::; En), K0 = (T ; D0) with nite ranking F = (F0; :::; Fn) :
Output: true if and only if E = F E0 := CollapseRanking(K; E) F0 := CollapseRanking(K; F) n := jE0j, m := jF0j, el := 0, eh := n, fl = 0, fh = m if T j= FE00 ? then
el := el + 1 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: if T j= FF00 fl := fl + 1
? then if T j= FEn0 > then
eh := eh 1 if T j= FFm0 > then
fh := fh 1 E00 := E0[el : eh], F00 := F0[fl : fh] n0 := jE00j, m0 = jF00j if n0 6= m0 then
return false for i from 0 to n0 do if T 6j= FE00 FF00 then
return false return true
Algorithm 6, Equivalent, uses Corollary 3 to determine if two rankings are
equivalent. The algorithm consists of linearly many entailment checks, and since
ALC entailment checking is ExpTime-complete [
Broadly, redundant statements are statements which do not e ect the set of entailed statements. In other words, on adding or removing redundant statements, the new and old rankings should be equivalent. In this section,we de ne and discuss two forms of redundancy, local and total redundancy.
De nition 7 (Locally redundant). Let E be a ranking of a DTBox D in K = (T ; D), and let C @ D 2 D. C @ D is locally redundant at i if T j= FEi FEi0 where Ei0 = (Ei n fC @ Dg).
It follows trivially from the de nition that if C @ D is locally redundant at i and Ei0 = (Ei n fC @ Dg), then T j= FEi u A FEi0 u A holds for all concepts A; so for any concept B, T j= FEi u A v B i T j= FEi0 u A v B.
To see the relevance of local redundancy at i, consider E = (E0; E1; :::; En), a ranking relative to KB K = (T ; D), and a defeasible subsumption statement C @ D 2 Ei that is locally redundant at i, i > 0. Let R = fA @ BjA @ B 2 Ei 1 and A @ B 62 Eig. Note that C @ D 2 Ei and Ei Ei 1, so C @ D 62 R.
Ei [R = Ei 1, so T j= FEi u FR FEi 1. By assumption, T j= FEi FEi0, so T j= FEi0 u FR FEi u FR and in turn T j= FEi u FR FEi 1. But
FEi0 u FR is the conjunction of the materialization of every A @ B 2 Ei 1 except C @ D, so it is equivalent to FEi 1nfC @ Dg. Then T j= FEi 1
FEi 1nfC @ Dg, so C @ D is locally redundant at i 1. A simple inductive argument yields:
We also have the apparently stronger total redundancy: De nition 8 (Totally redundant). For a ranking E = (E0; :::; En):and conditional KB K = (T ; D), a statement C @ D is totally redundant if E = E 0, where E 0 = (E0nfC @ Dg; :::; EnnfC @ Dg) relative to K = (T ; DnfC @ Dg)
In fact, total and local redundancy are strongly related. Theorem 5 shows that for dense rankings, the two are interde nable.
Theorem 5. Let E = (E0; :::; En) be a dense ranking relative to KB K = (T ; D). Let i 2 [0; n] be the largest integer such that C @ D 2 Ei. Then C @ D is totally redundant if and only if it is locally redundant at i. 5
Clearly rational closure is in the class of entailment relations de nable using rankings and Algorithm 3, since it corresponds to using the output of ComputeRanking as input ranking for Algorithm 3. But is the class of entailment relations de nable using rational closure a proper subset of the class of relations de nable from rankings and Algorithm 3? Actually, this is not the case: for an arbitrary ranking sEucrehlatthivaet tEo K=: BE K0w=he(rTe; DE0),=it CisomaplwuatyesRapnoksisinbgle(Kto0).crSeiantcee aRKatBioKn0al=Cl(Tos;uDr0e) uses the ranking output by ComputeRanking, we have for all statements C @ D, RationalClosure(K0; C @ D) = IsEntailed(K; E ; C @ D).
Theorem 6. Let E = (E0; :::; En) be a ranking relative to conditional KB K = (T ; D). Let D0 = f> @ FE0g [ f: FEi @ FEi+1 j: i 2 Z; 0 i < ng. Let K0 = (T ; D0) and E 0 = ComputeRanking(K0). Then E = E 0.
F 0 D FD0 and T j= Lemma 7. For all integers i 2 [0; n], Lemma 5. T j= Lemma 6. For all i 2 [1; n],
FE0.
T j=
GEj+1 j j 2 Z; i j < ng
GEi+1 Exceptional(T ; Ei0) = f:
GEj+1 j j 2 Z; i j < ng 6
A recent proposal for dealing with defeasible reasoning in the framework of
DLs that is relatively related to the present approach is the one by Bonatti,
Sauro and others [
The results in this paper can be expanded upon in a number of ways. From
the point of view of implementation, there is a software tool, PRO (Preferential
Reasoner for Ontologies ), that models Algorithm 3 and is available online,y. It
can be the base for the development of more advanced tools. From the theoretical
point of view, the most urgent step would be to add an ABox and enable
drawing presumptive conclusions about individuals, as it has already been modelled
for the Rational Closure and other forms of closure [
Acknowledgments. G. Casini and T. Meyer have received funding from the EU Horizon 2020 programme under the Marie Sklodowska-Curie grant agr. No. 690974 (MIREL). The work of T. Meyer has been supported in part by the National Research Foundation of South Africa (grant No. UID 98019). y https://github.com/MindfulMichaelJames/PRO