Strong Syntax Splitting for Iterated Belief Revision

1 Introduction

AGM theory [Alchourr´on et al., 1985; G¨ardenfors and Makinson, 1988], named after its inventors Alchourr´on, G¨ardenfors and Makinson, is by far the most influential formal account of belief revision, and the AGM postulates are widely accepted as properties rational revision functions should possess. In spite of its popularity, there are two main problems with the original AGM approach. First of all, AGM specifies revision in dependance of the prior belief set only rather than as a fully binary operator: there is no connection between revision operators on different prior belief sets of a given language. If we think of a binary AGM operator as a family of revision operators, each being based on some belief set of L, no connections are imposed between different operators by AGM. This issue has been addressed in iterated revision (for a seminal paper, see [Darwiche and Pearl, 1997]) where AGM theory was extended in a way such that also such connections are captured. A crucial point for this extension is that iterated revision works on epistemic states and their associated total preorders rather than on belief sets. This way adequate semantical structures on possible worlds are provided which allow us to perform AGM revision without losing the connections missing in the original AGM approach.

There is a second problem, first pointed out by Parikh [Parikh, 1999]: AGM revision is not local: beliefs which are entirely irrelevant to the new information may be affected. In a nutshell, in AGM new information about, say, your favourite soccer team my affect your beliefs on the breeding behaviour of penguins in the arctic. To avoid such undesired effects, Parikh proposed to extend the AGM postulates with an additional axiom (P) building on the notion of syntax splitting. This allows to set up local contexts for revision.

Recent work [Peppas et al., 2015] elaborates on constraints on total preorders that implement the strong version of (P). Strong (P) not only considers revision as a fully binary operator taking a prior belief set and a new sentence, but also claims relations between revision on different prior belief sets. [Peppas et al., 2015] aims at characterizing the subclass of faithful preorders that induce revision operators satisfying axiom (P) in addition to the AGM postulates. However, this work is based on belief sets, not on epistemic states, and uses total preorders as structures providing meta information for AGM revision. Therefore, it cannot capture iterated belief revision.

The analysis we provide in this paper goes significantly beyond [Peppas et al., 2015] in various respects. Our contributions are the following:

• We introduce a concept of syntax splitting for the revision of epistemic states. This concept is in compliance with AGM and [Darwiche and Pearl, 1997]. In particular, we show that marginalization of epistemic states (well-known from probabilistics) is a perfect means to implement techniques of syntax splitting.
• We generalize the properties considered in [Peppas et al., 2015] for epistemic states and hence for iterated revision. Moreover, we study revision by sets of sentences.
• We study the concept of epistemic syntax splitting in the specific framework of ordinal conditional functions (OCFs, [Spohn, 1988]), and present c-revisions as a proper means to realize epistemic syntax splitting. This also provides connections to revision via the principle of minimum cross-entropy in probability theory.

The rest of the paper is organized as follows. In Sect. 2 we introduce relevant formal preliminaries. Sect. 3 discusses aspects of AGM theory and related work relevant to the topic of this paper. Our generalization of syntax splitting to epistemic states is presented in Sect. 4. Sect. 5 then studies epistemic syntax splitting in the context of ordinal conditional functions. Finally, Sect. 6 concludes.

For lack of space all proofs are omitted.

2 Formal Preliminaries

Let L be a finitely generated propositional language over an alphabet Σ with atoms a, b, c, . . ., and with formulas A,B,C, . . .. For conciseness of notation, we will omit the logical and-connector, writing AB instead of A ∧ B, and overlining formulas will indicate negation, i.e. A means ¬A. Let Ω denote the set of possible worlds over L; Ω will be taken here simply as the set of all propositional interpretations over L. ω |= A means that the propositional formula A ∈ L holds in the possible world ω ∈ Ω; then ω is called a model of A, and the set of all models of A is denoted by Mod (A). For propositions A,B ∈ L, A |= B holds iff Mod (A) ⊆ Mod (B), as usual. By slight abuse of notation, we will use ω both for the model and the corresponding conjunction of all positive or negated atoms. This will allow us to use ω both as an interpretation and a proposition, which will ease notation a lot. Since ω |= A means the same for both readings of ω, no confusion will arise.

