Belief Change Based on Global Minimisation

1 Introduction andMotivation

Minimisation of change is a crucial element in many approaches to knowledge representation and reasoning, including reasoning about action and time, belief revision, and belief merging. Generally speaking, these approaches take as input a collection of formulas (or sets of formulas) and have as output another set of formulas (or sets of formulas). For instance, in standard approaches to belief revision, we start from an initial belief state represented by a formula φ, 1 a formula α, and come up with a new belief state φ∗α that satisfies α while retaining as much as possible from φ. In belief merging, we start from a collection 〈φ1, . . . , φn〉 of belief states (again, single formulas), possibly with integrity constraints, and end up with a single belief state, computed by retaining as much as possible from the initial information. In a number of approaches to reasoning about time and change, the input consists of a series of observations and/or actions over a discrete time scale, and the output is series of belief states, one for each time point, obtained by minimising change over time. (Note that, for each of these areas, there is obviously not a single nor a best way of minimising change.)

∗Affiliated with the School of Computing Science at Simon Fraser University, Canada, and IIIS at Griffith University, Australia.

1 More generally, initial beliefs are expressed by belief sets, i.e. closed propositional theories; it is well-known that both representations are equivalent when the set of propositional symbols is finite.

Two questions come to mind. First, can we see (some of) these change-minimising approaches as instances of a more general framework? Second, are there other specific cases of this more general setting that are worth considering? This paper answers both questions. The general setting we consider starts with a set of points structured in a graph, and with a formula attached to each point. Following a minimisation step, a formula is determined at each point, representing the original information associated with the point along with information gleaned from connected points. This minimisation step is driven by disagreements among the formulas attached to connected points. We show that a number of approaches to belief merging fit within this general setting, as do a number of approaches to reasoning about time and change, as well as an approach to revision.

The approach is intended to model any domain that can be modelled by a set of connected points, with data associated with each point. Here are some typical examples:

• Multisource merging The graph is a network of interconnected agents (or knowledge bases), where each agent consistently incorporates information from other agents.
• Temporal minimisation of change The graph is a set of time points, and we minimise the set of changes between successive time points.
• Spatial minimisation of change The points are places or regions in space, vertices express adjacency or proximity between places/regions, and the principle of minimising change is justified by the assumption of spatial persistence between connected places or points.

Thus for the last example, if it is raining in some place, e.g. Amsterdam, and we don't know whether it is raining in a neighbouring place, e.g. Brussels, we might want to infer by default that it is also raining there. However, if we also know that it is not raining in Luxembourg, we might want to conclude that we don't knowwhether it is raining in Brussels.

The next section introduces basic notation and reviews related work. Section 3 presents the general approach, while Section 4 discusses specific instances of the approach. This is followed by a section on extensions to the approach, including adding weights to edges. The final section gives concluding remarks and directions for future work.

2 RelatedWork

The approach described herein falls into a broad category of approaches to belief change based on minimisation of change. In our approach, we employ a graph G = 〈V,E〉 to model various phenomena. Some earlier work can be regarded as a specific case of this general approach (and in Section 4 we show that this is indeed the case). Thus belief extrapolation [Dupin de Saint-Cyr and Lang, 2002] involve minimisation of change in a chain (with intended interpretation of the chain being a series of time points). Similarly, the approaches to merging of [Delgrande and Schaub, 2006] can be regarded as minimisation over complete graph or star graphs. Chronological minimisation corresponds to a version of the approach on a chain with priorities on edges. The approach of [Zhang et al., 2004] to negotiation essentially reduces negotiation to a form of mutual belief revision.

