On Definite Iterated Belief Revision with Belief Algebras

1 Introduction

Updating or revising the beliefs of an agent in light of new evidence is a fundamental process in both everyday life and scientific activities. For instance, Newton's laws of motion were widely accepted for centuries until discoveries at very small scales or very high speeds revealed their limitations. Similarly, our knowledge is continuously updated and enriched through learning and communication. To formalize this process, researchers in artificial intelligence have developed the subfield of belief change (see, e.g., [Doyle, 1979;

∗An extended version can be found at https://arxiv.org/abs/2505. 06505.

†Corresponding author.

Harper, 1976]). Among the most influential contributions to this field is the AGM framework [Alchourron et al., 1985], which has inspired numerous extensions and applications in areas such as game theory and argumentation [Williams, 1998; van Harmelen et al., 2008; Ferm´e and Hansson, 2011; Diller et al., 2015; Zhang, 2010].

Motivation. The AGM framework addresses various forms of belief change, including belief revision, which is of particular interest in this paper. The AGM framework, along with its various subsequent developments, aims to update a current belief state to a new one when new evidence is acquired. This process can be formally described syntactically as revising a set of logical formulas (belief set) with a single logical formula (new evidence) [Alchourron et al., 1985]. Alternatively, it can be characterized semantically using preferences over possible worlds (total preorder) [Katsuno and Mendelzon, 1991], where the revision process involves updating these preferences based on new evidence. Furthermore, belief revision based on partial preorders and iterated belief revision have been extensively studied [Lehmann, 1995; Boutilier, 1996; Darwiche and Pearl, 1997; Nayak et al., 2003; Booth and Chandler, 2016; Aravanis et al., 2019; KernIsberner et al., 2024]. Researchers have primarily focused on how to constrain belief revision behaviors through postulates or how to characterize revision with new semantics, leading to the proposal of various rule systems [Liberatore, 2024; Bonanno, 2025]. These rule systems are evaluated from different perspectives to build a comprehensive framework. However, these rule systems are often too loose, resulting in multiple revision operators that all satisfy the same set of rules, which might not be desirable in practice. For example, in scenarios where multiple intelligent agents collaborate in urban traffic management, their initial beliefs are aligned. Upon acquiring new traffic condition information, these agents must update their traffic control strategies deterministically so that they maintain aligned beliefs, otherwise the transportation system might descend into chaos.

Contributions. The goal and main contribution of this paper is not to establish a new rule system for belief revision, but to explore a simple and effective way to represent belief information in more depth, and to propose a definite revision operator suitable for applications requiring deterministic revision. To this end, we use belief algebra (introduced in [Meng et al., 2015]) as the foundational tool for representing belief information. Unlike preorders over worlds, a belief algebra represents belief information as a preference relation over subsets of worlds. In our framework, both the current belief state and the new evidence are represented as belief algebras. Specifically, the iterated belief revision process is modeled as revising a belief algebra G1 with another belief algebra G2 to produce a new belief algebra G3. By analyzing the structural properties of a belief algebra, we propose a set of revision postulates, including an upper bound constraint on the outcomes of revision, and prove that these postulates inherently induce a unique revision operator. Additionally, we discuss the algorithmic implementation of this iterated belief revision framework, providing practical support for designing agents with belief revision capabilities in applications.

Organization. The rest of the paper is organized as follows: Section 2 discusses related work and Section 3 introduces basic knowledge. Section 4 explores properties of belief algebras, and Section 5 considers a special case of revision with a belief algebra. Section 6 extends the discussion to general cases and Section 7 describes the practical algorithm. Finally, Section 8 concludes the paper.

2 RelatedWork

Various research efforts have focused on representing belief information in iterated revision. Spohn [1988] introduced the concept of ordinal conditional function (OCF) to encode preference information over worlds and developed a process called conditionalization to revise OCFs. Williams [1994] proposed a formula-based counterpart to OCF, mapping formulas to ordinals based on their resistance to change. Darwiche and Pearl [1997] advanced the field by representing belief information as total preorders on worlds and extending the AGM framework with four postulates to characterize iterated revision.

Several researchers have improved the DP (Darwiche and Pearl) framework's settings. Benferhat et al. [2005] used partial preorders, while Peppas and Williams [2014] employed semiorders. Ma et al. [2015] revised epistemic states with partial epistemic states. Andrikopoulou et al. [2025] discussed belief revision under filters that are subsets of partially ordered sets. Benferhat et al. [2000] enhanced the representation of new evidence by using an epistemic state, proposing postulates for minimal-model preserving operators and proving the uniqueness of the revision result given a total preorder and a new total preorder as evidence. This aligns with our discussion in Section 5, as their operator satisfies (RE1)-(RE3). Meanwhile, new frameworks and semantic structures continue to be proposed [Liberatore, 2024; Bonanno, 2025].