Given a set of possible worlds Ω′ ⊆ Ω, T (Ω′ ) denotes the set of formulas which are true in all elements of Ω′ ,

For subsets Θ of Σ, let L(Θ) denote the propositional language defined by Θ, with associated set of interpretations Ω(Θ). Note that while each sentence of L(Θ) can also be considered as a sentence of L, the interpretations ωΘ ∈ Ω(Θ) are not elements of Ω if Θ ̸= Σ. But each interpretation ω ∈ Ω can be written uniquely in the form ω = ωΘωΘ with concatenated ωΘ ∈ Ω(Θ) and ωΘ ∈ Ω(Θ), where Θ = Σ\Θ is the complement of Θ in Σ. Note that the syntactical reading of interpretations as conjunctions makes perfect sense here: According to this reading, ω is a conjunction of ωΘ and ωΘ (with omitted ∧ symbol). We also call ωΘ the restriction of ω to Θ. If Ω′ ⊆ Ω is a subset of models, then Ω′ |Θ = {ωΘ|ω ∈ Ω′ } ⊆ Ω(Θ) restricts Ω′ to a subset of Ω(Θ).

For a proposition A ∈ L, let Σ(A) be the minimal subset of atoms of Σ in which A can be expressed. Note that tautologies ⊤ are part of any sublanguage L(Θ) of L.

Ordinal conditional functions (OCFs), (also called ranking functions) κ : Ω → N ∪ {∞} with κ-1 (0) ̸= ∅, were introduced (in a more general form) first by [Spohn, 1988]. They express degrees of plausibility of propositional formulas A by specifying degrees of disbeliefs of their negations A. More formally, we have κ(A) := min{κ(ω) | ω |= A}, so that κ(A ∨ B) = min{κ(A), κ(B)}. Hence, due to κ-1 (0) ̸= ∅, at least one of κ(A), κ(A) must be 0. A proposition A is believed if κ(A) > 0 (which implies particularly κ(A) = 0).

In more general settings, epistemic states Ψ will be represented by a total preorder ⪯Ψ on Ω which is most suitable in the context of belief revision (cf. Section 3). ⪯Ψ can be lifted to a total preorder on the set of propositions via A ⪯Ψ B iff there is a (minimal) ω ∈ Mod (A) such that ω ⪯Ψ ω′ for all

ω′ ∈ Mod (B). As usual, ω ≺Ψ ω′ iff ω ⪯Ψ ω′ and not ω′ ⪯Ψ ω, and ω ≈Ψ ω′ iff both ω ⪯Ψ ω′ and ω′ ⪯Ψ ω.

Note that also OCFs κ induce total preorders on Ω via ω1 ⪯κ ω2 iff κ(ω1) ⩽ κ(ω2), so everything we state on general epistemic states will apply to OCFs, but OCFs allow for more expressive statements because of their usage of natural numbers and the corresponding arithmetics.

If Ω′ ⊆ Ω, then min(Ψ,Ω′ ) = min(⪯Ψ,Ω′ ) = {ω′ ∈ Ω′ | ω′ ⪯Ψ ω′′ for all ω′′ ∈ Ω′ } denotes the set of minimal models in Ω′ . If Ω′ = Ω, then we simply write min(Ψ) instead of min(Ψ,Ω). If A ∈ L, then min(Ψ,A) = min(Ψ, Mod (A)). The minimal models of an epistemic state form its associated belief set: Bel (Ψ) = T (min(Ψ)), i.e., the agent believes exactly the propositions that are valid in all most plausible models. For an OCF κ, we have accordingly Bel (κ) = T ({ω ∈ Ω | κ(ω) = 0}).