On the other hand, the general approach is distinct from belief merging as usually understood, in that most merging operators begin with a set of belief states but yield a single belief state (see for example [Liberatore and Schaerf, 1995; Konieczny and Pino P´erez, 2002]). The conciliation operators of [Gauwin et al., 2005] however are closer to the approach at hand: in this case there is a global merging of the agent's knowledge after which each agent revises its beliefs by the "consensual" knowledge. Similar remarks apply to [Booth, 2002] which, for our purposes, can be regarded as employing multi-agent contraction. [Liberatore and Schaerf, 2000] describes a specific approach combining merging of multiple sources, revision and update; there the process of propagating information temporally is somewhat similar to extrapolation. One approach that conforms very well to our underlying intuitions is the REV!GIS project [W¨urbel et al., 2000] which addresses revision in geographical information systems: flooding information (for example) is encoded for different regions, and persistence of water levels can be used for revising information in adjacent regions.

3 Global minimisation of change

Let LP be a propositional language over Alphabet P = {p, q, . . . }, using the logical constants ⊤, ⊥ and connectives ¬, ∨, ∧, ⊃ and ↔. Formulas are denoted by Greek letters α, ϕ, . . .The set of interpretations of LP is denoted by ΩP. (Whenever clear from the context, we omit the underlying alphabet P.) We denote interpretations explicitly as lists of literals, the falsity of an atom p being indicated by ¯ p. For instance, for P = {p, q, r}, the interpretation where only q is true is denoted by ¯ pq¯ r. Mod(α) is the set of models of α; Cn(α) is the deductive closure of α.

For each i > 0, define alphabet P i = {pi | p ∈ P}; that is, P i is a copy of P where atomic symbols carry the superscript i. We rely on the fact that P i and P j are disjoint for i ̸= j. Similarly, Li is a shorthand for LP i . We associate P 0 with P and L0 with LP. For α ∈ Li , the function ren is defined so that ren(α, j) is the formula α where every occurrence of pi ∈ P i is replaced by the corresponding proposition pj ∈ P j . We can thus write αj for α ∈ L as an abbreviation for ren(α, j). For instance, if α = (¬p∧(q∨r)) then ren(α, 3) = (¬p3 ∧ (q3 ∨ r3 )) = α3 .

3.1 Completion and consensus

In this paper we make use of finite undirected graphs only. Thus for graph G, G = 〈V, E〉 where E is a set of unordered pairs of elements of V . For the sake of simplicity we associate the set of vertices V with an initial sequence of the natural numbers; thus for |V | = n we have V = {1, . . . , n}. Conventionally we write an edge as (x, y) rather than {x, y}.

In the entire paper, let G = 〈V, E〉 be a graph where |V | = n, and P an alphabet.

Definition 3.1 (Scenarios and Interpretations)

• A G-scenario ΣG is a list 〈φ1, . . . , φn〉, where φi ∈ LP
• for each i ∈ V . ΣG is consistent iff φi is consistent for all i ∈ V . ΣG[i] denotes φi, the ith component of ΣG.
• A G-interpretation MG is a list 〈M1, . . . ,Mn〉, where eachMi is an interpretation from ΩP.
• MG is said to satisfyΣG, denotedMG |= ΣG, iffMi |= φi holds for all i ∈ V . ΩV is the set of all G-interpretations and Mod(ΣG) =
• {MG | MG |= ΣG} is the set of all G-models of ΣG.
• The shared or invariant knowledge of a G-scenario ΣG, SK(ΣG), is the formula ∨ni=1 φi.

When clear from the context we drop the subscript G, and simply write Σ and M rather than ΣG and MG. Sometimes, to make notation more readable, we make use of this notation for scenarios: 〈1 : φ1, . . . , n : φn〉 instead of 〈φ1, . . . , φn〉. Similarly, a G-interpretation 〈M1, . . . ,Mn〉 is sometimes denoted as 〈1 : M1, . . . , n : Mn〉. Slightly abusing notation, we denote by Mi(p) the truth value of p ∈ P given by the interpretation Mi.

Definition 3.2 (Change sets)

• A change set for P and G is a subset Δ of E × P.
• Let Mbe a G-interpretation. The change set associated withM, Δ(M), is defined as

• A change set Δ is a change set for a G-scenario Σ iff there exists a G-interpretation M such that M |= Σ and Δ = Δ(M).
• Δ is a minimal change set for Σ if Δ is a change set for Σ and there is no change set Δ′ for Σ such that Δ′ ⊂ Δ.

