Weighted-knowledge bases and cost-based semantics represent a recent formalism introduced by Bienvenu et al. for Ontology Mediated Data Querying in the case where a given knowledge base is inconsistent. This is done by adding a weight to each statement in the knowledge base (KB), and then giving each DL interpretation a cost based on how often it breaks rules in the KB. In this paper we compare this approach with -representations, a form of non-monotonic reasoning originally introduced by Kern-Isberner. -Representations describe a means to itnhteefirrsptr-eotrddeerfecaassieb.leTchoisncisepdtoninecbluysiaosnsisgonfinthgeafnourmmeri c⊏∼alra(nrkeiandg“tionsetaacnhceinstoefrpreatraetiuosnusavlliya pinesntaalnticeessfoofrea”c)hin violated conditional. We compare these two approaches on a semantic level. In particular, we show that under certain conditions a weighted knowledge base and a set of defeasible conditionals can generate the same ordering on interpretations, and therefore an equivalence of semantic structures up to relative cost. Moreover, we compare entailment described in both cases, where certain notions are equivalently expressible in both formalisms. Our results have the potential to benefit further work on both cost-based semantics and c-representations.
Description logics (DLs) [
In this paper we consider two specific semantic constructions, each connected to one of these two areas. On the side of inconsistency handling, we take under consideration a recent proposal by Bienvenu et al. [14], formulated for the DL ℒ. In the area of defeasible reasoning, we will consider -representations [15], a semantic framework based on ranking functions, and we refer to its formulation for First Order Logic (FOL) [16], that we constrain to the expressivity of ℒ. Both these semantic constructions are based on a similar idea: ranking the interpretations according to a numeric value that is determined by the amount of information that each interpretation violates.
We present a formal comparison between these two frameworks. The main contribution of the paper is to show that, under certain conditions, both semantic structures are equivalent up to relative cost. That is, on one hand we prove that for any ranking function defining a -representation of a defeasible ℒ knowledge base , we can construct a weighted knowledge base that induces the same ordering of interpretations, according to the methods in [14]. On the other hand, we provide necessary and suficient conditions that a weighted knowledge base must satisfy for the converse to hold. We also show how certain entailment relations defined in each semantic framework can be equivalently expressed in terms of the other.
The paper is organised as follows: Sections 2.2 and 2.3 present the two formal frameworks we refer to: cost-based semantics and c-representations, respectively; in Section 3 we present the focus of the 23rd International Workshop on Nonmonotonic Reasoning, November 11-13, 2025, Melbourne, Australia $ lsgnic001@myuct.ac.za (N. Leisegang); giovanni.casini@isti.cnr.it (G. Casini); tmeyer@airu.co.za (T. Meyer) 0000-0002-8436-552X (N. Leisegang); 0000-0002-4267-4447 (G. Casini); 0000-0003-2204-6969 (T. Meyer) © 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). paper, making a first comparison between the semantic structures and the forms of reasoning that we can model in these two structures; finally, in Sections 4 and 5 we mention related and future work. An extended version of this paper with proofs is available as a technical report [17].
2.1. Description Logic ℒ
In this section we provide a brief introduction to the description logic ℒ[
::= | {} | ¬ | ⊓ | ⊔ | ∃. | ∀. | ⊥ | ⊤ for ∈ , ∈ , ∈ , and , ∈ ℒ . An ABox is a finite set of assertions of the form : and (, ): where , ∈ , ∈ and ∈ . These are called concept and role assertions respectively. A TBox is a finite set of concept inclusions (GCIs) of the form ⊑ for , ∈ ℒ . An ℒ knowledge base is a pair = ( , ) where is a TBox and is an ABox.
Interpretations give a semantics to assertions and concept inclusions. An interpretation is a tuple ℐ = ⟨∆ ℐ , · ℐ ⟩ where ∆ ℐ is a non-empty set called the domain and · ℐ is a function that maps every ∈ to an individual ℐ ∈ ∆ ℐ , every ∈ to a set of ordered pairs ℐ ⊆ ∆ ℐ × ∆ ℐ , and every ∈ to a set ℐ ⊆ ∆ ℐ . Interpretations are lifted to complex concepts by: ⊥ℐ = ∅,
⊤ℐ = ∆ ℐ , ( ⊓ )ℐ = ℐ ∩ ℐ , {}ℐ = ℐ ,
(¬)ℐ = ∆ ℐ ∖ ℐ , ( ⊔ )ℐ = ℐ ∪ ℐ , (∃.)ℐ = { ∈ ∆ ℐ | there is an (, ) ∈ ℐ s.t. ∈ ℐ },
(∀.)ℐ = { ∈ ∆ ℐ | ∈ ℐ for all (, ) ∈ ℐ }.
An interpretation ℐ is a model of a concept inclusion ⊑ if ℐ ⊆ ℐ . ℐ is a model of the assertion : if ℐ ∈ ℐ , and ℐ is a model of (, ): if (ℐ , ℐ ) ∈ ℐ . This is denoted ℐ ⊩ for any assertion or GCI . ℐ is a model of the knowledge base = ( , ) (denoted ℐ ⊩ ) if ℐ ⊩ for all ∈ ∪ . A knowledge base entails a concept inclusion or assertion if ℐ ⊩ implies ℐ ⊩ .
Concept inclusions ⊑ , read as “Every is a ”, represent the main element of a DL knowledge bbaeesen, ibnuttrothdueyceddoinnovtaarilolouws ffoorrmesxc[e1p8,ti9o,n4s]. aTnoddaosssooc,idaetfeedastoibdleifecroennctepset minacnlutisciso,nbsu(tDaCl wIsa)ys ⊏w∼ith hthaeve same intended reading: ⊏∼ stands for “Typically, an element of is also an element of ”. In Section 2.3 we provide an interpretation of DCIs by adapting to ℒ a semantic approach defined for defeasible conditionals in FOL. 2.2. Cost-Based Semantics Cost-based semantics in DLs were introduced by Bienvenu et al. [14] in order to facilitate query answering over inconsistent DL knowledge bases. Intuitively, they assign a numerical “penalty” to each element of an ABox and TBox in the knowledge base. Then an interpretation ℐ is assigned a weight based on how many elements of ∆ ℐ “break” rules of the knowledge base. This is defined as follows. Definition 1 ([ 14]). A weighted knowledge base (WKB) is a pair = (( , ), ) where ( , ) is a classical DL KB and : ∪ → N ∪ {∞} is a cost function.
This cost function is then migrated from the knowledge base to an interpretation by tracking the violations of each rule in the interpretation.
Definition 2 ([14]). The set of violations of a GCI, ⊑ , is given by, while the violations of an ABox in ℐ are given by
vio⊑(ℐ) = ( ⊓ ¬)ℐ vio(ℐ) = { ∈ | ℐ ⊭ } Definition 3 ([ 14]). Given a WKB = (( , ), ), the cost of an interpretation ℐ with regards to is given by, cost (ℐ) = ∑︁ ( )|vio (ℐ)| + ∈
∑︁ ∈vio (ℐ) (), where |vio (ℐ)| is the cardinality of the set vio (ℐ). We will, in some cases, omit the subscript from the function cost . For each WKB = (( , ), ) we can define the optimal cost of as optc() = minℐ (cost (ℐ)).
The intuition is that an interpretation with a higher cost is “worse” in the sense that it contradicts more axioms with a greater cost. In particular, if some TBox or ABox axiom has a cost of ∞, for any interpretation ℐ breaking it we have cost(ℐ) = ∞. From this semantics, there are several diferent notions of entailment which are defined [ 14]. These are originally defined for Boolean Conjunctive Queries, but it is straightforward to extend them to general ℒ statements.
Definition 4 ([ 14]). For any GCI or assertion in ℒ, any weighted knowledge base , and any ∈ N, we define the following entailment relations: • ⊨ if ℐ ⊩ for all interpretations ℐ with cost • ⊨ if ℐ ⊩ for some interpretation ℐ with cost
if ℐ ⊩ for all interpretations ℐ with cost • ⊨
if ℐ ⊩ for some interpretation ℐ with cost • ⊨ (ℐ) ≤ .
(ℐ) ≤ . (ℐ) = ().
(ℐ) = ().
Note that if the knowledge base is classically consistent, then the optimal cost for is 0. In this case, we have that ⊨ coincides with classical reasoning [14]. Another preliminary result of particular interest in our context concerns the monotonicity of these entailment relations. For that, we first need to define monotonicity in the context of WKBs.
any WKB , we have
⊨ =⇒ ′′ ⊨ where ⊆ ′ and ′( ′) = ( ′) for all ′ ∈ .
This characterization of monotonicity is fairly straightforward: the knowledge base ′ extends the information contained in . New information and its associated costs can be added to the TBox or ABox, while the existing information and its costs are preserved. Under this framework, only one of the four mentioned entailment relations is monotonic. and ⊨ are
non-monotonic. In this section, we present a semantic framework aimed at modeling non-monotonic reasoning: crepresentations [15]. They are a subclass of ranking functions, also known as Ordinal Conditional Functions (OCFs)[19]. Both frameworks were originally introduced for propositional logic, but extensions to a conditional language in FOL have been proposed first for ranking functions [ 20], and subsequently tailored for c-representations [16]. Since DLs correspond to specific fragments of FOL, these characterizations can be applied to DLs as well. Therefore, we introduce ranking functions and c-representations directly for the DL ℒ: the following definitions are those presented in [ 16] for FOL, here reformulated to match the expressivity of defeasible ℒ. A defeasible ℒ KB is a triple = ( , , ), where and are, respectively, a TBox containing GCIs ⊑ , and an ABox containing assertions : and (, ): , while = {1 ⊏∼ 1, . . . , ⊏∼ } is a finite set of DCIs [18].
Remark. In order to adapt the definition for conditional FOL to defeasible ℒ, we rely on the translation of ℒ statements in FOL as presented in [16]:
: ⇝ () (, ): ⇝ (, ) ⊑ ⇝ ∀(() ⇒ ())
⇝ () ⊏∼ ⇝ (()|()) ∼
In particular, a defeasible inclusion is interpreted as an open conditional. We refer the reader to [16] to check the details and notation used for conditional FOL. Here, we also define the additional symbol ⊏ ∀ in order to refer to a universally quantified defeasible conditional, as introduced in [20]. That is: ⊏∼ ∀ ⇝ ∀(()|()).
Intuitively, a quantified DCI ⊏∼ ∀ expresses that, in the most typical situations, ∈ ℐ implies ∈ ℐ for every ∈ ∆ ℐ , whereas ⊏∼ expresses that, in the most typical situations, ∈ ℐ implies ∈ ℐ for certain elements ∈ ∆ ℐ : the most preferred (or typical) members of ℐ . In what follows, the technical diferences between various forms of defeasible concept inclusions become apparent.
Another aspect we adapt from the FOL formulation is Herbrand semantics, a well-known form of ifrst-order interpretations, that in [ 20] are used to define ranking semantics for defeasible reasoning. In the present setting, we fix a finite set of individual names = , referred to as the Herbrand Universe. That is, corresponds to the set in the vocabulary, hence it includes all the individual names appearing in the KB and possibly others. An ℒ interpretation ℐ is a Herbrand interpretation if ∆ ℐ = and ℐ = for all ∈ . The set of all Herbrand interpretations for a given ℒ vocabulary is denoted by Ω . In the following, we assume that all interpretations are Herbrand interpretations defined over some vocabulary. The following definition are all reformulations of notions presented for conditional FOL in [20, 16].
Definition 6. A ranking function is a mapping : Ω → N ∪ {∞}, such that −1 (0) ̸= ∅.
Ranking functions are generally interpreted as representing the expectations of an agent: the lower the rank associated to an interpretation, the more plausible the represented situation is considered by the agent. The interpretations with rank 0 describe what the agent expects to hold.
Although these ranking functions are initially defined on interpretations, they can be extended to ℒ statements.
Definition 7. Let be a ranking function.
• for every assertion : , (: ) = min ℐ⊩: (ℐ); • for every assertion (, ): , ((, ): ) = min ℐ⊩(,): (ℐ); • for every TBox statement ⊑ , ( ⊑ ) = min ℐ⊩⊑ (ℐ); • for every concept , () = min ∈Δℐ (: ); • for every DBox statement ⊏∼ , ( ⊏∼ ) = min∈Δℐ ((: ⊓ ) − (: )).
Based on such ranking functions, we can define the satisfaction relation of classical ℒ statements and ⊏ ∀-inclusions.
∼ Definition 8. Given a ranking function we define satisfaction of ℒ statements as follows: • ⊩ : if ℐ ⊩ : for all ℐ ∈ −1 (0). • ⊩ (, ): if ℐ ⊩ (, ): for all ℐ ∈ −1 (0). • ⊩ ⊑ if ℐ ⊩ ⊑ for all ℐ ∈ −1 (0).
• ⊩ ⊏∼ ∀ if (: ⊓ ) < (: ⊓ ¬) for all ∈ .
More elaborate is the definition of acceptance for DCIs. (1) (2) (3) Definition 9. Let ⊏∼ be any defeasible subsumption. We say that ∈ is a weak representative for ⊏∼ if the following conditions hold:
(: ⊓ ) = ( ⊓ ) (: ⊓ ) < (: ⊓ ¬). and denote the set of weak representatives by ( ⊏∼). A strong representative of ⊏∼ is defined as a weak representative of ⊏∼ such that (: ⊓ ¬) =
min ∈( ⊏∼ ) (: ⊓ ¬) We denote the set of strong representatives by ( ⊏∼ ).
The conditions above for representatives may appear somewhat technical. However, the intuition behind each condition can be described as follows. If is a (strong) representative for the rule ⊏∼ , then is a “maximally typical” instance of both and (as per condition (1)). Moreover, it is more “typical” for to satisfy the defeasible inclusion than to violate it (according to condition (2)), and ccoomndpiatiroend t(o3)ostpheecrigfiersotuhnadtinwghsetnhatsadtoisefsy v(1io)laanted (2)⊏.∼Thi,siitndteoremsesdoiafroyr dthefineit“imonosetncaobmlesmuosnt”ordeeafinsoens, acceptance for open conditionals, that is, defeasible inclusions.
Definition 10. Let be a ranking function and ⊏∼ be a defeasible inclusion. Then we say that satisfies ⊏∼ ( ⊩ ⊏∼ ) if ( ) ̸= ∅ and one of the following conditions hold: A. ( ⊓ ) < ( ⊓ ¬).
B. ( ⊓ ) = ( ⊓ ¬) and either ( ⊏∼ ¬) is empty, or for all ∈ ( ⊏∼ ) and all ∈ ( ⊏∼ ¬) we have, (: ⊓ ¬) < (: ⊓ ).
Condition A. refers to the prototypical case where the validation of a conditional is universally more likely than a contradiction to it. Condition B. refers to the case where there are individuals on the same wrainnks wouhto, saicntcaesiatsrereppreresesenntatatitviveetsheviroullaeteth⊏∼erualendwit h⊏∼le¬sse.xHcoewpteiovnera,liintyt.hTehcaatseiso,tfhBe.,rtehpereruselentat∼ ⊏ives of rule ⊏ are behaving as they do not due to specific properties of their behaviour as individuals, but due to∼ the fact that they “fall in line” to the general prototypical patterns of the world around them. More discussion on this can be found in [20]. It should be noted here that the quantified DCI ⊏∼ ∀ can be equivalently expressed as a set of open ℒ DCIs: Proposition 2. ⊩ ⊏∼ ∀ if ⊩ ({} ⊓ )
⊏∼ for all ∈ Σ. sinHceenthcee,ywceanarbeeaelsxoparebslesetdo ainscalusdeet aonfyDqBuoaxnatixfieidomDCs.I ⊏∼ ∀ in our knowledge base = ( , , ), Definition 11. Let = ( , , ) be a knowledge base. Then a ranking function is a model of if the following conditions hold: 1. ⊩ ⊏∼ for all ⊏∼ ∈ . 2. For all ℐ ∈ Ω , if ℐ ̸⊩ ∪ then (ℐ) = ∞.
Now that we have introduced ranking functions as a semantics for defeasible ℒ KBs, we introduce -representations, a specific subclass of ranking functions. Also -representations have originally been introduced for propositional logic [15], and we refer to a recent reformulation for first order conditionals [16], again, constraining it to ℒ expressivity. -representations are ranking functions which assign a penalty to each defeasible conditional that occurs in the knowledge base, and then assigns a rank to a DL interpretation based on how many times the interpretation violates defeasible inclusions in the knowledge base. This is defined formally below.
Definition 12. Let = ( , , ) be a defeasible ℒ KB with = {1 ⊏∼ 1, . . . , ⊏∼ }. A ranking function is a c-representation of if it is a model of and there is some { 1, . . . , } ⊂ N and 0 ∈ Z s.t., for each ℐ ∈ Ω with ℐ ⊩ ∪ , we have (ℐ) = 0 + ∑︁ (ℐ) , =1 where (ℐ) = |{ ∈ ∆ ℐ | ℐ ⊩ : ⊓ ¬}|.
SecEtaiocnh 2v.a2l.uIentuitisivtehlye,itmheparactnfkaoctfoarnfoinrttehrperDetCatIion ⊏ℐ∼und,earnadgiitvsernole-riesparneasleongtoatuisonto thisedweteeirgmhitnsefdrobmy counting the number of times each DCI ⊏∼ is violated by ℐ, and adding the corresponding impact factor for each violation. The constant 0 serves as a normalization factor, ensuring that −1 (0) ̸= ∅, and thus that is a valid ranking function. In particular, if there exist Herbrand interpretations that do not violate any rules, then 0 = 0.
It is worth noting that this is not the only semantics for DCIs in DLs. In many instances, a single
DL interpretation (∆ ℐ , · ) is considered, with an additional order relation ≺⊆ ∆ ℐ × ∆ ℐ . In this case,
ℐ ⊩ ⊏∼ if min≺ ℐ ⊆ ℐ [
This notion of entailment has been employed in other versions of ranking based semantics for defeasible DLs [16]. One issue is to decide which -representation ought to be considered for entailment. We therefore also examine skeptical -inference [23, 24], and credulous -inference [25], which are entailment relations defined considering the set of all -representations. These are introduced in the propositional case with defeasible conditionals (i.e., DBox statements) specifically in mind. We extend these definitions to the DL setting, and also consider entailment for non-defeasible sentences. 1These postulates in turn are based closely on the original postulates given by Kraus et al. [22] Definition 14. Let = ( , , ) be a defeasible knowledge base, and let be an ℒ DCI, GCI, or concept or role assertion. Then: 1. is a skeptical -inference of , written |≈ if |≈
2. is a credulous -inference of , written |≈ if |≈ for every -representation of . for some -representation of .
Note here that while our definitions are clear extensions of the previous definitions given in [ 23, 24, 25], the syntax we give is diferent in order to describe the inference systems for non-defeasible statements in the language. 3. Comparing Ranking and Cost-Based Semantics In the following section we will make explicit the connection between the formalisms given in the previous two discussions. Both defeasible reasoning and cost-based semantics are methods which are introduced in DLs in order to combat contradictory information, and both take the approach that in the instance where information is contradictory, certain rules can be weakened in the knowledge base. More explicitly, both cost-based semantics and c-representations assign penalties to an interpretation based on how many elements of the interpretation break rules in the knowledge base. However, before we describe this explicitly, we must list some assumptions we make in order to compare these formalisms: 1. We only consider Herbrand interpretations, where = is a finite Herbrand universe. This is done in order to facilitate an equivalent set of interpretations in the -representation and cost-based semantics case, where -representations are defined for first-order logic in terms of Herbrand semantics [20]. It is worth noting that this does restrict the interpretations considered in the original cost-based semantics formulation given in [14] to a closed-world style of reasoning, where interpretations are finite. We refer to ∆ ℐ and interchangeably in the rest of the section. 2. W(h⊓en¬eve)r aacnodndthituiosndaol no∼ ⊏tconiscesrantisofieudrsbeylvseosmweit h-craespereBs.einntDateiofinnitio,nw1e0afsosrum e. tWhaet d(ot⊓hiss)in<ce we are interested in considering the most prototypical conditions under which a DCI is satisfied, and leave considerations of non-typical individuals for future work. A similar assumption is used in previous literature when applying -representations to DLs [16]. 3.1. Semantic Structures with Equivalent Relative Cost of Interpretations In this section, we show that for a -representation of some knowledge base ( , , ) we can define a weighted knowledge base such that: (ℐ) < (ℐ
′) if and only if cost (ℐ) < cost (ℐ′) and that in certain cases the converse is possible. This shows that the way cost functions and -representations structure the relative penalties attributed to interpretations may be equivalent in certain circumstances. However, the costs and the rankings of such worlds are usually not numerically equivalent, since for any -representation there is always some interpretation ℐ such that (ℐ) = 0 , while cost (ℐ) = 0 for some ℐ only if is classically satisfiable. If a WKB and a ranking function satisfy the condition given above, we say that and have equivalent relative cost of interpretations.
We begin by defining the derived weighted knowledge base for a given -representation. Definition 15. Given a defeasible knowledge base ( , , ) and a -representation defined by: (ℐ) = 0 + ∑︁ (ℐ)
=1 we define the weighted knowledge base translation as follows: • = ( * , ) where the ABox is the same in both cases and * = ∪ * . • * = { ⊑ | ⊏∼ ∈ }. • ( ) = ∞ for all ∈ ∪ .
• ( ⊑ ) = for all ⊏∼ ∈ * .
It is worth immediately noting that not all WKBs can be derived from a -representation using the above definition. In particular, each ABox assertion in the derived WKB is given an infinite cost and must therefore be entailed classically by every interpretation with finite cost. This results from the fact that in many defeasible reasoning formalisms in DLs there is no defeasibility included ABox statements. However, those WKBs which are derived from the above definition give us a structure with an equivalent relative cost of interpretations to the original -representation. This is formalised as follows. Proposition 3. For a given ℒ -representation , and an interpretation ℐ ∈ Ω , we have: cost (ℐ) = (ℐ) − 0
An example of such a translation can be seen below.
Example 1. We consider an example with a structure similar to the well-known “penguin triangle” in non-monotonic reasoning. Let the Herbrand universe consist of a single element = { }, the set of concept names be = {Scientist, Logician, Experiments}, and the set of role names be empty. Then consider the knowledge base given by: = {Logician( )}, and = { 1 = Logician ⊏∼ Scientist, 2 = Logician ⊏∼ ¬Experiments, 3 = Scientist ⊏∼ Experiments}. Intuitively, this knowledge base expresses that “logicians are usually considered scientists,” “scientists usually do experiments,” and “logicians usually do not do experiments,” while asserting that is a logician.
A -representation for the above knowledge base can be defined by assigning an impact factor to each , where 1 = 1, 2 = 2 and 3 = 3, and fixing 0 = −1 . Using Proposition 3, we derive the WKB defined by: = {Logician( )}, = { 1′ = Logician ⊑ Scientist, , 2′ = Logician ⊑ ¬Experiments, 3′ = Scientist ⊑ Experiments}, where (Logician( )) = ∞ and ( ′) = for each .
However, while we are able to construct a WKB and cost-based semantic structure from any given defeasible knowledge base and corresponding -representation, the converse is not as straightforward. This is due to the fact that, in order to translate “weak” TBox statements into defeasible implications we require the resulting -representation to satisfy the translated knowledge base, and this is not true for all the weight-assignments. We therefore treat two diferent translations of weighted TBoxes into defeasible conditionals, and for now only consider those WKBs with a strict ABox, formally defined below. We consider “weak” ABox rules later, using the specific expressivity in ℒ to translate weak ABox axioms into DCIs.
Definition 16. A WKB has a strict ABox if, for all ∈ , ( ) = ∞.
This means that any interpretation violating an ABox axiom is immediately moved to the highest infinite cost. Then, for any ∈ such that ( ) < ∞, we consider the following two translations: 1. For any such = ⊑ , we add ⊏∼ ∀ to the defeasible knowledge base. 2. For any such = ⊑ , we add ⊏∼ to the defeasible knowledge base.
The second case, as previously mentioned, provides a translation of “weak” TBox statements ⊑ to defeasible concept inclusions ⊏∼ , which is more faithful to the literature [16]. However, it is not always the case that such a weak concept inclusion in a weighted knowledge base is intended to represent a defeasible conditional. We therefore propose two translations, and define conditions on WKBs whose translations result in a well-defined -representation.
Definition 17. Let = (( , ), ) be a WKB with a strict ABox. Then the quantified -representation translation of is defined as the function over the knowledge base * = ( ∞, , ), where: • The ABox is the same in both cases. • ∞ := { ⊑ ∈ | ( ⊑ ) = ∞} • := {{} ⊓ ⊏∼ | ∈ , ⊑ ∈ ∖ ∞}. • (ℐ) := 0 +∑︀∈ (ℐ) for each interpretation ℐ ∈ Ω such that ℐ ⊩
otherwise. • := ( ⊑ ) for every {} ⊓ ⊏∼ = ∈ . • 0 := −( ). • (ℐ) = 1 if ℐ ̸⊩ {} ⊓ ⊑ and (ℐ) = 0 if ℐ ⊩ {} ⊓ ⊑ . ∞ ∪; (ℐ) = ∞ Definition 18. Let = (( , ), ) be a WKB with a strict ABox. Then the open -representation translation of is defined as the function over the knowledge base * = ( ∞, , ), where: ∞ ∪; (ℐ) = ∞ • The ABox is the same in both cases. • ∞ := { ⊑ ∈ | ( ⊑ ) = ∞} • := { ⊏∼ | ⊑ ∈ ∖ ∞}. • (ℐ) := 0 +∑︀∈ (ℐ) for each interpretation ℐ ∈ Ω such that ℐ ⊩
otherwise. • := ( ⊑ ) for every ⊏∼ = ∈ . • 0 := −( ).
• (ℐ) = |( ⊓ ¬)ℐ | for all ℐ ∈ Ω and all ∈ .
Proposition 4. For any WKB = (( , ), ), let 1 be the function generated by the quantified c-representation translation and let 2 be the function generated by the open c-representation translation. Then 1 = 2.
Proposition 5. For any WKB with a strict ABox, we have that
(ℐ) = (ℐ) + 0 for any interpretation ℐ where is the quantified or open c-representation translation of .
The above shows that the ranking functions defined in both cases have an equivalent relative cost of interpretation to the original WKB. Moreover, these are well-defined ranking functions, since 0 = −( ) ensures that −1 (0) ̸= ∅ in either case. However, although we refer to them as -representation translations, we are not guaranteed that the resulting functions satisfy the translated knowledge base, and thus they may not be well-defined -representations. We propose two conditions on WKBs that ensure their quantified and open -representation translations satisfy their respective translated knowledge bases.
Definition 19. A WKB with a strict ABox is strongly -compatible if for all ⊑ ∈ { ∈ | ( ) < ∞}, ∈ we have
min ℐ⊩:⊓ (ℐ) <
min ℐ⊩:⊓¬ (ℐ).
This definition intuitively gives us the condition required for quantified translations to generate -representations. The following gives us a definition for open translations.
Definition 20. A WKB with a strict ABox is -compatible if for all ⊑ ∈ { ∈ | ( ) < ∞} , we have
min ∈,ℐ⊩:⊓ (ℐ) <
min ∈,ℐ⊩:⊓¬ (ℐ).
Proposition 6. Any strongly -compatible WKB is -compatible.
In order to show that these definitions are necessary, we consider the following example of a WKB which is not -compatible (and therefore is also not strongly -compatible): Example 2. We consider the same WKB ABox and TBox as the one derived in Example 1. However, in this case, we change the cost function in our WKB, and consider defined by:
(Logician( )) = ∞; (Logician ⊑ Scientist) = 3; (Scientist ⊑ Experiments) = 2; (Logician ⊑ ¬Experiments) = 1.
We observe that for any interpretation ℐ with cost less than 3, we must have ℐ ⊩ Logician( ) and ℐ ⊩ Logician ⊑ Scientist , which implies ℐ ⊩ Scientist( ) . If ℐ ⊩ Experiments( ) , then (Logician ⊓ Experiments)ℐ = { }, while (Scientist ⊓ ¬Experiments)ℐ = ∅. Thus, (ℐ) = 1. On the other hand, if ℐ ⊩ ¬Experiments( ) , then (Logician ⊓ Experiments)ℐ = ∅, while (Scientist ⊓ ¬Experiments)ℐ = { }. In this case, (ℐ) = 2. Furthermore, due to the nature of the Herbrand interpretations considered and the fact that the given knowledge base is not classically satisfiable, these two cases represent the minimal cost for interpretations that satisfy the rules Logician ⊑ ¬Experiments and Scientist ⊑ Experiments, respectively. Then the following holds: min (ℐ) = 2 > 1 = min (ℐ) ∈,ℐ⊩:⊓ ∈,ℐ⊩:⊓¬ where and are shorthand for the predicates Scientist and Experiments, respectively. Therefore, is not -compatible when considering the rule Scientist ⊑ Experiments. Consequently, the quantified and open -representation translations of do not satisfy Scientist ⊏∼ ∀Experiments and Scientist ⊏∼ Experiments respectively. Moreover, Example 1 shows us that the same knowledge base ( , ) can be -compatible when considering a diferent cost function.
The following result tells us that the conditions of -compatibility and strong -compatibility are exactly those which allow for the open (resp. quantified) -representation translations to provide us a well-defined -representation.
Theorem 1. A WKB is strongly -compatible if and only if its quantified -representation translation satisfies the translated knowledge base. Similarly, a WKB is -compatible if and only if its open representation translation satisfies the translated knowledge base.
Moreover, we are able to use open -representation translations as an inverse to the weighted knowledge base translation.
Theorem 2. Let = ( , , ) be a defeasible knowledge base, and let be a -compatible WKB. Then ′ = , where is the open -representation translation of , and ′′ = , where ′′ is the open -representation translation of ′′ .
In our translation, we have assumed the ABox to be a strict ABox. However, in order to generalize the semantic comparison between -representations and cost-based semantics, we now turn to the case of weak ABox axioms. Instead of incorporating these directly into the -representation translation of a WKB, we make use of nominals in ℒ in order to translate a “weak” ABox axiom into a “weak” GCI. Definition 21. Consider a WKB = (( , ), ). Then the strict ABox translation of is given by ′′ = (( ′, ′), ′) where: • ′ := {: ∈ | (: ) = ∞}. • ′ := ∪ {{} ⊑ | : ∈ ∖ ′}.
• ′( ) = ( ) for all ∈ ( ′ ∪ ); ′({} ⊑ ) = (: ) for all : ∈ ∖ ′.
We note below that this strict ABox translation is faithful to the original knowledge base, since it preserves costs on interpretations, and thus preserves the entailments in Definition 4. Proposition 7. For any WKB , we have that (ℐ) = ′′ (ℐ) for all ℐ ∈ Ω , where ′′ is the strict ABox translation of .
This in combination with our previous results shows us that any WKB whose strict ABox translation is either -compatible or strongly -compatible can be translated into a -representation with the same relative cost of interpretations. On the other hand, every -representation can be translated into a valid WKB with equivalent relative cost of interpretations. that |≈ if ⊨
. -representation.
Proposition 9. Let be a WKB. Then: 3.2. Bridging Entailment Relations In this section, we discuss the impact of the semantic comparison between cost-based semantics and -representations on the entailment relations associated with each formalism. For this subsection, we assume that each WKB has a strict ABox and is strongly -compatible, unless stated otherwise. We begin by comparing the entailments introduced by cost-based semantics in Definition 4 with those defined by a single -representation, as in Definition 13. Intuitively, these are the two most closely related entailments: in cost-based semantics, the weight of each sentence is typically treated as inherent to the knowledge base, whereas in -representations, the impact factors assigned to each DCI are not intrinsic to the knowledge base but are instead part of the semantics and may vary, especially in entailment relations such as skeptical or credulous -inference. The most direct relationship to explore is the comparison of -entailment for classical DL statements with ⊨ and ⊨ . |≈ Proposition 8. For a given WKB and any GCI or ABox statement we have that ⊨ , where is the quantified or open translated knowledge base. Similarly, given a defeasible knowledge base = ( , , ), a -representation and a classical GCI or ABox statement , we have if On the other hand, we are able to express ⊨
as a negation of -entailment for the translated • If ⊑ is a GCI then ⊨ • If : is a concept assertion, then ⊨ ⊑ if ̸ |≈ : if ̸ |≈
: ¬. : ⊓ ¬ for all ∈ . where is the quantified or open translated knowledge base.
This result should be unsurprising since ⊨ and |≈ results when holds for all -representation. interpretations with minimal cost or rank in the cost-based semantics and -representation respectively. Since the translated interpretations have the same relative cost of interpretations, those with minimal cost are the same interpretations once translated. This relationship is not as clear when it comes to -entailment for DCIs and the relations ⊨ and ⊨ , especially since there is no way to fix a specific numerical threshold for rankings in -representation based entailment, such as is fixed for ⊨ and ⊨ . However, we are able to express entailment for DCIs in terms of ⊨ for the WKB translation of a ⊭ : ⊓ ¬ for all ∈ .
have that |≈ Proposition 10. For a defeasible knowledge base and a -representation which is a model of , we ⊏∼ if there exists some ∈ N such that ⊨ : ⊓ for some ∈ and is a -representation which is a model of }.
When we consider entailment relations from defeasible reasoning which consider more than one -representation, it is clear that this does not correspond to one specific WKB, but rather a class of -compatible WKBs where the ABox and TBox remain the constant, but the weighting function varies. This is made precise in the following results. In the following proposition, for a defeasible knowledge base , we define the class of WKBs considered by WKB := { | translate a given WKB into a defeasible knowledge base.
statement2 we have that |≈
Similarly, |≈ if ⊨ if
for some ∈ WKB.
⊨
for all ∈ WKB.
Proposition 11. Let = ( , , ) be a defeasible knowledge base. Then, if is a classical ℒ
We are also able to show that, under certain conditions, |≈ is a stronger notion of ⊨ once we 2That is, is an assertion or a GCI.
, where is the defeasible knowledge base in the open -representation translation of . that ⊨
We are therefore able to rephrase certain entailment relations in defeasible reasoning in terms of costbased semantics, as well as rephrasing certain entailment relations in cost-based semantics in terms of -representations, although these translations may not cover the full expressivity of the original relation. This does not only point to the potential for more unification between inconsistency tolerant semantics and defeasible reasoning in DLs, but it also allows each approach to possibly inherit techniques and results from the other. For example, defeasible reasoning using -representations stands to benefit from established complexity results in cost-based semantics [14], while work done in computing representations, such as reducing skeptical -inference to a Constraint Satisfaction Problem [23] may be applicable to cost-based semantics.
The current paper is based on the work of Bienvenu et al. [14], who introduce cost-based semantics
for query answering over inconsistent knowledge bases, and on the work of Kern-Isberner and others
[20, 16], who define ranking functions and -representations for conditional FOL. Defeasible concept
inclusions in DLs have been considered using preferential semantics in ℒ by Giordano et al. [
Cost-based semantics are related to repair-based semantics considered by Bienvenu et al. [
In this paper, we provide a comparison between the frameworks of cost-based semantics for inconsistency-tolerant query answering in the DL ℒ, and the ranking function based semantics of -representations for defeasible reasoning in First-Order Logic. In doing so, we highlight the similarities between both frameworks and suggest ways in which certain aspects can be expressed by the other under certain conditions. In particular, we show that for a given -representation for a defeasible knowledge base , we can define a weighted knowledge based such that (ℐ) < (ℐ′) if. (ℐ) < (ℐ ′), and show that when certain conditions are satisfied, the converse is possible. Moreover, we consider the resulting links between entailment in each framework and show that certain entailment relations which are defined for one framework can be expressed in terms of entailment relations defined in the other. Overall, the goal of this paper is to provide a technically precise means to understand one framework in terms of the other, and provide a starting point for unifying both approaches from the query-answering and defeasible reasoning communities, where desirable. This has the potential to benefit both frameworks, since under certain conditions they stand to inherit methodologies and results from the other framework, as well as increase the expressivity and scope of applicability for both frameworks.
As such, immediate future work to consider is to what extent results which hold in one framework can be applied to the other. In particular, it is worth investigating the complexity results given in cost-based semantics [14] as a means to determine complexity bounds for defeasible reasoning in DLs. On the other hand, it would be worth investigating methods used for determining relevant ranking functions within defeasible reasoning, such as the Constraint Satisfaction problems considered in [23], as a means to algorithmically determine cost functions within weighted knowledge bases, rather than requiring such cost functions to be declared. In order to further unify the field, a more detailed comparison between cost-based semantics and other semantics for defeasible descriptions logics, such as the more widely used preferential interpretations [18], could be considered.
This work is based on the research supported in part by the National Research Foundation of South Africa (REFERENCE NO: SAI240823262612). The work of Giovanni Casini and Thomas Meyer has been partially supported by the H2020 STARWARS Project (GA No. 101086252), action HORIZON TMA MSCA Staf Exchanges.
The authors have not employed any Generative AI tools. [14] M. Bienvenu, C. Bourgaux, R. Jean, Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases, in: Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, 2024, pp. 167–177. [15] G. Kern-Isberner, Conditionals in Nonmonotonic Reasoning and Belief Revision: Considering
Conditionals as Agents, Springer Verlag, 2001. [16] A. Hahn, G. Kern-Isberner, T. Meyer, Ranking-based defeasible reasoning for restricted first-order conditionals applied to description logics, in: N. Gierasimczuk, J. Heyninck (Eds.), Proceedings of the 22nd International Workshop on Nonmonotonic Reasoning (NMR 2024) co-located with 21st International Conference on Principles of Knowledge Representation and Reasoning (KR 2024), Hanoi, Vietnam, November 2-4, 2024, volume 3835 of CEUR Workshop Proceedings, CEUR-WS.org, 2024, pp. 162–172. [17] N. Leisegang, T. Meyer, G. Casini, Semantic Bridges Between First Order c-Representations and Cost-Based Semantics: An Initial Perspective, Technical Report, 2025. URL: https://arxiv.org/abs/ 2510.00817. [18] K. Britz, G. Casini, T. Meyer, K. Moodley, U. Sattler, I. Varzinczak, Principles of klm-style defeasible description logics, ACM Trans. Comput. Log. 22 (2021) 1:1–1:46. [19] W. Spohn, The Laws of Belief: Ranking Theory and its Philosophical Applications, Oxford University Press, Oxford, 2012. [20] G. Kern-Isberner, M. Thimm, A ranking semantics for first-order conditionals, in: L. D. Raedt, C. Bessiere, D. Dubois, P. Doherty, P. Frasconi, F. Heintz, P. J. F. Lucas (Eds.), ECAI 2012 - 20th European Conference on Artificial Intelligence. Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, Montpellier, France, August 27-31 , 2012, volume 242 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2012, pp. 456–461. [21] M. Pensel, A. Turhan, Reasoning in the defeasible description logic ℰ ℒ - computing standard inferences under rational and relevant semantics, International Journal of Approximate Reasoning 103 (2018) 28–70. [22] S. Kraus, D. Lehmann, M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence 44 (1990) 167–207. [23] C. Beierle, C. Eichhorn, G. Kern-Isberner, S. Kutsch, Properties of skeptical c-inference for conditional knowledge bases and its realization as a constraint satisfaction problem, Annals of Mathematics and Artificial Intelligence 83 (2018) 247–275. [24] C. Beierle, C. Eichhorn, G. Kern-Isberner, Skeptical inference based on c-representations and its characterization as a constraint satisfaction problem, in: M. Gyssens, G. R. Simari (Eds.), Foundations of Information and Knowledge Systems - 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings, volume 9616 of Lecture Notes in Computer Science, Springer, 2016, pp. 65–82. [25] C. Beierle, C. Eichhorn, G. Kern-Isberner, S. Kutsch, Skeptical, weakly skeptical, and credulous inference based on preferred ranking functions, in: G. A. Kaminka, M. Fox, P. Bouquet, E. Hüllermeier, V. Dignum, F. Dignum, F. van Harmelen (Eds.), ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), volume 285 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2016, pp. 1149–1157. [26] K. Britz, I. Varzinczak, Context-based defeasible subsumption for ℛℐ, in: A. S. Gordon, R. Miller, G. Turán (Eds.), Proceedings of the Thirteenth International Symposium on Commonsense Reasoning, COMMONSENSE 2017, London, UK, November 6-8, 2017, volume 2052 of CEUR Workshop Proceedings, CEUR-WS.org, 2017. [27] G. Casini, U. Straccia, T. Meyer, A polynomial time subsumption algorithm for nominal safe ℰ ℒ⊥ under rational closure, Inf. Sci. 501 (2019) 588–620. [28] G. Casini, T. Meyer, G. Paterson-Jones, I. Varzinczak, KLM-style defeasibility for restricted firstorder logic, in: Proceedings of the 6th International Joint Conference on Rules and Reasoning, Springer, Cham, Switzerland, 2022, pp. 81–94. [29] T. Eiter, T. Lukasiewicz, L. Predoiu, Generalized consistent query answering under existential rules, in: C. Baral, J. P. Delgrande, F. Wolter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR 2016, Cape Town, South Africa, April 25-29, 2016, AAAI Press, 2016, pp. 359–368.