Note that all these definitions depend crucially on the given language, i.e., if the logical language changes, the format of epistemic states will change, too. Sometimes we write Ψ = (Ω(Σ), ⪯Ψ) to make the format of Ψ explicit.

3 Syntax Splitting in Belief Revision and Related Work

The basic AGM theory [Alchourr´on et al., 1985] deals with belief revision in the context of belief sets, i.e., deductively closed sets of propositions, but also probability or possibility distributions have been considered already in the early years of belief revision as interesting and useful kinds of epistemic states (cf. [G¨ardenfors, 1988; Dubois and Prade, 1992]).

Whatever the type of epistemic state is, the question which epistemic structure is needed to guarantee that belief revision complies with AGM theory has been answered by [Katsuno and Mendelzon, 1991] and [Darwiche and Pearl, 1997]: AGM revision of an epistemic state Ψ can be ensured by assuming that a so-called faithful ranking underlies Ψ such that the revised beliefs can be computed from minimal models according to the ranking. Here, a faithful ranking is a total preorder ⪯Ψ on the possible worlds that is assigned to Ψ in such a way that the minimal models of ⪯Ψ (denoted by min(Ω,⪯Ψ) are precisely the models of the belief set K = Bel (Ψ) associated with Ψ.

Proposition 1 ([Darwiche and Pearl, 1997]) A revision operator ∗ that assigns a posterior epistemic state Ψ ∗ A to a prior state Ψ and a proposition A is an AGM revision operator for epistemic states iff there exists a faithful preorder ⪯Ψ for an epistemic state Ψ with associated belief set K = Bel (Ψ), such that for any proposition C it holds that

This proposition allows us to study AGM-style revisions by focussing on total preorders. An extension of this theorem for multiple revision of epistemic states by sets of propositions C = {C1, . . . , Cn} has been proved in [Delgrande and Jin, 2012]. Throughout this paper, we will assume that any (iterated, multiple) revision operator ∗ satisfies the epistemic AGM postulates, i.e. in particular, that Proposition 1 (respectively its appropriate extension) applies. Since epistemic states equipped with total preorders on worlds also encode implicitly revision strategies, revision of such epistemic states also deals with iterated revision (for further details, please cf. [Darwiche and Pearl, 1997]).

Parikh [Parikh, 1999] was the first to introduce syntax splitting in AGM-style revision. His axiom (P) [Parikh, 1999] aims to capture the intuition that whenever an agent's beliefs split over two disjoint sublanguages and the new information is expressed in one of the two, revision should not affect any belief expressed in the other sublanguage:

Parikh's notion of syntax splitting can be generalized as follows [Peppas et al., 2015]: Let (Σ1, . . . , Σn) be a partition of Σ, i.e., Σ = Σ1 ∪ . . . ∪Σn, and Σi ∩Σj = ∅ for i ̸= j. A belief set K splits over (Σ1, . . . ,Σn) iff there are propositions φi ∈ L(Σi), i = 1, . . . , n, such that K = Cn(φ1, . . . , φn). (Σ1, . . . ,Σn) is then called a K-splitting. In [Peppas et al., 2015] a weak and a strong reading of (P) were identified:

Strong (P) is equivalent to (R1) and (R2) (Theorem 1 of [Peppas et al., 2015]). Peppas et al. [Peppas et al., 2015] identified three conditions, called (Q1) - (Q3), that characterize faithful preorders ⪯ which induce revision operators that satisfy strong (P), i.e., (R1) and (R2). For presenting these conditions, we need to recall some technical details from [Peppas et al., 2015]). Let a theory K be given, and let F = (Fi)i∈I be its unique finest K-splitting [Parikh, 1999], i.e., for every other K-splitting (Σj)j∈J, each Fi is contained in some Σj. Then for a world ω, Diff(K, ω) = ⋃{Fi ∈ F | for some φ ∈ L(Fi),K |= φ and ω |= ¬φ}. For two worlds ω, ω′ , let diff(ω, ω′ ) denote the set of atoms that have different truth values in the two worlds. For a (contingent) proposition A and a world ω, ωA is the restriction of ω to L(A); for a preorder ⪯ on Ω, the A-filtering ⪯A of ⪯ is defined by ω ⪯A ω′ iff there is ω1 |= ωA such that for all ω′1 |= ω′A, ω1 ⪯ ω′1 .

