A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for Arbitrary Monotonic Logics Preliminary Report?

Abstract

The AGM postulates by Alchourro´n, Ga¨rdenfors, and Makinson continue to represent a cornerstone in research related to belief change. We generalize the approach of Katsuno and Mendelzon (KM) for characterizing AGM base revision from propositional logic to the setting of (multiple) base revision in arbitrary monotonic logics. Our core result is a representation theorem using the assignment of total - yet not transitive - “preference” relations to belief bases. We also provide a characterization of all logics for which our result can be strengthened to preorder assignments (as in KM's original work).

-

The question how a rational agent should change her beliefs in the light of new information is crucial to AI systems. It gave rise to the area of belief change, which has been massively influenced by the AGM paradigm of Alchourro´ n, Ga¨rdenfors, and Makinson [ 2 ]. The AGM theory assumes that an agent’s beliefs are represented by a deductively closed set of formulas (aka belief set). A change operator for belief sets is required to satisfy appropriate postulates in order to qualify as a rational change operator. While the contribution of AGM is widely accepted as solid and inspiring foundation, it lacks support for certain relevant aspects: it provides no immediate solution on how to deal with multiple inputs (i.e., several formulae instead of just one), with bases (i.e., arbitrary finite collections of formulae, not necessarily deductively closed), or with the problem of iterated belief changes.

While the AGM paradigm is axiomatic, much of its success originated from operationalizations via representation theorems. Yet, most existing characterizations of AGM revision require the underlying logic to fulfil the AGM assumptions, including compactness, closure under standard connectives, deduction, and supra-classicality [ 18 ].

Leaving the safe grounds of these assumptions complicates matters; representation theorems do not easily generalize to arbitrary monotonic logics. This has sparked investigations into tailored characterizations of AGM belief change for specific logics, such as Horn logic [ 5 ], temporal logics [ 3 ], action logics [ 19 ], first-order logic [ 20 ], and description logics [ 15, 10, 7 ]. More general approaches to revision in non-classical logics were given by Ribeiro, Wassermann et al. [ 18,16,17 ], Delgrande et al. [ 6 ], Pardo et al. [ 14 ], or Aiguier et al. [ 1 ].

In this paper, we consider (multiple) revision of finite bases in arbitrary monotonic logics, refining and generalizing the popular approach by Katsuno and Mendelzon [ 12 ] (KM) for propositional belief base revision. KM start out from finite belief bases, assigning to each a total preorder on the interpretations, which expresses – intuitively speaking – a degree of “modelishness”. The models of the result of any AGM revision will then coincide with the preferred (i.e., preorder-minimal) models of the received information.

We generalize this idea of preferences over interpretations to the general setting, which necessitates adjusting the nature of the “modelishness-indicating” assignments: transitivity needs to be waived, whereas certain natural requirements regarding minimality need to be imposed. Our approach covers many popular logical formalisms like first-order and second-order predicate logic, description logics, Horn-logic, propositional logic with finite and infinite signature and many more. However, our approach does not apply to non-monotonic approaches.

The main contributions of this paper are the following3: – We extend KM’s semantic approach from the setting of singular revision in propositional logic to multiple revision of finite bases in arbitrary monotone logics. – For this setting, we provide a representation theorem characterizing AGM belief change operators via assignments. – We characterize those logics for which every AGM operator can even be captured by preorder assignments (i.e., in the classical KM way). In particular, this condition applies to all logics supporting disjunction over sentences.

The paper is organized as follows. We start by presenting the background on Tarskian logics and introduce our running example in Section 2. Section 3 basic notions of the approach by KM and representation theorem for propositional logic by KM. We prepare additional notions for our representation theorem in Section 4. Finally, in Section 5 we present our representation theorem for revision in arbitrary monotonic logics. In Section 6, we generalize the representation theorem by providing a one-to-one correspondence between relations and revision operators. In Section 7, we identify those logics, where every revision operator is representable by a preorder assignment (like for the original KM approach). Related work is discussed in Section 8 and we close the paper with conclusions in Section 9. 2

Preliminaries

We consider arbitrary logics L with monotonic model-theoretic semantics. Syntactically, such logics are described by a (possibly infinite) set L of sentences. A belief base 3 This paper does not contain any proofs. However, we like to refer the interested reader to [ 8 ], which contains proofs for the results presented here. K is then a finite4 subset of L, that is K 2 P fin(L). Unlike in other belief revision frameworks, we impose no further requirements on L (such as closure under certain operators).

A model theory for L is defined in the classical way through a (potentially infinite) class ⌦ of interpretations (also called worlds) and a binary relation ✏ between ⌦ and L where ! ✏ ' indicates that ! is a model of '. Hence, a logic L is specified by the triple (L, ⌦, ✏). We let J'K = {! 2 ⌦ | ! ✏ '} denote the set of all models of ' 2 L and obtain the models of a belief base K via JKK = T' 2K J'K. A sentence or belief base is consistent if it has a model and inconsistent otherwise. Logical entailment is defined as usual (overloading the symbol ”✏”) via models: for two belief bases K and K0 we say K entails K0 (written K ✏ K0) if JKK ✓ JK0K. Note that this definition of the semantics enforces that L is monotonic.5 As usual we write K ⌘ K 0 to express JKK = JK K 0 . A multiple base change operator for L is a function : Pfin(L) ⇥ P fin(L) ! P fin(L). For convenience, we drop “multiple” and speak of base change operators instead.

