Total preorders over possible worlds are often used to represent epistemic states, with the minimal worlds representing an agent's beliefs. Marginalization refers to reducing the signature of an epistemic state, resulting in a smaller total preorder over possible worlds over the chosen subset of the original signature. Together with the syntax splitting principle, which states that only syntactically relevant parts of the epistemic state should be modified during revision, marginalization can be used to make belief revision more eficient: The original preorder is marginalized into smaller preorders, which are revised independently, and then merged back together. This last merging step ofers a challenge, however, since some information about the original ordering may be lost during marginalization. In this paper, we explore how this merging step may be performed while preserving as much information as possible, in particular the original syntax splitting.
Both in belief revision and in non-monotonic reasoning, total preorders over possible worlds play an important role as representations of an agent’s epistemic state. By ranking the possible worlds according to their plausibility, with the minimal worlds being most plausible, they encode both propositional and conditional beliefs.
Marginalization refers to reducing the signature of an epistemic state. The concept originates
from probability theory, where marginalization means reducing the dimensionality of a probability
distribution. Similarly, the marginalization of a total preorder is defined over a chosen subset of the
original signature, resulting in an exponentially smaller total preorder over the reduced signature. In
conjunction with the so-called syntax splitting principle, this technique can be used to make belief
revision and non-monotonic reasoning more eficient. The core idea of syntax splitting (which goes
back to Parikh [
In this paper, we will focus on the application of syntax splitting to iterated belief revision of
total preorders. In [
In summary, the main contributions of this paper are: • We propose a revision operator that satisfies both (P it) and (MR). • We propose two postulates for merging epistemic states which are defined over disjunct signatures: (ReMarg) and (MSplit). • We show that local revision of marginalized total preorders with an additional merging step, with a merging operator satisfying (ReMarg) and (MSplit), amounts to a global revision satisfying the syntax splitting postulates (Pit) and (MR).
The rest of this paper is organized as follows. In Section 2, we recall formal basics and notations. Afterwards, related work is discussed in Section 3. In Section 4, we recall syntax splitting for iterated belief revision, and we propose a revision operator satisfying the iterated syntax splitting postulates in Section 5. Section 6 is the core of this paper, where we develop general merging strategies for marginalized total preorders. Finally, Section 7 contains conclusions and pointers to future work.
Let ℒ be a finitely generated propositional language over the alphabet Σ = {, , , . . .}. Formulas , , , . . . are formed using the standard connectives ∧, ∨, ¬. For conciseness of notation, we will write instead of ∧ for conjunctions, and overlining formulas will indicate negation, i.e. means ¬. The symbol ⊤ denotes an arbitrary propositional tautology. The set of all possible worlds (propositional interpretations) over Σ′ ⊆ Σ is denoted by Ω(Σ′). If Σ′ is clear from the context we simply write Ω. We denote with |= that the propositional formula ∈ ℒ holds in the possible world ∈ Ω; then is called a model of , and the set of all models of is denoted by Mod(). For propositions , ∈ ℒ, |= holds if Mod() ⊆ Mod(), as usual. By slight abuse of notation, we will use both for the model and the corresponding conjunction of all positive or negated atoms. Since |= means the same for both readings of , no confusion will arise. For a subsignature Θ ⊆ Σ we denote by Θ the Θ-part of a world ∈ Ω, such that Ω(Θ) = {Θ | ∈ Ω(Σ)}.
As a structure for possible worlds we consider epistemic states represented as Ψ = (ΣΨ, ΩΨ, ⪯ Ψ) with ΩΨ ⊆ Ω(ΣΨ), and ⪯ Ψ ⊆ ΩΨ × ΩΨ being a total preorder (TPO), i.e., a total and transitive relation. We assume that every epistemic state can be uniquely identified by its associated total preorder ⪯ Ψ, that is each epistemic state Ψ induces a unique total preorder ⪯ Ψ, and each total preorder ⪯ induces a unique epistemic state Ψ⪯ . As usual, 1 ≺ 2 if 1 ⪯ 2, but not 2 ⪯ 1, and 1 ≈ 2 if both 1 ⪯ 2 and 2 ⪯ 1. Total preorders represent plausibility orderings, with the most plausible worlds being located in the lowermost layer of ⪯ which we denote by min(Ω, ⪯ ). More generally, if Ω′ ⊆ Ω is a subset of possible worlds, min(Ω′, ⪯ ) denotes the set of minimal worlds in Ω′ according to ⪯ . The preorder ⪯ is lifted to a relation between propositions in the usual way: ⪯ if there is |= such that ⪯ ′ for all ′ |= . The minimal formulas with respect to a total preorder ⪯ Ψ representing an epistemic state Ψ are the propositional beliefs of Ψ, denoted as Bel(Ψ). Note that Mod(Bel(Ψ)) = min(Ω, ⪯ Ψ).
Ordinal Conditional Functions (OCFs, also called ranking functions) : Ω → N∪{∞} with − 1(0) ̸= ∅
[
Every ranking function induces a unique total preorder which can be obtained via the transformation
operator [
min
∈ − 1(Ψ)
{ ()}
(2)
holds, i.e., maps Ψ to the minimal possible ranking function complying with Ψ. For a more detailed
analysis on such transformations we refer to [
There is a fairly large body of work on the general topic of merging information in logic-based
frameworks, see e.g. [
We are concerned with a diferent scenario. When merging marginalized total preorders, the
information encoded over pairwise disjoint signatures is interpreted as independent from and irrelevant to each
other. Our focus is on constructing a coherent global revision result from the results of local revisions,
in order to make the whole process more eficient. To the best of our knowledge, there currently exist
no merging strategies for marginalized TPOs. In [
(3) The additivity of OCFs is very similar in spirit to (and in fact our main inspiration for) what we call level-order merging of total preorders in this paper.
The notion of syntax splitting we consider in this paper goes back to Parikh [
Parikh originally formulated this concept as an axiom (P) for propositional revision of belief sets.
In [
Definition 1 (marginalization Ψ↓Θ). Let Ψ = (Σ, Ω, ⪯ Ψ) be an epistemic state, and let Θ ⊆ Σ. The marginalization of Ψ on Θ is an epistemic state Ψ↓Θ = (Θ, ΩΘ, ⪯ Ψ↓Θ ) with ΩΘ = {Θ | ∈ Ω} and: 1Θ ⪯ Ψ↓Θ 2Θ if 1Θ ⪯ Ψ 2Θ.
(4)
When the epistemic state Ψ is clear from context, or when the specific state does not matter and we only focus on the total preorder, we sometimes write ⪯ ↓Θ instead of ⪯ Ψ↓Θ in order to ease notation a bit, and talk about the marginalization of the total preorder instead of the marginalization of the corresponding epistemic state.
Definition 2 (TPO splitting [
1Σ ⪯ Ψ↓Σ 2Σ .
We use the symbol * to denote revision operators for epistemic states. We presuppose that * is able to
deal with epistemic states and formulas over any signature, i.e., it may be used both for global revision
(of epistemic states defined over the whole signature Σ) and local revision (of epistemic states defined
over subsignatures Σ′ ⊆ Σ). However, * does not have to make a connection between global and local
revision scenarios; (Ψ * )↓Σ′ and Ψ↓Σ′ * may lead to completely diferent results, even if only
contains information about Σ′. The syntax splitting postulates from [
(Ψ * )↓Σ = (Ψ↓Σ ) * . (Pit ) Let Ψ be an epistemic state defined on Σ that splits over (Σ1, . . . , Σ). Let = {1, . . . , } with ∈ ℒ(Σ) be the new information. Then Ψ * splits over (Σ1, . . . , Σ).
(MR) makes an explicit connection between global and local revision scenarios, given that the new
information fits a syntax splitting of Ψ. More precisely, (MR) states that it should not matter whether
you first revise the whole epistemic state and then marginalize to Σ, or marginalize first and only
locally revise with the relevant information. (Pit ), on the other hand, states that the splitting should be
preserved, but not how the individual should (or should not) influence the individual parts of the
belief state. This ensures that no unnecessary syntactical dependencies are introduced by the revision.
Hence, these two postulates formulate two diferent requirements for iterated revision operators, and
neither of the two postulates implies the other [
(5) (6) (7) (8) In this section we will show that (MR) and (Pit ) can indeed be brought together by defining a simple iterated revision operator which satisfies both postulates.
First, we define a measure for how much a set of formulas and a possible world deviate from each other as the number of formulas in that are not satisfied by :
() := |{ ∈ | ̸|= }| .
Next we define a variation of the (simplified) lexicographic revision operator proposed in [
Definition 3 (Multiple SimpLex Revision). Let Ψ be an epistemic state over Σ, and let ⊆ ℒ be a consistent set of formulas. Then the multiple SimpLex (MSL) revision operator * ℓ is defined via the following conditions. (MSL1) If (1) = (2), then: 1 ⪯ Ψ* ℓ 2 if 1 ⪯ Ψ 2. (MSL2) If (1) < (2), then: 1 ≺ Ψ* ℓ 2.
The two conditions given in the definition above uniquely define the posterior TPO ⪯ Ψ* ℓ. Moreover,
it is easy to show that this operator fits into the popular AGM framework 1 [
Proof. For all ∈ Mod() it holds that () = 0, and for all ′ ∈/ Mod() there must be some ∈ such that ′ ̸|= , which implies (′) > 0. Hence ≺ Ψ* ℓ ′ due do Definition 3. Therefore, if a world is minimal according to ⪯ Ψ* ℓ, then it must be a model of . Now let 1, 2 ∈ Mod(). Then (1) = (2), which implies 1 ⪯ Ψ* ℓ 2 if 1 ⪯ Ψ 2 according to Definition 3. Therefore, min(Mod(), ⪯ Ψ* ℓ) = min(Mod(), ⪯ Ψ).
The following example illustrates how the MSL operator works.
Example 1. Let Ψ = (ΣΨ, ΩΨ, ⪯ Ψ) be an epistemic state over the signature ΣΨ = {, , }. The total preorder ⪯ Ψ is given below, with possible worlds represented as conjunctions of literals, and worlds in the same column being considered equally plausible with respect to Ψ.
Ψ : ≺ Ψ ≺ Ψ ≺ Ψ
Now let = {(¬ ∨ ¬), ¬}. The revision Ψ * ℓ now results in the following TPO: (9) (10) (11) (12) ≺ Ψ* ℓ ⏟ deviati⏞on 0 dev⏟iati⏞on 1 ⏟ deviati⏞on 2 Ψ * ℓ : ≺ Ψ* ℓ ≺ Ψ* ℓ ≺ Ψ* ℓ
As shown above, the possible worlds are staggered with respect to their deviation from the new information (given by ), with equally-deviating worlds keeping their original relative ordering. Proposition 2. The revision operator * ℓ satisfies (P it).
Proof. Let Ψ be an epistemic state defined over Σ, and let {Σ1, . . . , Σ} be a TPO-splitting of ⪯ Ψ. Furthermore, let = {1, . . . , } ⊆ ℒ with ∈ ℒ(Σ). Let Φ = Ψ * ℓ be the revision result.
Now choose ∈ {1, . . . , }, and let 1, 2 ∈ Ω with 1Σ∖Σ = 2Σ∖Σ . In order to prove satisfaction of (Pit ), we need to show that the equivalence 1 ⪯ Φ 2 if 1Σ ⪯ Φ↓Σ 2Σ holds. We make a case distinction on whether exactly one of the two worlds 1, 2 satisfies :
Case 1: Let 1 |= and 2 ̸|= (without loss of generality). Then (1) < (2), resulting in 1 ≺ Φ 2. Now let 2′ ∈ min(Mod(2Σ ), ⪯ Φ). Since 2 ̸|= , also 2′ ̸|= holds. Now let 1′ be defined by
1′ := 1Σ ∧ (2′)Σ∖Σ .
Because of this construction, we have (1′) < (2′), resulting in 1′ ≺ Φ 2′, i.e. there is a model of
1Σ that is more plausible in ⪯ Φ than the minimal models of 2Σ . Therefore, 1 ≺ Φ↓Σ 2. Hence, (11)
holds for 1, 2.
1Originally, the AGM approach only considered revision of belief sets by single propositions [
Case 2: Let either 1, 2 |= , or 1, 2 |= ¬. Then (1) = (2) and 1 ⪯ Φ 2 holds if 1 ⪯ Ψ 2 holds. Assume 1 ⪯ Ψ 2 (without loss of generality). Using the same construction (12) as in the previous case, it follows that the minimal models of 1Σ in ⪯ Φ are at least as plausible as the minimal models of 2Σ . Hence 1 ⪯ Φ↓Σ 2, i.e., (11) holds.
Proposition 3. The revision operator * ℓ satisfies (MR).
Proof. Let Ψ be an epistemic state defined over Σ, and let {Σ1, . . . , Σ} be a TPO-splitting of ⪯ Ψ. Furthermore, let = {1, . . . , } ⊆ ℒ with ∈ ℒ(Σ). Let Φ = Ψ * ℓ be the revision result.
Now choose ∈ {1, . . . , }, and let 1 , 2 ∈ Ω(Σ). In order to prove satisfaction of (MR), we need to show that the equivalence 1 ⪯ Φ↓Σ 2 if 1 ⪯ (Ψ↓Σ )* ℓ 2 holds. In this proof, we will make use of Proposition 2, i.e. Ψ having a TPO-splitting implies the same TPO-splitting for Φ.
Direction “⇒”: Let 1 ⪯ Φ↓Σ 2 . We make a case distinction with respect to .
• Case 1: 1 |= and 2 ̸|= . Because of (1 ) < (2 ), it follows directly from (MSL2) that 1 ≺ (Ψ↓Σ )* ℓ 2 . • Case 2: 1 ̸|= and 2 |= . This would mean (1 ) > (2 ), which would imply 1 ≻ Φ↓Σ 2 due to (MSL2), contradicting the assumption that 1 ⪯ Φ↓Σ 2 . Therefore, this case is impossible. • Case 3: Both 1 , 2 |= , or both 1 , 2 |= ¬. Because we have a TPO-splitting, 1 ⪯ Φ↓Σ 2 implies that 1 ⪯ Φ 2 for all 1, 2 ∈ Ω with 1Σ = 1 , 2Σ = 2 , and 1Σ∖Σ = 2Σ∖Σ . Now choose 2 ∈ min(Mod(2 ), ⪯ Ψ), and let 1 be defined by
1 := 1 ∧ 2Σ∖Σ .
Then (1) = (2), and we have 1 ⪯ Ψ 2 according to (MSL1). Since 2 is a minimal model of 2 in ⪯ Ψ, it follows that 1 ⪯ Ψ↓Σ 2 . Therefore, (MSL1) requires that 1 ⪯ (Ψ↓Σ )* ℓ 2 . Direction “⇐”: Let 1 ⪯ (Ψ↓Σ )* ℓ 2 . We make a case distinction with respect to . • Case 1: 1 |= and 2 ̸|= . Let 2 ∈ min(Mod(2 ), ⪯ Φ), and let 1 be defined by 1 := 1 ∧ 2Σ∖Σ . (13) (14) (15) (16)
In order to summarize the main result of this section, we combine Propositions 2 and 3 into the following theorem.
Theorem 4. The revision operator * ℓ satisfies both (MR) and (P it), and thus (PMR).
Then (1) < (2) and, therefore, 1 ≺ Φ 2 due to (MSL2). Since 2 is a minimal model of 2 in ⪯ Φ, it follows that 1 ≺ Φ↓Σ 2 . • Case 2: 1 ̸|= and 2 |= . This would mean (1 ) > (2 ), which would imply 1 ≻ (Ψ↓Σ )* ℓ 2 due to (MSL2), contradicting the assumption that 1 ⪯ (Ψ↓Σ )* ℓ 2 . Therefore, this case is impossible. • Case 3: Both 1 , 2 |= , or both 1 , 2 |= ¬. Then 1 ⪯ Ψ↓Σ 2 follows directly from 1 ⪯ (Ψ↓Σ )* ℓ 2 according to (MSL1). Because we have a TPO-splitting, it follows that 1 ⪯ Ψ 2 for all 1, 2 ∈ Ω with 1Σ = 1 , 2Σ = 2 , and 1Σ∖Σ = 2Σ∖Σ . Now choose 2 ∈ min(Mod(2 ), ⪯ Φ), and let 1 be defined by
1 := 1 ∧ 2Σ∖Σ .
Then (1) = (2), and 1 ⪯ Φ 2 follows from 1 ⪯ Ψ 2 due to (MSL1). Since 2 is a minimal model of 2 in ⪯ Φ, it follows that 1 ⪯ Φ↓Σ 2 .
In the previous section, we showed that there is a revision operator which satisfies both (MR) and (P it). In this section, we want to build upon the concept of marginalized revision to obtain more general localized revision operators complying with the syntax splitting postulates. The idea is to first revise the marginalized epistemic states independently from each other, and then merge the results together.
In this paper, we use the symbol △ to denote merging operators for epistemic states that take two epistemic states as input and produce one merged epistemic state as output. In order to simplify notation, we stipulate that △ is left-associative, i.e. Ψ1 △ Ψ2 △ Ψ3 = (Ψ1 △ Ψ2) △ Ψ3. Note that △ may be commutative, but does not have to be; i.e., we may have Ψ1 △ Ψ2 ̸= Ψ2 △ Ψ1. For most of the results in this section, this does not make a big diference, since we do not consider any additional preferences over the epistemic states themselves during merging. However, we will briefly talk about non-commutative merging towards the end of this section.
Because we are mainly interested in syntax splitting properties, we want to merge marginalized epistemic states defined over disjoint signatures. This means that the possible worlds which the epistemic states respectively talk about do not share any atoms, whereas the merged epistemic state’s possible worlds should be defined over the combined signature. Therefore, we define the set of possible worlds over the combined signature as follows.
Definition 4 (Combined Possible Worlds). Let Σ1, Σ2 be signatures with Σ1 ∩Σ2 = ∅. Let Ω1 ⊆ Ω(Σ1), and Ω2 ⊆ Ω(Σ2). Then the combined set of possible worlds Ω1 ⊗ Ω2 ⊆ Ω(Σ1 ∪ Σ2) is defined by: (Ω1 ⊗ Ω2) := {12 | (1, 2) ∈ (Ω1 × Ω2)} .
Let Ψ1, . . . , Ψ be epistemic states represented by total preorders over sets of possible worlds Ω1, . . . , Ω, which are respectively defined over pairwise disjoint signatures Σ1, . . . , Σ. As the result of merging Ψ1, . . . , Ψ we henceforth expect an epistemic state represented by a total preorder over the combined possible worlds. More precisely, (Ψ1 △ . . . △ Ψ) := (Σ△, Ω△, ⪯ △) such that Σ△ = ⋃︀=1 Σ, Ω△ = Ω1 ⊗ . . . ⊗ Ω, and ⪯ △ ⊆ Ω△ × Ω△. We can now define revision via merging of localized revision results as follows.
Definition 5 (⊛△). Let Ψ be an epistemic state, let {Σ1, . . . , Σ} be a splitting of ⪯ Ψ, and let = {1, . . . , } with ∈ ℒ(Σ) for ∈ {1, . . . , }. Let * be a revision operator, and let △ be a merging operator. Then the revision operator ⊛△ is defined by
Ψ ⊛△ = (Ψ↓Σ1 * 1) △ . . . △ (Ψ↓Σ * ).
When merging Ψ1, . . . , Ψ, there should be no information conflicts since every epistemic state is concerned with a domain that is diferent from all others. Therefore, we expect that the merging is performed such that the individual Ψ can be recovered via marginalization. This is expressed by the following property: (17) (18) (ReMarg) (Ψ1 △ . . . △ Ψ)↓Σ = Ψ
Moreover, the merging should not introduce any dependencies between atoms from diferent Σ. Hence, the merged epistemic state should split over the original signatures. (MSplit) (Ψ1 △ . . . △ Ψ) splits over (Σ1, . . . Σ).
Just like (MR) and (Pit), these two merging postulates do not imply each other, i.e. they indeed specify
diferent requirements of merging operators. Counterexamples would be very similar to the ones
provided in [
Theorem 5. Let * be a revision operator, let △ be a merging operator, and let ⊛△ be the revision operator constructed from (* , △) via Definition 5. Then the following propositions holds: • If △ satisfies (ReMarg), then ⊛△ satisfies (MR).
• If △ satisfies (MSplit), then ⊛△ satisfies (P it).
Proof. Let Ψ be an epistemic state that splits over {Σ1, . . . , Σ}. Let = {1, . . . , } with ∈ ℒ(Σ). For (Pit ), assume that △ satisfies (MSplit). Then Ψ ⊛△ splits over {Σ1, . . . , Σ}, i.e. (Pit ) holds. For (MR), let △ satisfy (ReMarg) and observe that
(Ψ ⊛△ )↓Σ = (︀ (Ψ↓Σ1 * 1) △ . . . △ (Ψ↓Σ * ))︀ ↓Σ .
With (ReMarg), it follows that (Ψ ⊛△ )↓Σ = (Ψ↓Σ * ). The state Ψ↓Σ trivially splits over {Σ}. In this case ⊛△ and * coincide. Thus (Ψ ⊛△ )↓Σ = Ψ↓Σ ⊛△ and we are done.
As an easy consequence of Theorem 5, the revision operator ⊛△ from Definition 5 satisfies (P the utilized merging operator △ satisfies (ReMarg) and (MSplit). Next we are going to investigate how such a merging operator △ can be designed.
MR) if (19) (20) (21)
The first basic step towards merging total preorders, which are defined over disjoint subsignatures, is to define how relationships between possible worlds from the individual ⪯ should be adopted into the merged relation ⪯ △. The following definition gives us the core of the merged relation, i.e., it captures the relationships which we want to hold in any version of ⪯ △.
Definition 6 (Product Combination of TPOs). Let ⪯ 1, . . . , ⪯ be total preorders over Ω1, . . . , Ω, respectively, with Ω ⊆ Ω(Σ) for all ∈ {1, . . . , }, and Σ ∩ Σ = ∅ for all ̸= . The product combination of these TPOs, denoted as ⪯ ⊗ = (⪯ 1 ⊗ . . . ⊗ ⪯ ), is a relation over Ω1 ⊗ . . . ⊗ Ω, such that for all (1, . . . , ), (1′, . . . , ′) ∈ (Ω1 × . . . × Ω): 1 . . . ⪯ ⊗ 1′ . . . ′ if
⪯ ′ for all ∈ {1, . . . , }.
In essence, the product combination is what is called a product order in order theory (see e.g. [15]), except that it is defined on Ω1 ⊗ . . . ⊗ Ω instead of the Cartesian product Ω1 × . . . × Ω. The resulting order ⪯ ⊗ is a preorder, i.e. a reflexive and transitive relation, but it is usually not total: if there are , ′ ∈ Ω and , ′ ∈ Ω (, ∈ {1, . . . , }) such that ≺ ′ and ≺ ′ , then ′ and ′ are incomparable with respect to ⪯ ⊗ . Since we assume in this paper that epistemic states are uniquely identified by TPOs, we will also talk about the “product combination of epistemic states Ψ1, Ψ2” when we mean the product combination of ⪯ Ψ1 and ⪯ Ψ2 .
Example 2. Let Ψ1, Ψ2 be defined by the following total preorders: Ψ1 : Ψ2 : ≺ 1 ≺ 2 ≺ 1 ≺ 2 ≺ 1 ≺ 2 , .
The product combination of Ψ1 and Ψ2 as given by Definition 6, i.e. the preorder ⪯ ⊗ = (⪯ 1 ⊗ ⪯ 2), is visualized in Figure 1. Note that the elements along the diagonals in “antidiagonal” direction, e.g. and , are incomparable with respect to ⪯ ⊗ .
Since ⪯ ⊗ is not necessarily a total order, we need to extend this relation in order to represent a full epistemic state.
Definition 7 (faithful extension). Let ⪯ be a preorder, i.e. a reflexive and transitive relation, over some set . Let ⪯ ′ be a preorder over that extends ⪯ , i.e. ⪯ ⊆ ⪯ ′. We call this extension faithful if for all , ∈ , it holds that: ≺ implies ≺ ′ .
≺ ≺ ≺ ≺ ≺ ≺
≺ ≺ ≺
≺ ≺ ≺
≺ ≺ ≺ ≺ ≺
≺ ≺ ≺ ≺ ≺ ≺ ≺
In other words, a faithful extension of a preorder preserves all strict preferences and all equalities. This means that the only additional preferences introduced by a faithful extension are preferences among elements which were incomparable before. Clearly, every preorder is a faithful extension of itself. Moreover, all faithful extensions of a preorder have the same minimal (and maximal) worlds as the original preorder they extend. For product combinations, this property can be generalized to the Lemma below.
Lemma 6. Let Ψ1, . . . , Ψ be epistemic states with Ψ = (Σ, Ω, ⪯ ) for all ∈ {1, . . . , }, and Σ ∩ Σ = ∅ for all ̸= . Let ⪯ △ be a faithful extension of ⪯ ⊗ = (⪯ 1 ⊗ . . . ⊗ ⪯ ). Then for all ∈ {1, . . . , } and ∈ Ω, the following holds:
min(Mod(), ⪯ △) = {1 . . . (− 1)(+1) . . . | ∈ min(Mod(Ω ), ⪯ ) for all ̸= } . (22) Proof. First we show the direction “⊆ ”: Let ∈ min(Mod(), ⪯ △). By construction, has the form = 1 . . . (− 1)(+1) . . . with ∈ Ω for all ∈ {1, . . . , }. Suppose that there was some such that ∈/ min(Mod(Ω ), ⪯ ). Then there is ′ ∈ Ω with ′ ≺ . Let ′ be the world obtained by replacing with ′ in . Then ′ ≺ ⊗ according to Definition 6, which implies ′ ≺ △ due to Definition 7. This means that cannot be a minimal model of in ⪯ △, which contradicts the initial assumption that ∈ min(Mod(), ⪯ △).
“⊇ ”: Let ∈ min(Mod(Ω ), ⪯ ) for all ̸= , and let = 1 . . . (− 1)(+1) . . . . Suppose that there was some ′ |= such that ′ ≺ △ . Then, due to Definition 7, either ′ ≺ ⊗ or , ′ are incomparable w.r.t. ⪯ ⊗ .
Case 1: ′ ≺ ⊗ . Then ′ ⪯ for all , ′ ∈ Ω such that |= and ′ |= ′ . Moreover, there must be at least one such pair , ′ ∈ Ω with |= and ′ |= ′ such that ′ ≺ . However, that means ∈/ min(Mod(Ω), ⪯ ), contradicting the initial assumption that ∈ min(Mod(Ω ), ⪯ ) for all ̸= .
Case 2: , ′ are incomparable w.r.t. ⪯ ⊗ . Then there must be , ′ ∈ Ω and , ′ ∈ Ω (, ∈ {1, . . . , }) with such that |= and ′ |= ′ ′ such that ≺ ′ and ′ ≺ . However, that means again ∈/ min(Mod(Ω), ⪯ ), causing a contradiction.
Lemma 6 essentially states that the minimal models of every ∈ Ω according to ⪯ △ are those constructed from and minimal worlds in all other Ψ with ̸= . As a consequence, marginalization is preserved.
Proposition 7. Let Ψ1, . . . , Ψ be epistemic states with Ψ = (Σ, Ω, ⪯ ) for all , and Σ ∩ Σ = ∅ for all ̸= . Let ⪯ △ be a faithful extension of ⪯ ⊗ = (⪯ 1 ⊗ . . . ⊗ ⪯ ). Then for all ∈ {1, . . . , } the following holds:
△ ⪯ ↓Σ = ⪯ ⊗↓Σ = ⪯ . (23) Proof. Lemma 6 directly implies that the minimal models of are the same in ⪯ △ and ⪯ ⊗ , because △ ⪯ ⊗ is a faithful extension of itself. Hence, the equality ⪯ ↓Σ = ⪯ ⊗↓Σ holds.
Let , ′ ∈ Ω. According to Lemma 7, the minimal models of and ′ in ⪯ ⊗ have the form and ′ , respectively, with ∈ (Ω1 ⊗ . . . ⊗ Ω(− 1) ⊗ Ω(+1) ⊗ . . . ⊗ Ω). It follows with Definition 6 that ⪯ ⊗ ′ if ⪯ ′. Therefore, the equality ⪯ ⊗↓Σ = ⪯ holds.
Besides the marginalizations, faithful extension also preserve the splitting over the original signatures. Proposition 8. Let Ψ1, . . . , Ψ be epistemic states with Ψ = (Σ, Ω, ⪯ ) for all , and Σ ∩ Σ = ∅ for all ̸= . Let ⪯ △ be a faithful extension of ⪯ ⊗ = (⪯ 1 ⊗ . . . ⊗ ⪯ ). Then ⪯ △ splits over {Σ1, . . . , Σ}. Proof. Let , ′ ∈ Ω△ and let ∈ {1, . . . , }. Note that Σ = and (′)Σ = ′ for some , ′ ∈ Ω due to Definition 6. Therefore, we have to show that ⪯ △ ′ if ⪯ ↓△Σ ′ holds for all ∈ (Ω1 ⊗ . . . ⊗ Ω(− 1) ⊗ Ω(+1) ⊗ . . . ⊗ Ω).
“⇒”: Assume w.l.o.g. that ⪯ △ ′ . Then ′ ⊀ △ . Due to Definition 7, this means △ ′ ⊀ ⊗ . Hence ′ ⊀ , which is equivalent to ⪯ ′. Therefore, ⪯ ↓Σ ′ follows with Proposition 7.
“⇐”: Assume w.l.o.g. that ⪯ ↓△Σ ′. Due to Proposition 7, this is equivalent to ⪯ ′. Then by Definition 6, ⪯ ⊗ ′ holds for all ∈ (Ω1 ⊗ . . . ⊗ Ω(− 1) ⊗ Ω(+1) ⊗ . . . ⊗ Ω), which implies ⪯ △ ′ since ⪯ △ extends ⪯ ⊗ .
Propositions 7 and 8 together directly imply the following theorem.
Theorem 9. Let Ψ1, . . . , Ψ be epistemic states with Ψ = (Σ, Ω, ⪯ ) for all ∈ {1, . . . , }, and Σ ∩ Σ = ∅ for all ̸= . Let Ψ△ = (Σ△, Ω△, ⪯ △) = Ψ1 △ . . . △ Ψ be the result of merging these epistemic states via a merging operator △. If ⪯ △ is a faithful extension of ⪯ ⊗ = (⪯ 1 ⊗ . . . ⊗ ⪯ ), then △ satisfies both (ReMarg) and (MSplit).
Theorem 9 provides us with a blueprint for TPO merging operators that satisfy (ReMarg) and (MSplit). We will now define a concrete merging operator that satisfies this property, i.e., one that merges TPOs by creating a faithful extension of their product combination.
Definition 8 (level-order merging operator). Let Ψ1 = (Σ1, Ω1, ⪯ 1), Ψ2 = (Σ2, Ω2, ⪯ 2) be epistemic states with Σ1 ∩ Σ2 = ∅. Let 1 = (⪯ 1) and 2 = (⪯ 2). Then the level-order merging operator △lvl is defined by 12 ⪯ Ψ1△lvlΨ2 1′2′ if 1(1) + 2(2) ≤ 1(1′) + 2(2′) (24) for all 1, 1′ ∈ Ω1 and 2, 2′ ∈ Ω2.
The level-order2 merging operator combines worlds into one layer3 based on their distance from the lowermost layer in the product combination. To illustrate this, look again at Figure 1: each incomparable diagonal (see Example 2) becomes one layer in the merging result. Therefore, all strict preferences and equalities from the product combination are respected in the level-order merging result. Since level-order merging is based on addition of natural numbers, it is clear that it is both commutative and associative. Hence, Definition 8 can easily be generalized to merging an arbitrary number of epistemic states.
3The layers of a TPO ⪯ Ψ are the equivalence classes of worlds with respect to ≈ Ψ.
Proposition 10. The level-order merging operator satisfies both (ReMarg) and (MSplit). Proof. We prove the proposition via Theorem 9 by showing that ⪯ △ = ⪯ Ψ1△lvlΨ2 is a faithful extension of the product combination ⪯ ⊗ = (⪯ 1 ⊗ ⪯ 2). First observe that 1 ⪯ 1 1′ and 2 ⪯ 2 2′ together imply 1(1) + 2(2) ≤ 1(1′) + 2(2′). Hence ⪯ ⊗ ⊆ ⪯ △. Moreover, 1 ≺ 1 1′ and 2 ⪯ 2 2′ (w.l.o.g.) together imply 1(1) + 2(2) < 1(1′) + 2(2′). Therefore, 12 ≺ ⊗ 1′2′ implies 12 ≺ △ 1′2′. This means that ⪯ △ is a faithful extension of ⪯ ⊗ , and the proposition follows via Theorem 9.
Of course, level-order merging is not the only possible merging operator based on faithful extensions. A classic way of extending a product order to a total order is to construct a so-called lexicographic order [15], which could also be used for merging. However, note that the merging operator defined below is not commutative, i.e., the order of the epistemic states matters for the merging result. Definition 9 (lexicographic merging operator). Let Ψ1 = (Σ1, Ω1, ⪯ 1), Ψ2 = (Σ2, Ω2, ⪯ 2) be epistemic states with Σ1 ∩ Σ2 = ∅. The lexicographic merging operator △lex is defined by 12 ⪯ Ψ1△lexΨ2 1′2′ if (1 ≺ 1 1′) or (1 ≈ 1 1′ and 2 ⪯ 2 2′) (25) for all 1, 1′ ∈ Ω1 and 2, 2′ ∈ Ω2.
Despite not being commutative, the lexicographic merging operator defines a faithful extension of the product combination, and thus also preserves marginalization and splitting of the marginalized total preorders.
Proposition 11. The lexicographic merging operator satisfies both (ReMarg) and (MSplit). Proof. Similar to the previous result, we prove the proposition by showing that ⪯ △ = ⪯ Ψ1△lexΨ2 is a faithful extension of ⪯ ⊗ = (⪯ 1 ⊗ ⪯ 2). Observe that 1 ⪯ 1 1′ and 2 ⪯ 2 2′ together imply 12 ⪯ Ψ1△lexΨ2 1′2′, i.e. ⪯ ⊗ ⊆ ⪯ △. If 12 ≺ ⊗ 1′2′, then (1 ≺ 1 1′ and 2 ⪯ 2 2′), or (1 ⪯ 1 1′ and 2 ≺ 2 2′). If 1 ≺ 1 1′, then 12 ≺ △ 1′2′ follows directly from Definition 9. Otherwise, if (1 ⪯ 1 1′ and 2 ≺ 2 2′) still holds, we must have 1 ≈ 1 1′. Then 12 ≺ △ 1′2′ also follows via Definition 9. Therefore, ⪯ △ is a faithful extension of ⪯ ⊗ , and the proposition follows via Theorem 9.
Illustrating lexicographic merging again with Figure 1, the operator essentially proceeds “columnwise” from left to right, by appending the relative order between the -worlds to the relative order between the -worlds and so on. This makes the first epistemic state take priority over the second one, which might make sense in some scenarios. For example, if the TPOs represent plausibilities on diferent scales, i.e., if is vastly more plausible than , but is only slightly more plausible than , then one might desire to have all -worlds be more plausible than all -worlds.
In terms of propositional beliefs, however, the order in which the epistemic states are merged does not matter even when using non-commutative merging operators like lexicographic merging, as long as they are based on faithful extensions of product combinations. Since propositional beliefs only depend on the minimal worlds in the final merging result, and all faithful extensions have the same minimal worlds, they must share the same propositional beliefs as well.
We finish this section with the following example, which shows how the two merging operators △lvl and △lex may be used in a belief revision scenario in order to implement syntax splitting. Example 3. Consider again the total preorder ⪯ Ψ from Example 1, Equation (9). Instead of revising the complete TPO, we now want to revise Ψ↓Σ1 and Ψ↓Σ2 with Σ1 = {, }, Σ2 = {} independently, and merge the results together afterwards. These marginalizations of Ψ are given as follows:
Now we revise these marginalized TPOs with 1 = (¬ ∨ ¬) resp. 2 = ¬ using the MSL-revision operator4. Let Ψ*1 = Ψ↓Σ1 * ℓ 1 and Ψ*2 = Ψ↓Σ2 * ℓ 2. Then the revisions result in the following TPOs: Ψ*1 : .
Next, we use the merging operators presented in this section in order to obtain global revision results by = {1, 2} (in the spirit of Definition 5). The product combination of Ψ*1 and Ψ*2 is shown in Figure 2. First with △lvl, merging Ψ*1 and Ψ*2 leads to the following result: For the use of △lex, there are two possible results depending on which epistemic state is given priority: (27) (28) (29) (30) Clearly, all three global results shown above are diferent from each other. Depending on the specific use case, one may prefer one of them, or accept any result (e.g. if only propositional beliefs are relevant). As expected (because of Theorem 5 and Theorem 9), all three revision results adhere to the syntax splitting postulate (PMR). As a further remark, none of these results coincides with the MSL-revision result from Example 1, Equation (10). This is also expected since the MSL-revision operator * ℓ uses some information from Ψ which is lost during marginalization. Nevertheless, the TPO given in Equation (10) is also a faithful extension of the product combination of Ψ*1 and Ψ*2.
In this paper, we have shown how total preorders defined over disjoint signatures can be combined
while preserving desirable properties which we have introduced via the postulates (ReMarg) and
(MSplit). These postulates are satisfied if the merged total preorder is a faithful extension of the product
combination of the original TPOs. Performing localized revision on marginalized epistemic states, and
merging afterwards with an appropriate merging operator satisfying (ReMarg) and (MSplit), yields
a global revision operator that satisfies the iterated syntax splitting postulates (P it) and (MR). We
have investigated two such merging operators, namely the level-order and the lexicographic merging
operator, and have shown that they satisfy (ReMarg) and (MSplit). In future work we will investigate
merging in cases where the signatures of the marginalized total preorders are not disjoint but may
4Technically, MSL revision with a single formula coincides with regular lexicographic revision [
This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), project number 512363537, grant KE 1413/15-1 awarded to Gabriele Kern-Isberner and grant BE 1700/121 awarded to Christoph Beierle. Alexander Hahn was supported by grant KE 1413/15-1, and Lars-Phillip Spiegel was supported by grant BE 1700/12-1.
[14] J. Delgrande, Y. Jin, Parallel belief revision: Revising by sets of formulas, Artificial Intelligence 176 (2012) 2223–2245. doi:10.1016/j.artint.2011.10.001. [15] B. A. Davey, H. A. Priestley, Introduction to Lattices and Order, 2 ed., Cambridge University Press, 2002. doi:10.1017/CBO9780511809088. [16] G. Kern-Isberner, J. Heyninck, C. Beierle, Conditional independence for iterated belief revision, in: L. De Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, ijcai.org, 2022, pp. 2690–2696. doi:10. 24963/ijcai.2022/373. [17] G. Kern-Isberner, A thorough axiomatization of a principle of conditional preservation in belief revision, Annals of Mathematics and Artificial Intelligence 40(1-2) (2004) 127–164.