• (Q1) If Diff(K, ω) ⊂ Diff(K, ω′ ) and diff(ω, ω′ ) ∩ Diff(K, ω) = ∅, then ω ≺ ω′ .
• (Q2) If Diff(K, ω) = Diff(K, ω′ ) and diff(ω, ω′ ) ∩ Diff(K, ω) = ∅, then ω ≈ ω′ .
• (Q3) If K = Cn(A,B) and Σ(A) ∩ Σ(B) = ∅, then ⪯AK =⪯ACn(A) .

The main result of [Peppas et al., 2015] is the following theorem, slightly modified to match the notations of this paper:

Theorem 1 ([Peppas et al., 2015], Theorem 6) Let ∗ be an AGM revision operator, and let {⪯K}K be a family of faithful preorders (one for each consistent belief set K, corresponding to ∗ by means of (1). Then ∗ satisfies (R1) and (R2) (i.e., strong (P)) iff {⪯K}K satisfies (Q1) - (Q3).

We summarize the main ideas of syntax splitting in belief revision that have been presented so far in a slightly more abstract and general way:

If the prior belief state splits over (Σ1, . . . ,Σn), and the new information concerns exactly one Σi, then the revised belief state should also split over (Σ1, . . . ,Σn), and only its Σi-part is affected by revision.

In the next section, we present a framework that implements this idea for revision of epistemic states and broadens the scope of (P) to deal with cases where the new information also splits up and triggers revisions on substates.

4 Syntax Splitting for Epistemic State Revision

In this section, we will generalize the approach of [Peppas et al., 2015] to syntax splitting of revision operators for epistemic states represented by total preorders. On the one side, we define a strong (P) axiom for the revision of epistemic states, and on the other side, we generalize the semantic conditions (Q1) - (Q3) of [Peppas et al., 2015] (see the previous section) appropriately. As a first step we will carry over the concept of marginalization which is well-known in probabilistics to general epistemic states Ψ and allows for an easy implementation of A-filtering and axiom (Q3) of [Peppas et al., 2015]:

Definition 1 (Marginalization of Ψ, Ψ|Θ) Let Ψ = (Ω = Ω(Σ),⪯Ψ) be an epistemic state given by a total preorder ⪯Ψ on Ω = Ω(Σ), let Θ ⊆ Σ. The marginalization of Ψ on Θ, denoted by Ψ|Θ, is defined via the induced total preorder on Ω(Θ):

Note that on the right hand side of the iff condition above ωΘ 1 , ωΘ 2 are considered as propositions in the superlanguage L(Ω), hence ωΘ 1 ⪯Ψ ωΘ 2 is well defined and allows for a more concise notation of A-filtering [Peppas et al., 2015]. In this way, each epistemic state on Ω induces epistemic states on each sublanguage, ensuring (Q3) in a straightforward way. Indeed, marginalization turns out to be the basic concept needed for syntax splitting in the context of epistemic states.

Let (Σ1, . . . , Σn) be a partition of Σ. Then each ω ∈ Ω(Σ) can be written uniquely as ω = ω1 . . . ωn with ωi = ωΣi ∈ Ω(Σi). If the considered partition is fixed, then we also call ωi the i-part of ω. The following two conditions establish a compatibility between the marginalized epistemic states Ψ|Σi and the original state Ψ by considering the i-parts of possible worlds. These conditions are equivalent to (Q1) and (Q2) in [Peppas et al., 2015] and are denoted as (EQ1) and (EQ2):

• (EQ1) Let ω1, ω2 ∈ Ω be possible worlds. If for all i, 1 ⩽ i ⩽ n, ω1Σi ∈ min(Ψ|Σi ) or ω1Σi = ω2Σi , and there is i, 1 ⩽ i ⩽ n, such that ω1Σi ∈ min(Ψ|Σi ) and ω2Σi ̸∈ min(Ψ|Σi ), then ω1 ≺Ψ ω2.
• (EQ2) Let ω1, ω2 ∈ Ω be possible worlds. If for all i, 1 ⩽ i ⩽ n, both ω1Σi , ω2Σi ∈ min(Ψ|Σi ) or ω1Σi = ω2Σi , then ω1 ≈Ψ ω2.

These conditions allow us to lift relationships from the level of marginalizations to complete epistemic states. According to (Q1) and (Q2), the latter relationships should only depend on the i-parts of two possible worlds that differ from each other. However, these axioms rephrased from [Peppas et al., 2015] deal just with minimal worlds and hence are too weak in the context of epistemic, or iterated revision. We generalize the rationale underlying (EQ1) and (EQ2) to define a semantic version of strong syntax splitting:

Definition 2 Let (Σ1, . . . ,Σn) be a partition of Σ, let Ψ be an epistemic state defined on Σ. For each ω ∈ Ω(Σ), define that part of ω that excludes exactly the i-part ωi as

where, as before, ωj = ωΣj .

Ψ splits over (Σ1, . . . , Σn) if the following condition holds for all i:

In our approach, syntax splitting for epistemic states means that ceteris paribus (i.e., if ̂ ω1 i = ̂ ω2 i holds), relationships between marginalized worlds can be lifted. The next proposition shows that epistemic syntax splitting according to (2) generalizes (EQ1) and (EQ2):

Proposition 2 If the epistemic state Ψ splits over (Σ1, . . . , Σn), then (EQ1) and (EQ2) hold.

Moreover, syntax splitting of epistemic states also generalizes K-splitting:

Proposition 3 Let (Σ1, . . . ,Σn) be a partition of Σ, let Ψ be an epistemic state defined on Σ. If Ψ splits over (Σ1, . . . ,Σn), then Bel (Ψ) splits over (Σ1, . . . ,Σn). More precisely: if Bel (Ψ|Σi ) = Cn(Ci) for Ci ∈ L(Σi), 1 ⩽ i ⩽ n, then Bel (Ψ) = Cn(C1, . . . , Cn).

To summarize what we achieved so far, Definition 2 extends the semantic axioms (Q1) - (Q3) of [Peppas et al., 2015] to full epistemic states. Now, we will elaborate on what syntax splitting means for (iterated) revision operators. First, we lift (R1) and (R2) from [Peppas et al., 2015] to the level of revising epistemic states.

Theorem 2 Let Ψ be an epistemic state defined on Ω(Σ) such that Bel (Ψ) = Cn(A, B) with Σ(A) ∩ Σ(B) = ∅. Let C ∈ L(Σ(A)), let Ψ ∗ C be a revision of Ψ by C. Let the conditions (ER1) and (ER2) be defined as follows:

Then (ER1) and (ER2) imply (R1) and (R2) for K = Bel (Ψ), i.e., (ER1) and (ER2) are the epistemic versions of (R1), (R2).

According to [Peppas et al., 2015], particularly (R2) was crucial to establish the strong version of the (P) axiom because it allows to make connections between revisions in different contexts. So does (ER2) by postulating that marginalization and revision can be swapped. Indeed, in this paper we argue that this is a fundamental principle of syntax splitting since it allows to focus on relevant parts of the language. Generalizing the original ideas of [Parikh, 1999; Peppas et al., 2015] where syntax splitting meant to change just the part of the beliefs which are directly relevant to the new information and maintain the other parts, we will broaden the scope of syntax splitting by considering changes on (syntactically) different parts of the beliefs affected by (syntactically) different parts of the new information. This requires the usage of multiple revision operators which are able to take sets of propositions as input for the new information [Kern-Isberner and Huvermann, 2017; Delgrande and Jin, 2012]. Note that due to the version of Proposition 1 for multiple revision, Bel (Ψ∗{C1, . . . , Cn}) = Bel (Ψ∗C1∧. . . Cn), so our results and techniques still generalize the approaches of [Parikh, 1999; Peppas et al., 2015] which concern mainly belief sets. In the framework of multiple revision, we are now able to formalize an axiom that covers and generalizes both (ER1) and (ER2):

Marginalized Revision (MR) Let (Σ1, . . . ,Σn) be a partition of Σ, let ∗ be a binary revision operator that takes as input an epistemic state and a set of propositions (all based on Σ) and returns an epistemic state based on Σ. Let Ψ be an epistemic state that splits over a partition (Σ1, . . . ,Σn) of Σ, and let C = {C1, . . . ,Cn} with Ci ∈ L(Σi) be the new information. Then

(MR) postulates that revision can be interchanged with marginalization. This is a very strong but also very intuitive postulate for (iterated, multiple) revision since it allows the agent to revise its beliefs and hence to reason in local contexts. Instead of syntax splitting, one might more appropriately call it a local revision postulate. A connection to both (ER1) and (ER2) can be shown if the revision operator satisfies quite a trivial postulate claiming that revising by a tautology should not change anything:

(Trivial Vacuity) Ψ∗⊤ = Ψ

Theorem 3 If ∗ satisfies (Trivial Vacuity) then (MR) implies both (ER1) and (ER2).

Therefore, in cases when ∗ satisfies (Trivial Vacuity), we can unambigously write Ψ ∗ Ci for Ci ∈ L(Σi) to study syntax splitting when just one part of the language is affected by the new information, as in [Parikh, 1999; Peppas et al., 2015].

(MR) thus extends the axioms (R1) and (R2) of [Peppas et al., 2015] to iterated revision operators; these axioms are meant to implement the strong (P) axiom. Likewise, Definition 2 defines syntax splitting for epistemic states as a generalization of (Q1)-(Q3) from [Peppas et al., 2015]. The question now is whether these two generalizations fully match, in the sense that (MR) helps preserving, or even ensures syntax splitting, as made precise by the following version of strong (P) for (multiple) iterated revision:

Strong iterated P (Pit ) Let (Σ1, . . . ,Σn) be a partition of Σ, let Ψ be an epistemic state defined on Σ that splits over (Σ1, . . . ,Σn). Let C = {C1, . . . ,Cn} with Ci ∈ L(Σi) be the new information. Then Ψ ∗ C splits over (Σ1, . . . , Σn).

The following example shows that (MR) does not imply (Pit ).

Example 1 Let Σ = {a, b, c}, Σ1 = {a, b}, Σ2 = {c}, and A = a∨b. Table 1 shows an epistemic state Ψ and its revision Ψ ∗ A as well as the induced marginalized epistemic states and marginalized revisions over Σ1 and Σ2 such that Ψ splits over (Σ1,Σ2), (MR) is fulfilled, but Ψ∗A does not split over (Σ1, Σ2), since for ω1 = abc and ω2 = abc, we have ̂ ω1 1 = c = ̂ ω2 1 and ω1 ⪯Ψ∗A ω2, but ω1 2 = ab ≺Ψ∗A|Σ1 ab = ω1 1 .

It is even easier to find examples for epistemic states Ψ where both Ψ and Ψ∗ C split, i.e., (Pit ) is fulfilled, but Ψ ∗ C|Σi and Ψ|Σi ∗Ci differ, so that (MR) is violated. This also holds even if we presuppose that all involved revision operators satisfy the Darwiche-Pearl postulates [Darwiche and Pearl, 1997] for iterated revision. This failure is caused by the fact that our extension of the syntactical part of strong (P) in its current form (i.e., via (MR) or (ER1), (ER2), respectively) only restricts the revisions of the marginalized epistemic state. However, marginalization is not reversible in general, that is, while an epistemic state induces uniquely marginalized epistemic states, there is no way to reconstruct the full epistemic state from its marginals in a purely qualitative setting. To solve this problem, more arithmetic quality is needed, as we find it, e.g., in the framework of ordinal conditional functions which we will study in the next section.

5 Syntax Splitting for OCFs and c-Revisions

Syntax splitting in revision, in a nutshell, means that if both the prior epistemic state and the new information can be split up according to some partition of the signature, then it should also be possible to split up the revised epistemic state accordingly. For general epistemic states, which we dealt with in the previous section, we were unable to fully capture epistemic syntax splitting under revision. In this section, we focus on the OCF framework. This will allow us to strengthen considerably the concepts presented in the previous section by making use of the arithmetic properties of OCFs. In particular, we are able to state a strong iterated (P) axiom, called (Pocf ), for OCF revision operators. The axiom allows us to build up a full revised OCF from its revised marginals while observing syntax splitting, as formalized generally by (Pit ). With this strengthened (P) axiom we will be able to establish a connection to (MR) for OCFs. As a proof of concept, we will use the approach of c-revisions to illustrate how syntax splitting can be implemented for iterated revision.

In the context of OCFs, splitting can be defined to preserve syntactical independencies even more accurately:

Definition 3 Let (Σ1, . . . ,Σn) be a partition of Σ, let κ be an OCF defined on Σ. κ ocf-splits over (Σ1, . . . , Σn) iff there are OCFs κi defined on Σi such that

In this case, we write κ = κ1 ⊕ . . . ⊕ κn.

It is straightforward to check that if κ = κ1⊕. . .⊕κn, then κi is the marginal of κ on Σi, i.e., κi = κ|Σi . Moreover, this definition specifies the notion of splitting for general epistemic states (see Def. 2) appropriately in the context of OCFs:

Proposition 4 If κ ocf-splits over (Σ1, . . . ,Σn), then ⪯κ splits over (Σ1, . . . , Σn).

After having formalized syntax splitting for OCFs, we now make (Pit ) precise for revising OCFs by sets of propositions: (Pocf ) Let (Σ1, . . . ,Σn) be a partition of Σ, let C = {C1, . . . ,Cn} with Ci ∈ L(Σi) be a set of propositions of L. Let κ be an OCF defined on Σ such that κ = κ1 ⊕ . . . ⊕ κn with marginal OCFs κi defined on

(Pocf ) perfectly shows what syntax splitting means: A syntax splitting revision operator should not introduce unjustified logical dependencies. Now, we are able to establish the desired connection between the (P) and (MR) axioms:

Theorem 4 Let ∗ be a (binary) revision operator taking OCFs and sets of propositions as inputs. If ∗ satisfies (Pocf ), then it also satisfies an OCF-version of (MR):

(MRocf ) Let (Σ1, . . . ,Σn) be a partition of Σ, let κ be an OCF defined on Σ such that κ = κ1 ⊕ . . . ⊕ κn with marginal OCFs κi defined on Σi. Let C = {C1, . . . , Cn} with Ci ∈ L(Σi). Then

In the rest of this section, we illustrate OCF revision satisfying (Pocf ) by making use of c-revisions [Kern-Isberner, 2004]. The latter provide a highly general framework for revising OCFs by sets of conditionals. For the purposes of this section it will be sufficient to consider a simplified version of the definition which is obtained from the original one by identifying a proposition A with the conditional (A|⊤) [KernIsberner and Huvermann, 2017]. We will return to the topic of revision by sets of conditionals in Sect. 6.

Definition 4 (Propositional c-revisions for OCFs) Let κ be an OCF specifying a prior epistemic state, and let C = {C1, . . . ,Cn} represent new information. Then a (propositional) c-revision of κ by C is given by the OCF

with non-negative integers ηi satisfying

If (6) holds then we write κ∗ = κ∗⃗ ηRwith ⃗η = (η1, . . . , ηn).

κ(C1 . . .Cn) in (6) is a normalization factor, and (7) ensures that a c-revision κ ∗ C satisfies κ ∗ C |= C. The ηi can be considered as impact factors of the single propositions, or as penalty factors for falsifying the propositions in C. Each crevision is an iterated revision in the sense of [Darwiche and Pearl, 1997], and it also satisfies (Pocf ):

Theorem 5 Let (Σ1, . . . ,Σn) be a partition of Σ, let C = {C1, . . . , Cn} with Ci ∈ L(Σi) be a set of propositions of L. Let κ be an OCF defined on Σ such that κ = κ1 ⊕ . . . ⊕ κn with marginal OCFs κi defined on Σi. Then any c-revision of κ by C satisfies (Pocf ). More precisely,

where the ηi's are the impact factors associated with the propositions Ci.

We exemplify syntax splitting for c-revisions.

Example 2 Let Σ = {a, b, c, d} with splitting (Σ1 = {a},Σ2 = {b, c},Σ3 = {d}). The OCF κ in Table 2 ocfsplits over (Σ1,Σ2,Σ3) (the marginals κi = κ|Σi , i = 1, 2, 3, can be found in Table 3. Then κ is c-revised by the new information C = {a, bc, d} which is also split over (Σ1,Σ2,Σ3). The schematic c-revision (according to (6)) with the parameters η1, η2, η3 is shown in the third column of Table 2 (note that κ(abcd) = 6), and the fourth column contains a c-revision (κ ∗ {a, bc, d})min with (Pareto) minimal parameters η1 = 3, η2 = 4, η3 = 2. It is straightforward to check that (κ ∗ {a, bc, d})min satisfies (Pocf ) and (MRocf ) (the revised marginals can also be found in Table 3. To illustrate the difference that is made by using multiple revision, also a c-revised (κ∗abcd)min with a minimal change parameter is shown in column five of Table 2. While it has the same minimal world(s) as (κ∗{a, bc, d})min, it is substantially different otherwise and does not ocf-split over (Σ1, Σ2, Σ3).

6 Conclusions

Syntax splitting aims to capture the intuition that whenever beliefs are revised with a new piece of information φ only those beliefs should be affected which are relevant to φ. In this paper we have shown how syntax splitting can be generalized - in compliance with AGM and the postulates of [Darwiche and Pearl, 1997] - to the revision of epistemic states, a necessary prerequisite for covering iterated revision. The key to our approach is marginalization, a concept well-known from probability theory.

On the more technical side, we generalized various properties considered in [Peppas et al., 2015] to epistemic states. It turned out that in the general setting where an epistemic state is taken to be a total preorder on the set of worlds, there is a certain mismatch between postulate (MR) which basically states that revision and marginalization should be interchangeable, and (Pit ), the iterated version of strong (P): (MR) does not imply (Pit ), nor the other way round. This was one of our main motivations for studying the concept of epistemic syntax splitting in the specific framework of ordinal conditional functions (OCFs, [Spohn, 1988]). For OCFs, we were able to show that the mismatch observed in the general setting can be overcome and illustrated syntax splitting with c-revisions.

The original definition of c-revisions in [Kern-Isberner, 2004] actually allows for revisions of epistemic states (implemented by OCFs) by a set of (plausible) conditionals of the form (B|A) which are meant to express plausible, defeasible rules "If A then plausibly (usually, typically etc.) B". We did not use this additional generality of c-revisions in Sect. 5, but would like to point out that, given our results, it is rather straightforward to formulate a variant of (Pocf ) which also covers conditionals. Moreover, it can be shown that Theorem 5 also holds in this very general setting.

In [Kern-Isberner, 2001] c-revisions were devised as a qualitative counterpart to probabilistic revision via the principle of minimum cross-entropy (MinCEnt) and thus inherit many high quality properties of that revision operator. Also our (Pocf ) axiom is inspired by results from MinCEnt revision: it is the OCF-version of the so-called system independence property which is one of the characterizing axioms of MinCEnt revision, according to [Shore and Johnson, 1980].

Acknowledgements

This work was partially funded by DFG Research Unit 1513, projects BR 1817/7-2 and KE 1413/8-2.