In the following, we provide an extension of an example given by Delgrande et al. [ 6 ] as a running example for illustrative purpose.

Example 1 (based on [ 6 ]). Let LEx = (LEx, ⌦ Ex, ✏Ex) be the logic defined by LEx = { 0, . . . , 5, '0, . . . , '4} and ⌦ Ex = {!0, . . . , !5}, with the models relation ✏Ex implicitly given by:

J iK = {!i} J'0K = {!0, . . . , !3} J'1K = {!1, !2} J'2K = {!2, !3} J'3K = {!3, !1}

J'4K = {!1, . . . , !5} Since defined in the classical model-theoretic way, LEx is a monotonic logic. Note that logic LEx has no connectives.

We will endow the interpretation space ⌦ with some structure. A binary relation over ⌦ is total if, for any !1, !2 2 ⌦ , at least one of !1 !2 or !2 !1 holds. We write !1 !2 for !1 !2 and !2 6 !1. For ⌦ 0 ✓ ⌦ , ! 2 ⌦ 0 is called -minimal in ⌦ 0 if ! !0 for all !0 2 ⌦ 0.6 We let min(⌦ 0, ) denote the set of -minimal interpretations in ⌦ 0. We call a preorder, if it is transitive and reflexive. 3

Base Revision in Propositional Logic

