Revision Sequences and Nested Conditionals

1 Introduction

Subjunctive conditionals have recently attracted much attention in the knowledge representation community. It has been pointed out that counterfactuals may play a large role in planning and diagnostic systems {Ginsberg 1986), that subjunctives may be used to capture knowl­ edge base update and revision (Katsuno and Mendel­ zoo 1991; Boutilier 1992b), and that they are intimately related to the conditionals used in default reasoning (Boutilier 1992c; Makinson and Gardenfors 1990). We denote by A > B the subjunctive conditional "If A were the case then B would be true." Various subjunctive logics have been proposed to account for properties of the connective > (Stalnaker 1968; Lewis 1973).

From the point of view of knowledge representation, acceptance conditions for A > B are especially impor­ tant. Under what conditions should an agent assent to the conditional? A widely endorsed acceptance test for conditionals is the Ramsey test (Stalnaker 1968, p.44):

First add the antecedent (hypothetically) to your stock of beliefs; second make whatever ad­ justments are required to maintain consistency (without modifying the hypothetical belief in the antecedent); finally, consider whether or not the consequent is true.

The key step in the Ramsey test is the revision of the belief set. The notion of revision adopted will de­ termine which conditionals are accepted and rejected. Conversely, given a fixed (complete) set of accepted con­ ditionals, the revision function adopted by an agent will also be determined: revising by A is simply a matter of believing those B such that A > B is accepted. Con­ sequently, the study of revision and (subjunctive) con­ ditional logic are virtually the same if one accepts the Ramsey test.

The most prominent theory of belief revision is that put forth by Alchourr6n, Gardenfors and Makinson (1985) and expounded by Gardenfors (1988) . Within this framework many people have explored the con­ nection to conditionals (Gardenfors 1988; Gardenfors 1986; Rott 1989; Boutilier 1992b; Boutilier 1992c). The AGM theory, which we describe in the next section, im­ poses various constraints on acceptable revision func­ tions. Roughly, a revision function preserves as much information as possible. Unfortunately, the AGM theory has little to say about revision sequences. If we accept the Ramsey test as determining conditional beliefs, this means that the conditionals accepted in the new belief set need not be related to those in the first set. Thus, while information content is "preserved" with respect to objective beliefs, the information content of conditionals is ignored.

It is this problem of preserving conditionals under re­ vision that we investigate here. The semantic model of AGM revision (for propositional belief sets) we describe in the next section orders possible worlds according to their plausibility, or "degree of consistency" with a fixed belief set K. While this ordering guides the selection of a revised belief set K.A (which incorporates A into K), this AGM model fails to provide a new ordering suitable for the revision of KA. The goal of this paper is to show how one might use the original ordering to constrain the new ordering, hence revision of the revised belief set KA. We propose that the new ordering retain as much of the old ordering as possible, consistent with the AGM pos­ tulates. This minimal change in the ordering is precisely defined and provides the semantic basis for our model of revision sequences. This approach, dubbed natural revision, ensures that a maximal subset of one's con­ ditional beliefs is retained during the revision process. Of course, this is a specific instance of the more gen­ eral phenomenon of iterated revision captured by gen­ eral revision systems. However, we shall argue that our model provides a very natural way of extending the con­ cept of "minimal change," the hallmark of the AGM theory, to sequences of revisions and conditional beliefs. Indeed, natural revision provably retains the maximum amount of conditional information consistent with the constraints of the AGM theory. It also provides a logical characterization and computational methods such itera­ tion. Proofs of the main results can be found in the full version of the paper (Boutilier 1992d).

2 A Logic for Revision

In this section we very briefly describe the AGM theory of revision (Alchourr6n, Gardenfors and Makinson 1985; Gardenfors 1988) and the logic and semantic model for revision proposed by Boutilier (1992b ). For more details and motivation we refer to these works.

We take a belief set K to be a deductively closed set of sentences in the language LcPL of classical propo­ sitional logic. New beliefs must be added to this set when an agent learns new information. If this new sen­ tence A is consistent with K, then the new belief set K1 = Cn( K U {A}) seems appropriate. However, when­ ever K f- ...,A, certain beliefs must be given up before adding A to K . Alchourr6n, Gardenfors and Makinson (1985) have proposed that those sentences inK with the least information content be retracted. They propose a set of postulates (K*1 )-(K*8) that constrain the behav­ ior of logically acceptable revision functions. We use KA to denote revision of belief set K by A. Two of the key postulates are (K*3) and (K*4)