Many works aim to define the most "reasonable" revision rules, yet achieving consensus on rationality remains challenging. These debates often resemble philosophical discussions, focusing on abstract principles rather than practical implementations. The rationality of the basic AGM rules has been questioned [Aravanis, 2023]. Sauerwald and Thimm [2024] considered the realizability of AGM revision and contraction operators in Epistemic Spaces. Some researchers, such as [Booth and Meyer, 2006; Jin and Thielscher, 2007; Nayak et al., 2003], have observed that the DP framework can produce counter-intuitive revision results. To address that issue, they proposed modifications or additions to the DP postulates. For instance, Nayak, Pagnucco, and Peppas [2003] introduced conjunction postulates, treating consistent evidences as order-independent, while Jin and Thielscher [2007] proposed a weaker independence postulate. Notably, these works primarily focus on rule construction, with limited attention to operator selection.

While the exploration of revision rules continues, the potential and application prospects of belief revision have also received significant attention [Hunter and Boyarinov, 2022; Baroni et al., 2022]. This shift reflects a growing interest in leveraging belief revision for practical, real-world problems. In applications such as constrained differential privacy [Liu et al., 2023] and text generation by large language models [Wilie et al., 2024], the focus has shifted towards applications of revision. In industrial agent design, selecting a specific update algorithm is crucial to enable agents to iteratively refine their beliefs. To address this, our work focuses on representing belief information through belief algebra building on [Meng et al., 2015], and proposes a unique revision operator by strengthening revision rules in a natural way, aiming to provide a deterministic and practical solution for real-world applications.

3 Preliminaries

We recall some necessary knowledge for what will follow.

3.1 Belief as A Total Preorder

In this paper, we restrict our discussion to belief revision in a finite propositional language L. We denote by W the set of all (possible) worlds (i.e., interpretations).

For each propositional formula ψ, we denote by [ψ] the set of all worlds of ψ, i.e., [ψ] = {ω ∈ W | ω |= ψ}. We will also use a consequence operator Cn(Γ) = {ϕ ∈ L | [Γ] ⊆ [ϕ]} to obtain the set of formulas implied by Γ.

A (partial) preorder ⪯ on A is a binary relation on A that is reflexive and transitive. A preorder ⪯ is called total if any two elements in A are comparable under ⪯. We write x ∼ y if x ⪯ y and y ⪯ x, and x ≺ y if x ⪯ y but y ̸⪯ x. The strict part of a preorder ⪯ is the set ≺= {(x, y) | x ≺ y} ⊆⪯.

A belief set K is a set of formulas in L that is deductively closed, i.e., Cn(K) = K. Generally, belief revision is the process of changing a current belief state with a new piece of evidence, where the current belief state and the new evidence can be represented in different ways. For example, in the AGM framework, the current belief state is represented as a belief set and the new evidence is represented as a formula.

When belief revision needs to be done sequentially, known as iterated belief revision, the representation mechanism of the AGM framework is not suitable anymore. A more sophisticated structure known as epistemic state is then used to represent belief information. In their original paper, Darwiche and Pearl [1997] captured the concept of an epistemic state in terms of a revision operator. Particularly, an epistemic state is a set of beliefs and conditional beliefs satisfying several postulates. A conditional belief has the form (β | α), where α, β

are formulas in L. An agent has a conditional belief (β | α) if she will believe β whenever she believes α. Within the DP framework, an epistemic state can be characterized semantically as a total preorder on worlds as follows.

Lemma 1 ( [Darwiche and Pearl, 1997]). Suppose Ψ consists of a belief set Bel(Ψ) and several conditional beliefs, then Ψ is an epistemic state iff there is a total preorder ⪯ on worlds such that:

(ES1) φ ∈ Bel(Ψ) iff there is a world ω in [φ] such that ω ≺ ω′ for all ω′ ∈ [¬φ].

(ES2) (β | α) ∈ Ψ iff there is a world ω in [α ∧ β] such that ω ≺ ω′ for all ω′ ∈ [α ∧ ¬β].

3.2 Belief as A Belief Algebra

To provide a unified representation of belief information, the concept of belief algebra was introduced in [Meng et al., 2015]. It is a class of ordering structures on 2W , the power set of possible worlds, which can intuitively capture the belief preference of an agent, and is actually more general than total preorder (see Section 5).

Definition 1 ([Meng et al., 2015]). Suppose ≫ is a binary relation on 2W , and write RW = {(U, V ) | U, V ⊆ W, U ∩ V = ∅}. Then (2W ,≫) is called a belief algebra (BA) if it satisfies the following rules (U, V, U1, V1, U2, V2 ⊆ W):

(A1) U ≫ ∅ iff U ̸= ∅.

(A2) If U ≫ V , then V ̸≫U.

(A3) If U1 ⊇ U ≫ V ⊇ V1 and U1 ∩ V1 = ∅, then U1 ≫ V1.

(A4) If U = U1∪V1 = U2∪V2 and U1 ≫ V1, U2 ≫ V2, then U1 ∩ U2 ≫ V1 ∪ V2.

