Conditional Independence for Iterated Belief Revision

1 Introduction

Over the last decades, conditional independence was shown to be a crucial concept supporting adequate modelling and efficient reasoning in probabilistics. For example, in medical diagnosis, symptoms are often assumed to be conditionally independent given the disease [Pearl, 1988]. It is the fundamental concept underlying network-based reasoning in probabilistics, which has been arguably one of the most important factors in the rise of contemporary artificial intelligence. Even though many reasoning tasks on the basis of probabilistic information have a high worst-case complexity due to their semantic nature, network-based models allow an efficient computation for many concrete instances of these reasoning tasks thanks to local reasoning techniques.

On the other hand, for the modelling of intelligent agents, it is important to give a formal account of the dynamics of knowledge and belief. This is done in the field of belief change. Traditionally, researchers have been mainly interested in studying the dynamics of sets of propositional formulas (so-called AGM theory, based on [Alchourr´on et al., 1985]). One of the drawbacks of this perspective is that such formal models do not give an account of iterated belief revision, i.e. of how to revise a previously revised set of formulas. It became clear that for iterated revision, information about the state of mind of an agent that goes beyond the merely propositional level is needed. Such information can be represented by epistemic states, and iterated belief revision can then be viewed as the revision of these epistemic states. In the AGM framework, total preorders over propositional interpretations that represent the respective (im)plausibility of these interpretations, provide the basic semantic structures for iterated revision [Darwiche and Pearl, 1997].

∗Contact Author

In this paper, we present a concept of conditional independence for total preorders that provides a novel axiomatic foundation for iterated belief revision, allowing for local reasoning in the revised epistemic state. The basic idea of such axioms is simple: If we have conditional independence in the prior epistemic state, and the new information is compatible with that, then we also should have conditional independence in the posterior epistemic state. The challenge is to define conditional independence for total preorders that is, on the one hand, compatible with (iterated) AGM revision, and, on the other hand, shows basic characteristics of probabilistic conditional independence. However, conditional independence in probabilistics makes heavy use of the rich arithmetic properties of probabilities which are not available for total preorders. Spohn's ranking functions [Spohn, 1988; Spohn, 2012] are a good mediator between these different semantic frameworks. We use the notion of conditional independence for ranking functions to fully elaborate our approach to conditional independence in belief revision by providing c-revisions [Kern-Isberner and Huvermann, 2017] as a proof of concept. Moreover, we show how many of the features of that framework can be made relevant also for total preorders, and hence for iterated revision in general.

This paper is organized as follows: In the next section, we compile basics on propositional logic, total preoders and ranking functions, and iterated AGM belief revision. In Section 3, we recall related work on conditional independence which is relevant to this paper. Then Section 4 presents our approach to conditional independence for total preorders, and Section 5 makes it usable for iterated revision. Section 6 concludes and puts out future work.

2 Formal Preliminaries

Propositional Logic. 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. For a proposition A ∈ L, Cn(A) = {B ∈ L | A |= B} is the set of consequences of A in L. 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.

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 ωΣ\Θ ∈ Ω(Σ \ Θ). Here, ωΘ is called the reduct of ω to Θ [Delgrande, 2017]. If Ω′ ⊆ Ω is a subset of models, then Ω′ |Θ = {ωΘ|ω ∈ Ω′ } ⊆ Ω(Θ) restricts Ω′ to a subset of Ω(Θ). In the following, we will often consider the case that Σ is the union of three disjoint subsignatures Σ1, Σ2, Σ3, i.e., Σ = Σ1 ˙∪Σ2 ˙∪Σ3 where Σi ∩Σj = ∅ for i ̸= j, and ˙∪ denotes the exclusive union. Then we write ωi instead of ωΣi for the reducts to ease notation, i.e., in this case, each ω ∈ Ω can be written in the form ω = ω1ω2ω3 with ωi ∈ Ω(Σi), i ∈ {1, 2, 3}. For Θ ⊆ Σ and A ∈ L(Σ), with AΘ ∈ L(Θ), called the reduct of A to Θ, we denote any formula with Mod(AΘ) = {ωΘ | ω ∈ Mod(A)}. Note that AΘ is uniquely defined up to logical equivalence. For instance, for Σ = Σ1 ˙∪Σ2 ˙∪Σ3 and A ∈ L(Σ), we get AΣi ∈ L(Σi) for i ∈ {1, 2, 3}, and, e.g., AΣ1 ˙∪Σ3 ∈ L(Σ1 ˙∪Σ3). Just like ωΘ with ω ∈ Ω(Σ), we will consider AΘ also as a sentence in L(Σ) and thus having models over the larger signature Σ; using this view, AΘ is called the projection of A onto Θ in [Lynn et al., 2022]. Instead of AΣi ˙∪Σj , we will often just write AΣi,Σj .