A well-known and by now popular characterization of base revision has been described by Katsuno and Mendelzon [ 12 ] for the special case of propositional logic. KM’s ap4 The term base is sometimes also used for arbitrary sets [ 9 ]. We follow the mainstream in computer science and assume finite bases. 5 From here on, when simply speaking of “logic”, we always assume the classical, monotonic setting described here. Moreover, we also assume a logic L = (L, ⌦, ✏) as given and fixed. 6 If is total, this definition is equivalent to the absence of any !00 2 ⌦ 0 with !00 !. proach hinges on several properties of propositional logics. To start with, any propositional belief base K can be written as a single propositional formula V↵ 2K ↵ . Consequently, in their approach, belief bases are represented by single formulas. They provide the following set of postulates, derived from the AGM revision postulates, where ', '1, '2, ↵ , and are propositional formulae and is a base change operator: (KM1) ' ↵ ✏ ↵ . (KM2) If ' ^ ↵ is consistent, then ' ↵ ⌘ ' ^ ↵ . (KM3) If ↵ is consistent, then ' ↵ is consistent. (KM4) If '1 ⌘ '2 and ↵ ⌘ , then '1 ↵ ⌘ '2 (KM5) (' ↵ ) ^ ✏ ' (↵ ^ ). (KM6) If (' ↵ ) ^ is consistent, then ' (↵ ^

One key contribution of KM is to provide an alternative characterization of those propositional base revision operators satisfying (KM1)–(KM6) by model-theoretic means, i.e. through comparisons between propositional interpretations. In the following, we present their results in a formulation that facilitates later generalization. One central notion for the characterization is the notion of faithful assignment.

Definition 1 (assignment, faithful). An assignment (for L) is a function (.): Pfin(L) ! P(⌦ ⇥ ⌦ ) that assigns to each belief base K a total binary relation K over ⌦ . An assignment (.) is called faithful if it satisfies the following conditions: (F1) If !, !0 ✏ K, then ! K !0 does not hold. (F2) If ! ✏ K and !0 6✏ K, then ! K !0. (F3) If K ⌘ K 0, then K = K0 .

An assignment (.) is called a preorder assignment if

base K 2 P fin(L).

K is a preorder for every belief

Intuitively, faithful assignments provide information which of the two interpretations is “closer to K-modelhood”. Consequently, the actual K-models are K-minimal. The next definition captures the idea of an assignment adequately representing the behaviour of a revision operator.

Definition 2 (compatible). A base change operator is called compatible with some assignment (.) if it satisfies JK K = min(J K, K) for all belief bases K and .

With these notions in place, KM’s representation result can be smoothly expressed as follows:

Theorem 1 (Katsuno and Mendelzon [12]). In propositional logic, a base change

operator satisfies (KM1)–(KM6) if and only if is compatible with some faithful preorder assignment.

In the next section, we present additional notions, which we will employ for a representation result in fashion of Theorem 1 in the general setting of monotonic logics. 4

The Approach

In this section, we prepare our main result by transferring KM’s concepts from propositional logic to our general setting. As mentioned, KM’s characterization hinges on features of propositional logic that do not generally hold. So far, attempts to find similarly elegant formulations for less restrictive logics have made good progress to the benefit of the understanding the nature of AGM revision, yet, none of them capture the very general case considered here (cf. Section 8).

For our presentation, we use the following straightforward reformulation of (KM1)– (KM6): (G1) K ✏ . (G2) If JK [ K 6= ; then K ⌘ K [ (G3) If J K 6= ; then JK K 6= ; . (G4) If K1 ⌘ K 2 and 1 ⌘ 2 then K1 (G5) (K 1) [ 2 ✏ K ( 1 [ 2). (G6) If J(K 1) [ 2K 6= ; then K . 1 ⌘ K 2

2. ( 1 [ 2) ✏ (K

This set of postulates was first given by Qi et al. [ 15 ] in the context of belief base revision specifically for Description Logics, yet, the formulation is generic and perfectly suitable for our general setting, too. We can see that (G1)–(G6) tightly correspond to (KM1)–(KM6), respectively. One advantage of this presentation is that it does not require L to support conjunction (while, of course, conjunction on the sentence level is still implicitly supported via set union of bases).

When switching from the setting of propositional to arbitrary logics, two obstacles become apparent.

Observation 1 Transitivity in the relation, as required in Theorem 1, is a too strict property for certain logics.

Example 2 (continuation of Example 1). Let KEx = { 0} and let Ex be the base change operator defined as follows: KEx Ex = >:>>>>>>> 8 <>>>>>>>> KEx [ [ { [ { [ { [ {

if JKEx [ 4} if JKEx [ 1} if JKEx [ 2} if JKEx [

K 6= ; , K=; and J{ 4} [ K=; and J{ 1} [

K=; and J{ 2} [ 3} if JKEx [ K=; and J{ 3} [

if none of the above applies.

For all K0 with K0 ⌘ K Ex we define K0 we define

K0 = ( 0

K [ = KEx if K0 [ otherwise.

K 6= ; , K 6= ; and J{ 3} [ K 6= ; and J{ 1} [ K 6= ; and J{ 2} [

K = ; , K = ; ,

K = ; , and for all K0 with K0 6⌘ K Ex consistent For all K0 with K0 6⌘ K Ex, there is no violation of the postulates (G1)–(G6) since we obtain a full meet revision known to satisfy (G1)–(G6) [ 11 ]. For the case of K0 ⌘ K Ex, we show the satisfaction of (G1)–(G6) using Theorem 3 in Section 6. Now assume there were a preorder assignment (.) compatible with Ex. This means that for all bases K and from P(LEx), the relation K is a preorder and JK Ex K = min(J K, KEx ). Now consider 1 = {'1}, 2 = {'2}, and 3 = {'3}. From the definition of Ex and compatibility, we obtain:

JKEx Ex 1K = {!1} = min(J 1K, JKEx Ex 2K = {!2} = min(J 2K, JKEx Ex 3K = {!3} = min(J 3K,

KEx ) KEx ) KEx ) Recall that J 1K = {!1, !2}, J 2K = {!2, !3}, and J 3K = {!3, !1}. Yet, this implies !1 KEx !2, !2 KEx !3, and !3 KEx !1, contradicting the assumption that KEx is transitive. Hence it cannot be a preorder.

In fact, it has been observed before that the incompatibility between transitivity and KM’s approach already arises for propositional Horn logic [ 5 ]. However, for our result, we need to retain totality as well as a new weaker property (which would come for free with transitivity present) defined next.

Definition 3 (min-retractive). A binary relation over ⌦ is called min-retractive (for L!0) 2if fmorine(vJeryK, 2)P. fin(L) and !0, ! 2 J K with !0 ! and ! 2 min(J K, ) holds

In particular, min-retractivity prevents elements lying on a strict cycle being equivalent to minimal elements.

Observation 2 For arbitrary monotonic logics, the minimum from Definition 2, required in Theorem 1, might be empty.

Thus, one missing ingredient when going to the general case is that of min-completeness, defined next.

Definition 4 (min-complete). A binary relation over ⌦ is called min-complete (for L) if for every 2 P fin(L) with J K 6= ; holds min(J K, ) 6= ; .

In the special case of being transitive and total, min-completeness trivially holds whenever ⌦ is finite (as, e.g., in the case of propositional logic). In the infinite case, however, it might need to be explicitly imposed, as already noted earlier [ 6 ] (cf. also the notion of limit assumption by Lewis [ 13 ]). If is total but not transitive, mincompleteness can be violated even in the finite setting through strict cyclic relationships.

We conveniently unite the two properties into one notion.

Definition 5 (min-friendly). A binary relation over ⌦ is called min-friendly (for L) if it is both min-retractive and min-complete. An assignment (.): Pfin(L) ! P (⌦ ⇥ ⌦ ) is called min-friendly if K is min-friendly for all K 2 P fin(L). 5

The Representation Theorem

We are now generalizing KM’s representation theorem from propositional to monotonic logics, by employing the notion of compatible min-friendly faithful assignments. Theorem 2. A base change operator satisfies (G1)–(G6) iff it is compatible with some min-friendly faithful assignment.

In the following, we provide a canonical way of obtaining an assignment for a given revision operator. Then, we present our line of arguments that our construction indeed yields a min-friendly faithful assignment that is compatible with the revision operator.

Unfortunately, established methods for obtaining a canonical encoding of the revision strategy of , like the elegant one by Darwiche and Pearl [ 4 ], do not generalize well beyond propositional logic. We suggest the following construction, which we consider one of this paper’s core contributions.

K Definition 6. Let be a base change operator and K 2 P fin(L) a belief base. The relation over ⌦ is defined by !1

K !2 iff for all 2 P fin(L) with !1, !2 ✏ holds !1 ✏ K or !2 6✏ K .

Let (.): Pfin(L) ! P (⌦ ⇥ ⌦ ) denote the mapping K 7!

Intuitively, according to the relation K, an interpretation !1 is “at least as Kmodelish as” an interpretation !2 if every change either justifies that !1 is more preferred than !2 or the change yields no information about the preference. This construction is strong enough for always obtaining a relation that is total and reflexive. Lemma 1 (totality). If satisfies (G5) and (G6), the relation reflexive) for every K 2 P fin(L).

Next comes an auxiliary lemma about belief bases and Lemma 2. Let satisfy (G5) and (G6) and let K 2 P fin(L). (a) If !1 6 K !2, then !2

!2 ✏ K and !1 6✏ K (b) If there is a with !1, !2 ✏ (c) If there is a with !1, !2 ✏

K !1 and there exists some .

with !1, !2 ✏

as well as such that !1 ✏ K and !1 ✏ K

, then !1 and !2 6✏ K

K !2. , then !1

Lemma 2 gives rise to the following lemma, which present how the relation connects the notions presented in Section 4 and the postulates (G1) – (G6). Lemma 3. Let satisfy (G5) and (G6). (a) If satisfies (G1) and (G3), then it is compatible with (.). (b) If satisfies (G1) and (G3), then K is min-friendly for every K 2 P fin(L). (c) If satisfies (G2) and (G4), the assignment (.) is faithful.

The previous lemma can finally be put to use to show that the construction of (.) according to Definition 6 yields an assignment with the desired properties.

Proposition 1. If satisfies (G1)–(G6), then

compatible with . (.) is a min-friendly faithful assignment Example 3 (continuation of Example 2). Applying Definition 6 to K and Ex yields the following relation KEx on ⌦ Ex (where ! KEx !0 denotes ! KEx !0 and !0 6 KEx !): !i !0 !1 !2 !3 !4 !i

KEx !i, 0  i  5 KEx !i, 1  i  5 Ex !2 K Ex !3 K Ex !1 K KEx !i, i 2 { 1, 2, 3, 5}

KEx !5, 0  i  4

Observe that KEx is not transitive, since !1, !2, !3 form a circle. Yet, one can easily verify that KEx is a total and min-friendly relation. In particular, as ⌦ Ex is finite, min-completeness is directly given. Moreover, there is no belief base 2 P (LEx) such ts!hu1ac,th!tha2esraientuidsat!sioo3mnaecnod!utl2hd/eamrepipwne(oa,rulidn bKEeKxEa)xabinefdliae!ifn0bt2 earspmereinta(st,iaotinsfi!KeEdwx)oinwulaidtlhlbt!ehesKeKEEixxn-te!eqr0pu.riNveaotalteteinotthntasot, e.g., if ! = !5 would be equal to !1, !2 and !3, and J K = {!1, !2, !3, !5}. However, this is not the case in KEx and such a belief base does not exist in LEx. Therefore, the relation KEx is min-retractive. 6 Theorem 2 establishes the correspondence between operators and assignments under the assumption that is known to exist. Toward a full characterization, we provide an additional condition on assignments, capturing operator existence.

A semantic base change function is a mapping R : Pfin(L) ⇥ P fin(L) ! P (⌦ ). A base change operator is said to implement R if for all K, 2 P fin(L) holds JK K = R(K, ). An assignment (.) is said to represent R if min(J K, K) = R(K, ) for all K, 2 P fin(L).

For the existence of an operator, it will turn out to be essential that any minimal model set of a belief base obtained from an assignment corresponds to some belief base, a property which is formalized by the following notion.

Definition 7 (min-expressible). Given a logic L = (L, ⌦, ✏), a binary relation over ⌦ is called min-expressible if for each 2 P fin(L) there exists a belief base B, 2 P fin(L) such that JB, K = min(J K, ). An assignment (.) will be called min-expressible, if for each K 2 P fin(L), K is min-expressible. Given a min-expressible assignment (.), let (.) denote the base change operator defined by K (.) = B, K .

We find the following abstract relation between expressibility, assignments and operators. Theorem 3. Let L be a logic and let R be a semantic base change function for L. Then R is implemented by a base change operator satisfying (G1)–(G6) iff R is represented by a min-expressible and min-friendly faithful assignment.

Continuing our running example, we will now observe that expressible relation.

Ex is also a minK iEsxcaommppleat4ibl(ecownittihnuaEtixo,ni.oef. EJKxampleK 3=). mCionn(sJideKr, agKaEixn). TKhExu,s,anfodroebvseerryvebethliaetf bKaEsxe fTahite2hoPfruelm(mLi3En-xge)ux,aptrrhaeenstsmeiebislneiumasnudtmhmatmini-nEfr(xi,esnadtilKsyfiEaxes)ssiy(gGine1lmd)–se(naGt.6se),t aexspwreessciabnleebxytenadbeliKeEfxbtaosea.

Some colleagues argue that revising bases instead of belief sets calls for syntaxdependence and therefore (G4) should be discarded [ 9 ]. Without positioning ourselves in this matter, we would like to emphasize that our characterizations from Theorem 2 and Theorem 3 can be easily adjusted to a more syntax-sensitive setting: a careful inspection of the results shows that the results remain valid upon dropping (G4) from the postulates and (F3) from the faithfulness definition. 7

Total Preorder Representability

We identify those logics for which every revision operator is representable by a total preorder assignment.

Definition 8 (total preorder representable). A base change operator is called total

preorder representable if there is a min-complete faithful preorder assignment compatible with .

The following setting, describing a relationship between belief bases, will turn out to be the one and only reason to prevent total preorder representability. Definition 9 (critical loop). Let L = (L, ⌦, ✏) be a logic. Three bases 0, 1, 2 2 P fin(L) form a critical loop for L if there exist K, 00, 10, 20 2 P fin(L) such that (1) JK [ 0K = JK [ 1K = JK [ 2K = ; (2) ; 6 = J i0K ✓ (J iK \ J i 1K) \ J i 2K with i 2 { 0, 1, 2} (where is addition mod 3) (3) for any 2 P fin(L) with J i0 [ K 6= ; for all 0 i 2 exists a 0 2 P fin(L) with ; 6 = J 0K ✓ J K\(J 0K [ J 1K [ J 2K).

We note that Definition 9 generalizes a known example for non-total preorder representability in Horn logic [ 5,6 ].

Proposition 2. If L exhibits a critical loop, then there is a base change operator for L satisfying (G1)–(G6) that is not total preorder representable.

We call pairs of interpretations detached when the base change operator gives no hint about how to order them. Definition 10. A pair (!, !0) 2 ⌦ ⇥ ⌦ is called detached from in K, if !, !0 6✏ K for all 2 P fin(L).

Detached pairs will be helpful when proving the missing part of the correspondence between critical loop and total preorder representability. In particular, violations of transitivity in K from Definition 6 always contain a detached pair.

Lemma 4. Assume L does not admit a critical loop and satisfies (G1)–(G6). If !0 !1 and !1 K !2 with !0 6 K !2, then (!0, !1) or (!1, !2) is detached from in K. K

Lemma 4 allows us to complete the correspondence between critical loops and total preorder representability.

Theorem 4. A logic L = (L, ⌦, ✏) does not admit a critical loop if and only if every base change operator for L satisfying (G1)–(G6) is total preorder representable.

We close this section with an implication of Theorem 4. A logic L = (L, ⌦, ✏) is called disjunctive, if for every two bases 1, 2 2 P fin(L) there is a base 1_ 2 2 Pfin(L) such that J 1_ 2K = J 1K [ J 2K. This includes the case of any logic allowing for disjunction on the sentence level, i.e., when for every , 2 L exists some _ 2 L such that J _ K = J K [ J K, because then 1_ 2 can be obtained as { _ | 2 1, 2 2}.

Corollary 1. In a disjunctive logic, every belief change operator satisfying (G1)–(G6) is total preorder representable. 8

Related Work

We are aware of two closely related approaches for revising belief bases (or sets) in settings beyond propositional logic, both proposing model-based frameworks for belief revision without fixing a particular logic or the internal structure of interpretations, and characterizing revision operators via minimal models a` la KM with some additional assumptions.

Delgrande et al. [ 6 ] add additional restrictions both for the interpretations (aka possible worlds) as well as for the postulates. On the interpretation side, unlike us, they restrict their number to be finite. Also they impose a constraint called regularity which serves the very same purpose on their preorders as min-expressibility serves on our total relations. As for the postulates, they extend the basic AGM postulates with a new one, called (Acyc), with the goal to exclude cyclic preference situations (our “critical loops”). Yet, by imposing this postulate, they rule out some cases of AGM belief revision that we can cover with our framework, which works with (and characterizes) the pristine AGM postulates.

Aiguier et al. [ 1 ] consider AGM-like belief base revision with possibly infinite sets of interpretations. Moreover, like us, they argue in favor of dropping the requirement that assignments have to yield preorders. However, they rule out (KM4)/(G4) from the postulates, thus immediately restricting attention to the syntax-dependent case. Also, alike Delgrande et al.’s, their characterization imposes an additional postulate. On another note, Aiguier et al. consider some bases, that actually do have models, as inconsistent (and thus in need of revision), which in our view is at odds with the foundational assumptions of belief revision.

Conclusion

We presented a characterization of AGM belief base revision in terms of preference assignments, adapting the approach by KM. Contrary to prior work, our result requires no adjustment of the AGM postulates themselves and yet applies to arbitrary monotonic logics with possibly infinite model sets. While we need to allow for non-transitive preference relations, we also precisely identify the logics where the preference relations can be guaranteed to be preorders as in the original KM result. In particular, this holds for all logics featuring disjunction.

As one of the avenues for future work, we will consider iterated revision. To this end, our aim is to advance the line of research by Darwiche and Pearl [ 4 ] to more general logics. Finally, we will also be working on concrete realizations of the approach presented here in popular KR formalisms such as ontology languages. Acknowledgments. Faiq Miftakhul Falakh is supported by Indonesia Endowment Fund for Education (LPDP) Scholarship. Sebastian Rudolph is supported by the ERC through his Consolidator Grant 771779 (DeciGUT). Kai Sauerwald is supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Grant BE 1700/10-1 awarded to Christoph Beierle as part of the priority program ”Intentional Forgetting in Organizations” (SPP 1921). The authors also thank Christoph Beierle for his helpful comments and support.

References

1. Aiguier , M. , Atif , J. , Bloch , I. , Hudelot , C. : Belief revision, minimal change and relaxation: A general framework based on satisfaction systems, and applications to description logics . Artificial Intelligence 256 , 160 - 180 ( 2018 )

2. Alchourro´n, C.E. , Gardenfors , P. , Makinson , D. : On the logic of theory change: Partial meet contraction and revision functions . Journal of Symbolic Logic 50 ( 22 ), 510 - 530 ( 1985 )

3. Bonanno , G.: Axiomatic characterization of the AGM theory of belief revision in a temporal logic . Artificial Intelligence 171 ( 2-3 ), 144 - 160 ( 2007 )

4. Darwiche , A. , Pearl , J. : On the logic of iterated belief revision . Artificial Intelligence 89 , 1 - 29 ( 1997 )

5. Delgrande , J.P. , Peppas , P. : Belief revision in Horn theories . Artificial Intelligence 218 , 1 - 22 ( 2015 )

6. Delgrande , J.P. , Peppas , P. , Woltran , S.: General belief revision . J. ACM 65 ( 5 ) ( Sep 2018 )

7. Dong , T. , Duc , C.L. , Lamolle , M. : Tableau-based revision for expressive description logics with individuals . Journal of Web Semantics 45 , 63 - 79 ( 2017 )

8. Falakh , F.M. , Rudolph , S. , Sauerwald , K. : A general Katsuno-Mendelzon-style characterization of AGM belief base revision for arbitrary monotonic logics . CoRR abs/2104 .14512 ( 2021 ), https://arxiv.org/abs/2104.14512

9. Ferme´, E.L. , Hansson , S.O. : Belief Change - Introduction and Overview . Springer Briefs in Intelligent Systems , Springer ( 2018 )

10. Halaschek-Wiener , C. , Katz , Y. : Belief base revision for expressive description logics . In: Grau, B.C. , Hitzler , P. , Shankey , C. , Wallace , E. (eds.) Proceedings of the OWLED*06 Workshop on OWL: Experiences and Directions. CEUR Workshop Proceedings , vol. 216 . CEUR-WS.org ( 2006 ), http://ceur-ws. org/ Vol- 216 /submission 21.pdf

11. Hansson , S.O.: A Textbook of Belief Dynamics: Theory Change and Database Updating . Springer ( 1999 )

12. Katsuno , H. , Mendelzon , A.O. : Propositional knowledge base revision and minimal change . Artificial Intelligence 52 ( 3 ), 263 - 294 ( 1991 )

13. Lewis , D.K. : Counterfactuals . Harvard University Press, Cambridge, Massachusetts ( 1973 )

14. Pardo , P. , Dellunde , P. , Godo , L. : Base belief change for finitary monotonic logics . In: Meseguer, P. , Mandow , L. , Gasca , R.M. (eds.) Current Topics in Artificial Intelligence, 13th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2009. Lecture Notes in Computer Science , vol. 5988 , pp. 81 - 90 . Springer ( 2009 )

15. Qi , G. , Liu , W. , Bell , D.A. : Knowledge base revision in description logics . In: Fisher, M., van der Hoek , W., Konev , B. , Lisitsa , A . (eds.) Logics in Artificial Intelligence . pp. 386 - 398 . Springer Berlin Heidelberg ( 2006 )

16. Ribeiro , M.M. : Belief Revision in Non-Classical Logics . Springer Briefs in Computer Science, Springer ( 2013 )

17. Ribeiro , M.M. , Wassermann , R.: Minimal change in AGM revision for non-classical logics . In: Baral, C. , Giacomo , G.D. , Eiter , T. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference , KR 2014 . AAAI Press ( 2014 ), http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/8008

18. Ribeiro , M.M. , Wassermann , R. , Flouris , G. , Antoniou , G.: Minimal change: Relevance and recovery revisited . Artificial Intelligence 201 , 59 - 80 ( 2013 )

19. Shapiro , S. , Pagnucco , M. , Lespe´rance, Y., Levesque , H.J.: Iterated belief change in the situation calculus . Artificial Intelligence 175 ( 1 ), 165 - 192 ( 2011 )

20. Zhuang , Z. , Wang , Z. , Wang , K. , Delgrande , J.P.: A generalisation of AGM contraction and revision to fragments of first-order logic . J. Artif. Intell. Res . 64 , 147 - 179 ( 2019 )