Roughly speaking, ≫ directly describes the belief preference of agents in a semantic way. For instance, [φ] ≫ [¬φ] means that φ is more believable than ¬φ, and if [φ] and [ψ] are incomparable in ≫, then the agent has no idea which one is more believable. (A0) shows that we only need to compare disjoint subsets of W. (A1) shows that each nonempty set has a higher preference level than the empty set. (A2) shows that ≫ is a strict ordering. (A3) shows that ≫ satisfies certain transitivity. (A4) considers the case where if φ is more believable than ¬φ and ψ is more believable than ¬ψ, then φ ∧ ψ is more believable than ¬(φ ∧ ψ).

Traditionally, the semantic characterization of an epistemic state is often represented as a total preorder on W, where W is the set of all possible worlds. In contrast, a belief algebra is defined as an ordering relation on 2W , the power set of W. Interestingly, a total preorder on W can be naturally extended to a belief algebra on 2W . This relationship can be formalized in the following theorem:

Theorem 1 ([Meng et al., 2015]). Let ⪯ be a total preorder on W . Define a binary relation ≫ on 2W as follows: U ≫ V if and only if U ∩ V = ∅ and ∃ω1 ∈ U such that ∀ω2 ∈ V, ω1 ≺ ω2. Then (2W ,≫) is a belief algebra.

This theorem demonstrates that the structure of a total preorder on W can be lifted to a belief algebra on 2W , preserving the agent's belief preferences in a more expressive and generalized framework. The relation≫captures the intuition that a subset U is preferred over V if there exists at least one world in U that is strictly preferred to all worlds in V . This extension provides a natural bridge between traditional epistemic states and the more general belief algebra framework.

Definition 2 (Complete Belief Algebra (CBA)). A belief algebra (2W ,≫) is called a complete belief algebra (CBA) if it can be generated from a total preorder ⪯ on W in the manner described in Theorem 1.

Complete belief algebras provide a natural connection between total preorders on W, and the more expressive framework of belief algebras. They capture the intuition that belief preferences over subsets of worlds can be fully determined by a total preorder on individual worlds.

Example 1. Suppose ω1 ∼ ω2 ≺ ω3 ∼ ω4 is a total preorder and thus an epistemic state. Let W = {ω1, ω2, ω3, ω4} and Tr(W) = {(U, ∅) | U ⊆ W,U ̸= ∅}. For the sake of brevity we use (x, y) for representing {ωx} ≫ {ωy}, (xy, z) for {ωx, ωy} ≫ {ωz}, and so on. Then this total preorder is equivalent to a complete belief algebra G as follows:

(12, 3), (12, 4), (12, 34), (123, 4), (124, 3)} ∪ T r(W).

4 Exploring Belief Algebra inMore Depth

Given two belief algebras G1 = (2W ,≫1) and G2 = (2W ,≫2) on W, we denote by G1 ⊆ G2 iff ≫1⊆≫2. Also, we will not distinguish between G1 ∪ G2 and ≫1 ∪ ≫2, and G1 ∩ G2 and ≫1 ∩ ≫2, whenever it is self-explanatory based on context. For each belief algebra G = (2W ,≫), Tr(W) = {(U, ∅) | U ⊆ W, U ̸= ∅} is always contained in ≫ by (A1). It is not difficult to verify that (2W , Tr(W)) is a belief algebra. Then for each belief algebra G on W, we always have (2W , T r(W)) ⊆ G.

A subset of RW (defined in Definition 1) can generate a belief algebra.

Definition 3. Given Ω ⊆ RW, we denote by Gen(Ω) the smallest subset of RW that contains Ω and is closed under the rules (A1), (A3) and (A4) used for expansion.

Example 2. Suppose W = {ω1, ω2, ω3, ω4} and Ω = ({ω1, ω2}, {ω3, ω4}). Then for each belief algebra (2W ,≫), if Ω ∈≫ we have {ω1, ω2} ≫ {ω3, ω4}. Again, for the sake of brevity we use (x, y) for representing {ωx} ≫ {ωy}, (xy, z) for {ωx, ωy} ≫ {ωz}, and so on. With respect to (A3) we have that (123, 4), (124, 3) are all in ≫, and by (A4) (12, 34) ∈≫. Then it can be verified that Gen(Ω) = {(12, 34), (123, 4), (124, 3)} ∪ Tr(W) is the smallest belief algebra which contains Ω.

If Gen(Ω) also satisfies (A2), then (2W ,Gen(Ω)) is a belief algebra by definition, and we will also use Gen(Ω) to denote this belief algebra. Here we always assume that the agent is rational and Gen(Ω) is always a belief algebra when Ω represents some belief information. Given Ω, Gen(Ω) can be obtained by closing Ω under (A1), (A3), and (A4).

With the operator Gen(·), one can see that each CBA is entirely determined by preferences on the sets consisting of a single world.

Corollary 1. Suppose G = (2W ,≫) and G′ = (2W ,≫′ ) are CBAs, then:

