=Paper=
{{Paper
|id=Vol-2961/paper_5
|storemode=property
|title=A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for Arbitrary Monotonic Logics (Preliminary Report)
|pdfUrl=https://ceur-ws.org/Vol-2961/paper_5.pdf
|volume=Vol-2961
|authors=Faiq Miftakhul Falakh,Sebastian Rudolph,Kai Sauerwald
|dblpUrl=https://dblp.org/rec/conf/ki/FalakhRS21
}}
==A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for Arbitrary Monotonic Logics (Preliminary Report)==
https://ceur-ws.org/Vol-2961/paper_5.pdf
Proceedings of the 7th Workshop on Formal and Cognitive Reasoning
A Katsuno-Mendelzon-Style Characterization of AGM
Belief Base Revision for Arbitrary Monotonic Logics
Preliminary Report?
Faiq Miftakhul Falakh1 , Sebastian Rudolph1 , and Kai Sauerwald2
1
Computational Logic Group, TU Dresden, Germany
{faiq miftakhul.falakh, sebastian.rudolph}@tu-dresden.de
2
Knowledge Based Systems Group, FernUniversität in Hagen, Germany
kai.sauerwald@fernuni-hagen.de
Abstract. The AGM postulates by Alchourrón, Gärdenfors, and Makinson con-
tinue to represent a cornerstone in research related to belief change. We generalize
the approach of Katsuno and Mendelzon (KM) for characterizing AGM base revi-
sion from propositional logic to the setting of (multiple) base revision in arbitrary
monotonic logics. Our core result is a representation theorem using the assign-
ment 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).
1 Introduction
The question how a rational agent should change her beliefs in the light of new infor-
mation is crucial to AI systems. It gave rise to the area of belief change, which has been
massively influenced by the AGM paradigm of Alchourrón, Gä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 sup-
port 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 opera-
tionalizations via representation theorems. Yet, most existing characterizations of AGM
revision require the underlying logic to fulfil the AGM assumptions, including compact-
ness, 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 in-
vestigations into tailored characterizations of AGM belief change for specific logics,
?
This is a preliminary report. Generalizations of the announced results and their proofs will be
the subject of a forthcoming journal article.
Copyright c 2021 for this paper by its authors. Use permitted under
Creative Commons License Attribution 4.0 International (CC BY 4.0).
48
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
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, as-
signing 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 mini-
mality need to be imposed. Our approach covers many popular logical formalisms like
first-order and second-order predicate logic, description logics, Horn-logic, proposi-
tional 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 propo-
sitional 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. Syntacti-
cally, 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.
49
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
K is then a finite4 subset of L, that is K 2 Pfin (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 T the set of all models of ' 2 L and
obtain the models of a belief base K via JKK = '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 ✓ JK0 K. Note that this definition of the semantics
enforces that L is monotonic.5 As usual we write K ⌘ K0 to express JKK = JK0 K. A
multiple base change operator for L is a function : Pfin (L) ⇥ Pfin (L) ! Pfin (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 im-
plicitly given by:
J i K = {!i }
J'0 K = {!0 , . . . , !3 }
J'1 K = {!1 , !2 }
J'2 K = {!2 , !3 }
J'3 K = {!3 , !1 }
J'4 K = {!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 ap-
4
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 !.
50
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
proach hinges on several properties of propositional logics. To start with,
V any proposi-
tional belief base K can be written as a single propositional formula ↵2K ↵. Conse-
quently, in their approach, belief bases are represented by single formulas. They pro-
vide 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 ⌘ K0 , then K = K0 .
An assignment (.) is called a preorder assignment if K is a preorder for every belief
base K 2 Pfin (L).
Intuitively, faithful assignments provide information which of the two interpreta-
tions 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 be-
haviour 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 rep-
resentation result in fashion of Theorem 1 in the general setting of monotonic logics.
51
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
4 The Approach
In this section, we prepare our main result by transferring KM’s concepts from propo-
sitional 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 sim-
ilarly 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 ⌘ K2 and 1 ⌘ 2 then K1 1 ⌘ K2 2.
(G5) (K 1 ) [ 2 ✏ K ( 1 [ 2 ).
(G6) If J(K 1 ) [ 2 K 6= ; then K ( 1 [ 2 ) ✏ (K 1) [ 2.
This set of postulates was first given by Qi et al. [15] in the context of belief base re-
vision 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 re-
quire 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:
8
>
> KEx [ if JKEx [ K 6= ;,
>
>
>
> [ { 4 } if JKEx [ K=; and J{ 4 } [ K 6= ;,
>
>
< [ { } if JK [ K=; and J{ } [ K 6= ; and J{ } [ K = ;,
1 Ex 1 3
KEx Ex =
> [ { 2 } if JKEx [ K=; and J{ 2 } [ K 6= ; and J{ 1 } [ K = ;,
>
>
>
>
> [ { 3 } if JKEx [ K=; and J{ 3 } [ K 6= ; and J{ 2 } [ K = ;,
>
>
:
if none of the above applies.
For all K0 with K0 ⌘ KEx we define K0 = KEx and for all K0 with K0 6⌘ KEx
we define (
0 K0 [ if K0 [ consistent
K =
otherwise.
For all K0 with K0 6⌘ KEx , 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 ⌘ KEx ,
52
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
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 1 K = {!1 } = min(J 1 K, KEx )
JKEx Ex 2 K = {!2 } = min(J 2 K, KEx )
JKEx Ex 3 K = {!3 } = min(J 3 K, KEx )
Recall that J 1 K = {!1 , !2 }, J 2 K = {!2 , !3 }, and J 3 K = {!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) if for every 2 Pfin (L) and ! 0 , ! 2 J K with ! 0 ! and ! 2 min(J K, ) holds
! 0 2 min(J K, ).
In particular, min-retractivity prevents elements lying on a strict cycle being equiv-
alent to minimal elements.
Observation 2 For arbitrary monotonic logics, the minimum from Definition 2, re-
quired 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 Pfin (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, min-
completeness 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 Pfin (L).
53
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
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 revi-
sion 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.
Definition 6. Let be a base change operator and K 2 Pfin (L) a belief base. The
relation K over ⌦ is defined by
!1 K !2 iff for all 2 Pfin (L) with !1 , !2 ✏ holds !1 ✏ K or !2 6✏ K .
Let (.) : Pfin (L) ! P(⌦ ⇥ ⌦) denote the mapping K 7! K.
Intuitively, according to the relation K , an interpretation !1 is “at least as K-
modelish as” an interpretation !2 if every change either justifies that !1 is more pre-
ferred than !2 or the change yields no information about the preference. This construc-
tion is strong enough for always obtaining a relation that is total and reflexive.
Lemma 1 (totality). If satisfies (G5) and (G6), the relation K is total (and hence
reflexive) for every K 2 Pfin (L).
Next comes an auxiliary lemma about belief bases and K.
Lemma 2. Let satisfy (G5) and (G6) and let K 2 Pfin (L).
(a) If !1 6 K !2 , then !2 K !1 and there exists some with !1 , !2 ✏ as well as
!2 ✏ K and !1 6✏ K .
(b) If there is a with !1 , !2 ✏ such that !1 ✏ K , then !1 K !2 .
(c) If there is a with !1 , !2 ✏ and !1 ✏ K and !2 6✏ K , then !1 K !2 .
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 Pfin (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.
54
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
Proposition 1. If satisfies (G1)–(G6), then (.) is a min-friendly faithful assignment
compatible with .
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 K
Ex
!i , 0 i 5
!0 K
Ex
!i , 1 i 5
!1 K
Ex
!2
!2 K
Ex
!3
!3 K
Ex
!1
!4 K
Ex
!i , i 2 {1, 2, 3, 5}
!i K
Ex
!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
that there is some ! 2/ min( , KEx ) and ! 0 2 min( , KEx ) with ! KEx ! 0 . Note that
such a situation could appear in KEx if a interpretation ! would be KEx -equivalent to
!1 , !2 and !3 and there would be a belief base satisfied in all these interpretations,
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 Abstract Representation Theorem
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) ⇥ Pfin (L) ! P(⌦). A
base change operator is said to implement R if for all K, 2 Pfin (L) holds JK K =
R(K, ). An assignment (.) is said to represent R if min(J K, K ) = R(K, ) for
all K, 2 Pfin (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 Pfin (L) there exists a belief base
B , 2 Pfin (L) such that JB , K = min(J K, ). An assignment (.) will be called
min-expressible, if for each K 2 Pfin (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 op-
erators.
55
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
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 K
Ex
is also a min-
expressible relation.
Example 4 (continuation of Example 3). Consider again KEx , and observe that KEx
is compatible with Ex , i.e. JK K = min(J K, KEx ). Thus, for every belief base
2 P(LEx ), the minimum min( , KEx ) yields a set expressible by a belief base.
Theorem 3 guarantees us that Ex satisfies (G1)–(G6), as we can extend KEx to a
faithful min-expressible and min-friendly assignment.
Some colleagues argue that revising bases instead of belief sets calls for syntax-
dependence 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 in-
spection 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 compat-
ible 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 Pfin (L) form a critical loop for L if there exist K, 00 , 10 , 20 2 Pfin (L) such that
(1) JK [ 0 K = JK [ 1 K = JK [ 2 K = ;
(2) ; =
6 J i0 K ✓ (J i K \ J i 1 K) \ J i 2 K with i 2 {0, 1, 2} (where is addition mod 3)
(3) for any 2 Pfin (L) with J i0 [ K 6= ; for all 0i2 exists a 0 2 Pfin (L) with
;=6 J 0 K ✓ J K\(J 0 K [ J 1 K [ J 2 K).
We note that Definition 9 generalizes a known example for non-total preorder rep-
resentability 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.
56
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
Definition 10. A pair (!, ! 0 ) 2 ⌦ ⇥ ⌦ is called detached from in K, if !, ! 0 6✏ K
for all 2 Pfin (L).
Detached pairs will be helpful when proving the missing part of the correspondence be-
tween critical loop and total preorder representability. In particular, violations of tran-
sitivity 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 K
!1 and !1 K !2 with !0 6 K !2 , then (!0 , !1 ) or (!1 , !2 ) is detached from in 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 Pfin (L) there is a base 1 _ 2 2
Pfin (L) such that J 1 _ 2 K = J 1 K [ J 2 K. 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 à la KM with some additional
assumptions.
Delgrande et al. [6] add additional restrictions both for the interpretations (aka pos-
sible 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 to-
tal 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 revi-
sion 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 an-
other note, Aiguier et al. consider some bases, that actually do have models, as incon-
sistent (and thus in need of revision), which in our view is at odds with the foundational
assumptions of belief revision.
57
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
9 Conclusion
We presented a characterization of AGM belief base revision in terms of preference as-
signments, 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 pref-
erence 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. Alchourró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 characteri-
zation of AGM belief base revision for arbitrary monotonic logics. CoRR abs/2104.14512
(2021), https://arxiv.org/abs/2104.14512
9. Fermé, 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
58
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for
Arbitrary Monotonic Logics (Preliminary Report)
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 Sci-
ence, 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., Lespérance, Y., Levesque, H.J.: Iterated belief change in the sit-
uation 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)
59