While semantic approaches for revising knowledge bases are fine-grained and independent of the syntactical forms, they are unable to be straightforwardly applied to description logics (DLs) under standard semantics. In this paper, we present a characterization of revision for (finite) knowledge bases in DLs under the fixed-domain semantics, where the domain is fixed and finite. We also introduce an instantiation of a model-based revision operator which satisfies all standard postulates using the notion of distance between interpretations. The model set of the revision result is shown to be expressible in a KB in our setting. In addition, by weakening the KB based on certain domain elements, an individual-based revision operator is provided as an alternative approach.
Description logics (DLs) have been widely used to represent domain knowledge of the world in
knowledge bases (KBs). As knowledge bases are not static entities but change over time, it is
mandatory to efectively and eficiently manage such changes. One scenario is when a knowledge
base has to incorporate new information while maintaining its consistency by performing
changes as minimal as possible. This task is known in the literature as knowledge base revision
and has been massively influenced by the AGM paradigm of Alchourrón, Gärdenfors, and
Makinson [
Approaches for revising DL knowledge bases are classified into syntax-based and
semanticbased approaches. In syntax-based approaches, the operators directly modify the axioms in the
knowledge bases. Existing work on syntactic approaches could not satisfy all AGM postulates
[
In contrast, semantic-based revision approaches investigate the models of KBs, search for the
most plausible set of models to become the revision result, and generate a KB which corresponds
to the produced model set. However, it has been shown that in DL with standard semantics,
there are two main issues: (1) the models of the knowledge bases can be infinitely many and (2)
even if we can somehow “compute” the model-based revision, the set of models as the result of
the revision may not be expressible by a knowledge base (this is known as the inexpressibility
problem [
Fixed-domain semantics for DLs has been introduced to accommodate the scenario when the
knowledge bases represent constraint-type or configuration problems [
In this article, we show the semantic representation theorem for knowledge base revision
in DLs under the fixed-domain semantics. Alongside, we present two concrete approaches for
revising knowledge bases. The first approach is a semantic-based revision approach, which is
inspired from the approach by Katsuno and Mendelzon (KM) [
The paper is organized as follows. We very briefly recap basic notions in the description logic ℛℐ in Section 2. In Section 3, we formally introduce the fixed-domain semantics and present an axiom construction from a given set of interpretations. Revision operator and postulates are introduced in Section 4, followed by a semantic characterization of the revision operator in DL under the fixed-domain semantics in Section 5. The instantiations of the revision approaches are presented in Section 6 for the semantic-based approach and in Section 7 for the individual-based approach.
We assume the readers are familiar with the description logic ℛℐ (which is the logical
counterpart of the standard Web Ontology Language) with its standard syntax and semantics
[
Given a ℛℐ knowledge base , we essentially determine the size of by counting the number of symbols it takes to write the knowledge base. We start by inductively defining the 1https://github.com/wolpertinger-reasoner size of ℛℐ concepts2 and axioms as shown in Table 1 and Table 2. Then, the size of is the sum of the size of all axioms in , i.e. size() = ∑︀ ∈ size( ).
Now we briefly recall the ℛℐ semantics. Let ℐ = (∆ ℐ , · ℐ ) be a standard ℛℐ interpretation, where ∆ ℐ is a non-empty set that is called domain of ℐ and · ℐ is a function that maps each individual ∈ to an element ℐ ∈ ∆ ℐ , each concept ∈ to a subset of ∆ ℐ , and each role name ∈ to a subset of ∆ ℐ × ∆ ℐ . We say that ℐ satisfies a knowledge base (or ℐ is a model of ) if it satisefis all axioms of , denoted as ℐ |= . A knowledge base entails an axiom if all models of are models of . We use ℒ to denote the DL language, i.e. the set of all possible DL axioms and Ω to denote the set of all interpretations.
For describing belief revision on the semantic level, we endow the interpretation space Ω with some structure. In particular, we will employ binary relations ⪯ over Ω (formally: ⪯ ⊆ Ω × Ω ), where the intuitive meaning of ℐ1 ⪯ ℐ 2 is that ℐ1 is “equally good or better” than ℐ2 when it comes to serving as a model. We call ⪯ total if ℐ1 ⪯ ℐ 2 or ℐ2 ⪯ ℐ 1 for any ℐ1, ℐ2 ∈ Ω . We write ℐ1 ≺ ℐ 2 as a shorthand, whenever ℐ1 ⪯ ℐ 2 and ℐ2 ̸⪯ ℐ 1 (the intuition being that ℐ1 is “strictly better” than ℐ2). For a selection Ω ′ ⊆ Ω of interpretations, an ℐ ∈ Ω ′ is called ⪯ -minimal in Ω ′ if ℐ ⪯ ℐ ′ for all ℐ′ ∈ Ω ′.3 We let min(Ω ′, ⪯ ) denote the set of ⪯ -minimal interpretations in Ω ′. We call ⪯ a preorder if it is transitive and reflexive.
Let ∆ be a non-empty finite set called the fixed domain. An interpretation ℐ = (∆ ℐ , · ℐ ) is said to be ∆ -fixed, if ∆ ℐ = ∆ and ℐ = for all ∈ ∆ . For a DL knowledge base , an interpretation 2We assume that the number in the qualified number restriction concept is written in binary encoding. 3If ⪯ is total, this definition is equivalent to the absence of any ℐ′′ ∈ Ω′ with ℐ′′ ≺ ℐ . bases in the process of revision. ℐ is a ∆ -model of (ℐ |=Δ ), if ℐ is a ∆ -fixed interpretation and ℐ |= . A knowledge base is called ∆ -consistent (or ∆ -satisfiable) if it has at least one ∆ -model. A knowledge base ∆ -entails an axiom ( |=Δ ) if ℐ |= for every ℐ |=Δ . Two KBs and ′ are ∆ -semantically equivalent (written as ≡ Δ ′) if |=Δ ′ and ′ |=Δ . We will just say consistent, entail, or equivalent, and omit the subscript ∆ , if it is clear from the context. The set of all ∆ -models of is denoted by Mod Δ(). Note that we only consider finite knowledge
Fixed-domain semantics can be seen as a further restriction of finite-model reasoning [
We are working with ℛℐ knowledge bases under some assumptions on the axiom side.
The original definition of ℛℐ RBox contains axioms expressing role hierarchy ( ⊑ ), role
chains (1 ∘ ... ∘ ⊑ ), role disjointness ((, )), transitivity ( ()), symmetry (()),
asymmetry (()), reflexivity ( Ref ()), and irreflexivity ( ()). In this article, we will
only consider the first three axiom expressions since the remaining forms can be syntactically
rewritten into other known axioms: () can be translated as −
⊑ , () can be
expressed as (, − ), and () can be rewritten into the role chain axiom ∘ ⊑ . For
(ir)reflexivity axioms, Ref () and () can be translated as ⊤ ⊑ ∃.Self and ⊤ ⊑ ¬∃.Self ,
respectively. Moreover, as opposed to the standard ℛℐ definition, we do not impose the
global restriction called regularity since reasoning in KBs with unrestricted role hierarchies is
always guaranteed to be decidable under the fixed-domain semantics[
In the following, we introduce a method to construct a ℛℐ axiom under fixed-domain semantics from a given set of interpretations such that the models of the axiom are exactly the given interpretations. This construction is useful to express the result of our model-based revision approach (see Section 6) into a DL knowledge base and to show that our semantic characterization is indeed compatible with the revision operator (see Definition 4.1). Let {ℐ1, ..., ℐ} ⊆ Ω be a set of ∆ -interpretations and ℐ ∈ {ℐ1, ..., ℐ} be one of the interpretations, we define (ℐ) = ∈ ∈Δ and ∈ℐ
∈ ,∈Δ and (,)∈ℐ ︂( ︂( ︂( l l l l l ∃.({} ⊓ ) ∃.({} ⊓ ¬) ∈ ∈Δ and ∈/ℐ
∃.({} ⊓ {}) ∈ ()∖Δ,∈Δ and ℐ = ︂) ︂) ⊓ ︂( ⊓
︂( ︂) , l
l l
l ∈ ,∈Δ and (,)∈/ℐ ∃.({} ⊓ ∃.{}) ∃.({} ⊓ ¬∃.{})
⊓ ︂) ⊓ ︂) where is the universal role. Then, we construct a ℛℐ axiom as follows: formΔ({ℐ1 , ..., ℐn }) = ⊤ ⊑
⨆︁ ( (ℐ)) 1≤ ≤ (1) Proposition 3.1. Let {ℐ1, ..., ℐ} be a set of ∆ -interpretations. Mod Δ(formΔ(ℐ1 , ..., ℐn )) = {ℐ1, ..., ℐ} holds.
In this article, we use knowledge base revision operators to model multiple revision, which is the process of incorporating multiple new beliefs (axioms) into the present beliefs (axioms) held by an agent, in a consistent way (whenever that is possible). We define revision operators over knowledge bases as follows.
Definition 4.1 (Revision operator). Let ∆ be a fixed domain and ℒ be the set of all axioms of a given DL. A function ∘ : fin(ℒ) × fin(ℒ) → fin(ℒ) is called a (multiple) revision operator.
We consider multiple revision, which is that all given axioms have to be incorporated, i.e.
given a knowledge base and new information ′ (also a knowledge base here), we demand
success of revision, i.e. ∘ ′ |= ′. Besides the success condition, the belief change community
has brought up and discussed several further requirements for revision operators to make them
rational (for summaries, see [
We will make use of the AGM postulates for Description Logics [
(G1) guarantees that the newly added belief must be a logical consequence of the result of the revision. (G2) says that if the expansion of by ′ is consistent, then the result of the revision is equivalent to the expansion of by ′. (G3) guarantees the consistency of the revision result if the newly added belief is consistent. (G4) is the principle of the irrelevance of the syntax, stating that the revision operation is independent of the syntactic form of the bases. (G5) and (G6) ensure more careful handling of unions of belief bases. In particular, together, they enforce that ∘ (′ ∪ ′′) ≡ ( ∘ ) ∪ ′′, unless ′′ contradicts ∘ ′.
One central notion for the characterization of revisions is the notion of faithful assignment,
which was introduced by Katsuno and Mendelzon [
Definition 5.1 (assignment, faithful). Let ℒ be a set of all axioms of a given DL. An assignment is a function ⪯ (.): fin(ℒ) → (Ω × Ω) that assigns to each knowledge base a total binary relation ⪯ over Ω . An assignment ⪯ (.) is called faithful if it satisfies the following conditions for all ℐ, ℐ′ ∈ Ω and all knowledge bases and ′: (F1) If ℐ, ℐ′ |= , then ℐ ≺ ℐ′ does not hold. (F2) If ℐ |= and ℐ′ ̸|= , then ℐ ≺ ℐ′.
(F3) If ≡ ′, then ⪯ =⪯ ′ .
An assignment ⪯ (.) is a preorder assignment if ⪯ is a preorder for every knowledge base .
Intuitively, faithful assignments provide information about which of the two interpretations is “closer to -modelhood”. Consequently, the actual -models are ⪯ -minimal. The next definition captures the idea of an assignment adequately representing the behavior of a revision operator.
Definition 5.2 (compatible). A revision operator ∘ is called compatible with some assignment
⪯ (.) if Mod( ∘ ′) = min(Mod(′), ⪯ ) for all knowledge bases and ′.
Theorem 5.3 (Adaptation of Theorem 3.3. in [
Proof. The proof is similar to the one of the Representation Theorem by Katsuno and Mendelzon [15, Theorem 3.3.]. For the “if” direction, the arguments are similar and straightforward. For the “only if” direction, we assume the existence of a revision operator ∘ which satisfies postulates (G1)-(G6). Then, for any knowledge base , one can obtain a faithful preorder assignment compatible with ∘ by employing relation encoding ⪯ as: ℐ ⪯ ℐ′ if and only if either ℐ ∈ Mod () or ℐ ∈ Mod ( ∘ formΔ(ℐ, ℐ′)) for any interpretations ℐ and ℐ′.
In this section, we present our first approach to perform model-based revision in the
fixeddomain semantics setting. Our concrete revision operator is adapted from Dalal’s operator [26].
The original operator works for two propositional formulas and . The diference set between
their models consists of propositional variables that are interpreted diferently by them. Then,
the distance between them is defined as the minimal cardinality of the diference sets between
models of and . The set of models of revising by consists of models of such that there
exists a model of such that the cardinality of the diference set between the two models is the
same as the distance between and . In [
To adapt Dalal’s revision operator to DLs under fixed-domain semantics, we need to define the “diference set” between two models. Thanks to the elements in the domain being finite and known, we can characterize the ∆ -models of the knowledge bases and then we can define the diference between two ∆ -models in a similar way as the diference set between two models in propositional logic based on the grounded form of the interpretations.
Definition 6.1 (Grounded interpretation). Let be a KB and ℐ = (∆ ℐ , · ℐ ) be a ∆ -fixed interpretation. The ground representation of ℐ is the following: (ℐ) = {() | ∈ ∆ and ∈ ℐ } ∪ {(, ) | , ∈ ∆ and (, ) ∈ ℐ } ∪ { = | ∈ ℐ (), ∈ ∆ and ℐ = }.
In the following, we introduce a distance between two models based on the operator of symmetric diference, denoted with ⊕ , which is defined as ⊕ ′ = ( ∪ ′) ∖ ( ∩ ′) for any set and ′.
Definition 6.2 (Distance). Let be a KB and ℐ be a ∆ -fixed interpretation. The distance between Mod Δ() and ℐ is defined as: (Mod Δ(), ℐ) = minℐ′∈ModΔ() (ℐ′, ℐ), where (ℐ′, ℐ) = |diff (ℐ′, ℐ)| and diff (ℐ′, ℐ) = (ℐ′) ⊕ (ℐ).
Now we are ready to introduce a model-based revision operator for Description Logic under ifxed-domain semantics.
Definition 6.3. Let and ′ be any two knowledge bases. Let ⪯ (Δ.): ↦→ ⪯ Δ be an assignment, where the binary relation ⪯ Δ is defined by letting ℐ1 ⪯ Δ ℐ2 if and only if (Mod Δ(), ℐ1) ≤ (Mod Δ(), ℐ2) for all interpretations ℐ1 and ℐ2. We define the model-based revision operator ∘ Δ as follows:
∘ Δ ′ = {formΔ(min(Mod Δ(′), ⪯ Δ ))}.
Proposition 6.4. The model-based change operator ∘ Δ satisfies the postulates (G1)-(G6). Proof. Similar to the assignment presented in [15, Section 4.1.], we have that the assignment ⪯ (Δ.) is a faithful preorder assignment. From Proposition 3.1, we obtain Mod Δ( ∘ Δ ′) = Δ), which shows compatibility. Finally from Theorem 5.3, we obtain that ∘ Δ min(Mod Δ(′), ⪯ satisfies the postulates (G1)-(G6).
In this section, we present the second approach to revise our DL knowledge bases. The main idea is that instead of removing the whole axiom(s) whenever inconsistency occurs, the axioms are weakened, that is, modified by adding some exceptions. Diferent from the previous approach (cf. Section 6) which computes the interpretations, this approach focuses on the elements of the fixed domain. In particular, we will work with sets of exceptional individuals, which serve as a basis to weaken the knowledge base. For the weakening process, we impose the assumption that the knowledge base is free of RBox axioms. This assumption enables simpler weakening steps as we only consider TBox and ABox axioms. To this end, we introduce an equivalent transformation for an arbitrary knowledge base into a KB without RBox axioms. This transformation is possible as we are working with fixed-domain semantics. The idea is to keep the TBox and ABox axioms unchanged and to “partially ground” any RBox axiom into a set of GCIs involving existential restriction with nominal concepts.
Definition 7.1 (KB transformation). Let ∆ be a fixed domain and = (, , ℛ) be a KB under the fixed-domain semantics, where is an ABox, is a TBox, and ℛ is an RBox. The KB transformation is transΔ() = ⋃︁ transΔ( ), where:
∈ • transΔ( ) = { } for any ∈ ∪ . • transΔ( ) = ⋃︀∈Δ{∃.{} ⊑ ∃.{}} for any = ⊑ ∈ ℛ. • transΔ( ) = ⋃︀∈Δ{∃1...∃.{} ⊑ ∃(+1).{}} for any = 1∘ ...∘ ⊑ (+1) ∈ ℛ. • transΔ( ) = ⋃︀∈Δ{(∃.{}) ⊓ (∃.{}) ⊑ ⊥} for any = (, ) ∈ ℛ.
We observe that the new RBox-free KB is semantically equivalent to the original one. Lemma 7.2. Let ∆ be a fixed domain and = (, , ℛ) be a KB under the fixed-domain semantics and trans() be the transformation of (cf. Definition 7.1). trans() ≡ Δ holds.
While preserving the semantics of the original KB , one might notice that the new KB transΔ() is “bigger” than . Let be the size of some KB = (, , ℛ). Since transΔ( ) produces the same axiom for each axiom ∈ or ∈ , the size of the transformed ABox and TBox are equal to the size of the original ABox and TBox in . For an RBox axiom ∈ ℛ, transΔ( ) generates |∆ | number of transformed axioms. Then, the size of transΔ() is linearly bounded by × | ∆ |.
Given the knowledge base is in the transformed form, now we are ready to weaken the axioms in the knowledge base.
Definition 7.3 (Weakened knowledge base). Let ∆ be a fixed domain and be a transformed knowledge base, , be any two concept names, be a role name, and ∆ ′ = {1, ..., } be a set of individual elements with ∆ ′ ⊆ ∆ . Consider an axiom ∈ : (1) If is a general concept inclusion ⊑ , then the weakened GCI − Δ′ w.r.t ∆ ′ is ⊓ ¬{1} ⊓ ... ⊓ ¬{} ⊑ . (2) If is a concept assertion (), then the weakened concept assertion − Δ′ w.r.t ∆ ′ is ⊤() if ∈ ∆ ′ and () otherwise. (3) If is a role assertion (, ), then the weakened role assertion − Δ′ w.r.t ∆ ′ is (, ) if ∈ ∆ ′, and (, ) otherwise. The same rule also applies for any inverse role assertion − (, ).
The weakened knowledge base − Δ′ of w.r.t. ∆ ′ is − Δ′ = { − Δ′ | ∈ }, i.e., the set of all weakened axioms of .
Definition 7.3 describes the way to weaken any axiom in a KB given the individual set ∆ ′ ⊆ ∆ . We note that our definition of weakening is syntax-dependent. For two semantically equivalent knowledge bases, the weakening process might produce two non-equivalent results, even if we weaken both knowledge bases based on the exact same individuals. For instance, let ∆ = {, }, 1 = { ⊑ ∀., (), (, )} and 2 = {∃− . ⊑ , (), − (, )}. It can be checked that 1 ≡ Δ 2. Suppose we weaken the two KBs w.r.t. ∆ ′ = {}, then the results are 1 − Δ′ = {∃− . ⊓ ¬{} ⊑ , ⊤(), − (, )}.
− Δ′ = { ⊓ ¬{} ⊑ ∀., ⊤(), (, )} and 2 Consider a ∆ -interpretation ℐ such that ℐ = {, }, ℐ = {}, and ℐ = {(, )}. We observe that ℐ is a model of 1− Δ′ , but it is not a model of 2− Δ′ . This shows that 1− Δ′ and 2− Δ′ are not semantically equivalent. Next, we proceed by defining the notion of an exceptional individual set as follows.
Definition 7.4 (Exceptional individual set). Let and ′ be two knowledge bases. A set of exceptional individuals w.r.t. and ′ is a set Exc ⊆ ∆ such that − Exc ∪ ′ is consistent. We use ℰ (, ′) to denote the set of all sets of exceptional individuals w.r.t. and ′.
The following lemma shows that an exceptional individual set always exists w.r.t. any two consistent knowledge bases.
Lemma 7.5. Let ∆ =
{1, ..., } be a set of fixed-domain elements. For any two knowledge bases and ′ which are consistent and in the transformed forms (w.l.o.g), we have ℰ (, ′) ̸= ∅.
We show that our exceptional-individual-based weakening is monotonic in terms of ∆ entailment between two weakened knowledge bases. ∆ 1, ∆ 2 ⊆ ∆ be two sets of individuals. If ∆ 1 ⊆ ∆ 2, then − Δ1 |=Δ − Δ2 .
Lemma 7.6. Let be a knowledge base that is consistent and w.l.o.g in a transformed form. Let
Using the notion of the exceptional individual set, we present the individual-based revision operator for any two knowledge bases under the fixed-domain semantics. Whenever the incoming KB is inconsistent with the prior KB, the operator chooses one of the minimal exceptional individual sets so that the weakened prior KB is consistent with the incoming one. Definition 7.7 (Individual-based Revision). Let and ′ be two knowledge bases. An individualbased revision operator is a revision operator ∘ Δ such that for any knowledge base and ′: ∘ Δ ′ =
′ ︂{ transΔ()− (ℰ(,′)) ∪ ′ if ′ is consistent, otherwise, ( ) ∈ and there is no ∈ such that ⊂ ( ). where : ((∆)) → (∆) is a selection function retrieving subset-minimal elements, i.e.
The result of the revision ∘ Δ ′ is linearly bigger than the inputs and ′. The only size change is for the prior KB (i.e. to be transformed and weakened), while ′ remains unchanged. In the weakening process, the size of the axioms changes only whenever the GCIs are weakened. As (ℰ (, ′)) ⊆ ∆ , every GCI weakening adds at most Δ negated nominal concepts which represent exceptional individuals, where Δ = |∆ |. Hence, the size growth from transΔ() to transΔ()− (ℰ(,′)) is only linearly bounded by Δ. Overall, in the worst Note that 2Δ comes from transformation and weakening procedures. case scenario, when we revise an arbitrary knowledge base (with the size of ) by some KB ′ (with the size of ′ ), the result of the revision ∘ Δ ′ has the size of ( × 2Δ) + ′ .
This individual-based revision operator works on the syntactic level by weakening the axioms of the original knowledge base. Recall that the weakening process is syntax-dependent, therefore, this revision operation also depends on the syntax of the knowledge base. For two knowledge bases which are semantically equivalent but syntactically diferent, there is no guarantee that the revision would result in two equivalent weakened knowledge bases. For instance, assume we have ∆ =
{, } and two equivalent knowledge bases as previously defined 1 = { ⊑ ∀., (), (, )} and 2 = {∃− . ⊑ , (), − (, )}. Suppose we want to revise each 1 and 2 by an incoming KB 3 = {¬()}. Since both union 1∪3 and 2∪3 are inconsistent, we search for the minimal set of exceptional individuals that would make the weakened version of the two prior KBs consistent with 3. Then, we find (ℰ (1, 3)) = {} and (ℰ (2, 3)) = {}. The result of the revision 1 ∘ Δ 3 = { ⊓ ¬{} ⊑ ∀., ¬()}, while for the other one 2 ∘ Δ 3 = {∃− . ⊓ ¬{} ⊑ , (), ¬()}. Hence, we observe that 1 ∘ Δ 3 ̸≡ Δ 2 ∘ Δ 3. This observation can be considered as a counter example to show that the revision operator ∘ Δ fails to satisfy postulate (G4) which would guarantee syntaxindependence. For the satisfaction of the five remaining postulates, the following proposition shows positive results. and (G6).
Proposition 7.8. The individual-based change operator ∘ Δ satisfies postulates (G1)-(G3), (G5),
Syntax-based approaches for revision in DLs directly modify the axioms occurring in the
knowledge base. The modification may include dropping axioms [
To deal with the possibility of infinitely many models in DL knowledge bases under standard
semantics, many studies in semantic-based approaches [
* with Mod ( ∘ ′) ⊆ Mod (* ) and Mod (′) ⊂
semantics setting, both above issues can be resolved naturally. The most plausible (the minimal) models can be computed as the interpretations are finite and the revised knowledge base can be obtained as these models can be expressed into axioms. Table 3 summarizes the related approaches and compares them with our model-based and individual-based approach.
We have presented two approaches for revising knowledge bases in Description Logics under the fixed-domain semantics, where the models of the knowledge bases are guaranteed to be ifnite. For our model-based approach, we provided an axiom construction from a given set of interpretations where the axiom’s models are exactly the given interpretation set. We adapted KM’s semantic approach and provided a representation theorem for AGM revision operators in ℛℐ under fixed-domain semantics, as well as a concrete model-based revision operation using the notion of distance. The second approach is a novel revision technique for this particular DL by axiom weakening based on exceptional individual sets.
For future work, we want to find a new axiom construction from a given set of ∆
interpretations, as the current construction is arguably rather technical (cf. Equation (1)).
In addition, we also plan to implement both revision approaches in ASP (Answer Set
Programming) and evaluate their performances, following the use of ASP in earlier work for reasoning
[
Faiq Miftakhul Falakh was supported by the Indonesia Endowment Fund for Education (LPDP) Scholarship and by the Federal Ministry of Education and Research, Germany (BMBF) in the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI). Sebastian Rudolph is supported by the ERC through his Consolidator Grant 771779 (DeciGUT). We are grateful for the reviews and comments by Tim Lyon as well as the three anonymous reviewers. [26] M. Dalal, Investigations into a theory of knowledge base revision : Preliminary report, in:
AAAI, 1988. [27] M. M. Ribeiro, R. Wassermann, The ontology reviser plug-in for protégé, in: F. L. G. de Freitas, H. Stuckenschmidt, H. S. Pinto, A. Malucelli, Ó. Corcho (Eds.), Proceedings of the 3rd Workshop on Ontologies and their Applications, Salvador, Bahia, Brazil, October 26, 2008, volume 427 of CEUR Workshop Proceedings, CEUR-WS.org, 2008. URL: http: //ceur-ws.org/Vol-427/paper1.pdf. [28] D. Zheleznyakov, E. Kharlamov, W. Nutt, D. Calvanese, On expansion and contraction of dl-lite knowledge bases, J. Web Semant. 57 (2019). URL: https://doi.org/10.1016/j.websem. 2018.12.002. doi:10.1016/j.websem.2018.12.002. [29] V. B. Matos, R. Guimarães, Y. D. Santos, R. Wassermann, Pseudo-contractions as gentle repairs, in: C. Lutz, U. Sattler, C. Tinelli, A. Turhan, F. Wolter (Eds.), Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, volume 11560 of Lecture Notes in Computer Science, Springer, 2019, pp. 385–403. URL: https://doi.org/10.1007/978-3-030-22102-7_18. doi:10.1007/978-3-030-22102-7\_18. [30] F. Baader, F. Kriegel, A. Nuradiansyah, R. Peñaloza, Making repairs in description logics more gentle, in: M. Thielscher, F. Toni, F. Wolter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018, AAAI Press, 2018, pp. 319–328. URL: https://aaai.org/ocs/index.php/KR/KR18/paper/view/18056. [31] N. Troquard, R. Confalonieri, P. Galliani, R. Peñaloza, D. Porello, O. Kutz, Repairing ontologies via axiom weakening, in: S. A. McIlraith, K. Q. Weinberger (Eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, AAAI Press, 2018, pp. 1981–1988. URL: https://www.aaai.org/ ocs/index.php/AAAI/AAAI18/paper/view/17189. [32] Z. Wang, K. Wang, R. W. Topor, A new approach to knowledge base revision in dl-lite, in: M. Fox, D. Poole (Eds.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, AAAI Press, 2010. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1786. [33] L. Chang, U. Sattler, T. Gu, An abox revision algorithm for the description logic el_bot, in: M. Bienvenu, M. Ortiz, R. Rosati, M. Simkus (Eds.), Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014, volume 1193 of CEUR Workshop Proceedings, CEUR-WS.org, 2014, pp. 459–470. URL: http://ceur-ws. org/Vol-1193/paper_64.pdf. [34] Z. Wang, K. Wang, G. Qi, Z. Zhuang, Y. Li, Instance-driven tbox revision in dl-lite, in: M. Bienvenu, M. Ortiz, R. Rosati, M. Simkus (Eds.), Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014, volume 1193 of CEUR Workshop Proceedings, CEUR-WS.org, 2014, pp. 734–745. URL: http://ceur-ws. org/Vol-1193/paper_39.pdf. [35] G. D. Giacomo, M. Lenzerini, A. Poggi, R. Rosati, On the update of description logic ontologies at the instance level, in: Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, AAAI Press, 2006, pp. 1271–1276. URL: http://www.aaai.org/Library/AAAI/2006/aaai06-199.php.