• Gen(Ω) = G, where Ω = {({ω}, {ω′ }) | {ω} ≫ {ω′ }}.
• If G and G′ have the same preferences on single world sets, i.e., for any ω, ω′ ∈ W, ({ω}, {ω′ }) ∈ G iff ({ω}, {ω′ }) ∈ G′ , then G = G′ .

The following proposition shows how to construct new belief algebras from existing belief algebras.

Proposition 1. Suppose G = (2W ,≫) and G′ = (2W ,≫′ ) are belief algebras. Then G∩G′ = (2W , ≫ ∩ ≫′ ) is a belief algebra.

Corollary 2. Suppose G = (2W ,≫) is a belief algebra and Ω ⊆≫, and A is the set of all the belief algebras that contains Ω. Then Gen(Ω) is a belief algebra, and Gen(Ω) = ⋂ A.

The following result unveils the structure of ≫, which consists of levels of subsets of worlds.

Lemma 2 ([Meng et al., 2015]). Suppose (2W ,≫) is a belief algebra. Then there is a unique chain, called backbone, ∆ = {U1 ≫ U2 ≫ U3 ≫ · · · ≫ Un}, such that:

(Ch1) {Ui}ni=1 is a partition of W, i.e., {Ui}ni=1 consists of pairwise disjoint nonempty subsets of W and ⋃ni=1 Ui = W.

(Ch2) For each Ui, if V1, V2 are two disjoint nonempty subsets of Ui, then V1 and V2 are incomparable in ≫, i.e., (V1, V2) /∈≫and (V2, V1) /∈≫.

The above lemma shows that the backbone is the core structure of a belief algebra. (Ch2) shows that for each Ui in a backbone, any subsets of Ui can not be compared with one another. In terms of belief preferences, this means that an agent has no preference on subsets of Ui. Another important concept is the support of a subset of W w.r.t. some backbone.

Definition 4. Let ∆ = {U1 ≫ U2 ≫ U3 ≫ · · · ≫ Un} be the backbone of a belief algebra. The support of a nonempty set V ⊆ W w.r.t. ∆ is defined as I(V ) = Ui, where V ∩Ui ̸= ∅ and ∀j ̸= i, if V ∩ Uj ̸= ∅,Ui ≫ Uj. That is, I(V ) is the largest Ui under ≫ in the backbone such that V ∩ Ui ̸= ∅.

Figure 1 gives an illustration of the above definitions. Moreover, the preferences of an agent are "consistent" with the backbone in the sense of property (1) in Lemma 3 that follows.

Lemma 3 ([Meng et al., 2015]). The relations between belief algebras and their backbones are as follows:

1. Suppose G = (2W ,≫) is a belief algebra, then U ≫ V only if I(U) ≫ I(V ).
2. Suppose G = (2W ,≫) is a complete belief algebra, then U ≫ V if and only if I(U) ≫ I(V ).
3. Suppose G = (2W ,≫) is a belief algebra, and ∆ = {U1 ≫ U2 ≫ U3 ≫ · · · ≫ Un} is its backbone. Then there is a unique complete belief algebra G′ = (2W ,≫′ ) containing G and having the same backbone with G. Moreover, ≫′= {(U, V ) ∈ RW | U, V ̸= ∅, I(U) ≫ I(V )} ∪ Tr(W).

The above lemma shows that there are different belief algebras that have the same backbone ∆, and there is a unique complete belief algebra with ∆ as its backbone, viz., the largest one containing all the pairs (U, V ) s.t. I(U) ≫ I(V ). Roughly speaking, the backbone of a belief algebra is the "core" belief information that reflects the main preferences of the agent. Taking Figure 1 as an example, a belief algebra G with {U1 ≫ U2 ≫ U3 ≫ · · · ≫ Un} as its backbone may or may not contain V1 ≫ V2, but if it is CBA, then it must contain V1 ≫ V2, and it should never contain V2 ≫ V1 because I(V1) = U1 ≫ U2 = I(V2).

Definition 5. Suppose G = (2W ,≫) is a belief algebra. Then we denote by Com(G) the complete belief algebra that contains G and has the same backbone as G. Suppose G1 and G2 are both belief algebras. Then we write G1 ≤ G2 if these two belief algebras have the same backbone and G1 ⊆ G2.

Example 3. Let L be a propositional language with two variables {b, f} and W = {ω1 := b ∧ f, ω2 := b ∧ ¬f, ω3 := ¬b ∧ f, ω4 := ¬b ∧ ¬f}. Suppose Bob's current belief state is represented as a total preorder ω1 ∼ ω2 ≺ ω3 ∼ ω4, and the new evidence is a formula µ such that the worlds that entail µ are represented as [µ] = {ω1, ω4}. In this situation, Bob holds a new preference that [µ] ≫ [¬µ]. These belief preferences can be represented using belief algebra. Following the notation in Example 2, Bob's current belief information can be represented as: Gen({(1, 3), (1, 4), (2, 3), (2, 4)}). Similarly, the new evidence µ can be represented as Gen({(14, 23)}). Note that Gen({(1, 3), (1, 4), (2, 3), (2, 4)}) is a complete belief algebra (CBA), while Gen({(14, 23)}) is not a CBA. The backbone of the former is {ω1, ω2} ≫ {ω3, ω4}, while the backbone of the latter is {ω1, ω4} ≫ {ω2, ω3}. Moreover, Com(Gen({(14, 23)})) = Gen({(1, 2), (1, 3), (4, 2), (4, 3)}).