Minimal change sets pick out those G-interpretations that in a certain (viz. set-containment) sense maximise "closeness" between individual interpretations of members of Σ. To be sure, there are other measures of "closeness" that can be used, a point that we return to later.

Definition 3.3 (Preferred G-interpretations) Given two Ginterpretations M and M′ , define M ⪰ M′ iff Δ(M) ⊆ Δ(M′ ), andM≻M′ iff Δ(M) ⊂Δ(M′ ).

Given a G-scenario Σ and a G-interpretation M, we say that M is a preferred G-interpretation of Σ iff

1. M |= Σ;
2. there is noM′ such thatM′ ≻MandM′ |= Σ.

The set of preferred G-interpretations of Σ is denoted Pref (Mod (Σ), ⪰).

Thus M is preferred to M′ iff the change set of M is included in the change set ofM′ .

Definition 3.4 Let Σ be a G-scenario.

• A completion Θ(Σ) of Σ is a G-scenario Σ′ = 〈φ′1 , . . . , φ′n〉 such that for every i ∈ {1, . . . , n},

• The consensus of Σ is the invariant of its completion, that is, Consensus(Σ) = ∨ni=1 φ′i

We note that a completion is unique up to logical equivalence. Consequently we henceforth refer to the completion, understanding some canonical representative for a set of formulas; see also Proposition 3.3.

Example 1 Let G = 〈V,E〉 be the graph with V = {1, 2, 3, 4} and E = {(1, 2), (2, 3), (2, 4), (3, 4)}. Let Σ = 〈1 : ¬p, 2 : (p ∨ q) ∧ r, 3 : ¬q, 4 : ¬r〉, The preferred models of Σ are 〈¯ pqr, ¯ pqr, ¯ p¯ qr, ¯ p¯ q¯ r〉, 〈¯ pqr, ¯ pqr, ¯ p¯ qr, ¯ pq¯ r〉, 〈¯ pqr, ¯ pqr, ¯ p¯ q¯ r, ¯ p¯ q¯ r〉, 〈¯ pqr, ¯ pqr, ¯ p¯ q¯ r, ¯ pq¯ r〉, 〈 ¯ p¯ qr, p¯ qr, p¯ qr, p¯ q¯ r〉 and 〈¯ p¯ qr, p¯ qr, p¯ q¯ r, p¯ q¯ r〉.

Therefore, the completion of Σ is Θ(Σ) = 〈1 : ¬p ∧ r, 2 : (p ↔ ¬q) ∧ r, 3 : ¬q, 4 : ¬r ∧ (¬p ∨ ¬q)〉.

Although Vertices 2 and 4 disagree about r, the completion of Σ contains r at Vertex 1 (because 1 is connected to 2 only, and so r being true at 2 "blocks" the potential propagation of ¬r at 3 to Vertex 1). In contrast, the completion contains neither r nor ¬r at 3. The consensus of Σ is Consensus(Σ) ≡ ¬p ∨ ¬q As can be verified, this is equivalent to the disjunction of the constituent formulas, viz (¬p ∧ r) ∨ ((p ↔ ¬q) ∧ r) ∨ ¬q ∨ (¬r ∧ (¬p ∨ ¬q)).

3.2 Syntactic characterisation

Definition 3.5 (Equivalence sets, Fits, Maximal fits)

• An equivalence set is a subset of

• The equivalence set induced by a change set Δ is EQ(Δ) = {pi ↔ pj | 〈(i, j), p〉 ∈ (E ×P) \Δ}.
• An equivalence set EQ is a fit for a G-scenario Σ = 〈φ1, . . . , φn〉 iff EQ ∪ ⋃1≤i≤nren(φi, i) is consistent.

A fit EQ for Σ is maximal iff for every EQ ′ ⊃ EQ we have EQ ′ ∪ ⋃1≤i≤n ren(φi, i) is inconsistent.