TPOs and OCFs. Total preorders (TPO) ⪯ over possible worlds are total, reflexive, and transitive relations over Ω. As usual, ω ≺ ω′ iff ω ⪯ ω′ and not ω′ ⪯ ω, and ω ≈Ψ ω′ iff both ω ⪯ ω′ and ω′ ⪯ ω. Such TPOs can be lifted to total preorders on the set of propositions via A ⪯ B iff there is a (minimal) ω ∈ Mod(A) such that ω ⪯ ω′ for all ω′ ∈ Mod(B). If Ω′ ⊆ Ω, thenmin⪯(Ω′ ) = {ω′ ∈ Ω′ | ω′ ⪯ ω′′ 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 a TPO form its associated belief set: Bel (⪯) = T (min(⪯)), where T (Ω′ ) denotes the set of formulas which are true in all elements of Ω′ ⊆ Ω. I.e., the agent believes exactly the propositions that are valid in all most plausible models. With K⪯ ∈ L, we denote the core of Bel (⪯), i.e., the unique (up to logical equivalence) formula that respresents Bel (⪯), in the sense that Bel (⪯) = Cn(K⪯).

For Θ ⊆ Σ, any TPO ⪯ on Ω(Σ) induces uniquely a marginalized TPO ⪯|Θ on Ω(Θ) by

Note that on the right hand side of the iff condition above ωΘ 1 , ωΘ 2 are considered as propositions in L(Ω), hence ωΘ 1 ⪯ ωΘ 2 is well defined [Kern-Isberner and Brewka, 2017].

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}. Note that also OCFs κ induce total preorders on Ω via ω1 ⪯κ ω2 iff κ(ω1) ⩽ κ(ω2). Analogously to TPOs, Bel (κ) = T ({ω | κ(ω) = 0} is the set of beliefs of an OCF κ. An OCF κ is called convex if it does not have empty layers, i.e., if κ-1 (i) ̸= ∅ implies κ-1 (j) ̸= ∅ for all j < i.

The marginalization of κ on Θ ⊆ Σ, denoted by κ|Θ, is defined by κ|Θ(ωΘ) = κ(ωΘ) for any ωΘ ∈ Ω(Θ). OCFs can also be conditionalized with respect to propositional formulas: for any A ∈ L with κ(A) < ∞, κ|A is an OCF on the models of A defined by κ|A(ω) = κ(ω) - κ(A).

Note that the marginalization for TPOs and OCFs as given above are special cases of the forgetful functor Mod(σ) from Σ-models to Θ-models in [Beierle and Kern-Isberner, 2012] where Θ ⊆ Σ and σ : Θ → Σ is the inclusion from Θ to Σ.

Revision of Beliefs and Epistemic States. The following theorem that generalizes results from [Katsuno and Mendelzon, 1991] is fundamental to (iterated) AGM belief revision [Alchourr´on et al., 1985]. In particular, it reveals that total preorders are the basic semantic structures that are needed for iterated belief revision.

Theorem 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 total preorder ⪯Ψ for an epistemic state Ψ with associated belief set K = Bel (Ψ), such that for any proposition A it holds that

This theorem also allows us to use the same symbol ∗ for revisions of belief sets and revision of epistemic states, where implicitly the validity of (2) is presupposed.

C-revisions provide a highly general framework for revising OCFs (as specific implementations of total preorders) by (sets of) conditionals resp. propositions. For the purposes of this paper it will be sufficient to recall c-revisions by a single proposition [Kern-Isberner and Huvermann, 2017].

Definition 1 (Propositional c-revisions for OCFs). Let κ be an OCF specifying a prior epistemic state, and let A ∈ L. A (propositional) c-revision of κ by A is given by the OCF

κ(A) in (3) is a normalization factor, and η > κ(A)-κ(A) ensures κ ∗ A |= A. Each c-revision is an iterated revision in the sense of [Darwiche and Pearl, 1997].

3 RelatedWork on Conditional Independence

Conditional independence is the crucial ingredient to make computations efficient in probabilistic networks [Pearl, 1988]. Thanks to the close relationship between rankings and probabilities, there is a straightforward adaptation of conditional independence for OCFs [Spohn, 2012, Chapter 7].

Definition 2. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ and let κ be an OCF. Σ2,Σ3 are conditionally independent given Σ1 with respect to κ, in symbols Σ2 |= κ Σ3|Σ1, if for all ω1 ∈ Ω(Σ1), ω2 ∈ Ω(Σ2), and ω3 ∈ Ω(Σ3), κ(ω2 |ω1ω3 ) = κ(ω2 |ω1 ) holds.

As for probabilities, conditional independence for OCFs expresses that information on Σ3 is redundant for Σ2 if full information on Σ1 is available and used. The following lemma is straightforward and helpful for technical proofs.

Lemma 1. Let Σ1,Σ2,Σ3 be disjoint subsignatures of Σ, let κ be an OCF. Then Σ2, Σ3 are conditionally independent given Σ1 with respect to κ iff for all ω1 ∈ Ω(Σ1), ω2 ∈ Ω(Σ2), and ω3 ∈ Ω(Σ3), we have κ(ω1ω2ω3 ) = κ(ω1ω2 ) + κ(ω1ω3 ) - κ(ω1 ).

As in probabilistics, conditional independence with respect to an OCF κ generalizes κ-independence, as defined in [KernIsberner and Huvermann, 2017; Kern-Isberner and Brewka, 2017]; more precisely, Σ1,Σ2 are κ-independent iff they are conditionally independent given the empty set.

Conditional independence with respect to databases resp. propositional formulas have been considered in [Darwiche, 1997; Lang and Marquis, 1998; Lang et al., 2002; Lynn et al., 2022]. We recall the definition of [Lynn et al., 2022] here.

Definition 3 ([Lynn et al., 2022]). Let K ∈ L be a propositional formula. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ. Σ2,Σ3 are conditionally independent given Σ1 modulo K if for all ω ∈ Ω, for all A2 ∈ L(Σ2), A3 ∈ L(Σ3) such that K ∧ ω1 |= A2 ∨ A3, we have K ∧ω1 |= A2 or K ∧ω1 |= A3.

In their paper [Lynn et al., 2022], Lynn, Delgrande, and Peppas considered conditional independence for (basic) AGM revision on the level of belief sets via syntactical representations called multivalued dependencies, and consider TPO-based AGM revision operators that comply with such dependencies. Our approach to conditional independence is a semantic one directly for TPOs, and hence is applicable to (more general) iterated revision tasks. For a more detailed comparison with that work, please see Section 5.

4 Conditional Independence for TPOs

The basic semantic structure for iterated belief revision are total preorders (TPOs) on possible worlds, according to the seminal works by Katsuno and Mendelzon [Katsuno and Mendelzon, 1991], and Darwiche and Pearl [Darwiche and Pearl, 1997]. We first present a semantic notion of conditional independence for total preorders.

Definition 4. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ let ⪯ be a TPO on Ω. Σ2,Σ3 are conditionally independent given Σ1 with respect to ⪯, in symbols Σ2 |= ⪯Σ3|Σ1, if for all ω1 ∈ Ω(Σ1), ω2 1 , ω2 2 ∈ Ω(Σ2), and ω3 1 , ω3 2 ∈ Ω(Σ3) holds that for all i, j ∈ {2, 3}, i ̸= j,

Again, conditional independence expresses that in the context of given information fromΣ1, information on Σj is irrelevant for the ordering of worlds on Σi. Practically speaking, ωj1 can be "cancelled out". We illustrate this by examples.

Example 1. Consider the following TPO over the signature Σ = {p, q, r}:

Then {q} |= ⪯ {r}|{p}. A witness of this is the fact that p q ≺ pq and p qr ≺ pqr and p qr ≺ pqr.

Notice that {q} |= ⪯ {r}|{p} yet it does not hold that {q, p} |= ⪯ {r}|∅. To see this, it suffices to observe that p q ≺ pq (in view of p qr ≺ pqr) yet p q r ̸≺ pqr. Likewise, it does not hold that {p} |= ⪯ {r}|{q}. This can be seen by observing that p q ⪯ pq yet p q r ̸⪯ pq r.

The next example uses slightly increased signatures.

Example 2. Let Σ = Σ1 ˙∪Σ2 ˙∪Σ3 with Σ = {a, b, c, d}, Σ1 = {a, b}, Σ2 = {c}, Σ3 = {d}, and let ⪯ be the TPO over Σ given by:

For checking that Σ2, Σ3 are conditionally independent given Σ1 with respect to ⪯, we have to ensure that for all ω1 ∈ {ab, ab, ab, ab}, all ω2 1 , ω2 2 ∈ {c, c}, and all ω3 1 , ω3 2 ∈ {d, d} the condition in (4) holds. For ω1 = ab we get, e.g., abc ⪯ abc and abcd ⪯ abcd and abcd ⪯ abcd, and furthermore abd ⪯ abd and abcd ⪯ abcd and abcd ⪯ abcd. Checking also the remaining instances of (4) reveals that Σ2 |= ⪯Σ3|Σ1 holds.

This definition of conditional independence for TPOs is compatible with the definition for OCFs, in the sense that conditional independence with respect to an OCF κ implies conditional independence with respect to the corresponding TPO ⪯κ:

Proposition 1. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ, let κ be an OCF. Then Σ2 |= κ Σ3|Σ1 implies Σ2 |= ⪯κ Σ3|Σ1.

Proof. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ, and let κ be an OCF such that Σ2 |= κ Σ3|Σ1 holds. For the proof of Σ2 |= ⪯κ Σ3|Σ1, we focus on Σ2, the proof for Σ3 is analogous. Let ω1 ∈ Ω(Σ1), ω2 1 , ω2 2 ∈ Ω(Σ2), and ω3 ∈ Ω(Σ3). ω1ω2 1 ω3 ⪯κ ω1ω2 2 ω3 means κ(ω1ω2 1 ω3 ) ⩽ κ(ω1ω2 2 ω3 ), which is equivalent to κ(ω2 1 |ω1ω3 ) ⩽ κ(ω2 2 |ω1ω3 ). Because of Σ2 |= κ Σ3|Σ1, this is equivalent to κ(ω2 1 |ω1 ) ⩽ κ(ω2 2 |ω1 ), and hence to κ(ω1ω2 1 ) ⩽ κ(ω1ω2 2 ), i.e., ω1ω2 1 ⪯κ ω1ω2 2 , which was to be shown.

The converse of Proposition 1, i.e., that Σ2 |= ⪯ Σ3|Σ1 implies Σ2 |= κ Σ3|Σ1 for some κ with ⪯κ=⪯, cannot be expected in general because TPOs are too weak to mimick the arithmetic features of OCFs faithfully. However, in some cases, we might indeed lift conditional independence with respect to TPOs to conditional independence with respect to suitable OCFs.

Proposition 2. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ, and let ⪯ be a TPO on Ω such that Σ2 |= ⪯ Σ3|Σ1 holds. Let κ be an OCF such that ⪯κ=⪯. Furthermore presuppose that all conditional OCFs in the sets {κ|ω1ω3 | ω1 ∈ Ω(Σ1), ω3 ∈ Ω(Σ3)} and {κ|ω1 | ω1 ∈ Ω(Σ1)} are convex. Then we also have Σ2 |= κ Σ3|Σ1.

Proof. We have to show that κ(ω2 |ω1ω3 ) = κ(ω2 |ω1 ) for all ω1 ∈ Ω(Σ1), ω2 ∈ Ω(Σ2), ω3 ∈ Ω(Σ3). Since all conditional OCFs κ|ω1ω3 , κ|ω1 define convex OCFs on Ω(Σ2) and start with rank 0, this is equivalent to (κ(ω2 1 |ω1ω3 ) ⩽ κ(ω2 2 |ω1ω3 ) iff κ(ω2 1 |ω1 ) ⩽ κ(ω2 2 |ω1 )), for all ω1 ∈ Ω(Σ1), ω2 1 , ω2 2 ∈ Ω(Σ2), ω3 ∈ Ω(Σ3). But this is straightforward: we have κ(ω2 1 |ω1ω3 ) ⩽ κ(ω2 2 |ω1ω3 ) iff κ(ω1ω2 1 ω3 ) ⩽ κ(ω1ω2 2 ω3 ). Due to ⪯κ=⪯, this means ω1ω2 1 ω3 ⪯ ω1ω2 2 ω3 . Because of Σ2 |= ⪯Σ3|Σ1, this is equivalent to ω1ω2 1 ⪯ ω1ω2 2 , and hence to κ(ω1ω2 1 ) ⩽ κ(ω1ω2 2 ), i.e., to κ(ω2 1 |ω1 ) ⩽ κ(ω2 2 |ω1 ).

We illustrate this by continuing Example 1.

Example 3. The minimal OCF implementing the TPO from Example 1 is given by κ(p qr) = κ(pqr) = 0, κ(pqr) = κ(pqr) = κ(pq r) = 1, κ(pqr) = κ(p q r) = 2, κ(pqr) = 3. It is straightforward to check that all conditional OCFs κ|ω1ω3 , κ|ω1 are convex (they all take on only the ranks 0 and 1), so we also have {q} |= κ {r}|{p} according to Prop. 2 which can easily be verified.

Next, we show that conditional independence of total preorders is compatible with the notion of conditional independence modulo propositional formulas (see Definition 3):

Proposition 3. Let Σ1 ˙∪Σ2 ˙∪Σ3 ⊆ Σ. If Σ2,Σ3 are conditionally independent given Σ1 with respect to ⪯, then Σ2, Σ3 are also conditionally independent given Σ1 modulo the core K⪯.

The proof of this proposition is straightforward, but omitted due to lack of space. The following example illustrates Proposition 3.

Example 4. For Σ = Σ1 ˙∪Σ2 ˙∪Σ3 and ⪯ as in Example 2 we have Σ2 |= ⪯Σ3|Σ1 and K⪯ ≡ abcd ∨ abc. For checking whether Σ2,Σ3 are conditionally independent given Σ1 modulo K⪯, we have to consider all ω ∈ Ω, all A2 ∈ L(Σ2), and all A3 ∈ L(Σ3). If K⪯ ∧ ω1 ≡ ⊥ or if any of A2, A3 is equivalent to ⊤ or equivalent to ⊥, the conditional independence requirement holds trivially. Thus, we are left to check the requirement for ω ∈ {abcd, abcd, abcd}, A2 ∈ {c, c}, and A3 ∈ {d, d}. First, let ω = abcd and thus ω1 = ab. Since K⪯ ∧ ab ≡ abcd, we get K⪯ ∧ ω1 |= A2 ∨ A3 only for the three cases (i) A2 ≡ c and A3 ≡ d, (ii) A2 ≡ c and A3 ≡ d, or (iii) A2 ≡ c and A3 ≡ d. In each of these cases, K⪯ ∧ ω1 |= A2 or K⪯ ∧ ω1 |= A3 holds. Otherwise, let ω ∈ {abcd, abcd} and thus ω1 = ab in both cases. Since K⪯ ∧ab ≡ abc, we get K⪯ ∧ω1 |= A2 ∨A3 only for the two cases (i) A2 ≡ c and A3 ≡ d, or (ii) A2 ≡ c and A3 ≡ d. In both cases, K⪯ ∧ ω1 |= A2 holds. In summary, we observe that Σ2,Σ3 are conditionally independent given Σ1 modulo K⪯.

Among the most important properties of independence relations is that of being a (semi-)graphoid:

Definition 5 ([Pearl and Paz, 1985]). A ternary relation · |= ·|· among subsets of some signature Σ is a semi-graphoid over Σ iff for all pairwise disjoint Σ1,Σ2,Σ3,Σ4 ⊆ Σ the following properties hold:

Symmetry if Σ2 |= Σ3|Σ1 then Σ3 |= Σ2|Σ1.

Decomposition if Σ2 |= Σ3 ∪Σ4|Σ1 then Σ2 |= Σ3|Σ1.

Weak Union if Σ2 |= Σ3 ∪Σ4|Σ1 then Σ2 |= Σ3|Σ1 ∪ Σ4.

Contraction if Σ2 |= Σ3|Σ1 and Σ2 |= Σ4|Σ3 ∪Σ1 then Σ2 |= Σ3 ∪ Σ4|Σ1.

· |= · |· is a graphoid (over Σ), if the following additional property is satisfied::

Intersection If Σ2 |= Σ3|Σ1 ∪Σ4 and Σ2 |= Σ4|Σ3 ∪ Σ1 then Σ2 |= Σ3 ∪ Σ4|Σ1.

Spohn already showed that conditional independence in OCFs is a graphoid [Spohn, 2012, Theorem 7.10]. Since TPOs cannot make use of any of the arithmetic features that ranking functions and probabilities rely on, we cannot expect a similarly strong result here. Nevertheless, we are able to prove some of these properties, at least in a weakened form:

Proposition 4. Let a TPO ⪯ be given. Then conditional independence . |= ⪯ .|. over Σ satisfies symmetry, weak union, and the following variant of decomposition:

Symmetric decomposition if Σ2 |= Σ3 ∪ Σ4|Σ1 and Σ2 ∪ Σ4 |= Σ3|Σ1 then Σ2 |= Σ3|Σ1.

The proof of this proposition is a lengthy technical exercise and left out due to lack of space. It is an open question whether conditional independence for TPOs is, in general, a graphoid.

For OCFs, and hence also regarding the appertaining TPOs according to Proposition 1, ranking functions respecting specific conditional independence statements can be easily constructed under mild conditions of compatibility, as shown next:

Proposition 5. Let Σ = Σ1 ˙∪Σ2 ˙∪Σ3, let κ2, κ3 be OCFs defined over Σ1 ˙∪Σ2 and Σ1 ˙∪Σ3, respectively, such that κ2(ω1 ) = κ3(ω1 ) for all ω1 ∈ Ω(Σ1). Define κ over Σ via κ(ω) = κ2(ω1ω2 ) + κ3(ω1ω3 ) - κ2(ω1 ). Then κ is an OCF such that Σ2 |= κ Σ3|Σ1 holds.

Proof. First, κ is an OCF, i.e., there are worlds ω with κ(ω) = 0. Due to the prerequisite κ2(ω1 ) = κ3(ω1 ) for all ω1 ∈ Ω(Σ1), κ2|Σ1 , κ3|Σ1 are marginalized OCFs such that κ2|Σ1 = κ3|Σ1 . So, there is ω1 0 ∈ Ω(Σ1) such that κ2(ω1 0 ) = κ3(ω1 0 ) = 0. Then there are ω2 0 ∈ Ω(Σ2) and ω3 0 ∈ Ω(Σ3) such that κ2(ω1 0 ω2 0 ) = κ2(ω1 0 ) = 0 = κ3(ω1 0 ) = κ3(ω1 0 ω3 0 ). For ω0 = ω1 0 ω2 0 ω3 0 , we have κ(ω0) = κ2(ω1 0 ω2 0 ) + κ3(ω1 0 ω3 0 ) - κ2(ω1 0 ) = 0.

Furthermore, we simply have to show that κ(ω1ω2 ) = κ2(ω1ω2 ), κ(ω1ω3 ) = κ3(ω1ω3 ), and κ(ω1 ) = κ2(ω1 )(= κ3(ω1 )), then the statement is immediate from the definition of κ. We show the first statement, the others are anologous:

We illustrate this construction by an example.

Example 5. Let Σ = Σ1 ˙∪Σ2 ˙∪Σ3 with Σ = {a, b, c, d},Σ1 = {a, b},Σ2 = {c},Σ3 = {d}. With ω12 , ω13 , we denote worlds from Ω(Σ1 ˙∪Σ2) resp. Ω(Σ1 ˙∪Σ3), where ω1 is their common part over Σ1. Let κ2, κ3 over Σ1 ˙∪Σ2 resp. Σ1 ˙∪Σ3 be defined as in Table 1. We can easily observe that the compatibility condition κ2(ω1 ) = κ3(ω1 ) is satisfied. The constructed OCF κ(ω) = κ2(ω1ω2 ) + κ3(ω1ω3 ) - κ2(ω1 ) is shown in Table 2.

We might also use this construction for TPOs that are sufficiently compatible. More precisely, suppose we have Σ = Σ1 ˙∪Σ2 ˙∪Σ3 and two TPOs ⪯2,⪯3 on Σ1 ˙∪Σ2 resp. Σ1 ˙∪Σ3 are given such that we can associate with them suitable OCFs κ2, κ3 over the respective subsignatures satisfying ⪯κ2 =⪯2, ⪯κ3 =⪯3 and obeying the compatibility condition κ2(ω1 ) = κ3(ω1 ) for any ω1 ∈ Ω(Σ1). Then κ constructed as in Proposition 5 is an OCF, and Propositions 5 and 1 ensure that Σ2 |= ⪯κ Σ3|Σ1 holds.

At this point, the reader might wonder where conditional independencies come from. There are at least three sources where a knowledge engineer might look for conditional independencies. The first is background knowledge about the domain that being modelled, not unlike Bayesian networks, which are often manually constructed on the basis of background assumptions about the domain being modelled. A second source of conditional independencies is combining a set of component OCFs over different (possibly overlapping) sub-signatures as outlined in Proposition 5. Thirdly, we plan to develop algorithms for the extraction of conditional independencies between sub-signatures, taking inspiration of the learning of the structure of Bayesian networks [Pearl, 1988, Ch. 8].

5 Conditional Independence Axioms for Iterated Revision

The basic idea of axioms of conditional independence for iterated belief revision would be that conditional independencies should be respected under revision, as far as possible. This means that if a conditional independence prevails in the prior epistemic state, and the new information is compatible with this independence in the sense that it does not contain atoms from both conditionally independent sets (see also [Lynn et al., 2022]), then also the posterior epistemic state should show that same conditional independence.

Proposition 6. C-revisions satisfy (CIocf ).

Proof Sketch. Let Σ = Σ1 ˙∪Σ2 ˙∪Σ3, and let κ be an OCF over Ω such that Σ2 |= κ Σ3|Σ1 holds. Let A ∈ L(Σ1 ˙∪Σ2). We have to show that then Σ2 |= κ∗ Σ3|Σ1 also holds, where κ∗ = κ ∗ A is a c-revision of κ by A according to Definition 1. In other words, we have to show that κ∗ (ω1ω2ω3 ) = κ∗ (ω1ω2 ) + κ∗ (ω1ω3 ) - κ∗ (ω1 ).

We outline the proof of the case for ω |= A, the case for ω |= A is similar. The claim is shown by first deriving the following equalities: κ∗ (ω) = -κ(A) + κ(ω1ω2 ) + κ(ω1ω3 ) - κ(ω1 ) (I), κ∗ (ω1ω3 ) = -κ(A) + min{κ(Aω1 ), κ(Aω1 ) + η} + κ(ω1ω3 ) - κ(ω1 ) (II), and κ∗ (ω1 ) = -κ(A) + min{κ(Aω1 ), κ(Aω1 )+η} (III). Combining (I), (II) and (III) then yields κ∗ (ω1ω2ω3 ) = κ∗ (ω1ω2 ) + κ∗ (ω1ω3 ) - κ∗ (ω1 ) as desired.

We illustrate this result by an example.

Example 6. We have Σ = Σ1 ˙∪Σ2 ˙∪Σ3 with Σ = {a, b, c, d},Σ1 = {a, b},Σ2 = {c},Σ3 = {d}, and κ is given by Table. 3 with Σ2 |= κ Σ3|Σ1 (see also Example 5) and Bel (κ) = Cn(abc), i.e., Kκ = abc. We revise by A = bc. We have κ(A) = 1, so any c-revision κ∗ of κ by A has the form

We illustrate this with κ and a generic c-revision κ∗ with η > κ(A) - κ(A) = 1 in Table 3. It is straightforward to verify that indeed, Σ2,Σ3 are also conditionally independent given Σ1 in κ∗ . Choosing η = 2 yields an OCF κ∗ whose induced TPO ⪯κ∗ coincides with ⪯ given in Example 2.

It is also interesting to note that in Example 6, all crevisions as shown in Table 3 with η > 2 would yield the same total preorder. This means that in spite of the numerical nature of OCFs, the purely qualitative result of the revision, i.e., the TPO ⪯κ∗A, does not depend so much on the chosen impact factor η, but more on the qualitative structure in the prior epistemic state. Therefore, we can very well use the power of OCF-based c-revisions also for TPOs to obtain revisions that satisfy (CItpo ), if suitable transformations into OCFs are possible. More precisely, if Σ2 |= ⪯Σ3|Σ1 holds in a TPO ⪯, and we can find an OCF κ with ⪯κ=⪯ and Σ2 |= κ Σ3|Σ1, then we can apply c-revisions to this κ such that also Σ2 |= κ∗ Σ3|Σ1 holds, and via ⪯κ∗ we obtain a revision of ⪯ that satisfies (CItpo ) thanks to Propositions 6 and 1. We illustrate this by continuing Examples 1 and 3.

Example 7. The TPO ⪯ from Example 1 is defined over the signature Σ = {p, q, r}, has the belief set Bel (⪯) = Cn(qr), and satisfies {q} |= ⪯ {r}|{p}, i.e., Σ1 = {p}, Σ2 = {q},Σ3 = {r}. We want to revise this TPO by A = pq ∈ L(Σ1 ˙∪Σ2) with the help of c-revisions. The minimal OCF κ implementing this TPO has been computed in Example 3 and is shown in Table 4. According to Proposition 2 and Example 3, we have {q} |= κ {r}|{p}, and revising κ by A via c-revisions yields κ∗ = κ ∗ A with

with η > 1 - 0. We choose η = 2 and obtain the revised κ∗ shown in Table 4 satisfying {q} |= κ∗ {r}|{p} according to Proposition 6. Then a revision of ⪯ by A can be defined via ⪯ ∗A =⪯κ∗A and is given by

Thanks to Proposition 1, we also have {q} |= ⪯∗A {r}|{p}.

Finally, we show some partial agreement with the results from the paper [Lynn et al., 2022] that focuses on propositional AGM revision; the proof is straightforward and left out due to lack of space.

Proposition 7. Let ∗ be a revision operator for TPOs, let Σ = Σ1 ˙∪Σ2 ˙∪Σ3. Let ⪯ be a TPO over Ω such that Σ2 |= ⪯Σ3|Σ1 holds. Let A ∈ L(Σ1 ˙∪Σ2) such that A ∧ KΣ1,Σ3 ⪯ is consistent. If ∗ satisfies (CItpo ), then KΣ1,Σ2 ⪯∗A ∧ KΣ1,Σ3 ⪯ |=K⪯∗A.

Note that full compliance of a (propositional) revision operator ∗ with a conditional independence statement modulo formulas in [Lynn et al., 2022] postulates KΣ1,Σ2 ⪯∗A ∧KΣ1,Σ3 ⪯ ≡ K⪯∗A. This seems to be a bit too strong for iterated revision, as also Example 6 illustrates. Here we have Kκ ≡ abc and A = bc, so A ∧ KΣ1,Σ3 κ ≡ bc ∧ ab ≡ abc is consistent, and Σ2 |= κ Σ3|Σ1 and Σ2 |= κ∗ Σ3|Σ1 imply conditional independence modulo the respective belief sets according to Prop. 3. But Kκ∗ ≡ abcd ∨ abc, hence we only have KΣ1,Σ2 κ∗ ∧KΣ1,Σ3 κ ≡ (abc∨abc)∧ab ≡ abc |=Kκ∗, verifying Prop. 7.

6 Conclusion

We presented a semantic approach to conditional independence for total preorders which are the basic structure for revision of epistemic states resp. iterated revision according to the AGM and Darwiche-Pearl frameworks [Alchourr ´on et al., 1985; Darwiche and Pearl, 1997]. We showed that this concept of conditional independence is compatible to respective notions for purely propositional frameworks, Spohn's ranking functions, and some of Pearl's basic characteristics of conditional independence coming from probabilistics. Moreover, we made precise by axioms what it means for an iterated revision operator to respect conditional independence, both for total preorders and ranking functions, which basically say that conditional independencies should be preserved under revision if the revision input does not violate it. We proposed c-revision operators [Kern-Isberner and Huvermann, 2017] as a proof of concept to satisfy these axioms. Therefore, for the framework of ranking functions, conditional independence in the revised epistemic state can be easily implemented via c-revisions: once we have conditional independence in the prior ranking function, any c-revision (with a suitable input) will preserve it. We also provided a constructive method to build up a prior ranking function from local ranking functions (on subsignatures) that satisfies a conditional independence statement, thereby bringing in ideas of local reasoning. Via the close relationships between total preorders and ranking functions, many of these results can be used for the purely qualitative framework of total preorders. This paper complements the work [Kern-Isberner and Brewka, 2017] that deals with independence over marginalizations, whereas this paper deals with independence over conditionalization.

As part of our future work, we plan to elaborate on the construction of total preorders from local ones that are compatible with conditional independence statements, and we will extend our considerations to also include revisions by conditionals. Furthermore, we plan to take advantage of the notion of conditional independence to design efficient networkbased models for iterated revision, and to show how complexity of revision tasks can be reduced effectively in these models.

Acknowledgements

The work of Jesse Heyninck was partially supported by Fonds Wetenschappelijk Onderzoek - Vlaanderen (project G0B2221N).