Note that G1 ≤ G2 is different fromG1 ⊆ G2. It actually means that G1 and G2 contain the same "core" belief information, but G1 is "less informational" than G2, in the sense that any revision result of G1 should be contained in that of G2, as we will see later in the postulate (RA5). Let BAL be the set of belief algebras over the worlds of L. It is easy to check that ≤ as defined above is a partial order on BAL. We also use BAL to denote the partial order set (BAL, ≤).

Theorem 2. Let ∆ = {U1 ≫ U2 ≫ U3 ≫ · · · ≫ Un} be a backbone and denote by BA(∆) = {G ∈ BAL | ∆

is the backbone of G} the set of belief algebras having ∆ as backbone. Suppose G1, G2 ∈ BA(∆). Then:

Remark 1. Theorem 2 shows that BA(∆) is a lattice that contains the smallest element Gen(∆) and the largest element Com(Gen(∆)). Here, a lattice is a set equipped with a partial order such that every two elements have a unique supremum (also called the least upper bound) and a unique infimum (also called the greatest lower bound). Furthermore, BAL is divided into disjoint parts by the backbone, and each part is a lattice under ≤ (see Figure 2).

Example 4. Suppose W = {ω1, ω2, ω3, ω4}. Let G1 = {(123, 4)} ∪ Tr(W), G2 = {(123, 4), (12, 4)} ∪ Tr(W), G3 = {(123, 4), (13, 4)} ∪ Tr(W), G4 = {(123, 4), (12, 4), (13, 4), (23, 4), (1, 4), (2, 4), (3, 4)} ∪ Tr(W). Then G1,G2,G3,G4 are all belief algebras, and they all have the same backbone ∆ = {ω1, ω2, ω3} ≫ {ω4}. G4 is a complete belief algebra, and G1 ≤ G2 ≤ G4, G1 ≤ G3 ≤ G4, but G2,G3 can not be compared by ≤. Furthermore, G1 = Gen(∆) is the smallest element in BA(∆), and G4 = Com(G1) is the biggest one.

5 Special Case: Revising CBAwith CBA

Before discussing the general case of revision with belief algebras, we first consider a simplified scenario where the agent's current belief, the new evidence, and the revision result are all represented as complete belief algebras (CBAs; see Definition 2). This process is equivalent to revising an existing total preorder ⪯1 by a new total preorder ⪯2 to obtain a revised total preorder ⪯3.

Inspired by existing research (e.g., [Alchourron et al., 1985; Darwiche and Pearl, 1997; Ma et al., 2015]), we propose the following revision rules for this setting. The revision of a total preorder by another total preorder, denoted as ⪯1 ◦ ⪯2=⪯3, has been studied in [Benferhat et al., 2000] and is known as a minimal-model preserving operator. This operator can be equivalently characterized by the following postulates:

(RE3) If ω ∼2 ω′ , then: ω ≺3 ω′ if and only if ω ≺1 ω′ .

The postulate (RE1) is natural by underlying setting. The postulate (RE2) requires that the new belief information (corresponding to the strict part of the new total preorder) must be fully incorporated into the revision result. Finally, (RE3) ensures that for worlds with equal (non)preference under ⪯2, the preference relation from ⪯1 is preserved in ⪯3. This allows the revision process to retain more of the original belief information while incorporating the new evidence.

Example 5. Following Example 3, Bob's current belief is ⪯1= {ω1 ∼ ω2 ≺ ω3 ∼ ω4} which has {(ω1 ≺ ω3), (ω1 ≺ ω4), (ω2 ≺ ω3), (ω2 ≺ ω4)} as its strict part. Now, instead of considering revision by a formula, we consider revision by another total preorder ⪯2= {ω1 ∼ ω2 ∼ ω3 ∼ ω4}. Then ⪯2 has an empty strict part, which means that ⪯2 cannot lead to any new preference. In this sense, all the strict orderings of ⪯1 can be kept into the revision result. It is natural that ⪯1 ◦ ⪯2=⪯1. Suppose instead ⪯2= {ω4 ≺ ω3 ≺ ω2 ≺ ω1}. Then, in ⪯2, all worlds are ordered by ≺. In this sense, no information in ⪯1 is useful and ⪯1 ◦ ⪯2=⪯2. On the other hand, if ⪯2= {ω2 ∼ ω4 ≺ ω1 ∼ ω3}. Then, ω2 and ω4 (ω1 and ω3 respectively) can not be distinguished in ⪯2, but ω2 ≺ ω4 and ω1 ≺ ω3 are in ⪯1. Following the information in ⪯1, Bob should hold ω2 ≺ ω4 and ω1 ≺ ω3 in ⪯1 ◦ ⪯2. Then ⪯1 ◦ ⪯2= {ω2 ≺ ω4 ≺ ω1 ≺ ω3}.