Proposition 3.1 Δ is a minimal change set for Σ iff EQ(Δ) is a maximal fit for Σ.

Hence, maximising fit between propositional symbols or minimising change between models is equivalent. This in turn leads to a syntactic characterisation of completion:

Proposition 3.2 Let Σ = 〈φ1, . . . , φn〉 be a G-scenario, and let F be the set of maximal fits of Σ.

Then, Θ(Σ) = 〈φ′1, . . . , φ′n〉 is the completion of Σ iff for every i ∈ {1, . . . , n},

Here is an equivalent formulation of Proposition 3.2:

Corollary 3.1 Let Σ = 〈φ1, . . . , φn〉 be a G-Scenario and let Θ(Σ) = 〈φ′1, . . . , φ′n〉. Then, for any β ∈ LP, φ′i |= β iff for every ⊆-maximal set EQ ⊆ {pi ↔ pj | 〈(i, j), p〉 ∈ E × P} consistent with ⋃nj=1 ren(φj , j) we have

This result shows that determining whether some formula holds at some vertex of the completion of Σ can be expressed as skeptical inference in normal default theories without prerequisites [Reiter, 1980]. An immediate consequence of this is that inference from the completion of a scenario is in Πp2 . (We will see shortly that it is also a lower bound.)

Next we describe a syntactic characterisation that determines a specific formula for the completion at each vertex. We begin by adapting the standard notion of a substitution to our requirements: Given alphabets P i , P j a substitution is a set {pi/l(pj ) | pi ∈ P i , pj ∈ P j } where l(pj ) is pj or ¬pj . That is, a substitution is simply a set of pairs, where each pair is made up of an atom in one language and that atom or its negation in the other language. For binary relation R, let R∗ be its transitive closure.

Definition 3.6 Let EQ be an equivalence set. For i, j ∈ V define σEQ i,j = (σEQ i,j )+ ∪ (σEQ i,j )- where

A substitution instance of αi ∈ P i with respect to σEQ i,j , written αiσEQ i,j , is as expected: every atom in αi is replaced by its unique counterpart according to σEQ i,j .

We obtain the following finite characterisation:

Proposition 3.3 Let Σ = 〈φ1, . . . , φn〉 a scenario of G. Let Θ(Σ) = 〈φ′1 , . . . , φ′n〉 be the completion of Σ, and let F be the set of maximal fits of Σ. Then for 1 ≤ j ≤ n we have that

Thus the above proposition gives a recipe whereby one can compute a formula for each vertex that gives the completion.

Example 2 Consider Example 1 again, and Vertex j = 3. For preferred model M1 and Vertex i = 2 we have that φ2 is (p ∨ q) ∧ r; thus φ22 is (p2 ∨ q2 ) ∧ r2 . The relevant part of EQ is p2 ≡ p3 and r2 ≡ r3 . Consequently φ22 σEQ 2,3 is (p3 ∨ ¬q3 ) ∧ r3 . Continuing in this fashion, for the maximal fit based on M1 we obtain:

The conjunction of these terms is equivalent to ¬p3 ∧¬q3 ∧r3 ; re-expressed in our original language this is ¬p∧¬q∧r. The other five preferred models similarly yield formulas for Vertex j = 3, in this example, each being a conjunction of literals. It can be confirmed that their disjunction is equivalent to ¬q.

3.3 Properties of completion and consensus

Here are some properties of completion and consensus.

Proposition 3.4 Let Σ = 〈φ1, . . . , φn〉 be a G-scenario, and let Θ(Σ) = 〈φ′1 , . . . , φ′n 〉.

1. Θ(Σ) = Θ(Θ(Σ)).
2. If ∃φ′i ∈ Θ(Σ), φ′i |= ⊥ then ∀φ′j ∈ Θ(Σ), φ′j |= ⊥.
3. If G is connected and ∧1≤i≤n φi is consistent then φ′j ↔ ∧1≤i≤n φi for every j ∈ {1, . . . , n}.
4. Σ is consistent iff Θ(Σ) is consistent.
5. φ′i |= φi for every φi ∈ Σ.
6. Consensus(Σ) |= SK(Σ).

