The AGM postulates by Alchourrón, Gä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).
? This is a preliminary report. Generalizations of the announced results and their proofs will be the subject of a forthcoming journal article.
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 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 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.
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 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 K 0 we say
Note that this definition of the semantics enforces that L is monotonic. 5 As usual we write K ⌘ K 0 to express JKK = JK 0 K. A multiple base change operator for L is a function : P fin (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 L Ex = (L Ex , ⌦ Ex , ✏Ex) be the logic defined by L Ex = { 0 , . . . , 5 , ' 0 , . . . , ' 4 } and ⌦ Ex = {! 0 , . . . , ! 5 }, with the models relation ✏Ex implicitly given by:
Since defined in the classical model-theoretic way, L Ex is a monotonic logic. Note that logic L Ex has no connectives.
We will endow the interpretation space ⌦ with some structure. A binary relation over ⌦ is total if, for any 6 We let min(⌦ 0 , ) denote the set of -minimal interpretations in ⌦ 0 . We call a preorder, if it is transitive and reflexive.
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-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:
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 (.) : P fin (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:
An assignment (.) is called a preorder assignment if K is a preorder for every belief base K 2 P fin (L).
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.
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.
Arbitrary Monotonic Logics (Preliminary Report)
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):
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 K Ex = { 0 } and let Ex be the base change operator defined as follows:
For all K 0 with K 0 ⌘ K Ex we define K 0 = K Ex and for all K 0 with K 0 6 ⌘ K Ex we define
For all K 0 with K 0 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 K 0 ⌘ 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(L Ex ), 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:
, 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.
A binary relation over ⌦ is called min-retractive (for L) if for every 2 P fin (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 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.
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.
if it is both min-retractive and min-complete. An assignment (.) : P fin (L) ! P(⌦ ⇥⌦) is called min-friendly if K is min-friendly for all K 2 P fin (L).
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. Definition 6. Let be a base change operator and K 2 P fin (L) a belief base. The relation K over ⌦ is defined by
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 K is total (and hence reflexive) for every K 2 P fin (L).
Next comes an auxiliary lemma about belief bases and K .
Lemma 2. Let satisfy (G5) and (G6) and let K 2 P fin (L).
(a) If ! 1 6 K ! 2 , then ! 2 K ! 1 and there exists some with ! 1 , ! 2 ✏ as well as
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).
(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.
Observe that Ex K is not transitive, since ! 1 , ! 2 , ! 3 form a circle. Yet, one can easily verify that Ex K 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(L Ex ) such that there is some ! / 2 min( , Ex K ) and ! 0 2 min( , Ex K ) with ! Ex K ! 0 . Note that such a situation could appear in Ex K if a interpretation ! would be Ex K -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 Ex K and such a belief base does not exist in L Ex . Therefore, the relation Ex K is min-retractive.
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 : P fin (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
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 Ex K is also a minexpressible relation.
K , and observe that Ex K is compatible with Ex , i.e. JK K = min(J K, Ex K ). Thus, for every belief base 2 P(L Ex ), the minimum min( , Ex K ) yields a set expressible by a belief base. Theorem 3 guarantees us that Ex satisfies (G1)-(G6), as we can extend Ex K to a faithful min-expressible and min-friendly assignment. 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.
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, 0 0 , 0 1 , 0 2 2 P fin (L) such that
(where is addition mod 3) (3) for any 2 P fin (L) with J 0 i [ K 6 = ; for all 0i2 exists a 0 2 P fin (L) with ; 6
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.
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)-
Lemma 4 allows us to complete the correspondence between critical loops and total preorder representability. 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
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
In a disjunctive logic, every belief change operator satisfying (G1)-(G6) is total preorder representable.
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 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.
Arbitrary Monotonic Logics (Preliminary Report)
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.