Interestingly, it can be shown that revision results satisfying the above postulates are unique.

Theorem 3. Suppose ⪯1 and ⪯2 are total preorders. Then there is a unique revision operator satisfying (RE1)-(RE3).

Remark 2. However, the above revision framework has the great limitation of not being able to deal with more general cases such as the new evidence or even the current belief state is not a total preorder, which is common in real-world applications, e.g., the agent only holds incomplete belief information. Therefore, it is necessary to consider other solutions without such limitation.

6 Revision with Belief Algebras

In this section, we extend our discussion to a more general framework of iterated belief revision based on a belief algebra, rather than restricting ourselves to CBAs. This framework allows for a richer representation of belief states and supports more flexible revision processes. For simplicity, we assume that the agent is rational (i.e. both her belief and the new evidence do not contain "conflicting information"). If not specified otherwise, we always suppose that the agent's current belief state is a belief algebra G1, the new evidence is a belief algebra G2, and the revision result is also a belief algebra denoted by G1 · G2, where · is a revision operator from BAL × BAL to BAL.

To give postulates to characterize rational revisions, following literature, e.g., [Alchourron et al., 1985; Darwiche and Pearl, 1997; Jin and Thielscher, 2007], we first assume that new evidence has a higher preference, that is, belief information of G2 is more believable than G1. Then G2 should be kept in G1 · G2, and we have:

Since G1 and G2 collectively cover all the agent's belief information, we assume that G1 · G2 is entirely determined by G1 and G2 and is generated by some subset of G1 ∪ G2. This leads to the following postulate:

(RA2) requires that the revision result cannot be generated with information outside G1 ∪ G2, and if G1 and G2 have conflicting information, one should choose a consistent subset in order to generate a belief algebra.

Notice that a complete belief algebra is equivalent to a total preorder on worlds. Revising a complete belief algebra G1 by another complete belief algebra G2 is equivalent to revising a total preorder by another total preorder. The following postulates (RA3) and (RA4) are thus inspired by (RE1) and (RE3) for revising total preorders in Section 5, respectively.

(RA3) Suppose G1 and G2 are complete belief algebras. Then G1 · G2 is also a complete belief algebra.

(RA4) Suppose G1 = (2W ,≫1) and G2 = (2W ,≫2) are complete belief algebras, and I2({ω}) = I2({ω′ }) in G2. Then ({ω}, {ω′ }) ∈ G1 · G2 iff {ω} ≫1 {ω′ }.

Theorem 4. Suppose · satisfies (RA1)-(RA4), and G1 = (2W , ≫1) and G2 = (2W , ≫2) are complete belief algebras. Λ(G1,G2) = {({ω}, {ω′ }) | {ω} ≫1 {ω′ }, I2({ω}) = I2({ω′ })}. Then G1 · G2 = Gen(Λ(G1,G2) ∪ G2), and the result of revising G1 by G2 is unique.

This above theorem generalizes Theorem 3 and shows that, under the postulates (RA1)-(RA4), the revision operator · is deterministic when applied to complete belief algebras. Specifically, the revision result G1 · G2 is uniquely determined by combining the preference relations from G1 and G2 in a principled way. The set Λ(G1, G2) captures the preferences from G1 that are consistent with the structure of G2, ensuring that the revision process preserves as much of the original belief information as possible while fully incorporating the new evidence. The following corollary establishes a direct correspondence between the revision operator · for complete belief algebras and the revision operator ◦ for their equivalent total preorders.

Corollary 3. Suppose, G1 and G2 are complete belief algebras, and ⪯1 and ⪯2 are their equivalent total preorders on worlds, respectively. If · satisfies (RA1)-(RA4), and ◦ satisfies (RE1)-(RE3), then the corresponding total preorder of G1 · G2 is exactly ⪯1 ◦ ⪯2.

Example 6. Suppose, ∆1 = {{ω1} ≫ {ω2} ≫ {ω3} ≫ {ω4}} and ∆2 = {{ω2} ≫ {ω1, ω3} ≫ {ω4}} are backbones, then G1 = Gen(∆1) and G2 = Gen(∆2 ∪ {(1, 4), (3, 4)}) are complete belief algebras. In this sense, Λ(G1,G2) = {(1, 3)}, and G1 · G2 = Gen({{ω2} ≫ {ω1} ≫ {ω3} ≫ {ω4}}), where {{ω2} ≫ {ω1} ≫ {ω3} ≫ {ω4}} is the backbone of G1 · G2.