Note that Property 3 above refers to the structure of the graph. Clearly, the information at a given vertex i can propagate to vertex j only if there is a path from i to j. This brings us to the following (easy but useful) decomposability result:

Proposition 3.5 Let G1, . . . ,Gq be the connected components of G and let {V1, . . . , Vq} be the corresponding partition of V . For each i ∈ {1, . . . n}, let k(i) be the unique integer such that i ∈ Vk(i). Given a G-scenario Σ, Θ(Σ) = 〈φ′1 , . . . , φ′n〉, and k ∈ {1, . . . , q}, let Σk = 〈φi | i ∈ Vk〉, and let Θ(Σk) = 〈φ′′ i | i ∈ Vk〉. Then:

• φ′i = φ′′ i for each i ∈ {1, . . . , n};
• Consensus(Σ) ≡ ∨1≤k≤q Consensus(Σk).

This result is a bit tedious to state but is very intuitive: if the graph G is not connected, then it is sufficient to consider its connected components separately, and to compute the completion of Σ for each one of these.

Example 3 Let G = 〈V, E〉 with V = {1, 2, 3, 4} and E = {(1, 2), (3, 4)}. Let Σ = 〈1 : a ∨ b, 2 : ¬a ∨ ¬b, 3 : a, 4 : ¬a ∧ ¬b〉. The connected components of G are G1 = 〈{1, 2}, {(1, 2)}〉 and G2 = 〈{3, 4}, {(3, 4)}〉, hence, Σ1 = 〈1 : a ∨ b, 2 : ¬a ∨ ¬b〉 and Σ2〈3 : a, 4 : ¬a ∧ ¬b〉.

We obtain Θ(Σ1) = 〈1 : a ↔ b, 2 : a ↔ b〉 and Θ(Σ2) =

〈3 : a ∧¬b, 4 : ¬a ∧¬b〉. Therefore,

Thus, without loss of generality, we may now assume that G is connected.

Another decomposition result concerns the propositional symbols the logical theories at different vertices are about. We say that φi is irrelevant to Q ⊆ P iff φi is logically equivalent to some formula ψi in which no symbol in Q appears [Lang et al., 2003].

Proposition 3.6 Let Σ be a G-scenario. Suppose there exist a partition {V1, V2} of V and a partition {Q1, Q2} of P such that for each i ∈ V1 (resp. i ∈ V2), φi is irrelevant to Q2 (resp. to Q1). Let Σ1 and Σ2 be the restrictions of Σ to V1 and V2, defined by Σ1[i] = Σ[i] if i ∈ V1 and Σ1[i] = ⊤ otherwise (and similarly for Σ2). Let Θ(Σ) = 〈φ′1 , . . . , φ′n 〉. Then, for every i ∈ V ,

• φ′i = Θ(Σ1)[i] ∧Θ(Σ2)[i]
• Consensus(Σ) = Consensus(Σ1) ∧ Consensus(Σ2).

Example 4 Let V = {1, 2, 3, 4, 5}, E = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)} and Σ = 〈1 : p ∨ q, 2 : ¬p, 3 : a ∧ b, 4 : ¬p ∧ q, 5 : a ∧ ¬b〉. Taking Q1 = {a, b}, Q2 = {p, q}, V1 = {3, 5} and V2 = {1, 2, 4}, we get Θ(Σ1) = 〈1 : a, 2 : a, 3 : a ∧ b, 4 : a, 5 : a ∧ ¬b〉 and Θ(Σ2) = 〈1 : ¬p ∧q, 2 : ¬p ∧q, 3 : ¬p ∧q, 4 : ¬p ∧q, 5 : ¬p ∧q〉. Hence, Θ(Σ) = 〈1 : a∧¬p∧q, 2 : a∧¬p∧q, 3 : a∧b∧¬p∧q, 4 : a ∧ ¬p ∧ q, 5 : a ∧ ¬b ∧ ¬p ∧ q〉.

