Revision of Partially Ordered Information: Axiomatization, Semantics and Iteration

1 Introduction

Belief revision is a central topic in databases, philosophy and arti�cial intelligence. The revision of a database consists of the insertion of some new information while preserving consistency.

This process has been discussed in different frameworks (probability theory, Spohn's ordinal conditional functions, Grove's systems of spheres, possibility theory, etc.) and from different points of view (axiomatization [Alchourr·on et al., 1985; Katsuno and Mendelzon, 1991], computational issue, etc.). The proposal of Alchourr ·on, G¤ardenfors and Makinson (AGM) [Alchourr·on et al., 1985] represents one of the most in�uential work. It concerns revision operations that revise a theory (representing agent's current beliefs) with a formula (representing new pieces of information). The AGM framework consists in a set of natural postulates that any revision operation should satisfy.

An important issue is that any revision operator satisfying AGM's postulates is implicitly based on a priority ordering. This result suggests that an agent's epistemic state, denoted by Ψ, is something more complex than a simple representation of agent's current beliefs (called belief set and denoted by Bel(Ψ)). It also contains strategies to revise his beliefs. The AGM's postulates have been largely studied and/or adapted in the literature. For instance, additional postulates have been proposed to manage the concept of iterated belief change in [Darwiche and Pearl, 1997] (see also [Rott, 2001; Lehmann, 1995; Nayak, 1994; Konieczny and Pino P·erez, Odile Papini LSIS-CNRS, Universit·e du Sud Toulon-Var. BP 132. 83957 La Garde Cedex France.

papini@univ-tln.fr

2000]). More generally, iterated revision is applied to an epistemic state, instead of a belief set, and the result is also an epistemic state.

Epistemic states are often represented by total pre-orders on possible worlds (or interpretations), denoted by ≤Ψ. The set of models of Bel(Ψ) are identi�ed to be minimal (i.e, preferred) elements with respect to ≤Ψ.

There is another issue in belief revision and which has been less investigated in the literature: the iterated revision of epistemic states represented by partial pre-orders (instead of total pre-orders) [Katsuno and Mendelzon, 1991]. Partial preorders offer more �exibility than total pre-orders to represent incomplete knowledge.

Katsuno and Mendelzon proposed in section 5 of [Katsuno and Mendelzon, 1991], a set of postulates and a representation theorem that characterize revision operations based on partial pre-orders. Unfortunately, the proposed approach is not satisfactory since only one class of partial pre-orders can be revised. For instance, assume that we have a partial preorder ⪯Ψ on four possible interpretations {ω0, ω1, ω2, ω3}, such that ω0 is �strictly preferred� to ω1 and ω1 is �strictly preferred� to ω2 but ω3 is incomparable with ω0, ω1 and ω2 (cf. �gure 1, for sake of clarity, re�exivity and transitivity are not represented). Clearly, ω0 and ω3 characterize (are models of) agent's currents beliefs Bel(Ψ) (no interpretation is strictly preferred to ω0 or to ω3), but ⪯Ψ is not a faithful assignment in the sense of [Katsuno and Mendelzon, 1991].

More generally, there is no consistent propositional formula that admits ⪯Ψ of Figure 1 as a faithful assignment. In

fact, faithful assignment requires that each model of agent's current beliefs (namely Bel(Ψ)) should be strictly preferred to each counter-model of agent's current beliefs. This requirement is appropriate for total pre-orders, but is too strong for partial pre-orders.

This paper investigates iterated belief revision of partially ordered information. Its main contributions can be summarized as follows:

• We propose an alternative de�nition of faithful assignment and an alternative set of natural postulates for revising partially ordered information.
• We provide a representation theorem for iterated revision operators satisfying this new set of postulates.
• We investigate additional postulates dedicated to iterated belief revision. In particular, we discuss the extension of Darwiche and Pearl's postulates, Boutilier's postulate and we propose two alternative postulates for capturing other forms of iterated belief revision.
• Lastly, we illustrate our results with three well-known operators (revision with memory, possibilistic revision and natural belief revision) for revising partially ordered information.

The rest of this paper is organized as follows. Section 2 presents the Katsuno and Mendelzon's postulates for belief revision. Section 3 contains a modi�cation of these postulates. Section 4 characterizes Darwiche and Pearl's postulates and Boutilier's postulate for iterated belief revision with partially ordered information. Lastly, Section 5 proposes two alternative additional postulates and provides three examples of operators that satisfy the proposed postulates.

2 Notations and KMpostulates

2.1 Notations

In this paper we use propositional calculus, denoted by L, as knowledge representation language with usual connectives ¬, ∧, ∨, →, ≡ (logical equivalence). The lower case letters a, b, c, · · · , are used to denote propositional variables and lower case Greeks letters ϕ, ψ, · · · , are used to denote formulas. We denote by Ω the set of interpretations of L and by Mod(ψ) the set of models of a formula ψ, that is Mod(ψ) = {ω ∈ Ω, ω |= ψ}. Upper case Greeks letters Ψ, Φ · · · , are used to denote epistemic states.

A partial pre-order, denoted by ⪯, on a set A is a re�exive and transitive binary relation. Let x, y ∈ A, we de�ne the equality x = y iff x ⪯ y and y ⪯ x. The corresponding strict partial pre-order associated with ⪯, denoted by ≺, is de�ned as usual: x ≺ y iff x ⪯ y holds but x ⪯ y does not hold. We denote by ∼ the incomparability relation, namely x ∼ y iff neither x ⪯ y nor y ⪯ x holds.

Given ⪯ on a set A, the set of the minimal elements of A, denoted by Min(A,⪯), is de�ned by Min(A,⪯) = {x : x ∈ A, ∄y ∈ A, y ≺ x}.

2.2 The KMpostulates for belief revision

Katsuno and Mendelzon proposed in [Katsuno and Mendelzon, 1991] a reformalization of the well-known AGM postulates [Alchourr·on et al., 1985]. In this framework, the epistemic state of an agent is represented by a formula ψ. A revision operator ◦ is a function from a formula ψ and produces a new formula denoted by ψ ◦ µ. The operator ◦ should satisfy the following postulates.

• (R1) ψ ◦ µ |= µ,
• (R2) if ψ ∧ µ is satis�able, then ψ ◦ µ ≡ ψ ∧ µ,
• (R3) if µ is satis�able, then ψ ◦ µ is satis�able,
• (R4) if ψ1 ≡ ψ2 and µ1 ≡ µ2 then ψ1 ◦ µ1 ≡ ψ2 ◦ µ2,
• (R5) (ψ ◦ µ) ∧ϕ |= ψ ◦ (µ ∧ϕ),
• (R6) if (ψ◦µ)∧ϕ is satis�able, thenψ◦(µ∧ϕ) |= (ψ◦µ)∧ϕ.

An important result is that any revision operator that satis�es (R1) - (R6) is implicitly based a total pre-order ≤ψ on

Ω. In order to deal with partial pre-orders, Katsuno and Mendelzon proposed in section 5 of [Katsuno and Mendelzon, 1991] to replace (R6) by the two following postulates:

• (R7) if ψ ◦ µ1 |= µ2 and ψ ◦ µ2 |= µ1 then ψ ◦ µ1 ≡ ψ ◦ µ2,

The following representation theorem has been proposed with these postulates for partial pre-orders.

Theorem 1 ([Katsuno andMendelzon, 1991]) A revision operator ◦ satis�es the postulates (R1) to (R5), (R7) and (R8) iff there exists a faithful assignment that maps ψ to a partial pre-order ⪯ψ such that: Mod(ψ ◦ µ) = Min(Mod(µ), ⪯ψ).

Where the faithful assignment is de�ned as follows.

De�nition 1 (faithful assignment) Let ψ be a propositional formula. A partial pre-order on Ω, associated with ψ, denoted by ⪯ψ, is said to be a faithful assignment if the three following conditions hold :

1. if ω, ω′ ∈Mod(ψ) then ω <ψ ω′ does not hold,
2. if ω ∈Mod(ψ) and ω′ /∈Mod(ψ), then ω <ψ ω′ holds,
3. if ψ ≡ ϕ, then ≤ψ=≤ϕ.

In the following, by KM postulates, we refer to (R1) - (R5), (R7) and (R8).

3 KMpostulates revisited

In the introduction, we pointed out that KM postulates are not fully satisfactory for iterated belief revision of partially ordered information. This section justi�es this statement and proposes a revisited set of KM postulates.

3.1 Faithful assignment revisited

This subsection proposes a modi�ed de�nition of faithful assignment. The one given by de�nition 1 is not appropriate. Indeed, if ⪯Ψ is a partial pre-order on the set of interpretations Ω representing agent's epistemic state, and if we de�ne Mod(Bel(Ψ)) = Min(Ω,⪯Ψ) to be the current agent's beliefs, then there is no guarantee that ⪯Ψ will be a faithful assignment.

For instance, the partial pre-order given by �gure 1 is not a faithful assignment, since condition (2) of De�nition 1 is not satis�ed. Indeed Mod(Bel(Ψ)) = {ω0, ω3} and ω3 ≺Ψ ω2 does not hold. Of course, one may simply suggest to enforce minimal elements of ⪯Ψ to be equal. In our example, we enforce ω0 to be equal to ω3 (as it is illustrated by Figure 2).

ω2

But this is not satisfactory. Indeed, if ⪯Ψ′ denotes the partial pre-order obtained from ⪯Ψ by enforcing minimal elements of ⪯Ψ to be equal then, in general, Bel(Ψ′ ◦ µ) ̸≡ Bel(Ψ ◦ µ). In our example, if we consider a new piece of information µ such that Mod(µ) = {ω1, ω3}, then, it can easily be checked that Bel(Ψ ◦ µ) ̸≡ Bel(Ψ′ ◦ µ). Indeed Mod(Bel(Ψ ◦ µ)) = Min({ω1, ω3}, ⪯Ψ) = {ω1, ω3} and Mod(Bel(Ψ′ ◦ µ)) = Min({ω1, ω3}, ⪯Ψ′ ) = {ω3},

where ⪯Ψ and ⪯Ψ′ are respectively represented by Figure 1 and Figure 2.

The problem with De�nition 1 is the condition (2), which requires that each model of agent's current beliefs is preferred to all counter-models of agent's current beliefs. We propose to weaken this condition by only requiring that each countermodel of agent's current beliefs is strictly less preferred than at least one model of agent's current beliefs.

In order to deal with iterated belief revision, which applies to epistemic states instead of formulas, we also modify condition (3) exactly as it is proposed in [Darwiche and Pearl, 1997]. These two changes lead to the following modi�ed definition of faithful assignment.

De�nition 2 (P-faithful assignment) Let Ψ be an epistemic state. A partial pre-order on Ω, associated to Ψ and denoted by ⪯Ψ is said to be a P-faithful assignment if the three following conditions hold :

1. if ω, ω′ |= Bel(Ψ) then ω ≺Ψ ω′ does not hold,
2. if ω′ ̸|= Bel(Ψ), then there exists ω such that ω |= Bel(Ψ) and ω ≺Ψ ω′ ,
3. if Ψ = Φ, then ⪯Ψ=⪯Φ.

Clearly, if ⪯Ψ is a faithful assignment, then it is also a Pfaithful assignment. Note that if ⪯Ψ is a total pre-order, then this de�nition is equivalent to the de�nition of a faithful assignment of Darwiche and Pearl [Darwiche and Pearl, 1997].

3.2 Revisited postulates for partially ordered information

Let us now present the �revision� of KM postulates. In the whole paper, we assume that the new information µ is consistent and the initial beliefs Mod(Bel(Ψ) is not empty. Basically, there is a need of two changes. The �rst change is the same as the one proposed by Darwiche and Pearl in [Darwiche and Pearl, 1997] (see also [Friedman and Halpern, 1999]). It consists in a simple adaptation of KM postulates in order to make belief revision operation a function on epistemic states instead on set of beliefs. More precisely, we propose to replace postulate (R4) by the one proposed in [Darwiche and Pearl, 1997].

Postulate (P4) requires the equality between epistemic states while R4 requires the equivalence between beliefs sets.

The second change concerns postulate (R2). We argue that (R2) is too strong when dealing with partial pre-orders.

Let us consider again the example represented by Figure 1. Let µ be such that Mod(µ) = {ω1, ω3}. Since Min(Mod(µ), ⪯Ψ) = {ω1, ω3}, we expect to have Bel(Ψ ◦ µ) ≡ {ω1, ω3}. But R2 leads to have Bel(Ψ ◦ µ) ≡ {ω3}. Indeed, (R2) says that if Bel(Ψ) ∧ µ is consistent, then Bel(Ψ) ◦ µ ≡ Bel(Ψ) ∧ µ. This equivalence makes sense if for each ω, ω′ models of Bel(Ψ), ω =Ψ ω′ holds. However, when models of Bel(Ψ) may be incomparable, then (R2) becomes questionable.

We suggest to replace R2 by the following postulate. It concerns the situation where the new piece of information is a tautology. In this case, agent's current beliefs should not change. Namely:

3.3 Representation theorem

The new set of postulates that we propose for characterizing the revision of partially ordered beliefs are the following ones.

• (P1) Bel(Ψ◦ µ) |= µ,
• (P2) Bel(Ψ◦⊤) ≡ Bel(Ψ),
• (P3) if µ is satis�able, then Bel(Ψ◦ µ) is satis�able,
• (P4) if Ψ1 = Ψ2 and µ1 ≡ µ2 then Bel(Ψ1 ◦ µ1) ≡ Bel(Ψ2 ◦ µ2),
• (P5) Bel(Ψ ◦ µ) ∧ ϕ |= Bel(Ψ ◦ (µ ∧ ϕ)),
• (P6) if Bel(Ψ ◦ µ1) |= µ2 and Bel(Ψ ◦ µ2) |= µ1 then Bel(Ψ ◦ µ1) ≡ Bel(Ψ ◦ µ2),
• (P7) Bel(Ψ ◦ µ1) ∧ Bel(Ψ ◦ µ2) |= Bel(Ψ ◦ (µ1 ∨ µ2)).

The postulates (P1), (P3), (P4), (P5), correspond respectively to the postulates (R1),(R3), (R4), (R5). The postulates (P6) and (P7) are respectively a reformalization of the postulates (R7) and (R8) proposed in [Katsuno and Mendelzon, 1991] for epistemic states.

Two weakenings of (R2) can be derived from this set of postulates:

The �rst one means that joint of initial beliefs Bel(Ψ) and the new information are contained in the set of new belief's models. The second one means that if we revise with some pieces of information that can be inferred from agent's current beliefs, then the agent's beliefs should not change.

Given this set of postulates and the de�nition of P-faithful assignment, we provide the following representation theorem:

Theorem 2 A revision operator ◦ satis�es the postulates (P1) to (P7) iff there exists a P-faithful assignment that maps each Ψ to a partial pre-order ⪯Ψ such that Mod(Bel(Ψ ◦ µ)) = Min(Mod(µ), ⪯Ψ).

4 Characterization of iterated revision postulates

Several authors (e.g. [Darwiche and Pearl, 1997]) argue that, in order to have a genuine iterated belief revision operator, we should augment basic AGM postulates with some additional postulates. Indeed, these basic postulates constrain the relationships between Bel(Ψ) and Bel(Ψ ◦ µ). The aim of these additional postulates is to provide more constraints between Ψ and Ψ ◦ µ by, for instance, expliciting the relationships between ⪯Ψ and ⪯Ψ◦µ. Given a formula µ, there are three questions that need to be addressed:

• How the order between models of µ does evolve?
• How the order between counter-models of µ does evolve?
• How the order between models and counter-models of µ does evolve?

Darwiche and Pearl [Darwiche and Pearl, 1997] gave four natural postulates for iterated belief revision that provide answers for these questions.

Another postulate, which has also been discussed in the literature, is the one which characterizes Boutilier's natural belief revision [Boutilier, 1993] (and hinted in [Spohn, 1988]) for totally ordered beliefs:

This section provides a characterization of the Darwiche and Pearl's postulates and the Boutilier's postulate, when epistemic states are represented by partial pre-orders.

In the following, we restrict ourselves to iterated belief revision operators that satisfy (P1)-(P7). Let ◦ be a such revision operator and ⪯Ψ be its associated P-faithful assignment. In order to characterize (C1)-(C4) and (CB), we de�ne �ve properties on relationships between ⪯Ψ and ⪯Ψ◦µ.

(Ip1) (resp. (Ip2)) means that the strict order between models (resp. counter-models) of the new piece of information µ is preserved. (Ip3) means that if a model of µ is strictly preferred to a counter-models then this strict preference is preserved. (Ip4) is similar with (Ip3) for non-strict preference. Finally, (Ip5) means that the strict order between the counter-models of the agent's current beliefs is preserved.

The following representation theorem provides a characterization of (C1) - (C4).

Theorem 3 Let ◦ be a revision operator satisfying the postulates (P1) - (P7). Then:

1. ◦ satis�es (C1) iff its associated faithful assignment satis�es (Ip1),
2. ◦ satis�es (C2) iff its associated faithful assignment satis�es (Ip2),
3. ◦ satis�es (C3) iff its associated faithful assignment satis�es (Ip3),

Note that only the characterization of (C3) is identical to the one provided by Darwiche and Pearl [Darwiche and Pearl, 1997]. The others are different.

More precisely, there are two main differences with the DP representation theorem. First, we have only

1. if the faithful assignment associated with ◦ satis�es (Ip4) then ◦ satis�es (C4).

The converse does not hold.

A similar remark also holds for Boutilier's postulate (CB).

The second main difference concerns (C1) and (C2). Indeed, Darwiche and Pearl have shown that when ⪯Ψ is a total pre-order, then (C1) (resp. (C2)) guarantees that ⪯Ψ and ⪯Ψ◦µ to be identical on their subdomainMod(µ)×Mod(µ) (resp. Mod(¬µ) ×Mod(¬µ)). However, when ⪯Ψ is a partial pre-order, then only the strict relations ≺Ψ and ≺Ψ◦µ are identical. Namely, it may happen that ω =Ψ ω′ and ω ∼Ψ◦µ ω′ both hold for revision operator satisfying (P1) - (P7) and (C1) (resp. (C2)).

Theorem 4 Let ◦ be a revision operator satisfying the postulates (P1) - (P7). Then:

When ⪯Ψ is a total pre-order, then ≺Ψ◦µ is uniquely de�ned for satisfying (CB). Theorem 4 shows that the unicity of the result is no longer valid and hence ⪯Ψ◦µ is not uniquely de�ned. Again, only the strict relation associated with ⪯Ψ◦µ is uniquely de�ned.

An example of revision operator satisfying (CB) is an extension to �natural revision� for partial pre-orders:

De�nition 3 Let Ψ be an epistemic state and µ be a propositional formula, the revised epistemic state Ψ◦nµ corresponds to the following partial pre-order:

• if ω, ω′ ∈ Min(Mod(µ),⪯Ψ) then ω ⪯Ψ◦nµ ω′ iff ω ⪯Ψ ω′ ,
• if ω, ω′ ̸∈ Min(Mod(µ),⪯Ψ) then ω ⪯Ψ◦nµ ω′ iff ω ⪯Ψ ω′ ,
• if ω ∈ Min(Mod(µ),⪯Ψ) and ω′ ̸∈ Min(Mod(µ), ⪯Ψ) then ω ≺Ψ◦nµ ω′ .

The �rst condition imposes that the order between the preferred models of µ is preserved. The second condition preserves the ordering between non-preferred models of µ. Finally, the third condition imposes that any minimal models of µ is preferred to any other model.

Example 1 Let us consider the epistemic state Ψ represented by Figure 3, where ω0 = {¬a, ¬b}, ω1 = {a, ¬b}, ω2 = {¬a, b}, ω3 = {a, b}. Let µ be a new piece of information such that Mod(µ) = {ω1, ω3}. Then the revision of Ψ by the new piece of information µ is represented by the partial pre-order ⪯Ψ◦nµ described by Figure 4.

According to this de�nition it can be checked that the revision operator ◦n provided by de�nition 3 satis�es the postulates (P1) - (P7) and (CB). Moreover, it can be noticed that ◦n does not satisfy (R2) since Mod(Bel(Ψ)) = {ω0, ω3}, Mod(Bel(Ψ) ◦n µ) = {ω1, ω3} and Mod(Bel(Ψ) ∧ µ) = {ω3}.

5 Two alternative postulates

Among additional postulates (C1) - (C4) proposed in [Darwiche and Pearl, 1997] for iterated belief revision, (C1) seems to be very acceptable. However it is less obvious with (C2) (for more detailed discussion, see, for instance, [Lehmann, 1995; Friedman and Halpern, 1999]). Moreover, (C3) may appear to be too cautious. We now propose to analyze two alternative postulates which capture two other forms of iterated belief revision.

The �rst one departs from the idea of (C2), and it is close to the idea of conditioning with a completely sure information used in uncertainty theories. In probability theory (and similarly in possibility theory), if we revise a probability distribution by some completely sure formula, then all counter-models of these formulas are considered as impossible. This properties is captured by the following postulate.

It expresses that if Ψ is revised by µ, and again by its contrary ¬µ, then piece of initial beliefs are ignored, and only last pieces of information are retained. The characterization of this postulate is as follows.

Theorem 5 A revision operator ◦ satis�es the postulates (P1) - (P7) and (Ccond) iff its corresponding P-faithful assignment leads to ⪯Ψ◦µ, which is such that if ω |= ¬µ and ω′ |= ¬µ then neither ω ≺Ψ◦µ ω′ , nor ω′ ≺Ψ◦µ ω holds.

We illustrate this postulate by the following de�nition of the extension of qualitative possibilistic revision [Dubois and Prade, 1992].

De�nition 4 Let Ψ be an epistemic state such that its corresponding P-faithful assignment leads to ⪯Ψ. Let µ be a propositional formula, The revised epistemic state Ψ ◦π µ is de�ned by:

• if ω, ω′ ∈ Mod(µ) then ω ⪯Ψ◦πµ ω′ iff ω ⪯Ψ ω′ ,
• if ω, ω′ ̸∈ Mod(µ) then ω =Ψ◦πµ ω′ ,
• if ω ∈Mod(µ) and ω′ ̸∈Mod(µ) then ω ≺Ψ◦πµ ω′ .

Namely, ⪯Ψ and ⪯Ψ◦πµ are identical on subdomain Mod(µ) ×Mod(µ). Each models of µ are preferred to each counter-models of µ. And lastly, the counter-models of µ are considered equally preferred.

Example 2 Let us again consider the epistemic state Ψ represented by Figure 3. Let µ be a new information such that Mod(µ) = {ω1, ω3}. Then, the revision of Ψ by the new information µ is represented by the partial pre-order ⪯Ψ◦π described by �gure 5

ω0 =Ψ◦πµ ω2

According to this de�nition it can be checked that the revision operator ◦π provided by de�nition 4 satis�es the postulates (P1) - (P7), (C1), (C3) - (C4) and (Ccond).

The second postulate concerns relationships between models and counter-models of the new piece of information µ. The postulate (C3) only requires if some strict preference in ⪯Ψ holds, then this preference should also hold in ⪯Ψ◦µ. We hence propose a stronger version of (C3), called (Clex), and characterized by:

Note also that (Clex) implies (C1), by replacing β by the contradiction ⊥.

Theorem 6 A revision operator ◦ satis�es the postulates (P1) - (P7) and (Clex) iff its associated P-faithful assignments leading to ⪯Ψ and ⪯Ψ◦µ are such that

• if ω, ω′ |= µ then ω ≺Ψ ω′ iff ω ≺Ψ◦µ ω′ ,
• if ω |= µ and ω′ ̸|= µ then ω ≺Ψ◦µ ω′ .

Revision operator ◦ satisfying (Clex) constraints each models to be strictly preferred to all counter-models of the new piece of information µ. Moreover, it preservers the order between the models of µ. An example of revision operator satisfying (Clex) is the revision with memory proposed in [Papini, 2001] and hinted by Spohn [Spohn, 1988] (see also [Nayak, 1994; Konieczny and Pino P·erez, 2000]).

De�nition 5 Let Ψ be an epistemic state and µ be a propositional formula, the revised epistemic state Ψ◦▷µ corresponds to the following partial pre-order:

• if ω, ω′ ∈ Mod(µ) then ω ⪯Ψ◦▷µ ω′ iff ω ⪯Ψ ω′ ,
• if ω, ω′ ̸∈ Mod(µ) then ω ⪯Ψ◦▷µ ω′ iff ω ⪯Ψ ω′ ,
• if ω ∈Mod(µ) and ω′ ̸∈Mod(µ) then ω ≺Ψ◦▷µ ω′ .

Example 3 Let us again consider the epistemic state Ψ represented by Figure 3. Let µ be a new information such that µ = a. We have Mod(µ) = {ω1, ω3}. Then, the revision of Ψ by the new information µ is represented by the partial pre-order ⪯Ψ◦▷ described by �gure 6

6 Conclusion

This paper has �rst proposed a new de�nition of faithful assignment suitable for revising partially ordered information. We then propose a revised version of Katsuno and Mendelzon's postulates. A representation theorem has been proposed for any revision operator satisfying this new set of postulates.

The paper also proposed a characterization of Darwiche and Pearl's postulates and a characterization of Boutilier's postulate when information is partially ordered. Two new postulates with their representation theorem have been proposed for capturing two other forms of belief revision.

When dealing with partial pre-orders, we have shown that revision operators satisfying iterated revision postulates such C1 does not allow to guarantee that ⪯Ψ and ⪯Ψ◦µ to be identical on some subdomains (for instance on Mod(µ) × Mod(µ) if C1 is satis�ed). A future work will be to investigate additional postulates that preserve equality on some subdomains. For instance, it would be interesting to consider a stronger version of P2, by requiring equality between epistemic states instead of logical equivalence between belief sets.

Even if results of this paper are oriented belief revision, it can be interesting to discuss this work in the framework of updating [Katsuno and Mendelzon, 1992] (since updating has also questioned (R2), even if representation theorems are clearly different).

Another future work is to extend results to this paper to the revision of a partial pre-order by a partial pre-order and extends, for instance, postulate proposed in [Benferhat et al., 2000].