(K*3) KA ~ K1; (K*4) If...,A ¢ K then K1 ~ KA .

Together these ensure that KA = K1 whenever K ~ ...,A. This reflects the principle of informational economy in the extreme case: if no beliefs need to be given up to accommodate a new belief A, then none should. Postu­ lates (K*7) and (K*8) taken together ensure that this applies to revised belief sets as well:

If ...,n ¢ KA then (KA)~ ~ KAAB ·

In (Boutilier 1992b) we provide a modal semantics and logic for AGM revision based on an observation of Grove (1988) that equates the entrenchment or importance of beliefs with an ordering on possible worlds. The modal logic used, called CO*, is based on a standard proposi­ tional language augmented with two modal operators D and D. We denote by LB this bimodal language and bl LcPL its classical propositional sublangua.ge. A CO - model is a triple M = (W, R, I('}, where W is a set of worlds with valuation function I(' and R is an ordering ("accessibility") relation over W. We insist that R be transitive and connected. 1 Furthermore, every propo­ sitional valuation, or logically possible world, must be represented by some world in W. This ensures that a E LcPL is satisfied at some world if it is consistent. An axiomatization can be found in (Boutilier 1992b ). Space limitations preclude a discussion of the semantics of the primitive modal operators. The defined operators (be­ low) are more crucial here. The satisfaction of a E LcPL at a world in a model ( M l=w a) is defined in the usual way. llall refers to the set { w : M F=w a} and we define the set of minima/ a-worlds as min(M, a)=

The notion of cluster will play a large role in future developments. In any reflexive, transitive Kripke frame, a cluster is any maximal set of mutually accessible worlds (Segerberg 1970); C ~ W is a cluster just when wRv for all v, w E C and no extension C' :J C has this property. CO*-structures consist of a totally-ordered set of clusters of worlds (see Figure 1).

We can use CO*-models to represent the revision of a theory K (for a more detailed account we refer to (Boutilier 1992b )). The interpretation of R is as follows: wRv iff v is as at least as plausible a state of affairs as w given an agent's b.elief state K. As usual, vis more plau­ sible than w iff wRv but not vRw. If v is more plausible than w, loosely speaking v is "more consistent" with the belief set K than w.

We require that those worlds consistent with our belief set K should be exactly those minimal in R. That is, vRw for all v E W iff M F=w K. This condition ensures that no world is more plausible than any world consistent with K, and that all K -worlds are equally plausible. It is just the epistemically possible worlds (those consistent with K) that should be most plausible. Such models are called K -revision models and have as their minimal cluster the set IIKII. This constraint can be expressed in LB for any K that is finitely expressible as KB (Boutilier 1992b). This sentence is dubbed O(KB) and is intended to mean we "only know" KB.

Given this structure, we want the set of minimal A­ worlds to represent the state of affairs believed when K is revised by A, since these are the most plausible worlds, the ones we are most willing to adopt, given A. In Figure 1, we have a typical K-revision model: each cir­ cle represents a cluster of equally plausible worlds, with arrows indicating accessibility between clusters. The minimal cluster consists of all K -worlds, and we have K f- ...,A. The set of minimal A-worlds is indicated by the shaded region, and this set forms the set of "newly accepted" worlds when K is revised by A. Thus A > B should hold exactly when B is true at each world in the shaded region. 2 This connective is definable in LB

1 R is (totally) connected if wRv or vRw for any v, w E W (this implies reflexivity). This restriction is relaxed in (Boutilier 1992a).

2 0f course such a minimal set of A-worlds may not exist. The definition of the connective is valid in this case as well (Boutilier 1992b), but we ignore this circumstance here for simplicity (see Section 3).

(Boutilier 1992b) and its truth conditions reduce to

It is important to note the "global" nature of this con­ nective. If A > B holds at some world in W then it holds at all worlds. The truth of A > B at w does not depend on w, but on the set min(M, A).

For any A E LcPL the belief set resulting from revi­ sion of K by A, for a giv· ' model M, is

We can show that *M satisfies the AGM postulates for belief revision and any AGM revision operator has an equivalent formulation as such a *M (Boutilier 1992b ). Thus, we can use the logic CO* to represent the revision of a theory KB, and reason about such a revision, in a manner respecting the AGM postulates.

CO* is a reasonable epistemic logic, as well . We can define a belief modality Bin LB (Boutilier 1992c) reading B(A) as "A is believed." This sentence will hold just when A is true at each epistemically possible (minimal) world: M Fw B(A) iff min(M, T) ~ IIAII iff A E K . We note that B behaves according to the usual weak S5 interpretation of belief (Boutilier 1992c), and its truth conditions too are "global." For any CO*-model M, we can define the objective belief set (or simply the belief set) associated with it to be its propositional "beliefs":

Def. 1 The objective belief set associated with M is {n E LcPL: M F Bn}.

Naturally, the belief set for any K -revision model is just K. We will be more interested in "subjective beliefs" of a revision model, those beliefs involving certain modal operators (in particular, conditional beliefs).

Def. 2 The extended belief set associated with M is {n E LB: M F Bn}.

For any CO* ~model with belief set K and extended belief set E, we have K ~ E . While we have clear characteri­ zation of the revised belief set KA., it is less clear what form the revised extended set EA. should take.

3 Natural Revision

3.1 The Problem of Iterated Revision

We say a model is smooth iff, for all A E Lcp£, min(A, M) 'I 0. Grove (1988) shows that such mod­ els are adequate for the representation of AGM revision functions and this result can be applied to our CO* model of revision directly. In what follows we assume all CO* -models are smooth in this sense.

Suppose we have a revision model M suitable for be­ lief set K . When K is revised by A the status of an objective belief B in the new belief set KA. is easily de­ termined by inspection of M . B is in KA. just when B is true at all most plausible A-worlds in M. (If E 2 K is the corresponding extended belief set, this simply means A> BE E.) We can speak of KA. being represented by the set min(M, A) because KA. contains only objective beliefs, and corresponds to this set of worlds in a natu­ ral fashion.

It is less clear just what new subjective beliefs an agent accepts after revision by A. If min(M, A) is the set of worlds representing an agent's new belief set KA. , we might hope that it captures the new extended belief set EA,, as well . However, this view is untenable because of the nonextensional truth conditions for conditionals and belief sentences. Unlike an objective sentence, the truth of a conditional A > B or explicit belief sentence B(A) is not determined by a set of worlds. These can only be evaluated with respect to a complete model, or ordering of worlds, stating the relative plausibility of all worlds. This is due to the global nature of the connectives B and >. It should be clear that the original model M is not suitable for this purpose. A K-revision model is suitable for a fixed belief set only (indeed, a fixed extended belief set). It represents one ordering, hence one set of conditionals and one set of beliefs. If we used

as the new extended belief set , one could never give up conditionals or other subjective beliefs, though the ob­ jective component K can change drastically. When E is revised by A, the CO*-model used to represent E be­ comes inadequate. This model is an E-revision model and the representation of EA. requires (of course) an EA.­ revision model.

What are the natural requirements on this new model? When a propositional revision A is received, we want the revision function * to map model M into a new model MA. that captures the revised belief set EA.. Clearly, KA. is uniquely determined by M (in particular, by min(M, A)). Naturally, we insist that KA. ~ EA. and that KA. form the entire objective component of EA. . This simply means that M.A should be a KA,-revision model, or that KA. is only known in M.A (Boutilier 1992b; Levesque 1990). The minimal cluster of worlds in M.A should be exactly min(M, A) . This is illustrated in Fig­ ure 2. Let us dub this constraint the Basic Requirement on revision functions as applied to models.

The Basic Requirement: If M is a K-revision model then the KA. -revision model M.A must be such that min(M_A, T) = min(M,A).

In fact, from a purely logical perspective, this is prob­ ably all we want to say about M.A . If one changes an ob­ jective belief, it is impossible in general to predict what becomes of one's conditionals. This model of iterated re­ vision is captured by Giirdenfors's (1988) belief revision systems, although not in this semantic fashion. A severe drawback of such a general model is that just about all of the ordering information, capturing an agent's condi­ tional beliefs and judgements of entrenchment, is (po­ tentially) lost in this mapping (see Figure 2). There is something unsatisfying about this model. The ordering relation R is intended to reflect the informational con­ tent or importance of beliefs. When certain beliefs must be given up, it seems natural to try to keep not only im­ portant beliefs, but as much of the ordering a possible. A revision should not usually change one's opinion of the relative importance of most sentences.

3.2 The Semantics of Natural Revision

Instead of arbitrary mappings from M to M~, we will propose a class of natural mappings that preserve as much ordering information as can be expected. This determines the class of natural revision functions, that tend to preserve the entrenchment information and con­ ditional beliefs found in an extended belief set. It is important to note that the model we propose is not com­ pletely general, for it permits only a subset of those re­ vision functions (on extended sets) allowed by the ar­ bitrary mappings above. However, it is a very natural subset, suitable for determining the result of proposi­ tional revision sequences, or the truth of right-nested conditionals, when the general model has little to offer.

The conditionals accepted by an agent are determined by its ordering of plausibility. If we insist that revision preserve as much of this ordering as possible, then, for the most part, the relative entrenchment and plausibil­ ity of sentences (hence conditional beliefs) will remain intact. Let M = {W, R, V'} be the revision model reflect­ ing some extended belief set E. Given a propositional revision A of E (or the associated K), we must find a revision model M~ = {W, R', V'} such that R' reflects the minimal mutilation of R.

If wE min(M, A), by the Basic Requirement w must be minimal in R', and these must be the only minimal worlds in R'. For any such w the relationships wR'v and vR'w are completely determined by membership of v in min(M, A), independently of their relationship in R. Figure 2 illustrates this. For w, v not in min(M, A), this picture leaves wRv completely unspecified. If R is to be left intact to the largest possible extent then the most compelling specification is to insist that vR'w iff vRw.

This has the effect of leaving R unaltered except as in­ disputably required by the Basic Requirement. Such a move is illustrated in Figure 3. We dub such a map­ ping on revision models the natural revision operator, and now describe the revision function it induces on the associated belief and extended belief sets.

• Def. 3 Let M = {W, R, V'} be a revision model. The natural revision operator * maps M into M~, for any A E LcPL, where M~ = {W, R', !{)}, and: a) if v E min(M, A) then wR'v for all w E W and vR'w iff wE min(M, A); and b) if v, w ¢ min(M, A) then vR'w iff vRw.

Def. 4 Let E be the extended belief set associated with the revision model M. The natural revision function

associated with M is *· defined for all A E LcPL as: E_A ={BE LB: M~ I= B(B)} Let K ~ E be the objective part of E. The natural revision of K, K_A, is the restriction of E_A to LcPLi K_A ={BE LcPL: M~ I= B(B)}

Clearly, the natural revision function is simply the AGM operator determined by M, when restricted to K.

Proposition 1 Let M be a K -revision model. The AGM function *M and the natural revision function* de­ termined by M are identical {when restricted to LcPL)·

Notice that this extends the AGM model of revision. The revised extended set E_A is defined using the updated re­ vision model M~ and incorporates non-objective beliefs, such as conditionals and nested belief sentences. Had we simply defined E:A to be those sentences true in M at the minimal A-worlds, we would have run into the problem discussed in Section 2, namely the fact that a model M can only model a fixed set of beliefs and conditionals.

If we are to extend the Ramsey test to include nested conditionals, the truth conditions for statements A > {3 must be recast in this framework. ForM to satisfy A> {3, we must have f3 E E_A for the natural revision function *· For f3 E LcPL these truth conditions will be identical to those provided in Section 2. Thus, our new truth conditions for > based on the Ramsey test will form a "conservative extension" of the old definition. However, for arbitrary {3 E Ls, especially sentences like B > C, the meaning of > given in Section 2 is inadequate since it refers to truth at worlds in min(M, A). To evaluate A > (B > C) we must test B > C in M.A., not at min(M, A). The connective > must be introduced as primitive. The conditional language Lc is the extension of Ls with primitive connective >. We have, for A E LcPL and B E Lc,

Now we have a conditional connective whose truth con­ ditions are specified directly by the Ramsey test. While this certainly provides us with a new logic, (seemingly) requiring a new axiomatization, we will soon see that these truth conditions can, in fact, be captured in the bimodal language using only the original version of the connective > (defined in Ls).

Notice that the truth of A > B is unspecified for A ¢. LcPL· Natural revision functions are suitable only for sequences of propositional revisions. Only the right­ nesting of conditionals is meaningfully sanctioned in this framework, e.g., A > (B > C) where A, B, C E LcPL· A sentence (A> B) > C has an unspecified truth value for it asks if C is believed when a knowledge base is re­ vised to include A > B. This framework does not spec­ ify how to revise a knowledge base with non-objective sentences, though this problem is addressed within the natural framework in (Boutilier and Goldszmidt 1993).

3.3 Properties of Single Revisions

In this section, we examine the behavior of the natural revision model when a single propositional revision is effected. We assume throughout that we have a revision model M determining a belief set K and extended set E. Natural revision is intended to change as little of the ordering information R as possible; consequently, as many conditional beliefs as possible should be retained in the move from E to E.A. We now examine the structure of E_A and show that this is indeed the case. Since we are only interested in single revisions at this point, we restrict our attention to the simple conditionals in E.A, of the form B > C where B, C E LcPL· We note:

Proposition 2 Let M be a K -revision model where A E K. Then M.A.= M.

Updating by a sentence already in a belief set not only causes no change in the belief set K, as required by the AGM postulates, but also leaves the revision model M (and the extended set E) intact.

Suppose we revise a belief set K ~ E by A as specified by model M. We wish to determine the set of condition­ als B > C contained in the revised extended set E_A . We consider two cases, -.B ¢. K.A and -.B E K.A.

Consider the first situation where -.B ¢. K.A; that is, M I= -.(A > -.B). This means that there is some B­ world among the set min(M, A) of minimal A-worlds in M (the shaded region of Figure 3). Clearly then we have that min(M.A.,B) = min(M,AAB); so M.A. I= B > C iff M I= A A B > C. Therefore, whenever K.A ~ -.B, a conditional B > C is in E.A iff A A B > C is in E. Notice that the status of B > C in E has no bearing on its acceptance or rejection in E.A. This behavior is exactly in accordance with the AGM postulates (K*7) and (K*S). Any AGM revision function must ensure that subsequent (iterated) consistent revisions are treated in the same manner as uniterated consistent revisions (i.e., as expansions).

The second situation arises when -.B E K.A; that is, M I= A > -.B. When K (or E) is revised by A, -.B is in the resulting belief set. This is true exactly when noB-world is contained in min(M, A) (again, the shaded region). Now, M.A. I= B > C just in case the set min(M.A., B) contains only C-worlds. Since -.B E K_A, the set min( M.A., B) is not contained in the minimal clus­ ter of M.A. . However, all worlds outside the minimal clus­ ter stand in exactly the same relation as they do in M. Therefore min( M.A., B) = min(M, B) and it follows that M.A. I= B > C iff M I= B > C. For conditionals B > C whose antecedents are not made plausible by the accep­ tance of A (i.e., K.A ~-.B), B > Cis in E_A iff B > C is in E. Since nothing forces the conditional to be aban­ doned when A is accepted, it is retained. We can sum­ marize these considerations in the following theorem and equivalent corollaries.

Theorem 3 Let M be a revision model, let * be the nat­ ural revision operator and let A, B, C E LcPL· (a) If M.A. I= B-.B then M.A. I= B > C iff M I= B >C. (b) If M.A. ~ B-.B then M.A. I= B > C iff M I= A A B > C.

Corollary 4 (a) If K.A 1- -.B then C E (K.A)a iff C E Ka. (b) If K.A ~ -.B thence (K.A)a iff c e K.A"s·

Corollary 5 (a) If A> -.BEE then B > C E E_A iff B > C E E. (b) If A > -.B ¢. E then B > C E E_A iff AAB > CE E.

These results precisely characterize the conditionals that will be preserved in a revised extended belief set. Each shows that the sentences accepted in the new revi­ sion model or belief state can be determined by appeal to the original model or belief state. Theorem 3 shows that the conditional belief set captured by M.A can be determined by the conditional beliefs of M. Further­ more, it demonstrates that natural revision preserves as much conditional information in the revised belief set as is consistent with the AGM postulates. The condi­ tionals removed from E when constructing E_A are only those compelled by postulates (K*7) and (K*S). These are just those conditionals B > C whose antecedent B is consistent with K_A . This is reflected in clause b) of the theorem. However, as indicated by clause a), there­ maining set of conditionals (or negated conditionals) in E.A coincides precisely with the conditional information in the original extended set E. Thus, no AGM revi­ sion function could preserve more conditional informa­ tion than the natural revision function.

Corollary 4 shows that the sequence of two revisions applied to K can be reduced to a single revision, requir­ ing no iterated revision, and that the test to establish which condition holds also requires no iterated revision. Similarly, Corollary 5 shows that the revised extended belief set E.A and the nested conditionals in E are deter­ mined by the unnested conditionals in E. These prop­ erties play a vital role in our characterization of revision sequences in terms of single updates.

3.4 Revision Sequences

For any revision sequence A1, . . . An, let us say that revision A~: is compatible within the sequence if it con­ sistent with the result of previous revisions, i.e, if ...,Al: ¢. ((KA.JA., ···)A.._,. The sequence is compatible if each element A2 , ... An is compatible. In the previous sec­ tion we saw that a two-element sequence can be reduce to a single propositional revision: (KA.)8 = KA.,.B if B is compatible with A, and (KA.)8 = K'B if B is in­ compatible. This analysis can be extended to arbitrary sequences as well, allowing us to compute single revisions that characterize revision sequences:

De£. 5 Revision sequence A1, ... An is characterized by the sentence a iff ((Kt)A., ···)A. . = K; .

Due to space limitations, a detailed motivation and anal­ ysis of the following definitions and results cannot be provided. We refer to the full paper (Boutilier 1992d).

We first note that compatible sequences are reducible to single updates.

Theorem 6 If A1 , . .. An as compatible then ((K· )· · · ·)· = K· A1 A 2 A,. A1 A···A,. ·

We also note that a sequence is compatible iff Kt If ...,(A2 I\ ···An)· We should note, however, that while the objective seth ((K.A, )A., ···)A. .. Js thhe equh:­ alent to KA,A···A,. · t is is not true tor t e revi­ sion model ( ( M.A, )A., · · ·)A... or the extended belief set ((EA., )A., ···)A.,. . The revised model is constructed by first moving the set min(M, At) to the bottom of the model, then moving the set min(M.A , A2) to the bot­ tom and so on. Because the sequence ls compatible, the final minimal cluster is precisely min(M, A1 I\ ··· An) as it would be in the model MA,A···A,. . However, in the model ((M.A, )A., ···)A.,. each revision has left a "resid­ ual trace" on the model (Boutilier 1992d) with as many as n new clusters added to M, whereas MA,A···A,. has only one new cluster. This complicates somewhat our analysis of incompatible revisions.

Suppose that an incompatible revision An+l is added to this sequence. Since ...,An+l E ((M.AJA., ···)A. . , the set min(((M.A)A., ···)A.,., An+l) does not lie within the minimal cluster of ((M.A )A. ···)A. . Furthermore, for any k < n, if the seq~en~e A1,: . . A~:, An+l is not compatible, then no An+l-worlds can lie in the cluster formed when revision by A~: took place (nor for any A; , j > k) . However, if A1, ... A~:, An+l is compatible, some An+l-world must lie within the cluster of A1 I\ · ··A~:­ worlds representing KA,A···A·.

For any revision A; in the sequence A1, ... An, its most recent compatible revision is defined as the A~:, k < j, such that

This is the most recent revision (before A;) in the se­ quence that did not force rejection of A;. If A; is com­ patible in the sequence, then clearly A;-1 is its most recent compatible revision. If the set above is empty, we say A; has no such compatible revision.

Theorem 7 Let A1 , .. . An be a revi6ion sequence with one incompatible update An. Then ((KA.JA., ···)A. .. =

KtA···A~cAA,. where A~: is the most recent compati­ ble update for An. If there is no such A~: then ((K.AJA., ···)A. .. = K_A,..

Thus, we need only look back to find the most recent revision that allows the "possibility" of An and conjoin An to its characterizing sentence. Putting together The­ orems 6 and 7 with the obvious inductive argument on the number of incompatible updates, we obtain the main result of this section.

Theorem 8 For any revision sequence At, .. . An, there is some subset S ~ { A1, · · ·,An} such that ((K_AJA., ···)A. .. = K_A and A= 1\S.

Corollary 9 For any revision sequence A1, . . . An, there is some subset of these updates S ~ {At;···, An} such that ((EA.,)A., ···)A.,._, F An > B iff E FA > B, and A= 1\S.

This result is given its constructive character by The­ orem 6, but it seems to suggest that one must keep track of a characterizing sentence s(A;) for each subsequence A1, . . . A;. In fact, the critical sentences are only those corresponding to incompatible revisions in the sequence. Every other characterizing sentence s(A;) is simply the conjunction of subsequent revisions to the most recent incompatible revision (Boutilier 1992d). Taken together, these theorems show that one may implement a pro­ cedure that tests for membership of B in a multiply­ revised belief set ((K.A}A, ···)A.,. using only an "oracle" that answers requests of the form "Is f3 E K; ?" for a, f3 E LcPL· Furthermore, the characterizing sentences s(A;) that need to be recorded are only those captur­ ing some incompatible revision (see the full paper for this algorithm). In essence, iterated revision can be ac­ complished virtually, without having to construct the se­ quence of new belief sets, and without having to change the ordering of entrenchment or plausibility associated with K. One need only find the appropriate character­ istic sentence, and test a simple conditional belief with that antecedent.

4 Concluding Remarks

We have presented a model for belief revision that ex­ tends the AGM theory in a manner that accounts for iterated revision. The natural revision model preserves the maximal amount of conditional information, and has the property that the result of any revision sequence can be calculated using only the AGM revision function on the original belief set K . This reduction is bears some resemblance to suggestions in the literature equating a nested conditional A> (B >C) with AI\B > C (Adams 1975; Levi 1988). If A and B are compatible this is pre­ cisely the behavior of natural revision. If A and B are incompatible, our model behaves differently, allowing a sentence like A > (...,A > C) to have meaningful truth conditions. But it also extends this idea to "defeasibly," not just logically, incompatible sentences.

Another important property of natural revision, re­ flecting its commitment to information preservation is the following (see (Boutilier 1992d)):

Theorem 10 Let M be a K -revi&ion model and A1, ... An a revi&ion &eq·ence. If i $ j then ((KA1)A~ · · ·)Aj <1. ((KA1)A~ ···)A;·

Thus, a revision sequence A1 , ... An causes a non­ decreasing change in "information" in a belief state. No belief set further along in the revision sequence can be smaller than an earlier belief set. This suggests that, as we process a revision sequence, our revision model be­ comes more and more informationally complete. Given "enough" revisions, a model approaches the point where each cluster becomes a single world (since clusters are only broken apart by revision, not put together): then K and KA become complete theories.

We need not have complete information to reason about natural revision. From a set of premises we can reason in CO* about "constraints" on natural revision, without perhaps determining complete theories. How­ ever, there are methods of "completing" an incomplete set of conditionals, for instance, Pearl's (1990) System z. In (Boutilier 1991) we show how such a completion can be expressed compactly in CO*. In the full paper, we show that if a revision model has a finite number of clusters each corresponding to a propositional theory (as in System Z), then only propositional (sometimes tractable) inference is required to compute natural revi­ sion.

Extensions of this work we are currently exploring in­ clude the application of this model to more quantitative types of conditionals (e.g., probabilistic degrees of belief and the J-conditionalization of (Goldszmidt and Pearl 1992)). We are also looking at applications to diagnosis, where a stream of observations must be reconciled with expected knowledge. Simply conjoining observations is not feasible if they conflict. Planning also requires a no­ tion of revision as an agent must change its beliefs in response to new information, and changes in the world, requiring that we account for belief update (Winslett 1988; Katsuno and Mendelzon 1991). Finally, arbitrary nesting is explored in {Boutilier and Goldszmidt 1993), where we extend natural revision to include new condi­ tional information, how one can·revise an extended belief set to include new conditional information A > B.

Acknowledgements

Thanks to Veronica Becher, Moises Goldszmidt and Mirek Truszczynski for discussing these ideas with me. This research was supported by NSERC Research Grant OGP0121843.