Let us now consider conjunctive formulas: a formula φi is conjunctive iff it is a consistent conjunction of literals.

Proposition 3.7 Let Σ = 〈φ1, . . . , φn〉 be a G-scenario such that each φi is a conjunctive formula. Let Θ(Σ) = 〈φ′1 , . . . , φ′n〉. Then, φ′i |= p iff the two following holds:

1. φj |= p for some j ∈ {1, . . . , n};
2. If φl |= ¬p, then for every path π from l to i, there is a m in π such that φm |= p.

Proposition 3.7 gives a simple method for computing Θ(Σ) when Σ consists of conjunctive belief bases. For any p ∈ P:

1. let Gp (resp. G¬p) be the graph obtained from G by deleting all vertices i such that φi |= ¬p (resp. φi |= p) and all edges to or from i;
2. let Xp (resp. X¬p) be the set of all i such that there is a path in Gp (resp. in G¬p) from a vertex j such that φj |= p (resp. φj |= ¬p).

Proposition 3.8 Let Σ = 〈φ1, . . . , φn〉 be a G-scenario such that each φi is a conjunctive formula and let Θ(Σ) = 〈φ′1 , . . . , φ′n〉. Then for every i ∈ {1, . . . , n},

As a corollary, the completion and the consensus of a conjunctive scenario can be computed in polynomial time.