For the case where G1 and G2 are possibly incomplete belief algebras, we include the following postulate:

(RA5) If G1 ≤ G′1 , G2 ≤ G′2 then G1 · G2 ⊆ G′1 · G′2 . Recall that G1 ≤ G′1 means that G1 ⊆ G′1 and G1 and G′1 have the same backbone. (RA5) means that if G1 and G2

contain less information than G′1 and G′2 , respectively, and they have the same core belief information (i.e., same backbones), then G1 · G2 also contains less belief information than G′1 ·G′2 . From (RA5), the following proposition is easy to verify.

Proposition 2. If · satisfies (RA5), then G1 · G2 ⊆ Com(G1) · Com(G2).

The above proposition shows that Com(G1) ·Com(G2) is an upper bound of G1 · G2 (under ⊆).

Furthermore, we suppose a rational agent will keep maximal information from G1 to G1 · G2 under (RA1)-(RA5), which is a "minimal change" rule. Hence, we assume that G1 · G2 is maximum in Com(G1) · Com(G2), i.e., there is no belief algebra Gen(Ω) ⊆ Com(G1) · Com(G2) such that G1 · G2 ⊂ Gen(Ω), where Ω ⊆ G1 ∪ G2. Then we have the following postulate.

(RA6) If Ω ⊆ G1 ∪ G2 and Gen(Ω) ⊆ Com(G1) · Com(G2), G1·G2 ⊆ Gen(Ω), then G1·G2 = Gen(Ω).

We arrive to one of the major results in this work:

Theorem 5. Suppose · satisfies (RA1)-(RA6), and G1,G2 are belief algebras. Then the revision result of G1 · G2 is unique, and G1 · G2 = Gen((G1 ∪ G2) ∩ Com(G1) · Com(G2)).

The above theorem shows that there is only one operator that satisfies (RA1)-(RA6). The postulate (RA5) provides an upper bound for the revision result. On the other hand, (RA6) imposes a conditional maximality requirement on the revision result, which, together with (RA5), leads to the uniqueness of the revision operator ·. In the next section, we will discuss how to algorithmically compute the revision result of this operator, providing a practical method for performing iterated belief revision in the belief algebra framework.

7 A Practical Algorithm and Discussion

In this section, we provide a practical algorithm for computing the revision result G1 · G2 based on the postulates (RA1)-(RA6).

7.1 Algorithm

We begin with a direct characterization of the revision result.

Proposition 3. Suppose G1 and G2 are belief algebras, · satisfies (RA1)-(RA6), and G∗ = Com(G1) · Com(G2). Then G1 · G2 = Gen((G1 ∩ G∗) ∪ G2), and G1 ∩ G∗ = {(U, V ) | U ≫1 V, and I∗(U) ≫∗ I∗(V )}.

Therefore, we can use Algorithm 1 to get G1 · G2. In the first step of the algorithm, we need to compute Com(G1) and Com(G2). Given a belief algebra G = (2W ,≫), to calculate Com(G), we need to obtain the backbone {U1 ≫ · · · ≫ Un} of G first. Let U1 = ⋂{U ⊆ W | U ≫ W \ U}, Wi+1 = Wi \ Ui and W1 = W. Then Ui = ⋂{U ⊆ Wi+1 | U ≫ Wi+1 \ U}. It can be verified that {U1 ≫ · · · ≫ Un} is indeed the backbone of G, and more details can be found in [Meng et al., 2015]. With the backbone of G, Com(G) = (2W , ≫∗ ) can be constructed by defining ≫∗ as ∀U, V ∈ RW, U ≫∗ V if I(U) ≫ I(V ). Then G∗ can be computed by Theorem 4, and thus G1 · G2

Algorithm 1: Definite revision on BAL.

• In : Current belief algebra G1 and new evidence G2.
• 5 return G1 ·G2.

Out: Resulting belief algebra G1 · G2. 1 Calculate Com(G1) and Com(G2) by Definition 5; 2 G∗ ← Com(G1) · Com(G2) by Theorem 4; 3 G1 ∩G∗ ← {(U, V ) | U ≫1 V, and I∗(U) ≫∗ I∗(V )}; 4 G1 · G2 ← Gen((G1 ∩ G∗) ∪ G2) by Definition 3;

can be obtained accordingly. Note that one can get Gen(≫) for some ≫ by calculating the closure of ≫ under (A1), (A3), and (A4).

Now we return to the traditional belief revision setting, where the current belief is represented as a total preorder ⪯ on possible worlds, and the new evidence is a formula µ. This revision setting can be viewed as revising a complete belief algebra by a new belief algebra generated by the formula µ. Suppose that · is the revision operator on BAL satisfying (RA1)-(RA6). Then the revision process proceeds as follows:

• (Step 1) Represent ⪯ and µ by belief algebras. Let G1 = (2W ,≫1) be the corresponding complete belief algebra of ⪯ i.e., ω ≺ ω′ iff {ω} ≫1 {ω′ }. Similarly, µ can be equivalently represented by Gµ = Gen(≫µ:= {([µ], [¬µ])}).
• (Step 2) Calculate G∗. Note that Com(Gµ) is equivalent to a total preorder ⪯µ s.t. ω ≺µ ω′ iff ω ∈ [µ] and ω′ ∈ [¬µ]. Moreover, G∗ = G1 · Com(Gµ) is also equivalent to a total preorder ⪯∗. Following (RE1)- (RE3) (by Corollary 3, (RA1)-(RA4) equivalently), we can conclude that the strict part of ⪯∗ is as follows.
• If ω1, ω2 ∈ [µ] then ω1 ≺∗ ω2 iff ω1 ≺ ω2.
• If ω1, ω2 ∈ [¬µ] then ω1 ≺∗ ω2 iff ω1 ≺ ω2.
• If ω1 ∈ [µ] and ω2 ∈ [¬µ] then ω1 ≺∗ ω2.
• (Step 3) Calculate G1 ∩G∗. From the result of last step, we can see that
• If ω1, ω2 ∈ [µ], then ({ω1}, {ω2}) ∈ G1 ∩ G∗ iff ({ω1}, {ω2}) ∈ G1.
• If ω1, ω2 ∈ [¬µ], then ({ω1}, {ω2}) ∈ G1 ∩G∗ iff ({ω1}, {ω2}) ∈ G1.
• If ω1 ∈ [µ], ω2 ∈ [¬µ] and ({ω1}, {ω2}) ∈ G1, then ({ω1}, {ω2}) ∈ G1 ∩ G∗.

It should be noted that, the preferences on single worlds in [µ] and [¬µ] remain unchanged after revision, and ω ≺ ω′ in ⪯ is also maintained if ω ∈ [µ] and ω′ ∈ [¬µ].

• (Step 4) Calculate G1 · Gµ = Gen((G1 ∩ G∗) ∪Gµ). Then we get the revision result G1 · Gµ.

Remark 3. It is evident that the above revision process attempts to preserve as much information from ⪯ as possible, particularly those preferences consistent with [µ] ≫ [¬µ]. This strategy aligns with the principles of the AGM and DP frameworks. However, unlike these frameworks, the specific preference relations to be preserved are determined by the upper bound G1 ·Com(Gµ). Only those preferences consistent with G1 · Com(Gµ) are included in the final result, and they must be included. This is the reason why the revision operator produces a unique result.

7.2 Discussion

Our iterative framework builds upon [Meng et al., 2015]. The belief algebra framework naturally extends to scenarios where the agent's beliefs are partial or incomplete. Unlike total preorders, which require a complete ranking of all worlds, belief algebras allow for the representation of preferences over subsets of worlds, even when some preferences are unspecified. This flexibility is particularly useful in realworld applications where the agent may have limited or uncertain information.

A key distinction with [Meng et al., 2015] is that we provide a deeper analysis of the structure of belief algebra and introduce two core revision rules, (RA5) and (RA6). (RA5) imposes a macro-level constraint on belief revision, ensuring that the revision result does not exceed the outcome under complete information when belief information is insufficient. (RA6), on the other hand, requires preserving as much of the original belief information as possible under these constraints. Interestingly, these rules induce a unique revision result. Under our framework, agents with the same belief algebra and evidence will produce identical revision outcomes. While traditional views attribute different revision results to varying operators, we argue that rational agents share highly similar revision operators, and differences arise from their distinct belief algebras.

8 Conclusion

In this paper, we proposed an iterated belief revision framework based on belief algebra where the current belief state, new evidence, and revision results are all represented as belief algebras. Through a deep analysis of the structure of belief algebra and inspired by existing principles of belief revision, we devised natural postulates for rational revision behaviors, including (RA5), which imposes an upper-bound constraint on revision results, ensuring that no revision exceeds the outcome under complete information, and (RA6), which requires preserving as much of the original belief information as possible while satisfying the upper-bound constraint. Interestingly, these postulates induce a unique revision operator, providing a deterministic and principled approach to belief revision. This uniqueness offers a clear guideline for selecting specific revision operators in practical applications.

Moreover, we developed a practical revision algorithm under the new framework, demonstrating its feasibility for realworld use. In future work, we aim to explore efficient methods for representing original belief information (e.g., logical statements or preferences) as belief algebra. Additionally, we will focus on improving the efficiency of our algorithm, reducing its complexity (currently, it is exponential to the number of worlds), and testing its application in specific domains, such as knowledge or rule revision in large language models.

Acknowledgments

We would like to thank the anonymous reviewers for their invaluable help to improve the paper. This work was supported by the National Natural Science Foundation of China under Grant numbers 61806170 and 62276218; the Fundamental Research Funds for the Central Universities under Grant numbers 2682022ZTPY082 and 2682023ZTPY027; the French National Research Agency under Grant number SA21PD01; and University of Montpellier under Grant number PP21PD01-RM06.