Example 5 Let V = {1, 2, 3, 4, 5, 6}, E = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (1, 6)} and Σ = 〈1 : p ∧ q, 2 : ¬q, 3 : ¬p, 4 : p, 5 : ⊤, 6 : ⊤〉. Gp is the graph whose set of edges is Ep = {(1, 2), (4, 5), (5, 6), (1, 6)}, therefore Xp = {1, 2, 4, 5, 6}. G¬p is the graph whose set of edges is E¬p = {(2, 3), (5, 6)}, therefore X¬p = {2, 3}. Similarly, E¬q = {(2, 3), (3, 4), (4, 5), (5, 6)}, Eq = {(3, 4), (4, 5), (5, 6), (1, 6)}, Xq = {(1, 3, 4, 5, 6} and X¬q = {2, 3, 4, 5, 6}. Therefore, Θ(Σ) = 〈1 : p ∧ q, 2 : ¬q, 3 : ¬p, 4 : p, 5 : p, 6 : p〉.

4 Particular Instances of the Approach

Our approach falls into the broad category of approaches to belief change based on minimisation. We consider initial formulas believed at vertices of G, and select those models that minimise differences between models of the individual formulas. So far, we haven't said much about specific interpretations of G. In this section, we give several examples of such interpretations, sometimes corresponding to particular classes of graphs; and we show that our setting generalises frameworks that have been explored previously.

We first consider three specific types of graphs: chain graphs, star graphs and complete graphs, and show that each of these three cases leads to a specific belief change operator studied previously.

Definition 4.1 (Extrapolation) Let G = 〈V,E〉 be a chain graph, where E = {(i, i + 1) | i ∈ V, 1 ≤ i < n}, and let Σ be a G-scenario. The extrapolation operator Ext(Σ) induced by ⪰ is unchanged from Definition 3.4: Ext(Σ) = Θ(Σ).

Ext is an extrapolation operator in the sense of [Dupin de Saint-Cyr and Lang, 2002], in which V is considered as a set of time points: if Θ(Σ) = 〈φ′1 , . . . , φ′n〉, then φ′t is the completed scenario at time t, obtained from the initial observations and a principle of minimal change. Other extrapolation operators can be obtained by varying the preference relation (see Section 5). As to Consensus(Σ), it simply expresses the information that remains invariant over time in the scenario.

Definition 4.2 (Projection) Let G = 〈V, E〉 be a star graph, where V = {0, 1, . . . , n} and E = {(0, i) | i ∈ V \{0}}, and let Σ be a G-scenario. The projection operator Proj induced by ⪯ is the function Proj(Σ) = Θ(Σ)[0]

Consensus(Σ) here coincides with the projection operator given in [Delgrande and Schaub, 2006]: {1, . . . , n} are the labels of the knowledge bases to be merged; φi represents the beliefs of source/agent i; and 0 is the label for the result of the merging (with φ0 = IS for set of integrity constraints IS).

Definition 4.3 (Consensus) Let G be a complete graph and let Σ be a G-scenario. The consensus operator of G is Con(Σ) = Consensus(Σ).

That is, the consensus operator contains the common knowledge implicit in the minimal models of Σ. This operator corresponds to the consensus merging operator of [Delgrande and Schaub, 2006].

A crucial difference between the preceding two operators is illustrated in the following example. Let G be the complete graph on 3 vertices, and assume we have φ1 = p ∧ q ∧ r, φ2 = ¬p ∧ ¬q ∧ r, φ3 = ⊤. The projection on φ3 is r while the consensus is (p ↔ q) ∧ r. See [Delgrande and Schaub, 2006] for a detailed examination of these operators.

Definition 4.4 (Revision) Let G = 〈{1, 2}, {(1, 2)}〉 and let 〈φ1, φ2〉 be a G-scenario. The revision operator ˙+ is the function φ1 ˙+φ2 = Θ(Σ)[2]

This notion of revision corresponds to the basic notion of revision given in [Satoh, 1988; Delgrande and Schaub, 2003].

Deciding whether β ∈ φ1 ˙+φ2 is Πp2 -complete [Delgrande et al., 2004]. Thus (given the remark in Section 3.2) the general problem of deciding, given a G-scenario Σ, a formula β, and i ∈ V , whether β ∈ Θ(Σ)[i], is Πp2 -complete (and so no more complex than all the particular cases considered above). A similar result holds for consensus.

There are of course other graph structures that could be investigated, for example trees or cycles. Further, one can consider other interpretations. Thus a graph may be considered under a spatial interpretation, in which nodes correspond to regions of space and edges correspond to connections between adjacent regions. Completion is then based on the principle that, normally, what holds in a region also holds in the adjacent region. Another possible interpretation of the graph would be a mixture of merging and extrapolation, in the same vein as [Liberatore and Schaerf, 2000], where we have several time points, and possibly several independent information sources at each time point.

5 Alternative Definitions of Completion and Consensus

So far, we have focussed on a very simple criterion for selecting preferred interpretations, namely, M being preferred to M′ iff Δ(M) ⊂ Δ(M′ ). Clearly, this notion of preference between change sets (and between interpretations) frequently gives many incomparable interpretations, hence a large number of preferred interpretations, and then completion and consensus may be rather weak. Here we give a more general definition without changing much of our notions and results.

A preference relation on change sets ⪰ is a reflexive and transitive relation over E × P. Any such preference relation induces a preference relation ⪰ on interpretations, by M ⪰ M′ iff Δ(M) ⪰ Δ(M′ ). We recover the preference relation considered previously if we define Δ ⪰I Δ′ iff Δ ⊆ Δ′ . Another intuitive preference relation is cardinality: Δ ⪰C Δ′ iff |Δ| ≤ |Δ′ |. The definition of a preferred Ginterpretation (w.r.t. ⪰) as well as those of completion and consensus are straightforward generalisations of Definitions 3.3 and 3.4. Note that for a star graph and ⪰C one obtains majority merging as in [Konieczny and Pino P´erez, 2002].

A second generalisation of the approach begins from the observation that edges, representing connected points, may have differing strengths or reliability. Hence, more sophisticated preference relations may incorporate ranking functions, or numerical weights, on edges. For graph G = 〈V,E〉, a priority assignment P is a mapping from E to the natural numbers IN (any totally ordered set serves equally well).

Definition 5.1 (P-preferredG-interpretations) Let Σ be a scenario of graph G = 〈V,E〉, and let P be a priority assignment to E. Let MandM′ be interpretations of Σ, and let Δ(M, e) (resp. Δ(M′ , e)) be the change set associated with edge e ∈ E in M (resp. M′ ).

DefineM≻P M′ iff

• M |= Σ andM′ |= Σ;
• there is i ∈ IN such that:
• for every e ∈ E such that P(e) = i we have Δ(M, e) ⊂ Δ(M′ , e), and
• for every e′ ∈ E such that P(e′ ) > i we have Δ(M, e′ ) = Δ(M′ , e′).

Example 6 Consider Example 1 where P((1, 2)) = 2 and other edges are assigned value 1. The preferred models are now M1, M2, M3, and M4. Consequently ¬p is true at each point in Θ(Σ).

The completion of Σ under P , Θ(Σ, P), is defined in an obvious extension to Definition 3.4, over the P-preferred interpretations; we omit details given space constraints.

Proposition 5.1 Let Σ be a scenario of graph G = 〈V,E〉 and let P be a priority assignment to E. Let Θ(Σ) = 〈φ′1, . . . , φ′n〉 be the completion of Σ and let Θ(Σ, P) = 〈φ′′ 1 , . . . , φ′′n〉 be the completion of Σ under P . Then φ′′ i |= φ′i for every 1 ≤ i ≤ n.

The notion of P-preferred G-interpretations captures the notion of chronological minimisation: let G be a chain graph 〈V,E〉 with V = {1, . . . , n}, E = {(t, t + 1) | t =

0, . . . , n - 1}, and priority assignment P (t, t + 1) = t. Then the completion of Σ corresponds to chronological ignorance [Shoham, 1988] in which later changes are preferred to earlier changes. Further, when G is star graph (for merging), the priority of the edge connecting a source i to the centre point 0 can encode the reliability of i. Of course other alternatives are possible.

In a further direction, and generalising cardinality-based preference, one can assign weights to propositions, reflecting that some propositions are more likely to persist than others. For instance, when crossing the border between two countries in Europe, the official language is more likely to change than the main religion. These weights would then be aggregated to assign an overall weight to a change set.

6 Discussion

We have described a general approach to belief change based on minimisation of change. In the approach, an undirected graph G = 〈V, E〉 has associated with each vertex some information represented in a formula. The graph structure can model various phenomena including spatially adjacent points, temporally adjacent points in time, connected agents, etc. Consequently it is quite expressive, and generalises similar frameworks that have been explored previously. The intuition is that change between neighbours is exceptional; this assumption justifies global minimisation of change. Following the minimisation process, the completion of the graph provides new information at each vertex, representing that information that may be consistently gleaned from other connected vertices. The approach generalises previous frameworks involving change minimisation, including extrapolation and related belief change operators, and some merging and revision operators. However, the general approach is of independent interest. In particular, it proves to be suitable to spatial mininisation of change. Along this line, an interesting practical issue would be to apply the approach to a domain such as is addressed in [W¨urbel et al., 2000]. Lastly, the general approach is computationally no more complex than each of these particular cases.

An interpretation of the graph that warrants more investigation is when it represents a network of agents. Global minimisation of change with respect to a network of agents can be understood as follows: agents have some initial beliefs that they don't want to give up, and after some communication process, the agents come to an equilibrium where changes between the belief bases of neighbouring agents are globally minimal. (Hence, our approach, based on global minimisation, can also be characterised as consistent expansion in a network of agents.) One interesting issue for future research is that of local minimisation of change, wherein minimisation at a vertex is with respect to that vertex's adjacent neighbours only. Clearly in this case the process admits nontrivial iteration. Our approach also departs from approaches such as [Gauwin et al., 2005], where agents iteratively revise or merge their current beliefs by/with the beliefs of other agents. Another promising issue for further research is to allow information to be similarly revised (and not just strengthened) at a vertex (and so where Theorem 3.4, Part 5 does not necessarily hold). In this case, an agent may in fact give up beliefs, perhaps as a result of contradicting beliefs at an adjacent vertex with higher reliability.

Acknowledgements

We wish to thank Florence Dupin de Saint-Cyr for many helpful discussions.