Abstract:
The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper (Friedman & Halpern, 1997), we introduce a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the change of beliefs over time. In this paper, we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method, and to better understand the principles underlying them. In particular, it shows that Katsuno and Mendelzon's notion of belief update (Katsuno & Mendelzon, 1991a) depends on several strong assumptions that may limit its applicability in artificial intelligence. Finally, our analysis allow us to identify a notion of minimal change that underlies a broad range of belief change operations including revision and update.

---

Extracted Text

Journal of Artificial Intelligence Research 10 (1999) 117-167 Submitted 2/98;
published 3/99

Modeling Belief in Dynamic Systems

Part II: Revision and Update

Nir Friedman nir@cs.huji.ac.il Institute of Computer Science Hebrew University,
Jerusalem, 91904, ISRAEL http://www.cs.huji.ac.il/,nir

Joseph Y. Halpern halpern@cs.cornell.edu Computer Science Department Cornell
University, Ithaca, NY 14853 http://www.cs.cornell.edu/home/halpern

Abstract The study of belief change has been an active area in philosophy
and AI. In recent years two special cases of belief change, belief revision
and belief update, have been studied in detail. In a companion paper (Friedman
& Halpern, 1997), we introduce a new framework to model belief change. This
framework combines temporal and epistemic modalities with a notion of plausibility,
allowing us to examine the change of beliefs over time. In this paper, we
show how belief revision and belief update can be captured in our framework.
This allows us to compare the assumptions made by each method, and to better
understand the principles underlying them. In particular, it shows that Katsuno
and Mendelzon's notion of belief update (Katsuno & Mendelzon, 1991a) depends
on several strong assumptions that may limit its applicability in artificial
intelligence. Finally, our analysis allow us to identify a notion of minimal
change that underlies a broad range of belief change operations including
revision and update.

1. Introduction The study of belief change has been an active area in philosophy
and artificial intelligence. The focus of this research is to understand
how an agent should change her beliefs as a result of getting new information.
Two instances of this general phenomenon have been studied in detail. Belief
revision (Alchourr'on, G"ardenfors, & Makinson, 1985; G"ardenfors, 1988)
focuses on how an agent should change her (set of) beliefs when she adopts
a particular new belief. Belief update (Katsuno & Mendelzon, 1991a), on the
other hand, focuses on how an agent should change her beliefs when she realizes
that the world has changed. Both approaches attempt to capture the intuition
that an agent should make minimal changes in her beliefs in order to accommodate
the new belief. The difference is that belief revision attempts to decide
what beliefs should be discarded to accommodate a new belief, while belief
update attempts to decide what changes in the world led to the new observation.1

1. Throughout the paper we use "revision" to refer to AGM's proposal for
revision (Alchourr'on et al., 1985)

not as a generic term for the general approach initiated by AGM; similarly,
we use "update" to refer to KM's proposal for update (Katsuno & Mendelzon,
1991a).

cfl1999 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Friedman & Halpern Belief revision and belief update are two of many possible
ways of modeling belief change. In (Friedman & Halpern, 1997), we introduce
a general framework for modeling belief change. We start with the framework
for analyzing knowledge in multi-agent systems, introduced in (Halpern &
Fagin, 1989), and add to it a measure of plausibility at each situation.
We then define belief as truth in the most plausible situations. The resulting
framework is very expressive; it captures both time and knowledge as well
as beliefs. Having time allows us to reason in the framework about changes
in the beliefs of the agent. It also allows us to relate the beliefs of the
agent about the future with her actual beliefs in the future. Knowledge captures
in a precise sense the non-defeasible information the agent has about the
world, while belief captures the defeasible assumptions implied by her plausibility
assessment. The framework allows us to represent a broad spectrum of notions
of belief change. In this paper, we focus on how, in particular, belief revision
and update can be represented.

We are certainly not the first to provide semantic models for belief revision
and update. For example, (Alchourr'on et al., 1985; Grove, 1988; G"ardenfors
& Makinson, 1988; Rott, 1991; Boutilier, 1992; de Rijke, 1992) deal with
revision, and (Katsuno & Mendelzon, 1991a; del Val & Shoham, 1992) deal with
update. In fact, there are several works in the literature that capture both
using the same machinery (Katsuno & Satoh, 1991; Goldszmidt & Pearl, 1996;
Boutilier, 1998), and others that simulate belief revision using belief update
(Grahne, Mendelzon, & Rieter, 1992; del Val & Shoham, 1994). Our approach
is different from most in that we do not construct a specific framework to
capture one or both of these belief change paradigms. Instead, we start from
a natural framework to model how an agent's knowledge changes over time and
add to it machinery that captures a defeasible notion of belief.

We believe that our representation offers a number of advantages, and gives
a deeper understanding of both revision and update. For one thing, we show
that both revision and update can be viewed as proceeding by conditioning
on initial prior plausibilities. Thus, our representation emphasizes the
role of conditioning as a way of understanding minimal change. Moreover,
it shows that that the major differences between revision and update can
be understood as corresponding to differences in initial beliefs. For example,
revision places full belief on the assumption that the propositions used
to describe the world are static, and do not change their truth value over
time. By way of contrast, update allows for the possibility that propositions
change their truth value over time. However, the family of prior plausibilities
that we use to capture update in our framework have the property that they
prefer sequences of events where abnormal events occur as late as possible.
Because of this property, conditioning in update always "explains" observations
by recent changes. The fact that time appears explicitly in our framework
allows us to make these issues precise.

In the literature, revision has been viewed as dealing with static worlds
(although an agent's beliefs may change, the underlying world about which
the agent is reasoning does not) while update has been viewed as dealing
with dynamic worlds (see, for example, (Katsuno & Mendelzon, 1991a)). We
believe that the distinction between static and dynamic worlds is somewhat
misleading. In fact, what is important for revision is not that the world
is static, but that the propositions used to describe the world are static.
For example, "At time 0 the block is on the table" is a static proposition,
while "The block is on the table" is not, since it implicitly references
the current state of affairs. (Note that the assumption that

118

Modeling Belief in Dynamic Systems. Part II. the propositions are static
is not unique to belief revision. Bayesian updating, for example, makes similar
assumptions.) Because we model time explicitly in our framework, we can examine
this issue in more detail. In fact, in Section 7, we show how we relate these
two viewpoints. More precisely, given a system, we replace each proposition
p used in the system by a family of propositions "p is true at time m", one
for each time m. The resulting system describes exactly the same process
as the original system, but from a different linguistic perspective. As we
show, if the original system corresponds to KM update, then the resulting
system is very close to satisfying the requirements of AGM revision. The
only requirement that is not met is that the prior is totally ordered, or
ranked. This requirement, however, has been relaxed in several variants of
revision (Katsuno & Mendelzon, 1991b; Rott, 1992). Thus, a large part of
the difference between revision and update can be understood as a difference
in the language used to describe what is happening.

The generality of our framework forces us to be clear about the assumptions
we make in the process of capturing revision and update. As a consequence,
we have to deal with issues that have been largely ignored by previous semantic
accounts. One of these issues is the status of observations. As we show below,
to capture either revision or update, we have to assume that observations
are minimally informative--the only information carried by an observation
of ' is that ' should be believed. This is a strong assumption, since most
observations carry additional information. For example, when trekking in
Nepal, one does not expect to observe the weather in Boston. If an agent
observes that it is in fact raining in Boston, then this "observation" might
well provide extra information about the world (for example, that cable television
is available in Nepal). We remark that in (Boutilier, Friedman, & Halpern,
1998) there is a treatment of revision in our framework where observations
are allowed to convey additional information.

Finally, our representation makes it clear how the intuitions of revision
and update can be applied in settings where the postulates used to describe
them are not sound. For example, we consider situations where they may be
irreversible changes (such as death, or breaking a glass vase), and where
the agent may perform actions beyond just making observations. Revision and
update, as they stand, cannot handle such situations. As we show, our framework
allows us to extend them in a natural way so they do.

The rest of the paper is organized as follows. In Section 2, we give an overview
of the framework we introduced in (Friedman & Halpern, 1997). In Section
3, we give a brief review of belief revision and belief update. In Section
4, we define a specific class of structures that embody assumptions that
are common to both update and revision. In Section 5, we describe additional
assumptions that are required to capture revision. In Section 6, we describe
the assumptions that are required to capture update. In Section 7, we reexamine
the differences and similarities between belief revision and update. In Section
8, we consider possible extensions to the setup of revision and update, and
discuss how these extensions can be handled in our framework. Finally, in
Section 9, we conclude with a discussion of related and future work.

119

Friedman & Halpern 2. The Framework We now review the framework of Halpern
and Fagin (1989) for modeling knowledge, and our extension of it for dealing
with belief change. The reader is encouraged to consult (Fagin, Halpern,
Moses, & Vardi, 1995) for further details and motivation.

2.1 Modeling Knowledge The framework of Halpern and Fagin was developed to
model knowledge in distributed (i.e., multi-agent) systems (Halpern & Fagin,
1989; Fagin et al., 1995). In this paper, we restrict our attention to the
single agent case. The key assumption in this framework is that we can characterize
the system by describing it in terms of a state that changes over time. Formally,
we assume that at each point in time, the agent is in one of a possibly infinite
set of (local) states. At this point, we do not put any further structure
on these states (although, as we shall see from our examples, when we model
situations in a natural way, states typically do have a great deal of meaningful
structure). Intuitively, this local state encodes the information the agent
has observed thus far. There is also an environment, whose state encodes
relevant aspects of the system that are not part of the agent's local state.

A global state is a pair (se; sa) consisting of the environment state se
and the local state sa of the agent. A run of the system is a function from
time (which, for ease of exposition, we assume ranges over the natural numbers)
to global states. Thus, if r is a run, then r(0); r(1); : : : is a sequence
of global states that, roughly speaking, is a complete description of what
happens over time in one possible execution of the system. Given a run r,
we can define two functions re and ra that map from time to states of the
environment and the agent, respectively, by taking re(m) to be the state
of the environment in the global state r(m) and ra(m) to be the agent's local
state in r(m). We can thus identify run r with the pair of functions hre;
rai. We take a system to consist of a set of runs. Intuitively, these runs
describe all the possible behaviors of the system, that is, all the possible
sequences of events that could occur in the system over time.

Given a system R, we refer to a pair (r; m) consisting of a run r 2 R and
a time m as a point. We say two points (r; m) and (r0; m0) are indistinguishable
to the agent, and write (r; m) ,a (r0; m0), if ra(m) = r0a(m0), i.e., if
the agent has the same local state at both points. Finally, an interpreted
system I is a tuple (R; ss) consisting of a system R together with a mapping
ss that associates with each point a truth assignment to a set Phi  of primitive
propositions. In an interpreted system we can talk about an agent's knowledge:
the agent knows ' at a point (r; m) if ' holds in all points (r0; m0) such
that (r; m) ,a (r0; m0). Intuitively, an agent knows ' at (r; m) if ' is
implied by the information in the local state ra(m). We give formal semantics
for a language of knowledge (and time and plausibility) in Section 2.3.

Example 2.1: The circuit diagnosis problem has been well studied in the literature
(see (Davis & Hamscher, 1988) for an overview). Consider a circuit that contains
n logical components c1; : : : ; cn and k lines l1; : : : ; lk. The agent
can set the values on the input lines of the circuit and observe the values
on the output lines. The agent then compares the actual output values to
the expected output values and attempts to locate faulty components.

120

Modeling Belief in Dynamic Systems. Part II. Since a single test is usually
insufficient to locate the problem, the agent might perform a sequence of
such tests.

We want to model diagnosis using an interpreted system. To do so, we need
to describe the agent's local state, the state of the environment, and some
appropriate propositions for reasoning about diagnosis. Intuitively, the
agent's state is the sequence of input-output relations observed, while the
environment's state describes the current state of the circuit. This consists
of the failure set, that is, the set of faulty components of the circuit
and the values on all the lines in the circuit. Each run describes the results
of a specific series of tests the agent performs and the results she observes.
We make two additional assumptions: (1) the agent does not forget what tests
were performed and their results, and (2) the faults are persistent and do
not change over time.

To make this precise, we define the environment state at a point (r; m) to
consist of the failure set at (r; m), which we denote fault(r; m), as well
as the values of all the lines in the circuit. We require that the environment
state be consistent with the description of the circuit. Thus, for example,
if c1 is an AND gate with input lines l1 and l2 and output line l3, then
if re(m) says that c1 is not faulty, then we require that there is a 1 on
l3 if and only if there is a 1 on both l1 and l2.2 We capture the assumption
that faults are persistent by requiring that fault(r; m) = fault(r; 0). For
our later results, it is useful to describe the agent's observations using
our logical language. Consider the set Phi diag = ff1; : : : ; fn; h1; :
: : ; hkg of primitive propositions, where fi denotes that component i is
faulty and hi denotes that there is a 1 on line i (that is, line i in a "high"
state). An observation is a conjunction of literals of the form hi and :hi.
The agent's state at time m is a sequence of m such observations. Formally,
we define the agent's state ra(m) to be ho1; : : : ; omi, where, intuitively,
ok is the formula describing the input-output relation observed at time k.
We use the notation io(r; k) to denote the formula describing the observation
made by the agent at the point (r; k). Given this language, we can define
the interpretation ssdiag in the obvious way. We say that an observation
o is consistent with an environment state re(m) if the states of the input/output
lines in re(m) agree with these in o. The system Rdiag consists of all runs
r satisfying these requirements in which io(r; m) is consistent with re(m)
for all times m.

Given the system (Rdiag; ssdiag), we can examine the agent's knowledge after
making a sequence of observations o1; : : : ; om. It is easy to see that
the agent knows that the fault set must be one with which all the observations
are consistent. However, the agent cannot rule out any of these fault sets.
Thus, even if all the observations are consistent with the circuit being
fault-free, the agent does not know that the circuit is fault-free, since
there might be a fault that manifests itself only in configurations that
have not yet been tested. Of course, the agent might strongly believe that
the circuit is fault-free, but we cannot (yet) express this fact in our formalism.
The next section rectifies this problem. ut

2. Note that this means that we can recover the behavior of the circuit (although
not necessarily its exact

description) by simply looking at the environment state at a point where
there are no failures. Of course, if we could have a yet richer environment
state that encodes the actual description of the circuit, but this is unnecessary
for the analysis we do here.

121

Friedman & Halpern 2.2 Plausibility Measures Most non-probabilistic approaches
to belief change require (explicitly or implicitly) that the agent has some
ordering over possible alternatives. For example, the agent might have a
preference ordering over possible worlds (Boutilier, 1994b; Grove, 1988;
Katsuno & Mendelzon, 1991b) or an entrenchment ordering over formulas (G"ardenfors
& Makinson, 1988). This ordering dictates how the agent's beliefs change.
For example, in (Grove, 1988), the new beliefs are characterized by the most
preferred worlds that are consistent with the new observation, while in (G"ardenfors
& Makinson, 1988), beliefs are discarded according to their degree of entrenchment
until it is consistent to add the new observation to the resulting set of
beliefs. We represent this ordering using plausibility measures, which were
introduced in (Friedman & Halpern, 1995, 1998b). We briefly review the relevant
definitions and results here.

Recall that a probability space is a tuple (W; F ; Pr), where W is a set
of worlds, F is an algebra of measurable subsets of W (that is, a set of
subsets closed under union and complementation to which we assign probability),
and Pr is a probability measure, that is, a function mapping each set in
F to a number in [0; 1] satisfying the well-known probability axioms (Pr(;)
= 0, Pr(W ) = 1, and Pr(A [ B) = Pr(A) + Pr(B), if A and B are disjoint).

Plausibility spaces are a direct generalization of probability spaces. We
simply replace the probability measure Pr by a plausibility measure Pl, which,
rather than mapping sets in F to numbers in [0; 1], maps them to elements
in some arbitrary partially ordered set. We read Pl(A) as "the plausibility
of set A". If Pl(A) ^ Pl(B), then B is at least as plausible as A. Formally,
a plausibility space is a tuple S = (W; F ; Pl), where W is a set of worlds,
F is an algebra of subsets of W , and Pl maps sets in F to some domain D
of plausibility values partially ordered by a relation ^D (so that ^D is
reflexive, transitive, and anti-symmetric). We assume that D is pointed :
that is, it contains two special elements ?D, and ?D such that ?D^D d ^D
?D for all d 2 D; we further assume that Pl(W ) = ?D and Pl(;) =?D. As usual,
we define the ordering !D by taking d1 !D d2 if d1 ^D d2 and d1 6= d2. We
omit the subscript D from ^D, !D, ?D, and ?D whenever it is clear from context.

Since we want a set to be at least as plausible as any of its subsets, we
require

A1 If A ` B, then Pl(A) ^ Pl(B). Some brief remarks on this definition: We
have deliberately suppressed the domain D from the tuple S, since for the
purposes of this paper, only the ordering induced by ^ on the subsets in
F is relevant. The algebra F also does not play a significant role in this
paper. Unless we say otherwise, we assume F contains all subsets of interest
and suppress mention of F , denoting a plausibility space as a pair (W; Pl).

Clearly plausibility spaces generalize probability spaces. In (Friedman &
Halpern, 1998b, 1995) we show that they also generalize belief function (Shafer,
1976), fuzzy measures (Wang & Klir, 1992), possibility measures (Dubois &
Prade, 1990), ordinal ranking (or ^-ranking) (Goldszmidt & Pearl, 1996; Spohn,
1988), preference orderings (Kraus, Lehmann, & Magidor, 1990; Shoham, 1987),
and parameterized probability distributions (Goldszmidt, Morris, & Pearl,
1993) that are used as a basis for Pearl's ffl-semantics for defaults (Pearl,
1989).

Our goal is to describe the agent's beliefs in terms of plausibility. To
do this, we describe how to evaluate statements of the form B' given a plausibility
space. In fact, we use a richer logical language that also allows us to describe
how the agent compares different

122

Modeling Belief in Dynamic Systems. Part II. alternatives. This is the logic
of conditionals. Conditionals are statements of the form '!, read "given
',  is plausible" or "given ', then by default ". The syntax of the logic
of conditionals is simple: we start with primitive propositions and close
off under conjunction, negation and the modal operator !. The resulting language
is denoted LC .

A plausibility structure is a tuple PL = (W;Pl; ss), where W is a set of
possible worlds, Pl is a plausibility measure on W , and ss(w) is a truth
assignment to primitive propositions. Given a plausibility structure PL =
(W;Pl; ss), we define [[']]PL = fw 2 W : ss(w) j= 'g to be the set of worlds
that satisfy '. We omit the subscript PL, when it is clear from the context.
Conditionals are evaluated according to a rule that is essentially the same
as the one used by Dubois and Prade (1991) to evaluate conditionals using
possibility measures:

ffl PL j= '! if either Pl([[']]) =? or Pl([[' ^ ]]) ? Pl([[' ^ :]]). Intuitively,
'! holds vacuously if ' is impossible; otherwise, it holds if ' ^  is more
plausible than ' ^ :. As we show in (Friedman & Halpern, 1998b), this semantics
of conditionals also generalizes the semantics of conditionals in ^-ranking
(Goldszmidt & Pearl, 1996), and PPD structures (Goldszmidt et al., 1993).
As we also show in (Friedman & Halpern, 1998b), this semantics for conditionals
generalizes the semantics of preferential structures. As this relationship
plays a role in the discussion below, we review the necessary definitions
here. A preferential structure is a tuple (W; OE; ss), where OE is a partial
order on W . Roughly speaking, w OE w0 holds if w is preferred to w0.3 The
intuition (Shoham, 1987) is that a preferential structure satisfies a conditional
'! if all the most preferred worlds (i.e., the minimal worlds according to
OE) in [[']] satisfy . However, there may be no minimal worlds in [[']].
This can happen if [[']] contains an infinite descending sequence : : : OE
w2 OE w1. What do we do in these structures? There are a number of options:
the first is to assume that, for each formula ', there are minimal worlds
in [[']]; this is the assumption actually made in (Kraus et al., 1990), where
it is called the smoothness assumption. A yet more general definition--one
that works even if OE is not smooth--is given in (Lewis, 1973; Boutilier,
1994a). Roughly speaking, '! is true if, from a certain point on, whenever
' is true, so is . More formally,

(W; OE; ss) satisfies '!, if for every world w1 2 [[']], there is a world
w2 such that (a) w2 _ w1 (so that w2 is at least as normal as w1), (b) w2
2 [[' ^ ]], and (c) for all worlds w3 OE w2, we have w3 2 [[' ) ]] (so any
world more normal than w2 that satisfies ' also satisfies ).

It is easy to verify that this definition is equivalent to the earlier one
if OE is smooth.

Proposition 2.2 : (Friedman & Halpern, 1998b) If OE is a preference ordering
on W , then there is a plausibility measure PlOE on W such that (W; OE; ss)
j= '! if and only if (W; PlOE; ss) j= '!.

We briefly describe the construction of PlOE here, since we use it in the
sequel. Given a preference order OE on W , let D0 be the domain of plausibility
values consisting of one

3. We follow the standard notation for preference here (Kraus et al., 1990),
which uses the (perhaps confusing) convention of placing the more likely
(or less abnormal) world on the left of the OE operator. Unfortunately, when
translated to plausibility, this will mean w OE w0 holds iff Pl(fwg ? Pl(fw0g).

123

Friedman & Halpern element dw for every element w 2 W . We define a partial
order on D0 using OE: dv ! dw if w OE v. (Recall that w OE w0 denotes that
w is preferred to w0.) We then take D to be the smallest set containing D0
that is closed under least upper bounds (so that every set of elements in
D has a least upper bound in D). For a subset A of W , we can then define
PlOE(A) to be the least upper bound of fdw : w 2 Ag. Since D is closed under
least upper bounds, Pl(A) is well defined. As we show in (Friedman & Halpern,
1998b), this choice of PlOE satisfies Proposition 2.2.

The results of (Friedman & Halpern, 1998b) show that this semantics for conditionals
generalizes previous semantics for conditionals. Does this semantics capture
our intuitions about conditionals? In the AI literature, there has been little
consensus on the "right" properties for defaults (which are essentially conditionals).
However, there has been some consensus on a reasonable "core" of inference
rules for default reasoning. This core is usually known as the KLM properties
(Kraus et al., 1990), and includes such properties as

AND From '!1 and '!2 infer '!1 ^ 2

OR From '1! and '2! infer '1 . '2! What constraints on plausibility spaces
gives us the KLM properties? Consider the following two conditions:

A2 If A, B, and C are pairwise disjoint sets, Pl(A[B) ? Pl(C), and Pl(A[C)
? Pl(B), then Pl(A) ? Pl(B [ C).

A3 If Pl(A) = Pl(B) =?, then Pl(A [ B) =?. A plausibility space (W; Pl) is
qualitative if it satisfies A2 and A3. A plausibility structure (W; Pl; ss)
is qualitative if (W; Pl) is a qualitative plausibility space. In (Friedman
& Halpern, 1998b), we show that, in a very general sense, qualitative plausibility
structures capture default reasoning. More precisely, we show that the KLM
properties are sound with respect to a class of plausibility structures if
and only if the class consists of qualitative plausibility structures. (We
also provide a weak condition that we show is necessary and sufficient for
the KLM properties to be complete.) These results show that plausibility
structures provide a unifying framework for the characterization of default
entailment in these different logics.

2.3 Plausibility and Knowledge In (Friedman & Halpern, 1997) we show how
plausibility measures can be incorporated into the multi-agent system framework
of (Halpern & Fagin, 1989). This allows us to describe the agent's assessment
of the possible states the system is in at each point in time. At the same
time we also introduce conditionals into the logical language in order to
reason about these plausibility assessments. We now review the relevant details.

An (interpreted) plausibility system is a tuple (R; ss; P) where, as before,
R is a set of runs and ss maps each point to a truth assignment, and where
P is a plausibility assignment function mapping each point (r; m) to a qualitative
plausibility space P(r; m) = (W(r;m); Pl(r;m)). Intuitively, the plausibility
space P(r; m) describes the relative plausibility of events from the point
of view of the agent at (r; m). In this paper, we restrict our attention
to plausibility spaces that satisfy two additional assumptions:

124

Modeling Belief in Dynamic Systems. Part II. ffl W(r;m) = f(r0; m0)j(r; m)
,a (r0; m0)g. Thus, the agent considers plausible only situations that are
possible according to her knowledge.

ffl if (r; m) ,a (r0; m0) then P(r; m) = P(r0; m0). This means that the plausibility
space

is a function of the agent's local state.4

We define a logical language to reason about interpreted systems. The syntax
of the logic is simple; we start with primitive propositions and close off
under conjunction, negation, the K modal operator (K' says that the agent
knows '), the fl modal operator (fl' says that ' is true at the next time
step), and the ! modal operator. The resulting language is denoted LKPT.5
We recursively assign truth values to formulas in LKPT at a point (r; m)
in a plausibility system I. The truth of primitive propositions is determined
by ss, so that

(I; r; m) j= p if ss(r; m)(p) = true. Conjunction and negation are treated
in the standard way, as is knowledge: The agent knows ' at (r; m) if ' holds
at all points that she cannot distinguish from (r; m). Thus,

(I; r; m) j= K' if (I; r0; m0) j= ' for all (r0; m0) ,a (r; m). fl' is true
at (r; m) if ' is true at (r; m + 1). Thus,

(I; r; m) j= fl' if (I; r; m + 1) j= '. Finally, we define the conditional
operator ! to describe the agent's plausibility assessment at the current
time. Let [[']](r;m) = f(r0; m0) 2 W(r;m) : (I; r; m) j= 'g.

(I; r; m) j= '! if either Pl(r;m)([[']](r;m)) = ? or Pl(r;m)([[' ^ ]](r;m))
? Pl(r;m)([[' ^ :]](r;m)).

We now define a notion of belief. Intuitively, the agent believes ' if '
is more plausible than not. Formally, we define B' , (true!').

In (Friedman & Halpern, 1997) we prove that, in this framework, knowledge
is an S5 operator, the conditional operator ! satisfies the usual axioms
of conditional logic (Burgess, 1981), and fl satisfies the usual properties
of temporal logic (Manna & Pnueli, 1992). In addition, these properties imply
that belief is a K45 operator, and the interactions between knowledge and
belief are captured by the axioms K' ) B' and B' ) KB'.

Example 2.3: (Friedman & Halpern, 1997) We add a plausibility measure to
the system defined in Example 2.1. We define Idiag = (Rdiag; ssdiag; Pdiag),
where Pdiag is the plausibility assignment we now describe. We assume that
failures of individual components are independent of one another. If we also
assume that the likelihood of each component failing is the same, and also
that this likelihood is small (i.e., failures are exceptional), then we can
construct a plausibility measure as follows. If (r0; m) and (r00; m) are
two points in W(r;m), we say that (r0; m) is more plausible than (r00; m)
if jfault(r0; m)j ! jfault(r00; m)j,

4. The framework presented in (Friedman & Halpern, 1997) is more general
than this, dealing with multiple

agents and allowing the agent to consider several plausibility spaces in
each local state. The simplified version we present here suffices to capture
belief revision and update. 5. It is easy to add other temporal modalities
such as until, eventually, since, etc. These do not play a role

in this paper.

125

Friedman & Halpern that is, if the failure set at (r0; m) consists of fewer
faulty components than at (r00; m). We extend these comparisons to sets:
Pl(r;m)(A) ^ Pl(r;m)(B) if min(r0;m)2A(jfault(r0; m)j) * min(r0;m)2B(jfault(r0;
m)j); that is, A is less plausible if all the points in A have failure sets
of larger cardinality then the minimal one in B. With this plausibility measure,
if all of the agent's observations up to time m are consistent with there
being no failures, then the agent believes that all components are functioning
correctly. On the other hand, if the observations do not match the expected
output of the circuit, then the agent considers minimal failure sets that
are consistent with her observations. Thus, if the observations are consistent
with a failure of c1, or a failure of c3, or the combined failure of c2 and
c7, then the agent believes that either c1 or c3 is faulty, but not both.

We now make this more precise. A failure set (i.e., a diagnosis) is characterized
by a complete formula over f1; : : : ; fn--that is, one that determines the
truth values all these propositions. For example, if n = 3, then f1^:f2 ^:f3
characterizes the failure set fc1g. We define D(r;m) to be the set of failure
sets (i.e., diagnoses) that the agent considers possible at (r; m); that
is D(r;m) = ff 2 F : (Idiag; r; m) j= :B:f g where F is the set of all possible
failure sets.

Belief change in Idiag is characterized by the following proposition.

Proposition 2.4: If there is some f 2 D(r;m) that is consistent with the
new observation io(r; m + 1), then D(r;m+1) consists of all the failure sets
in D(r;m) that are consistent with io(r; m + 1). If all f 2 D(r;m) are inconsistent
with io(r; m + 1), then D(r;m+1) consists of all failure sets of cardinality
j that are consistent with io(r; 1); : : :; io(r; m + 1), where j is the
least cardinality for which there is at least one failure set consistent
with these observations.

Thus, in Idiag, a new observation consistent with the current set of most
likely explanations reduces this set (to those consistent with the new observation).
On the other hand, a surprising observation (one inconsistent with the current
set of most likely explanations) has a rather drastic effect. It easily follows
from Proposition 2.4 that if io(r; m + 1) is surprising, then D(r;m) " D(r;m+1)
= ;, so the agent discards all her current explanations in this case. Moreover,
an easy induction on m shows that if D(r;m) " D(r;m+1) = ;, then the cardinality
of the failure sets in D(r;m+1) is greater than the cardinality of failure
sets in D(r;m). Thus, in this case, the explanations in D(r;m+1) are more
complicated than those in D(r;m). ut

2.4 Conditioning In an interpreted system, the agent's beliefs change from
point to point as her plausibility space changes. The general framework does
not put any constraints on how the plausibility space changes. If we were
thinking probabilistically, we could imagine the agent starting with a prior
on the runs in the system. Since a run describes a complete history over
time, this means that the agent puts a prior probability on the possible
sequences of events that could happen. We would then expect the agent to
modify her prior by conditioning on whatever information she has learned.
As we show below, this notion of conditioning is closely related to belief
revision and update. We remark that we are not the first to applying conditioning
in the context of belief change (cf. (Goldszmidt & Pearl, 1996; Spohn, 1988));
the details are a little more complex in our framework, because we model
time explicitly.

126

Modeling Belief in Dynamic Systems. Part II. We start by making the simplifying
assumption that we are dealing with synchronous systems where agents have
perfect recall (Halpern & Vardi, 1989). Intuitively, this means that the
agent knows what the time is and does not forget the observations she has
made. Formally, a system is synchronous if (r; m) ,a (r0; m0) only if m =
m0. In synchronous systems, the agent has perfect recall if (r0; m + 1) ,a
(r; m + 1) implies (r0; m) ,a (r; m). Thus, the agent considers run r possible
at the point (r; m + 1) only if she also considers it possible at (r; m).
This means that any runs considered impossible at (r; m) are also considered
impossible at (r; m + 1): the agent does not forget what she knew.

Just as with probability, we assume that the agent has a prior plausibility
measure on runs that describes her prior assessment on the possible executions
of the system. As the agent gains knowledge, she updates her prior by conditioning.
More precisely, at each point (r; m), the agent conditions her previous assessment
on the set of runs considered possible at (r; m). This results in an updated
assessment (posterior) of the plausibility of runs. This posterior induces,
via a projection from runs to points, a plausibility measure on points. We
can think of the agent's posterior at time m as simply her prior conditioned
on her knowledge at time m.

Formally, the prior plausibility of the agent is a plausibility measure Pa
= (R; Pla) over the runs in the system. If A is a set of points, we define
R(A) = fr : 9m((r; m) 2 A)g to be the set of runs on which the points in
A lie. The agent updates plausibilities by conditioning in I if the following
condition is met:

PRIOR There is prior Pa = (R; Pla) such that for all runs r 2 R, times m,
and sets A; B ` W(r;m), Pl(r;m)(A) ^ Pl(r;m)(B) if and only if Pla(R(A))
^ Pla(R(B)).

This definition implies that the agent's plausibility assessment at each
point is determined, in a straightforward fashion, by her prior.

As shown in (Friedman & Halpern, 1997), in synchronous systems that satisfy
PRIOR where agent have perfect recall, we can say even more: the agent's
plausibility measure at time m + 1 is determined by her plausibility measure
at time m. To make this precise, if A is a set of points, let prev(A) = f(r;
m) : (r; m + 1) 2 Ag.

Theorem 2.5: (Friedman & Halpern, 1997). Let I be a synchronous system satisfying
PRIOR where agents have perfect recall. Then Pl(r;m+1)(A) ^ Pl(r;m+1)(B)
if and only if Pl(r;m)(prev(A)) ^ Pl(r;m)(prev(B)), for all runs r, times
m, and sets A; B ` W(r;m+1).

Thus, in synchronous systems where agents have perfect recall PRIOR implies
a "local" rule for update that incrementally changes the agent's plausibility
at each step. This local rule consists of two steps. First, the agent's plausibility
at time m is projected to time m + 1 points. Second, time m + 1 points that
are inconsistent with the agent knowledge at (r; m + 1) are discarded. This
procedure implies that the relative plausibility of two sets of runs does
not change unless one of them is incompatible with the new knowledge.

Example 2.6: It is easy to verify that the system Idiag we consider in Example
2.3 satisfies PRIOR. The prior Pa is determined by the failure set in each
run in a manner similar to the construction of Pl(r;m). That is, R1 is more
plausible than R2 if there is a run in R1 with a smaller failure set than
all the runs in R2. ut

127

Friedman & Halpern 3. Review of Revision and Update We now present a brief
review of belief revision and update.

Belief revision attempts to describe how a rational agent incorporates new
beliefs. As we said earlier, the main intuition is that as few changes as
possible should be made. Thus, when something is learned that is consistent
with earlier beliefs, it is just added to the set of beliefs. The more interesting
situation is when the agent learns something inconsistent with her current
beliefs. She must then discard some of her old beliefs in order to incorporate
the new belief and remain consistent. The question is which ones?

The most widely accepted notion of belief revision is defined by the AGM
theory (Alchourr'on et al., 1985; G"ardenfors, 1988). This theory was originally
developed in philosophy of science, where one attempts to understand when
a scientist changes her beliefs (e.g., theory of physical laws) in a rational
manner. In this context, it seems reasonable to assume that the world is
static; that is, the laws of physics do not change while the scientist is
performing experiments.

Formally, this theory assumes a logical language Le over a set Phi e of
primitive propositions with a consequence relation `Le that contains the
propositional calculus and satisfies the deduction theorem. The AGM approach
assumes that an agent's epistemic state is represented by a belief set, that
is, a set K of formulas in the language Le.6 There is also assumed to be
a revision operator ffi that takes a belief set A and a formula ' and returns
a new belief set Affi', intuitively, the result of revising A by '. The following
AGM postulates are an attempt to characterize the intuition of "minimal change":

(R1) A ffi ' is a belief set (R2) ' 2 A ffi ' (R3) A ffi ' ` Cl(A [ f'g)7
(R4) If :' 62 A then Cl(A [ f'g) ` A ffi ' (R5) A ffi ' = Cl(false) if and
only if `Le :' (R6) If `Le ' ,  then A ffi ' = A ffi  (R7) A ffi (' ^ ) `
Cl(A ffi ' [ fg) (R8) If : 62 A ffi ' then Cl(A ffi ' [ fg) ` A ffi (' ^
).

The essence of these postulates is the following. After a revision by ' the
belief set should include ' (postulates R1 and R2). If the new belief is
consistent with the belief set, then the revision should not remove any of
the old beliefs and should not add any new beliefs except these implied by
the combination of the old beliefs with the new belief (postulates R3 and
R4). This condition is called persistence. The next two conditions discuss
the coherence of beliefs. Postulate R5 states that the agent is capable of
incorporating any consistent belief and postulate R6 states that the syntactic
form of the new belief does not affect the revision process. The last two
postulates enforce a certain coherency on the

6. For example, G"ardenfors (1988, p. 21) says "A simple way of modeling
the epistemic state of an individual

is to represent it by a set of sentences." 7. Cl(A) = f'jA `Le 'g is the
deductive closure of a set of formulas A.

128

Modeling Belief in Dynamic Systems. Part II. outcome of revisions by related
beliefs. Basically, they state that if  is consistent with A ffi ' then A
ffi (' ^ ) is just A ffi ' ffi .

The notion of belief update originated in the database community (Keller
& Winslett, 1985; Winslett, 1988). The problem is how a knowledge base should
change when something is learned about the world. For example, suppose that
a transaction adds to the knowledge base the fact "Table 7 is in Office 2",
which contradicts the previous belief that "Table 7 is in Office 1". What
else should change? The intuition that update attempts to capture is that
such a transaction describes a change that has occurred in the world. Thus,
in our example, by applying update we might conclude that the reason that
the table is in Office 2 is that it was moved, not that our earlier beliefs
were false. This example shows that, unlike revision, update does not assume
that the world is static.

Katsuno and Mendelzon (1991a) suggest a set of postulates that an update
operator should satisfy. The update postulates are expressed in terms of
formulas, not belief sets. That is, an update operator Pi  maps a pair of
formulas, one describing the agent's current beliefs and the other describing
the new observation, to a new formula that describes the agent's updated
beliefs. This is not unreasonable, since we can identify a formula ' with
the belief set Cl('). Indeed, if Phi  is finite (which is what Katsuno and
Mendelzon assume) every belief set A can be associated with some formula
'A such that Cl('A) = A, and every formula ' corresponds to a belief set
Cl('). Thus, any update operator induces an operator that maps a belief state
and an observation to a new belief state. We slightly abuse notation and
use the same symbol to denote both types of mappings. We say that a belief
set A is complete if, for every ' 2 Le, either ' 2 A or :' 2 A. A formula
_ is complete if Cl(_) is complete.

The KM postulates are:

(U1) `Le _ Pi  ' ) ' (U2) If `Le _ ) ', then `Le _ Pi  ' , _ (U3) `Le :_
Pi  ' if and only if `Le :_ or `Le :' (U4) If `Le _1 , _2 and `Le '1 , '2
then `Le _1 Pi  '1 , _2 Pi  '2 (U5) `Le (_ Pi  ') ^  ) _ Pi  (' ^ ) (U6)
If `Le _ Pi  '1 ) '2 and `Le _ Pi  '2 ) '1, then `Le _ Pi  '1 , _ Pi
'2 (U7) If _ is complete then `Le (_ Pi  '1) ^ (_ Pi  '2) ) _ Pi  ('1
. '2) (U8) `Le (_1 . _2) Pi  ' , (_1 Pi  ') . (_2 Pi  ').

The essence of these postulates is as following. After learning ', the agent
believes ' (postulate U1, which is analogous to R2). If ' is already believed,
then updating by ' does not change the agent's beliefs (postulate U2, which
is a weaker version of R3 and R4). The next two postulates (U3 and U4) deal
with coherence of the belief change process. They are analogous to R5 and
R6, respectively, with minor differences. Postulates U5 and U6 deal with
observations that are related to each other. U5 states that beliefs after
learning ' that are consistent with  are also believed after learning ' ^
. U6 states that if '2 is believed after learning '1 and '1 is believed after
learning '2, then learning either '1 or '2 leads to the same belief set.
Finally, U7 and U8 deal with decomposition properties of the update operation.
U7 states that if _ is essentially a truth assignment to L, then if 

129

Friedman & Halpern is believed after learning '1 and is also believed after
learning '2 then it is believed after learning '1 . '2. U8 states that the
update of the knowledge base can be computed by independent updates on each
sub-part of the knowledge. That is, if _ = _1 . _2, then we can apply update
to each of _1 and _2, and then combine the results.

4. Belief Change Systems We want to model belief change--particularly belief
revision and belief update--in the framework of systems. To do so, we consider
a particular class of systems that we call belief change systems. In belief
change systems, the agent makes observations about an external environment.
Just as is (implicitly) assumed in both revision and update, we assume that
these observations are described by formulas in some logical language. We
then make other assumptions regarding the plausibility measure used by the
agent. We formalize our assumptions as conditions BCS1-BCS5, described below,
and say that a system I = (R; ss; P) is a belief change system if it satisfies
these conditions. We denote by CBCS the set of belief change systems.

Assumption BCS1 formalizes the intuition that our language includes propositions
for reasoning about the environment, whose truth depends only on the environment
state.

BCS1 The language L includes a propositional sublanguage Le over a set Phi
e of primitive propositions. Le contains the usual propositional connectives
and comes equipped with a consequence relation `Le. The interpretation ss(r;
m) assigns truth to propositions in Phi e in such a way that

(a) ss(r; m) is consistent with `Le, that is, fp : p 2 Phi e; ss(r; m)(p)
= trueg [

f:p : p 2 Phi e; ss(r; m)(p) = falseg is `Le consistent, and

(b) ss(r; m)(p) depends only on re(m) for propositions in Phi e; that is,
ss(r; m)(p) =

ss(r0; m0)(p) whenever re(m) = r0e(m0).

Part (b) of BCS1 implies that we can evaluate formulas in Le with respect
to environment states; that is, if ' 2 Le and re(m) = r0e(m0), then (I; r;
m) j= ' if and only if (I; r0; m0) j= '. Since the environment is all that
is relevant for formulas in Le, if ' 2 Le, we write se j= ' if (I; r; m)
j= ' for some point (r; m) such that re(m) = se.

BCS2 is concerned with the form of the agent's local state. Recall that,
in our framework, the local state captures the relevant aspects of the agent's
epistemic state. The functional form of the revision and update operators
suggests that all that matters regarding how an agent changes her beliefs
are the agent's current epistemic state (which is taken by both AGM and KM
to be a belief set) and what is learned. In terms of our framework, this
suggests that agent's local state at time m + 1 should be a function of her
local state of time m and the observation made at time m. We in fact make
the stronger assumption here that the agent's state consists of the sequence
of observations made by the agent. This means that the agent remembers all
her past observations. Note that this surely implies that the agent's local
state at time m + 1 is determined by her state at time m and the observation
made at time m. We make the further assumption that the observations made
by the agent can be described by formulas in Le. Although this is quite a
strong assumption on the expressive power of Le, it is standard in the literature:
both revision and update

130

Modeling Belief in Dynamic Systems. Part II. assume that observations can
be expressed as formulas in the language (see Section 3). These assumptions
are formalized in BCS2:

BCS2 For all r 2 R and for all m, we have ra(m) = ho(r;1); : : : ; o(r;m)i
where o(r;k) 2 Le for 1 ^ k ^ m.

Intuitively, o(r;k) is the observation the agent makes immediately after
the transition from time k Gamma  1 to time k in run r. Thus, it represents
what the agent observes about the new state of the system at time k. Note
that BCS2 implies that the agent's state at time 0 is the empty sequence
in all runs. Moreover, it implies that ra(m + 1) = ra(m) Delta  o(r;m+1),
where Delta  is the append operation on sequences. That is, the agent's
state at (r; m + 1) is the result of appending to her previous state the
latest observation she has made about the system. It is not too hard to show
that belief change systems are synchronous and agents in them have perfect
recall. (We remark that the agents' local states are modeled in a similar
way in the model of knowledge bases presented in (Fagin et al., 1995).)

Clearly we want to reason in our language about the observations the agent
makes. Thus, we assume that the language includes propositions that describe
the observations made by the agent.

BCS3 The language L includes a set Phi obs of primitive propositions disjoint
from Phi e such that Phi obs = flearn(') : ' 2 Leg. Moreover, ss(r; m)(learn('))
= true if and only if o(r;m) = ' for all runs r and times m.

In a system satisfying BCS1-BCS3, we can talk about belief change. The agent's
state encodes observations, and we have propositions that allow us to talk
about what is observed. The next assumption is somewhat more geared to situations
where observations are always "accepted", so that after the agent observes
', she believes '. While this is not a necessary assumption, it is made by
both belief revision and belief update. We capture this assumption here in
what is perhaps the simplest possible way: by assuming that observations
are reliable, so that the agent observes ' only if the current state of the
environment satisfies '. This is certainly not the only way of enforcing
the assumption that observations are accepted, but it is perhaps the simplest,
so we focus on it here. As we shall see, this assumption is consistent with
both revision and update, in the sense that we can capture both in systems
satisfying it.

BCS4 (I; r; m) j= o(r;m) for all runs r and times m. Note that BCS4 implies
that the agent never observes false. Moreover, it implies that after observing
', the agent knows that ' is true. In (Boutilier et al., 1998), we consider
an instance of our framework in which observations are unreliable (so that
BCS4 does not hold in general), and examine the status of R2, the acceptance
postulate, in this case.

Finally, we assume that belief change proceeds by conditioning. While there
are certainly other assumptions that can be made, as we have tried to argue,
conditioning is a principled approach that captures the intuitions of minimal
change, given the observations. And, as we shall see, conditioning (as captured
by PRIOR) is consistent with both revision and update.

BCS5 I satisfies PRIOR.

131

Friedman & Halpern Many interesting systems can be viewed as BCS's. Example
4.1: Consider the systems Idiag;1 and Idiag;2 of Example 2.1. Are these systems
BCSs? Not quite, since ssdiag is not defined on primitive propositions of
the form learn('), but we can easily embed both systems in a BCS. Let Ldiag
the propositional language defined over Phi diag, and let Phi +diag consist
of Phi diag together with all the primitive propositions of the

form learn(') for ' 2 Ldiag. Let ss+diag be the obvious extension of ssdiag
to Phi +diag, defined so that BCS3 holds. Then in it is easy to see that
(Rdiag; ss+diag; Pdiag;i) is a BCS: we take the Phi e of BCS1 to be Phi
diag, and define `Ldiag so that it enforces the relationships determined
by the circuit layout. Thus, for example, if c1 is an AND gate with input
lines l1 and l2 and output line l3, then we would have `Ldiag :f1 ) (h3 ,
h1 ^ h2). It is then easy to see that BCS2-BCS5 hold by our construction.
ut

These definitions set the background for our presentation of belief revision
and belief update.

5. Capturing Revision Revision can be captured by restricting to BCSs that
satisfy several additional assumptions. Before describing these assumptions,
we briefly review a well-known representation of revision that will help
motivate them.

While there are several representation theorems for belief revision, the
clearest is perhaps the following (Grove, 1988; Katsuno & Mendelzon, 1991b).
We associate with each belief set A a set WA of possible worlds that consists
of those worlds where A is true. Thus, an agent whose belief set is A believes
that one of the worlds in WA is the real world. An agent that performs belief
revision behaves as though in each belief state A she has a ranking, i.e.,
a total preorder, over all possible worlds such that the minimal (i.e., most
plausible) worlds in the ranking are exactly those in WA. When revising by
', the agent chooses the minimal worlds satisfying ' in the ranking and constructs
a belief set from them. It is easy to see that this procedure for belief
revision satisfies the AGM postulates. Moreover, in (Grove, 1988; Katsuno
& Mendelzon, 1991b), it is shown that any belief revision operator can be
described in terms of such a ranking.

This representation suggests how we can capture belief revision in our framework.
We define CR ` CBCS to be the set of belief change systems I = (R; ss; P)
that satisfy the conditions REV1-REV4 that we define below.

Revision assumes that the world does not change during the revision process.
Formally this implies that propositions in Phi e do not change their truth
value along a run, i.e., (I; r; m) j= p if and only if (I; r; m + 1) j= p
for all p 2 Phi e. This says that the state of the world is the same with
respect to the properties that the agent reasons about (i.e., the propositions
in Phi e).

REV1 ss(r; m)(p) = ss(r; 0)(p) for all p 2 Phi e and points (r; m). Note
that REV1 does not necessarily imply that re(m) = re(m + 1). That is, REV1
allows for a changing environment. The only restriction is that the truth
value of propositions that describe the environment does not change. We return
to this issue in Section 7.

132

Modeling Belief in Dynamic Systems. Part II. The representation of (Grove,
1988; Katsuno & Mendelzon, 1991a) requires the agent to totally order possible
worlds. We put a similar requirement on the agent's plausibility assessment.
Recall that BCS5 says that the agent's plausibility is induced by a prior
Pla; REV2 strengthens this assumption.

REV2 The prior Pla of BCS5 is ranked; that is, for all A; B ` R, either Pla(A)
^ Pla(B) or Pla(B) ^ Pla(A), and Pl(A [ B) = max(Pl(A); Pl(B)).

The representation of (Grove, 1988; Katsuno & Mendelzon, 1991a) also requires
that the agent considers all truth assignments possible. We need a similar
condition, except that we want not only that all truth assignments be considered
possible, but that they have nontrivial plausibility (i.e., are more plausible
than ?) as well.

To make this precise, it is helpful to introduce some notation that will
be useful for our later definitions as well. Given a system I and two sequences
'1; : : : ; 'k and o1; : : : ; ok0 of formulas in Le, let R['1; : : :; 'k;
o1; : : :; ok0] consist of all runs r where for each i with 1 ^ i ^ k, the
formula 'i is true at (r; i) and the agent observes o1; : : : ; ok0. That
is, R['0; : : :; 'k; o1; : : :; ok0] = fr 2 I : (I; r; i) j= 'i; i = 0; :
: : ; k; and ra(k0) = ho1; : : : ; ok0ig. We allow either sequence of formulas
to be empty, so, for example, R['; Delta ] consists of all runs for which
' is true at the initial state. (Note that if REV1 holds, this means that
' is true in all subsequent states as well.) We use the notation R['1; :
: : ; 'm] as an abbreviation for R['1; : : : ; 'm; Delta ].

REV3 If ' 2 Le is consistent, then Pla(R[']) ? ?. It might seem that REV1-REV3
capture all of the assumptions made by the representation of (Grove, 1988;
Katsuno & Mendelzon, 1991a). However, there is another assumption implicit
in the way revision is performed in these representations that we must make
explicit in our representation, because of the way we have distinguished
observing ' (captured by the formula learn(')) from ' itself. Intuitively,
when the agent observes ', she updates her plausibility assessment by conditioning
on '. This is essentially what we can think of the earlier representations
as doing. However, in our representation, the agent does not condition on
', but on the fact that she has observed '. Although we do require that '
must be true if the agent observes it (BCS4), the agent may in general gain
extra information by observing '.

To understand this issue, consider the following example. Suppose that R
is such that the agent observes p1 at time (r; m) only if p2 and q are also
true at (r; m), and she observes p1 ^ p2 at (r; m) only if q is false. It
is easy to construct a BCS satisfying REV1-REV3 that also satisfies these
requirements. In this system, after observing p1, the agent believes p2 and
q. According to AGM's postulate R7 (and also KM's postulate U5) the agent
must believe q after observing p1 ^ p2. To see this, note that our assumptions
about R can be phrased in the AGM language as p2 ^ q 2 K ffi p1 and :q 2
K ffi (p1 ^ p2). Postulate R7 states that K ffi (p1 ^ p2) ` Cl(K ffi p1 [
fp2g). Since p2 2 K ffi p1, we have that Cl(K ffi p1 [ fp2g) = K ffi p1.
Thus, R7 implies in this case that q 2 K ffi (p1 ^ p2). However, in R, the
agent believes (indeed knows) :q after observing p1 ^ p2.8 Thus, revision
and update

8. We stress this does not mean that p1 ^ p2 implies :q in R. There may well
be points in R at which

p1 ^ p2 ^ q is true. However, at such points, the agent would not observe
p1 ^ p2, since the agent observes p1 ^ p2 only if q is false.

133

Friedman & Halpern both are implicitly assuming that the observation of '
does not provide such additional knowledge. The following assumption ensures
that this is the case for revision (a more general version will be required
for update; see Section 6).

REV4 Pla(R['; o1; : : : ; om]) * Pla(R[; o1; : : : ; om]) if and only if
Pla(R[' ^ o1 ^ : : : ^ om]) * Pla(R[ ^ o1 ^ : : : ^ om]).

This assumption captures the intuition that observing o1; : : : ; ok provides
no more information than just the fact that o1 ^ : : : ^ om is true. That
is, the agent compares the plausibility of ' and  in the same way after conditioning
by the observations o1; : : :; om as after conditioning by the fact that
o1 ^ : : : ^ om is true. It easily follows from REV4 and PRIOR that the agent
believes  after observing o1 ^ : : : ^ om exactly if o1 ^ : : : ^ om ^  was
initially considered more plausible than o1 ^ : : : ^ om ^ :. Thus, the agent
believes  after observing o1 ^ : : : ^ om exactly if initially, she believed
conditional on o1 ^ : : : ^ om: the observations provide no extra information
beyond the fact that each of the oi's are true.

REV4 is quite a strong assumption. Not only does it say that observations
do not give the agent any additional information (beyond the fact that they
are true), it also says that all consistent observations can be made (since
if ' ^ o is consistent, we must have Pla(R['; o]) = Pla(R[' ^ o]) ? ?, by
REV3 and REV4). We might instead consider using a weaker version of REV4
that says that, provided an observation can be made, it gives no additional
information. Formally, this would be captured as

REV40 If Pla(R['; o1; : : : ; om]) ? 0, then Pla(R['; o1; : : : ; om]) *
Pla(R[; o1; : : : ; om]) if and only if Pla(R[' ^ o1 ^ : : : ^ om]) * Pla(R[
^ o1 ^ : : : ^ om]).

The following examples suggests that REV40 may be more reasonable in practice
than REV4. We used REV4 only because it comes closer to the spirit of the
requirement of revision that all observations are possible.

Example 5.1: Consider the system Idiag;1 described in Example 2.1. As discussed
in Example 4.1, this system can be viewed as a BCS. Is it a revision system?
It is easy to see that Idiag;1 satisfies REV2 and REV3. It clearly does not
satisfy REV1, since propositions that describe input/output lines can change
their values from one point to the next. However, as we are about to show,
a slight variant of Idiag;1 does satisfy REV1. A more fundamental problem
is that Idiag;1 does not satisfy REV4. This is inherent in our assumption
that the agent never directly observes faults, so that, for example, we have
Pldiag;1(R[Delta ; f1]) = ?, while Pldiag;1(R[f1]) ? ?. It does, however,
satisfy REV40.

To see how to modify Idiag;1 so as to satisfy REV1, recall that in the diagnosis
task, the agent is mainly interested in her beliefs about faults. Since faults
are static in Idiag;1, we can satisfy REV1 if we ignore all propositions
except f1; : : : ; fn. Let Phi 0diag = ff1; : : : ; fng and let L0diag be
the propositional language over Phi 0diag. For every observation o made
by the agent regarding the value of the lines, there corresponds a formula
in L0diag that characterizes all the fault sets that are consistent with
o. Thus, for every run r in Idiag;1, we can construct a run r0 where the
agent's local state is a sequence of formulas in L0diag. Let I0diag be the
system consisting of all such runs r0. We can clearly put a plausibility
assignment on these runs so that Idiag;1 and I0diag are isomorphic in an
obvious sense. In particular, the agent has the same beliefs about formulas
in L0diag at corresponding points in the two systems.

134

Modeling Belief in Dynamic Systems. Part II. More precisely, if ' 2 L0diag,
then (I0diag; r; m) j= ' if and only if (Idiag;1; r; m) j= ' for all points
(r; m) in Idiag;1. It is easy to verify that I0diag satisfies REV1-REV3 and
REV40, although it still does not satisfy REV4.

We are not advocating here here using I0diag instead of Idiag--Idiag seems
to us a perfectly reasonable way of modeling the situation. Rather, the point
is that if we want a BCS to satisfy properties that validate the AGM postulates,
we must make some strong, and not always natural, assumptions. ut

We want to show that a revision operator corresponds to a system in CR and
vice versa. To do so, we need to examine the beliefs of the agent at each
point (r; m). First we note that if (r; m) ,a (r0; m0) then (I; r; m) j=
B' if and only if (I; r0; m0) j= B'; this is a consequence of the requirement
that, as we have defined interpreted systems, the agent's plausibility assessment
is a function of her local state. Thus, we think of the agent's beliefs as
a function of her local state. We use the notation (I; sa) j= B' as shorthand
for (I; r; m) j= B' for some (r; m) such that ra(m) = sa. Let sa be some
local state of the agent. We define the agent's belief state at sa as

Bel(I; sa) = f' 2 Le : (I; sa) j= B'g: Since the agent's state is a sequence
of observations, the agent's state after observing ' is simply sa Delta
', where Delta  is the append operation. Thus, Bel(I; sa Delta  ') is the
belief state after observing '. We adopt the convention that if the agent
can never attain the local state sa in I, then Bel(I; sa) = Le. With these
definitions, we can compare the agent's belief state before and after observing
', that is Bel(I; sa) and Bel(I; sa Delta  ').

We start by showing that every AGM revision operator can be represented in
CR.

Theorem 5.2: Let ffi be an AGM revision operator and let K ` Le be a consistent
belief state. Then there is a system Iffi;K 2 CR such that Bel(Iffi;K; hi)
= K and

Bel(Iffi;K; hi) ffi ' = Bel(Iffi;K; h'i) for all ' 2 Le. Proof: See Appendix
A.1. ut

Thus, Theorem 5.2 says that we can represent a revision operator ffi in the
sense that we have a family of systems Iffi;K 2 CR, one for each consistent
belief state K, such that K is the agent's initial belief state in Iffi;K,
and for each formula ' in Le, the agent's belief state after learning ' is
K ffi '. Notice that we restrict attention to consistent belief states K.
The AGM postulates allow the agent to "escape" from an inconsistent state,
so that K ffi ' may be consistent even if K is inconsistent. We might thus
hope to extend the theorem so that it also applies to the inconsistent belief
state, but this is impossible in our framework. If false 2 Bel(Iffi;K; sa)
for some state sa, and ra(m) = sa, then Pl(r;m)(W(r;m)) = ?. Since we update
by conditioning, we must have Pl(r;m+1)(W(r;m+1)) = ?, so the agent's belief
state will remain inconsistent no matter what she learns. Although we could
modify our framework to allow the agent to escape from inconsistent states,
we actually consider this to be a defect in the AGM postulates, not in our
framework. To see why, suppose that the

135

Friedman & Halpern agent's belief set is inconsistent at sa, and ra(m) =
sa. Thus, the agent considers all states in W(r;m) to be completely implausible
(since Pl(r;m)(W(r;m)) = ?). On the other hand, to escape inconsistency,
she must have a plausibility ordering over the worlds in W(r;m). These two
requirements seem somewhat inconsistent.9

Not surprisingly, this inconsistency creates problems for other semantic
representations in the literature. For example, Boutilier's representation
theorem (1992) states that for every revision operator ffi and belief state
K, there is a ranking R such that  2 K ffi ' if and only if  is believed
in the minimal '-worlds according to R. If we examine this theorem, we note
that he does not state that the minimal (i.e., most preferred) worlds in
R correspond to the belief state K (in the sense that the minimal worlds
are precisely those where the formulas in K hold); this would be the analogue
of our requiring that Bel(Iffi;K; hi) = K. In fact, if K is `Le-consistent,
the minimal worlds do correspond to K. However, if K is inconsistent, they
cannot, since any nonempty ranking induces a consistent set of beliefs. We
could state a weaker version of Theorem 5.2 that would correspond exactly
to Boutilier's theorem. We presented the stronger result (that does not apply
to inconsistent belief states) to bring out what we believe to be a problem
with the AGM postulates. See (Friedman & Halpern, 1998a) for further discussion
of this issue.

Theorem 5.2 shows that, in a precise sense, we can map AGM revision operations
to CR. What about the other direction? The next theorem shows that the first
belief change step in systems in CR satisfies the AGM postulates.

Theorem 5.3: Let I be a system in CR. Then there is an AGM revision operator
ffiI such that

Bel(I; hi) ffiI ' = Bel(I; h'i)

for all ' 2 Le.

Proof: See Appendix A.1. ut

We remark that if we used REV40 instead of REV4, then we would be able to
prove this result only for those formulas ' that are observable (i.e., for
which Pl(R[']) ? ?).

Both Theorems 5.2 and 5.3 apply to one-step revision, starting from the initial
(empty) state. What happens once we allow iterated revision? In our framework,
observations are taken to be known, so if the agent makes an inconsistent
sequence of observations, then her belief state will be inconsistent, and
(as we observed above) will remain inconsistent from then on, no matter what
she observes. This creates a problem if we try to get analogues to Theorems
5.2 and 5.3 for iterated revision. As the following theorem demonstrates,
we can already see the problem if we consider one-step revisions from a state
other than the initial state.

Theorem 5.4: Let I be a system in CR and let sa = h'1; : : : ; 'ki be a local
state in I. Then there is an AGM revision operator ffiI;sa such that

Bel(I; sa) ffiI;sa ' = Bel(I; sa Delta  ') 9. One strength of the AGM framework
is that it can deal with an inconsistent sequence of observations,

that is, it can cope with an observation sequence of the form hp; :p; p;
:p; : : :i. We stress that being able to cope with such an inconsistent sequence
of observations does not require allowing the agent to escape from inconsistent
belief sets. These are two orthogonal issues.

136

Modeling Belief in Dynamic Systems. Part II. for all formulas ' 2 Le such
that '1 ^ : : : ^ 'k ^ ' is consistent. Proof: See Appendix A.1. ut

We cannot do better than this. If '1 ^ : : : ^ 'k ^ ' is inconsistent then,
because of our requirements that all observations must be true of the current
state of the environment (BCS4) and that propositions are static (REV1),
there cannot be any global state in I where the agent's local state in sa
Delta  '. Thus, Bel(I; sa Delta  ') is inconsistent, contradicting R5.

There is another problem with trying to get an analogue of Theorem 5.3 for
iterated revision, a problem that seems inherent in the AGM framework. Our
framework makes a clear distinction between the agent's epistemic state at
a point (r; m) in I, which we can identify with her local state sa = ra(m),
and the agent's belief set at (r; m), Bel(I; sa), which is the set of formulas
she believes. In a system in CR, the agent's belief set does not in general
determine how the agent's beliefs will be revised; her epistemic state does.
On the other hand, the AGM postulates assume that revision is a function
of the agent's belief set and observations. Now suppose we have a system
I and two points (r; m) and (r; m0) on some run r 2 I such that (1) the agent's
belief set is the same at (r; m) and (r; m0), that is Bel(I; ra(m)) = Bel(I;
ra(m0)), (2) the agent observes ' at both (r; m) and (r; m0), (3) Bel(I;
ra(m + 1)) 6= Bel(I; ra(m0 + 1). It is not hard to construct such a system
I. However, there cannot be an analogue of Theorem 5.3 for I, even if we
restrict to consistent sequences of observations. For suppose there were
a revision operator ffi such Bel(I; hi)) ffi '1 ffi Delta  Delta  Delta
ffi 'k = Bel(I; h'1; : : :; 'ki) for all '1; : : : ; 'k such that '1 ^ :
: : ^ 'k is consistent. Then we would have Bel(I; ra(m+1)) = Bel(I; ra(m))ffi'
= Bel(I; ra(m0))ffi' = Bel(I; ra(m0 + 1)), contradicting our assumption.

The culprit here is the assumption that revision depends only on the agent's
belief set. To see why this is an unreasonable assumption, consider a situation
where at time 0 the agent believes both p and q, but her belief in q is stronger
than her belief in p (i.e., the plausibility of q is greater than that of
p). We can well imagine that after observing :p . :q at time 1, she would
believe :p and q. However, if she first observed p at time 1 and then :p
. :q at time 2, she would believe p and :q, because, as a result of observing
p, she would assign p greater plausibility than q. Note, however, that the
AGM postulates dictate that after an observation that is already believed,
the agent does not change her beliefs. Thus, the AGM setup would force the
agent to have the same beliefs after learning :p . :q in both situations.

There has been a great deal of work on the problem of iterated belief revision
(Boutilier, 1996a; Darwiche & Pearl, 1997; Freund & Lehmann, 1994; Lehmann,
1995; Levi, 1988; Nayak, 1994; Williams, 1994)). Much of the recent work
moves away from the assumption that belief revision depends solely on the
agent's belief set. For example the approaches of Boutilier (1996a) and Darwiche
and Pearl (1997) define revision operators that map (rankings Theta  formulas)
to rankings. Because our framework makes such a clear distinction between
epistemic states and belief states, it gives us a natural way of maintaining
the spirit of the AGM postulates while assuming that revision is a function
of epistemic states. Rather than taking ffi to be a function from (belief
states Theta  formulas) to belief states, we take it ffi to be a function
from (epistemic states Theta  formulas) to epistemic states.

This leaves open the question of how to represent epistemic states. Boutilier
and Darwiche and Pearl use rankings to represent epistemic states. In our
framework, we represent

137

Friedman & Halpern epistemic states by local states in interpreted systems.
That is, a pair (I; sa) denotes the agent's state in an interpreted system,
and the pair determines the agent's relevant epistemic attitudes, such as
her beliefs, how her beliefs changed given particular observations, her plausibility
assessment over runs, and so on. When the system is understood, we simply
use sa as a shorthand representation of an epistemic state.

We can easily modify the AGM postulates to deal with such revision operators
on epistemic states. We start by assuming that there is a set of epistemic
states and a function Bel(Delta ) that maps epistemic states to belief states.
We then have analogues to each of the AGM postulates, obtained by replacing
each belief set by the beliefs in the corresponding epistemic state. For
example, we have

(R10) E ffi ' is an epistemic state (R20) ' 2 Bel(E ffi ') (R30) Bel(E ffi
') ` Cl(Bel(E) [ f'g)

and so on, with the obvious transformation.10

We can get strong representation theorems if we work at the level of epistemic
states. Given a language Le (with an associated consequence relation `Le),
let ELe consist of all finite sequences of formulas in Le. Note that we allow
ELe to include sequences of formulas whose conjunction is inconsistent. We
define revision in ELe in the obvious way: if E 2 ELe, then E ffi ' = E Delta
'.

Theorem 5.5: Let I be a system in CR whose local states are ELe. There is
a function BelI that maps epistemic states to belief states such that

ffl if sa is a local state of the agent in I, then Bel(I; sa) = BelI (sa),
and ffl (ffi; BelI ) satisfies R10-R80.

Proof: Roughly speaking, we define BelI (sa) = Bel(I; sa) when sa is a local
state in I. If sa is not in I, then we set BelI(sa) = Bel(I; s0), where s0
is the longest consistent suffix of sa. See Appendix A.1 for details. ut

Notice that, by definition, we have BelI (I; hi ffiI '1 ffiI : : : ffiI 'k)
= BelI (I; h'1; : : : ; 'ki), so, at the level of epistemic states, we get
an analogue to Theorem 5.3. We remark that to ensure that R50 holds for (ffi;
BelI ), we need to define BelI (E) appropriately for sequences E 2 EI whose
conjunction is inconsistent.

Theorem 5.5 shows that any system in CR corresponds to a revision operator
over epistemic states that satisfies the generalized AGM postulates. We would
hope that the converse also holds. Unfortunately, this is not quite the case.
There are revision operators on epistemic states that satisfy the generalized
AGM postulates but do not correspond to a system in CR. This is because systems
in CR satisfy an additional postulate:

(R90) If 6`Le :(' ^ ) then Bel(E ffi ' ffi ) = Bel(E ffi ' ^ ). 10. The only
problematic postulate is R6. The question is whether R60 should be "If `Le
' ,  then

Bel(E ffi ') = Bel(E ffi )" or "If `Le ' ,  then E ffi ' = E ffi ". Dealing
with either version is straightforward. For definiteness, we adopt the first
alternative here.

138

Modeling Belief in Dynamic Systems. Part II. We show that R90 is sound in
CR by proving the following strengthening of Theorem 5.5. Proposition 5.6:
Let I be a system in CR whose local states are ELe. There is a function BelI
that maps epistemic states to belief states such that

ffl if sa is a local state of the agent in I, then Bel(I; sa) = BelI (sa),
and ffl (ffi; BelI ) satisfies R10-R90.

Proof: We show that the function BelI defined in the proof of Theorem 5.5
satisfies R90. See Appendix A.1 for details. ut

We can prove the converse to Proposition 5.6: a revision system on epistemic
states that satisfies the generalized AGM postulates and R90 does correspond
to a system in CR.

Theorem 5.7: Given a function BelLe mapping epistemic states in ELe to belief
sets over Le such that BelLe (hi) is consistent and (BelLe; ffi) satisfies
R10-R90, there is a system I 2 CR whose local states are in ELe such that
BelLe(sa) = Bel(sa) for each local state sain I.

Proof: According to Theorem 5.2, there is a system I such that Bel(I; hi)
= BelLe(hi) and Bel(I; h'i) = BelLe(h'i) for all ' 2 Le. We show that Bel(I;
sa) = BelLe(sa) for local states sa in I. See Appendix A.1. ut

Notice that, by definition, for the system I of Theorem 5.7, we have Bel(hiffi'1ffi:
: :ffi'k) = Bel(h'1; : : : ; 'ki) as long as '1 ^ : : : ^ 'k is consistent.

6. Capturing Update Update tries to capture the intuition that there is a
preference for runs where all the observations made are true, and where changes
from one point to the next along the run are minimized.

We start by reviewing Katsuno and Mendelzon's semantic representation of
update. To characterize an agent beliefs, Katsuno and Mendelzon consider
the set of "worlds" the agent considers possible. In their representation,
they associate a world with a truth assignment to the primitive propositions.
(In our terminology, we can think of a world as an environment state.) To
capture the notion of "minimal change from world to world", Katsuno and Mendelzon
use a distance function d on worlds. Given two worlds w and w0, d(w; w0)
measures the distance between them. Intuitively, the larger the distance,
the larger the change required to get from world w to w0. (Note that that
distances are not necessarily symmetric, that is, it might require a smaller
change to get from w to w0, than from w0 to w.) Distances might be incomparable,
so we require that d map pairs of worlds into a partially ordered domain
with a unique minimal element 0 and that d(w; w0) = 0 if and only if w =
w0.

Katsuno and Mendelzon show that there is a close relationship between update
operators and distance functions. To make this relationship precise, we need
to introduce some definitions. An update structure is a tuple U = (W; d;
ss), where W is a finite set of worlds, d is a distance function on W , and
ss is a mapping from worlds to truth assignments for Le such that

ffl ss(w) is `Le consistent,

139

Friedman & Halpern ffl if 6`Le :', then there is some w 2 W with ss(w)(')
= true, and ffl if w 6= w0 then ss(w) 6= ss(w0) for all w; w0 2 W .

Given an update structure U = (W; d; ss), we define [[']]U = fw : ss(w)(')
= trueg. Katsuno and Mendelzon use update structures as semantic representations
of update operators. Given an update structure U = (W; d; ss) and sets A;
B ` W , Katsuno and Mendelzon define minU (A; B) to be the set of worlds
in B that are closest to worlds in A, according to d. Formally, minU (A;
B) = fw 2 B : 9w0 2 A8w0 2 B d(w0; w0) 6! d(w0; w)g.

Theorem 6.1: (Katsuno & Mendelzon, 1991b) A belief change operator Pi  satisfies
U1-U8 if and only if there is an update structure U = (W; ss; d) such that

[[' Pi  ]]U = minU ([[']]U; [[]]U): Thus the worlds the agent believes possible
after updating with  are these worlds that are closest to some world considered
possible before learning .

Katsuno and Mendelzon's account of update is "static" in the sense that it
describes a single belief change. Nevertheless, there is a clear intuition
that each world w0 2 [[' Pi  ]]U is the result of considering a minimal
change from some world w 2 [[']]U . However, in Katsuno and Mendelzon's representation,
we do not keep track of the worlds that "lead to" the worlds in the current
belief set.

We now try to capture behavior similar to Katsuno and Mendelzon's semantics
in our framework. We define systems where each run describes the sequence
of changes, so that the most plausible runs, given a set of observations,
correspond the worlds that define the belief set in Katsuno and Mendelzon's
semantics. More precisely, given a sequence of observations 1; : : : ; n,
each world in [['Pi 1Pi : : :Pi n]]U can be "traced" back through a series
of minimal changes to a world in [[']]U . In our model, each such trace corresponds
to one of the most plausible runs, where the environment state at time m
is the mth world in the trace. We can capture this intuition by using a family
of priors with a particular form.

We start with some preliminary definitions. Let I be a BCS, and let s0; :
: : ; sn be a set of environment states in I. We define [s0; : : : ; sn]
as the set of runs where re(i) = si for all 0 ^ i ^ n. Thus, [s0; : : : ;
sn] describes a set of runs that share a common prefix of environment states.
A prior plausibility space Pa = (R; Pla) is consistent with a distance measure
d if the following holds:

Pla([s0; : : : ; sn]) ! Pla([s00; : : : ; s0n]) if and only if there is some
j ! n such that sk = s0k for all 0 ^ k ^ j, sj+1 6= s0j+1, and d(sj; sj+1)
! d(sj; s0j+1).

Intuitively, we compare events of the form [s0; : : : ; sn] using a lexicographic
ordering based on d. Notice that this ordering focuses on the first point
of difference. Runs with a smaller change at this point are preferred, even
if later there are abnormal changes. This point is emphasized in the borrowed
car example below.

Pla is prefix-defined if the plausibility of an event is uniquely defined
by the plausibility of run-prefixes that are contained in it, so that

Pla(R['0; : : : ; 'm]) * Pla(R[0; : : : ; m]) if and only if for all [s0;
: : :; sm] ` R[0; : : : ; m] Gamma  R['0; : : : ; 'm] there is some [s00;
: : : ; s0m] ` R['0; : : : ; 'm] such that Pla([s00; : : : ; s0m]) ? Pla([s0;
: : : ; sm]).

140

Modeling Belief in Dynamic Systems. Part II. Roughly speaking, this requirement
states that we compare events by properties of dominance. This property is
similar to one satisfied by the plausibility measures that we get from preference
ordering using the construction of Proposition 2.2.

We define the set CU to consist of BCSs I = (R; ss; P) that satisfy the following
four requirements UPD1-UPD4. UPD1 says that there are only finitely many
possible truth assignments, and that there is a one-to-one map between environment
states and truth assignments.

UPD1 The set Phi e of propositions (of BCS1) is finite and ss is such that
for all environment states s, s0, if s 6= s0, then there is a formula ' 2
Le such that s j= ' and s0 j= :'.

UPD2-UPD4 are analogues to REV2-REV4. Like REV2, UPD2 puts constraints on
the form of the prior, but now we consider lexicographic priors of the form
described above.

UPD2 The prior of BCS5 is prefix defined and consistent with some distance
measure.

Recall that REV3 requires only that all truth assignments initially have
nontrivial plausibility. In the case of revision, the truth assignment does
not change over time, since we are dealing with static propositions. In the
case of update, the truth assignment may change over time, so UPD3 requires
that all consistent sequences of truth assignments have nontrivial plausibility.

UPD3 If 'i 2 Le, i = 0; : : :; k, are consistent formulas, then Pl(R['0;
: : : ; 'k]) ? ?.

Finally, like REV4, UPD4 requires that the agent gain no information from
her observations beyond the fact that they are true.

UPD4 Pla(R['0; : : : ; 'k+1; o1; : : : ; ok]) * Pla(R[0; : : :; m+1; o1;
: : :; om]) if and only if Pla(R['0; '1 ^ o1; : : : ; 'm ^ om; 'm+1]) * Pla(R[0;
1 ^ o1; : : :; m ^ om; m+1])

We remark that in the presence of REV1, UPD4 is equivalent to REV4. We might
consider generalized versions of UPD4, where the two sequences of formulas
can have arbitrary relative lengths; this version suffices for our purposes.
We can also define an analogue UPD40 in the spirit of REV40, which applies
only if Pl(R['0; : : : ; 'm+1; o1; : : : ; om]) ? ?.

We now show that CU corresponds to (KM) update. Recall that Katsuno and Mendelzon
define an update operator as mapping a pair of formulas (_; '), where _ describes
the agent's beliefs and ' describes the observation, to a new formula _ Pi
' that describes the agent's new beliefs. However, as we discussed in Section
3, when Phi e is finite, we can also treat Pi  mapping a belief state and
a formula to a new belief state. Also recall that Bel(I; sa) is the agent's
belief set when her local state is sa.

Theorem 6.2: A belief change operator Pi  satisfies U1-U8 if and only if
there is a system I 2 CU such that

Bel(I; sa) Pi   = Bel(I; sa Delta  )

for all epistemic states sa and formulas  2 Le.

141

Friedman & Halpern Proof: Roughly speaking, we show that any system in CU
corresponds to a Katsuno and Mendelzon update structure. Suppose that I =2
CU is such that the set of environment states is Se and the prior of BCS5
is consistent with distance function d. We define an update structure UI
. We then show that belief change in I corresponds to belief change in UI
in the sense of Theorem 6.1. Since Theorem 6.1 states that any belief change
operation defined by an update structure satisfies U1-U8, this will suffice
to prove the "if" direction of the theorem. To prove the "only if" direction
of the theorem, we show that that for any update structure U , there is a
system I 2 CU such that UI = U .

See Appendix A.2 for details. ut

This result immediately generalizes to sequences of updates.

Corollary 6.3: A belief change operator Pi  satisfies U1-U8 if and only
if there is a system IPi  2 CU such that for all 1; : : :; k 2 Le, we have

Bel(IPi ; sa) Pi  1 Pi  : : : Pi  k = Bel(IPi ; sa Delta  1 Delta
: : : Delta  k): These results show that for update, unlike revision, the
systems we consider are such that the belief state does determine the result
of the update, i.e., if Bel(I; sa) = Bel(I; s0a), then for any ' we get that
Bel(I; sa Delta  ') = Bel(I; s0a Delta  '). Roughly speaking, the reason
is that the distance measure that determines the prior does not change over
time. While this allows us to get an elegant representation theorem, it also
causes problems for the applicability of update, as we shall see below.

Note that, since the world is allowed to change, there is no problem if we
update by a sequence 1; : : : ; k of consistent formulas such that 1 ^ :
: : ^ k is inconsistent. There is no requirement that the formulas 1; : :
: ; k be true simultaneously. All that matters is that i is true at time
i. Also note that an update by an inconsistent formula does not pose a problem
for our framework. It follows from postulates U1 and U2 that once the agent
learns an inconsistent formula (i.e., false), she believes false from then
on.

How reasonable is the notion of update? As the discussion of UPD2 above suggests,
it has a preference for deferring abnormal events. This makes it quite similar
to Shoham's chronological ignorance (1988), and it suffers from some of the
same problems. Consider the following story, that we call the borrowed-car
example.11 At time 1, the agent parks her car in front of her house with
a full fuel tank. At time 2, she is in her house. At time 3, she returns
outside to find the car still parked where she left it. Since the agent does
not observe the car while she is inside the house, there is no reason for
her to revise her beliefs regarding the car's location. Since she finds it
parked at time 3, she still has no reason to change her beliefs. Now, what
should the agent believe when, at time 4, she notices that the fuel tank
is no longer full? The agent may want to consider a number of possible explanations
for her time-4 observation, depending on what she considers to be the most
likely sequence(s) of events between time 1 and time 4. For example, if she
has had previous gas leaks, then she may consider leakage to be the most
plausible explanation. On the other hand, if her spouse also has the car
keys, she may consider it possible that he used the car in her absence. Update,
however, prefers to defer abnormalities, so it will conclude that the

11. This example is based on Kautz's stolen car story (1986), and is due
to Boutilier, who independently

observed this problem [private communication, 1993].

142

Modeling Belief in Dynamic Systems. Part II. fuel must have disappeared,
for inexplicable reasons, between times 3 and 4. To see this, note that runs
where the car has been taken on a ride have an abnormality at time 2, while
runs where the car did not move at time 2 but the fuel suddenly disappeared,
have their first abnormality at time 4, and thus are preferred!

Suppose we formalize the example using propositions such as car-parked-outside,
fueltank-full, etc. Let the agent's belief set at time i be _i, i = 1; :
: : ; 4. Notice that _1 includes the belief that the car is parked in front
of the house with a full fuel tank. (That is, `Le _1 ) fuel-tank-full ^ car-parked-outside.)
At time 2 the agent makes no observations since she is in her house, so _2
= _1 Pi  true = _1 by U2. At time 3 the agent observes the car outside her
house, so _3 = _2 Pi  car-parked-outside = _1, again by U2. Finally, _4
= _3 Pi  :fuel-tank-full. The observation of :fuel-tank-full at time 4 must
be explained by some means. In our semantics, the answer is clear. The most
plausible runs are these where the car was parked until time 3, and somewhere
between time 3 and 4 some change occurred.

Is this counterintuitive conclusion an artifact of our representation? To
some extent it is. This issue cannot be formally addressed within Katsuno
and Mendelzon's semantic framework, since that framework does not provide
an account of sequences of changes. Moreover, one might argue that within
out framework there might be other families of priors that satisfy U1-U8,
which will offer alternative explanations of the surprising observation at
time 4. Nevertheless, we claim that our semantics captures, in what we believe
to be the most straightforward way, the intuition embedded in the Katsuno
and Mendelzon's representation. In particular, condition UPD2, which enforces
the delay of abnormal events, was needed in order to capture the "pointwise"
nature of the update. It would be interesting to know whether there is a
natural way of capturing update in our framework that does not suffer from
these problems.

Does this way of capturing update semantically ever lead to reasonable results?
Of course, that depends on how we interpret "reasonable". We briefly consider
one approach here.

In a world w, the agent has some beliefs that are described by, say, the
formula '. These beliefs may or may not be correct (where we say a belief
' is correct in a world w if ' is true of w). Suppose something happens and
the world changes to w0. As a result of the agent's observations, she has
some new beliefs, described by '0. Again, there is no reason to believe that
'0 is correct. Indeed, it may be quite unreasonable to expect '0 to be correct,
even if ' is correct. Consider the borrowed-car example. Suppose that while
the agent was sitting inside the house, the car was, in fact, taken for a
ride. Nevertheless, the most reasonable belief for the agent to hold when
she observes that the car is still in the parked after she leaves the house
is that it was there all along.

The problem here is that the information the agent obtains at times 2 and
3 is insufficient to determine what happened. We cannot expect all the agent's
beliefs to be correct at this point. On the other hand, if she does obtain
sufficient information about the change and her beliefs were initially correct,
then it seems reasonable to expect that her new beliefs will be correct.
But what counts as sufficient information?

We say that ' provides sufficient information about the change from w to
w0 if there is no world w00 satisfying ' such that d(w; w00) ! d(w; w0).
In other words, ' is sufficient information if, after observing ' in world
w, the agent will consider the real world (w0) one

143

Friedman & Halpern of the most likely worlds. Note that this definition is
monotonic, in that if ' is sufficient information about the change, then
so is any formula  that implies ' (as long as it holds at w0). Moreover,
this definition depends on the agent's distance function d. What constitutes
sufficient information for one agent might not for another. We would hope
that the function d is realistic in the sense that the worlds judged closest
according to d really are the most likely to occur.

We can now show that update has the property that if the agent has correct
beliefs and receives sufficient information about a change, then she will
continue to have correct beliefs.

Theorem 6.4: Let I 2 CU . If the agent's beliefs at (r; m) are correct and
o(r;m) provides sufficient information about the change from re(m) to re(m
+ 1), then the agent's beliefs at (r; m + 1) are correct.

Proof: Straightforward; left to the reader. ut

As we observed earlier, we cannot expect the agent to always have correct
beliefs. Nevertheless, we might hope that if the agent does (eventually)
receive sufficiently detailed information, then she should realize that her
beliefs were incorrect. But this is precisely what does not happen in the
borrowed-car example. Intuitively, once the agent observes that the fuel
tank is not full, this should be sufficient information to eliminate the
possibility that the car remained in the parking lot. However, it is not.
Roughly speaking, this is because update focuses only on the current state
of the world, and thus cannot go back and revise beliefs about the past.

The problem here is again due to the fact that belief update is determined
only by the agent's belief state and not her epistemic state. Thus, update
can only take into account the agent's current beliefs and not other information,
such as the sequence of observations that led to these beliefs. In our example,
if we limit our attention to beliefs about the car's whereabouts and the
fuel tank, then since the agent has the same belief state at time 1 and 3,
she must change her beliefs in the same manner at both times. This implies
that the observation the fuel tank is not full at time 4 cannot be sufficient
information about the past, since a fuel leak might be the most plausible
explanation of missing fuel at time 2.12

Our discussion of update shows that update is guaranteed to be safe only
in situations where there is always enough information to characterize the
change that has occurred. While this may be a plausible assumption in database
applications, it seems somewhat less reasonable in AI examples, particularly
in cases involving reasoning about action.13

7. Synthesis In previous sections we analyzed belief revision and belief
update separately. We provided representation theorems for both notions and
discussed issues specific to each notion. In this section, we try to identify
some common themes and points of difference.

12. In this example the usual intuition is that, given the observation that
the tank is not full, the agent

should revise her belief in some manner instead of performing update. This
immediately raises the question of how the agent knows what the right belief
change operation should be here. We return to this issue below. 13. Similar
observations were independently made by Boutilier (1996b), although his representation
is quite

different from ours.

144

Modeling Belief in Dynamic Systems. Part II. Restriction on Revision Update

Environment changes No change(Static propositions) All possible sequences

Initial plausibility Total preorder Lexicographic Belief change Conditioning
Conditioning

Table 1: A summary of the restrictions we impose to capture revision and
update. Katsuno and Mendelzon (1991a) focused on the following three differences
between AGM revision and KM update:

1. Revision deals with static propositions, while update allows propositions
that are not

static.

2. Revision and update treat inconsistent belief states differently. Revision
allows an

agent to "recover" from an inconsistent state after observing a consistent
formula. Update dictates that once the agent has inconsistent beliefs, she
will continue to have inconsistent beliefs. As we noted above, it seems that
revision's ability to recover from an inconsistent belief set leads to several
technical anomalies in iterated revision.

3. Revision considers only total preorders, while update allows partial preorders.

Our framework suggests a different approach to categorizing the differences
between revision and update (and other approaches to belief change): focusing
on the restrictions that have to be added to basic BCSs to obtain systems
in CR and CU , respectively. In particular, we focus on three aspects of
a system:

ffl How does the environment state change? ffl How does the agent form her
initial beliefs? What regularities appear in the agent's

beliefs at the initial state?

ffl How does the agent change her beliefs?

Table 1 summarizes the answers to these questions for revision and update;
it highlights the different restrictions imposed by each. Revision puts a
severe restriction on changes of the environment (more precisely, on how
we describe the environment in the language) and a rather mild restriction
on the agent's prior beliefs (they must form a total preorder). On the other
hand, update allows all sequences of environment states, but requires the
agent's prior beliefs to have a specific form. These formal properties match
the intuitive description of revision and update given in (Alchourr'on et
al., 1985; Katsuno & Mendelzon, 1991b). However, the explicit representation
of time in our framework allows us to make these intuitions precise. Moreover,
our framework makes explicit other assumptions made by revision and update.
For example, the lexicographic nature of update is not immediately evident
from the presentation in (Katsuno & Mendelzon, 1991b).

145

Friedman & Halpern The key point to notice in this table is that belief change
in both revision and update is done by conditioning. This observation, and
the naturalness of conditioning as a notion of change, support our claim
that conditioning should be adopted as semantic foundations for minimal change.

How significant are the differences between revision and update? We claim
that some of these differences are a result of different ways of modeling
the same underlying process. Recall that in the introduction we noted that
the restriction to static propositions is not such a serious limitation of
belief revision, since we can always convert a dynamic proposition to a static
one by adding timestamps. More precisely, we can replace a proposition p
by a family of propositions pm that stand for "p is true at time m". This
makes it possible to use revision to reason about a changing world. We now
show how revision and update can be related under this viewpoint.

To make this discussion precise, we need to introduce some formal definitions.
Let I = (R; ss; P) be a BCS. We "statify" I into a system ILambda  = (RLambda
; ssLambda ; PLambda ) by replacing the underlying language with static
propositions.

Let Phi Lambda e = fpm : p 2 Phi e; m 2 N g be a set of timestamped propositions
and let LLambda e be the logical language based on these propositions. We
can easily "timestamp" every formula in L. We define timestamp('; m) recursively
as follows. The base case is timestamp(p; m) = pm for p 2 Phi e. For standard
logical connectives, we simply apply the transformation recursively, for
example timestamp(' ^ ) = timestamp('; m) ^ timestamp(; m).

Next, we define the set of runs in the "statified" system. For each run r
2 R, we define a rLambda  in RLambda  as follows. The environment states
in rLambda  are defined to be the whole sequence of environment states in
r, that is, rLambda e(m) = re. If ra(m) = ho(r;1); : : : ; o(r;m)i, we define
ra(m) = htimestamp(o(r;1); 1); : : :; timestamp(o(r;m); m)i. We define the
interpretation ssLambda  in the obvious way: ssLambda (rLambda ; m)(pm

0) = true if and only if ss(r; m0)(p) = true and

ssLambda (rLambda ; m)(learn(')) = true if and only if o(rLambda ;m) =
'.

Finally, we need to define the prior plausibility PlLambda a. We define
this prior to be isomorphic to Pla under the transformation rLambda  7!
r. That is, for each set of runs RLambda  ` RLambda , we define PlLambda
a(RLambda ) = Pla(fr 2 R : rLambda  2 RLambda g).

It is clear that the two systems I and ILambda  describe the same underlying
process. Perhaps the most significant difference is that the environment
state in a run of ILambda  encodes the future of the run. This was necessary
so that the environment state could determine the truth of all propositions
of the form pm, so as to satisfy BCS1. Without this requirement, we could
have simply changed ss and left R and P unchanged.

Because different base languages are used in I and ILambda , the agent has
different beliefs in the two systems. It is easy to show that, for all '
2 Le, we have (I; r; m) j= B' iff (ILambda ; rLambda ; m) j= B(timestamp(';
m)). However, at (rLambda ; m) the agent also has beliefs about propositions
that describe past and future times. Thus, the set of beliefs of the agent
in ILambda  can be viewed as a superset of her beliefs in I at the corresponding
points.

The following result makes precise the relationship between I and ILambda
in terms of the properties we have been considering.

Proposition 7.1: Let I be a BCS and let ILambda  the transformed system
defined above. Then

ffl ILambda  is a BCS, that is, it satisfies BCS1-BCS5. ffl ILambda  satisfies
REV1.

146

Modeling Belief in Dynamic Systems. Part II. ffl If I satisfies UPD3, then
ILambda  satisfies REV3. ffl If I satisfies UPD4, then ILambda  satisfies
REV40.

Proof: Straightforward; left to the reader. ut

Thus, if I is a BCS, so is ILambda . Moreover, if I 2 CU , then ILambda
satisfies all but two of the requirements for CR. First, ILambda  does not
necessarily satisfy REV2, since the prior of systems in CU is, in general,
not ranked. Second, ILambda  satisfies REV40, the weaker version of REV4.
The reason for this is that runs ILambda  do not allow all sequences of
possible observations. Remember that in the language of LLambda e, the agent
can observe the proposition p2 (i.e., that p is true at time 2) at time 1.
However, in the original system, the agent only observes properties of the
current time. Thus, o(rLambda ;m) involves only propositions that deal with
time m.

Neither of these shortcomings is serious. First, variants of AGM revision
that involve partial orders were discussed in the literature (Katsuno & Mendelzon,
1991b; Rott, 1992). It is fairly straightforward to show that these can captured
in our systems using BCSs that satisfy REV1, REV3, and REV4. Second, it is
easy to add to ILambda  runs so as to get a system that satisfies REV4.
Moreover, we can do this is a way that does not change the agent's beliefs
for sequences of observations that can be observed in I. Thus, the "statified"
version of a system in CU displays behavior much in the spirit of belief
revision.

This result may seem somewhat surprising in light of the significant differences
between the AGM postulates and KM postulates. In part, it shows how much
is bound up in our choice of language. (Recall that similar issues arose
in Example 5.1.) This highlights the sensitivity of the postulate approach
to the modeling assumptions we make. Unfortunately, these modeling assumptions
are rarely discussed in the belief change literature. (See (Friedman & Halpern,
1998a) for a more detailed discussion of this point.)

Table 1 emphasizes that, despite the well-known differences between revision
and update, they can be viewed as sharing one very important feature: they
both use conditioning to do belief change. Thus, we have a common mechanism
both for understanding and extending them. To a certain extent, our results
show that revision is more general than update, in the sense that we can
view the statified version of any system in CU as performing revision (possibly
with unranked prior) over runs.

8. Extensions In the preceding sections, we introduced several assumptions
that were needed to capture revision and update. Of course, there are other
ways of capturing these notions that require somewhat different assumptions.
Nevertheless, these assumptions give insight into the underlying choices
made, either explicitly or implicitly, in the definition of revision and
update. In addition, thinking in terms of such restrictions makes it straightforward
to extend the intuitions of revision and update beyond the context where
they were originally applied. In this section, we consider a number of such
extensions, to illustrate our point.

147

Friedman & Halpern 8.1 Knowledge In many domains of interest, the agent knows
that some sequences of observations are impossible. We already saw in the
circuit-diagnosis problem that observing failures was impossible. In the
context of update, we know that we cannot observe a person die and then be
alive, despite the fact that both being dead and being alive are consistent
states.

We can easily maintain what we regard as the defining properties of revision
and update, as discussed in the previous section: no change in the environment
state and a ranked prior in the case of revision, and a lexicographic prior
in the case of update, with belief change proceeding by conditioning in both
cases. We simply drop REV3 and replace REV4 by REV40 (resp., drop UPD3 and
replace UPD4 and UPD40). We remark that this change affects the postulates.
For example, consider update. Suppose that the agent considers the possibility
that Mr. Bond is dead. If she then observes Mr. Bond alive and well then,
according to update, she must account for the new observation by some change
from the worlds she previously considered possible. However, there is no
transition from worlds in which Mr. Bond is dead that can account for the
new observation. Thus, once the agent knows that certain transitions are
impossible, some observations (e.g., observing that Mr. Bond is alive) require
her to remove from consideration some of the worlds that she previously considered
possible. As a consequence, postulate U8 does not hold, since the agent's
new beliefs are not determined by a pointwise update at each of the worlds
she previously considered possible. (Boutilier (1998) uses a related semantic
framework to draw similar conclusions in his analysis of update.)

8.2 Language of Beliefs In our analysis of revision and update, we focused
on the agent's beliefs about the current state of the environment. Often
we are also interested in how the agent changes her beliefs about other types
of statements, such as beliefs about future states of the environment, beliefs
about other agents' beliefs, and introspective beliefs about her own beliefs.
Again, it is straightforward in our framework to deal with an enriched language
that lets us express such statements. For example, in (Friedman & Halpern,
1994) we examine Ramsey conditionals. These are formulas of the form ' ?
, which can be read as saying "after learning ', the agent believes ". This
formula can be expressed as learn(') ) B in the language LKPT. As is well
known, if belief sets include Ramsey conditionals (and not just propositional
formulas), then the AGM postulates become inconsistent (at least, provided
we have at least three mutually exclusive consistent formulas in the language)
(G"ardenfors, 1986). Similar inconsistency results arise when one tries to
add other forms of introspective beliefs (Fuhrmann, 1989). In our setting,
it is easy to see why the problem arises. Even if we allow belief sets to
include nonpropositional formulas, it still seems quite clear that we want
to distinguish the propositional formulas from formulas that talk explicitly
about an agent's beliefs. For example, it is not clear that we should allow
an observation of a formula such as ' ? . What would it mean to observe such
a formula? It clearly seems quite different from observing a propositional
formula. Nor does it make sense to extend an assumption such as REV1 to arbitrary
formulas. While it may be reasonable to restrict to static propositions if
we are viewing these as making statements about a relatively stable

148

Modeling Belief in Dynamic Systems. Part II. environment, it seems far less
reasonable to assume that formulas that talk about an agent's beliefs will
be static, especially when we are trying to model belief change!

Of course, if we allow only propositional formulas to be learned (or observed),
and restrict REV1 to propositional formulas, then it is easy to see that
all of our results still hold, even if the full language is quite rich; we
avoid the triviality result completely.

8.3 Observations One of the strongest assumptions made by revision and update
involves the treatment of observations. This assumption seems unreasonable
in most domains. REV4 and UPD4 essentially assume that the observation that
the agent makes is chosen randomly among all formulas consistent with the
current state of the world. Suppose that ' says that the agent is outdoors,
says that the agent is in the basement, and o1 says that the basement light
is on. We may well have Pla(R[' ^ o1]) ? Pla(R[ ^ o1]). For example, the
agent may hardly ever go to the basement and frequently go outdoors, but
her children may often leave the basement light on. Nevertheless, we may
also have Pla(R['; o1]) ! Pla(R[; o1]), contradicting REV4. Indeed, it may
well be impossible for the agent to observe that the basement light is on
when she is outdoors, so that Pla(R['; o1]) = ?, but this is not permitted
according to REV4 or UPD4.

In many domains it is useful to reason about hidden quantities that simply
cannot be observed. For example, the event that component ci is faulty in
Example 5.1 is a basic event in our description of the problem, yet it cannot
be observed. Similarly, the event where a patient has a disease X or the
opponent is planning to capture the queen are useful in reasoning about medical
diagnosis and game strategy, yet are not directly observable in practice.
Thus, the requirement that all formulas in the language can be observed seems
quite unnatural. We note that explicitly modeling sensory input is a standard
practice in control theory and stochastic processes (e.g., in hidden Markov
chains). In these fields, one models the probability of an observation in
various situations. Making an observation increases the probability of situations
where that observation is likely to be observation and decreases the probability
of situations where it is unlikely. Again, it is straightforward to consider
a more detailed model of the observation process in our framework; see (Friedman,
1997, Chapter 6) and (Boutilier et al., 1998).

8.4 Actions Our definition of belief change systems essentially assumes that
the agent is passive. The situation is more complex when the agent can influence
the environment. The agent's choice of action interacts with her beliefs.
It is clear that after performing an action, the agent should change her
beliefs.14 Moreover, the information content of observations depends on the
action the agent has just performed. For example, the agent might consider
hearing a loud noise to be surprising. However, it would be expected after
the agent pulls the trigger of her gun.

14. Indeed, an alternative interpretation of the update postulates is that
they describe how the agent should

update her beliefs after doing the action "achieve '" (Goldszmidt & Pearl,
1996; del Val & Shoham, 1992, 1993). However, as these works show, the update
postulates are problematic under this interpretation.

149

Friedman & Halpern 8.5 Summary This list of possible extensions is clearly
not exhaustive; there are many others that we may want to consider. Nevertheless,
these are extensions that seem to be of interest. The main points we want
to make here are (1) it is easy to accommodate these extensions in our framework
while still maintaining the main characteristics of revision and update,
and (2) it is difficult to deal with such extensions if we focus on postulates.

9. Conclusion We have shown how the framework introduced in (Friedman & Halpern,
1997) can be used to capture belief revision and update. Modeling revision
and update in the framework also gives us a great deal of further insight
into their properties, and emphasizes the role of conditioning as a way of
capturing minimal change.

Of course, revision and update are but two points in a wide spectrum of possible
types of belief change. Our ultimate goal is to use this framework to understand
the whole spectrum better and to help us design belief change operations
that overcome some of the difficulties we have observed with revision and
update. In particular, we want belief change operations that can handle dynamic
propositions, while still being able to revise information about the past.

Our framework suggests how to construct such belief change operations. In
this framework, belief change operations can be determined by choosing a
plausibility measure that captures the agent's preferences among sequences
of worlds. This is the agent's prior plausibility, and captures her initial
beliefs about the relative likelihood of runs. As the agent receives information,
she changes her beliefs using conditioning. In this paper we show that revision
and update correspond to two specific families of priors. Clearly, however,
there are prior plausibilities that, when conditioned on a surprising observation,
allow the agent to revise some earlier beliefs and to assume that some change
has occurred. One obvious problem is that, even if there are only two possible
states, there are uncountably many possible runs. How can an agent describe
a prior plausibility over such a complex space?

One approach to doing this is based on intuition from the probabilistic settings.
In these settings, the standard solution to this problem is to assume that
state transitions are independent of when they occur, that is, that the probability
of the system going from state s to state s0 is independent of the sequence
of transitions that brought the system to state s. This Markov assumption
significantly reduces the complexity of the problem. All that is necessary
is to describe the probability of state transitions. In (Friedman & Halpern,
1996; Friedman, 1997) we define a notion of plausibilistic independence,
and show how to describe priors that satisfy the Markov assumption and the
consequences for belief change. See also (Boutilier, 1998; Boutilier et al.,
1998) for recent proposals along these lines.

Whether or not this particular approach turns out to be a useful one, it
is clear that these are the types of questions we should be asking. As these
works show, our framework provides a useful basis for answering them.

Finally, we note that our approach is quite different from the traditional
approach to belief change (Alchourr'on et al., 1985; G"ardenfors, 1988; Katsuno
& Mendelzon, 1991a). Traditionally, belief change was viewed as an abstract
process. Our framework, on the other hand, models the agent and the environment
she is situated in, and how both change in time.

150

Modeling Belief in Dynamic Systems. Part II. This allows us to model concrete
agents in concrete settings (for example, diagnostic systems are analyzed
in (Friedman & Halpern, 1997) and throughout this paper), and to reason about
the beliefs and knowledge of such agents. We can then investigate what plausibility
ordering induces beliefs that match our intuitions. By gaining a better understanding
of such concrete situations, we can better investigate more abstract notions
of belief change. More generally, we believe that, when studying belief change,
it is important to specify the underlying ontology: that is, exactly what
scenario underlies the belief-change process. We have specified one such
scenario here. While others are certainly possible, we view it as a defect
in the literature on belief change that the underlying scenario is so rarely
discussed. The framework we have introduced here provides a way of making
formal what the scenario is. (See (Friedman & Halpern, 1998a) for further
discussion of this issue.)

Acknowledgments The authors are grateful to Craig Boutilier, Ronen Brafman,
Adnan Darwiche, Moises Goldszmidt, Adam Grove, Alberto Mendelzon, Alvaro
del Val, and particularly Daphne Koller and Moshe Vardi, for comments on
drafts of this paper and useful discussions relating to this work. Some of
this work was done while both authors were at the IBM Almaden Research Center.
The first author was also at Stanford while much of the work was done. IBM
and Stanford's support are gratefully acknowledged. The work was also supported
in part by the Air Force Office of Scientific Research (AFSC), under Contract
F49620-91-C-0080 and grant F94620-96-1-0323 and by NSF under grants IRI-95-03109
and IRI-96-25901. The first author was also supported in part by an IBM Graduate
Fellowship and by Rockwell Science Center. A preliminary version of this
paper appears in J. Doyle, E. Sandewall, and P. Torasso (Eds.), Principles
of Knowledge Representation and Reasoning: Proc. Fourth International Conference,
1994, pp. 190-201, under the title "A knowledge-based framework for belief
change, Part II: revision and update."

Appendix A. Proofs A.1 Proofs for Section 5

We start with the proof of Theorems 5.2 and 5.3. To do this, we need some
preliminary definitions and lemmas. Figure 1 shows the general outline of
the intermediate representations we use in these proofs. Roughly speaking,
we show how to map from a revision operator ffi and a consistent belief set
K to a ranking, and similarly how to map from a ranking to an AGM revision
operator. These rankings correspond, in a direct way, to priors in systems
in CR, and thus have close connection to the beliefs of the agent in various
states.

These mapping between AGM revision operators and rankings are related to
the representation theorems of Boutilier (1994b), Grove (1988), and Katsuno
and Mendelzon (1991a). However, the exact details of our representations
are different than those of Boutilier, Grove, and Katsuno and Mendelzon.
Thus, for completeness we provide the full proofs here.

We start with the mapping from revision operator applied to a specific belief
set to a ranking. As an intermediate step we construct a set of defaults
as follows. We then will use the results from (Friedman & Halpern, 1998b)
to construct a ranked plausibility structure that satisfies these defaults.

151

Friedman & Halpern AGM Revision

K; ffi

Set of Defaults

Bel(I; sa)

CCLambda Lambda  CCLambda Lambda 

,,XX,,XX

,,XX

,,XX

PLI ,,XX

Lemma A.4

Lemma A.1

Lemma A.3

Lemma A.2

Ranked Structure

Characteristic

Structure

Figure 1: Schematic description of the entities and lemmas involved in the
proof of Theorems 5.2 and 5.3.

Lemma A.1: Let ffi be an AGM revision operator, let K ` Le be a consistent
belief set, and let

Delta (ffi;K) = f'! : ';  2 Le;  2 K ffi 'g:

Then the following is true:

(a) Delta (ffi;K) is closed under the rules of system P,

(b) '!false 62 Delta (ffi;K) for all consistent ' 2 Le, and (c) Delta (ffi;K)
satisfies rational monotonicity; that is, if '! 2 Delta (ffi;K) and '!:,
62 Delta (ffi;K),

then ' ^ ,! 2 Delta (ffi;K).

Proof: We start with part (a):

LLE Assume that `Le ' j '0 and that '! 2 Delta (ffi;K). Thus,  2 K ffi '.
From R5, it

follows that  2 K ffi '0, and thus '0! 2 Delta (ffi;K).

RW Assume that `Le  ) 0 and that '! 2 Delta (ffi;K). Thus,  2 K ffi '. Since
K ffi ' is a

belief set, it is closed under logical consequence. In particular, 0 2 K
ffi ', and hence '!0 2 Delta (ffi;K).

REF By R2, ' 2 K ffi ', and thus, '!' 2 Delta (ffi;K). AND Assume that '!1;
'!2 2 Delta (ffi;K). Thus, 1; 2 2 K ffi '. Since K ffi ' is a belief

set, 1 ^ 2 2 K ffi '. Thus, '!1 ^ 2 2 Delta (ffi;K).

OR Assume that '1!; '2! 2 Delta (ffi;K). There are two cases. If K ffi ('1
. '2) is

inconsistent, then  2 K ffi ('1 . '2) and thus '1 . '2! 2 Delta (ffi;K).
If K ffi ('1 . '2) is

152

Modeling Belief in Dynamic Systems. Part II. consistent, then, by R2, '1
. '2 2 K ffi ('1 . '2). Thus, we cannot have both :'1 and :'2 in K ffi ('1
. '2). Without loss of generality, assume that :'1 62 K ffi ('1 . '2). Using
R7 and R8, we get that K ffi (('1 . '2) ^ '1) = Cl(K ffi ('1 . '2) [ f'1g).
Using R6, we get that K ffi (('1 . '2) ^ '1) = K ffi '1. Thus, we conclude
that K ffi '1 = Cl(K ffi ('1 . '2) [ f'1g). Since '1! 2 Delta (ffi;K), we
have that  2 K ffi '1. Thus, we get that '1 )  2 K ffi('1.'2). If :'2 62
K ffi('1.'2), by similar arguments we get that '2 )  2 K ffi ('1 . '2). This
implies that ('1 . '2) )  2 K ffi ('1 . '2), and thus  2 K ffi ('1 . '2).
On the other hand, if :'2 2 K ffi ('1 . '2), then, since '1 . '2 2 K ffi
('1 . '2), we get that '1 2 K ffi ('1 . '2), and thus  2 K ffi ('1 . '2).

CM Assume that '!1; '!2 2 Delta (ffi;K). If K ffi ' is inconsistent, then
using R5 we get

that ' is inconsistent. Thus, ' ^ 1 is inconsistent, so 2 2 K ffi (' ^ 1).
Now assume that K ffi ' is consistent. Since '!1, we have that 1 2 K ffi
'. Since K ffi ' is consistent, we get that :1 62 K ffi '. Applying R8, we
get that K ffi ' ` K ffi (' ^ 1). Since '!2 2 Delta (ffi;K), we have that
2 2 K ffi '. Thus, 2 2 K ffi (' ^ 1). This implies that (' ^ 1)!2 2 Delta
(ffi;K).

We now prove part (b). Let ' 2 Le be a consistent formula. Then, using R5,
we get that K ffi ' is consistent. Thus, '!false 62 Delta (ffi;K).

Finally we prove part (c). Assume that '! 2 Delta (ffi;K), and ' ^ ,! 62
Delta (ffi;K). Since '! 2 Delta (ffi;K), we have that  2 K ffi '. Now if
:, 62 K ffi ', then, using R8, we have that Cl(K ffi ' [ f,g) ` K ffi ('
^ ,). This implies that  2 K ffi (' ^ ,). However, since we assumed that
' ^ ,! 62 Delta (ffi;K), we have that  62 K ffi (' ^ ,); thus, we get a
contradiction. We conclude that :, 2 K ffi '. Thus, '!:, 2 Delta (ffi;K).
ut

We now use this result to show that there exists a plausibility structure
that corresponds to ffi applied to K.

Lemma A.2: Let ffi be an AGM revision operator, and let K ` Le be a consistent
belief set. Then there is a plausibility structure PL = (W; Pl; ss) such
that Pl is ranked, PL j= '! if and only if  2 K ffi ', and Pl([[']]) ? ?
for all `Le-consistent formulas ' 2 Le.

Proof: We use the basic techniques described in the proof of (Friedman &
Halpern, 1998b, Theorem 8.2). Let Delta (ffi;K) be the set of defaults defined
by Lemma A.1. We now construct a plausibility space PL0 = (W; Pl0; ss) such
that PL0 j= '! if and only if '! 2 Delta (ffi;K). We define PL0 as follows:

ffl W = fwV : V ` Le is a maximal `Le-consistent setg, ffl ss(wV )(p) = true
if p 2 V , and ffl Pl0([[']]) * Pl0([[]]) if and only if (' . )!' 2 Delta
(ffi;K).

Using (Friedman & Halpern, 1998b, Lemma 4.1), we get that PL0 j= '! if and
only if '! 2 Delta (ffi;K). From Lemma A.1 (c) and and results of (Friedman
& Halpern, 1998b), it follows that there is a ranked plausibility measure
Pl that is default-isomorphic to Pl0, that is (W; Pl; ss) satisfies precisely
the same defaults as (W; Pl0; ss). Let PL = (W; Pl; ss).

Since PL is default-isomorphic to PL0, we have that PL j= '! if and only
if '! 2 Delta (ffi;K). Moreover, using Lemma A.1, we have that '! 2 Delta
(ffi;K) if and only if  2 K ffi '. Thus, PL j= '! if and only if  2 K ffi'.
Finally, let ' be a `Le-consistent formula. From

153

Friedman & Halpern Lemma A.1 (b), we get that '!false 62 Delta (ffi;K).
Since Delta (ffi;K) is closed under the rules of system P, we conclude that
(' . false)!false 62 Delta (ffi;K). Thus, Pl0([[']]) 6^ ? = Pl0([[false]]),
and thus Pl0([[']]) ? ?. Since Pl is default-isomorphic to Pl0, we conclude
that Pl([[']]) ? ?. ut

We now prove the converse to Lemma A.2.

Lemma A.3: Let PL = (W; Pl; ss) be a ranked plausibility structure such that
ss(w) is `Leconsistent for all worlds w, and PL 6j= '!false for all `Le-consistent
formulas ' 2 Le; let K = f' 2 Le : PL j= true!'g. Then there is an AGM revision
operator ffi such that  2 K ffi ' if and only if PL j= '!.

Proof: Let ffi be some belief change operation such that K ffi ' = f : PL
j= '!g. Since this requirement constrains only the result of applying ffi
to K, we can assume without loss of generality that ffi satisfies the AGM
postulates when applied to belief sets other than K. Thus, we need prove
only that ffi satisfies the AGM postulates for revision applied to K. (Note
that the proofs for R3 and R4 follow from the proofs for R7 and R8, respectively.)

R1 Since PL is qualitative, we have that f : PL j= '!g is a belief set, that
is, closed

under logical consequences.

R2 Axiom C1 implies that PL j= '!'. Thus, ' 2 K ffi '. R5 By our assumptions,
if ' is `Le-consistent, then Pl([[']]) ? ?, and thus PL 6j= '!false.

On the other hand, if ' is not `Le-consistent, then [[']] = ;, and thus Pl([[']])
= ?. We conclude that Pl([[']]) = ? if and only if `Le :'. This implies that
PL j= '!false if and only if `Le :'. Thus, K ffi ' = Cl(false) if and only
if `Le :'.

R6 Assume that `Le ' , '0. Then, by our assumption, ss(w)(') = ss(w)('0).
Thus,

[[' ^ ]] = [['0 ^ ]] for all formulas  2 Le. We conclude that PL j= '! if
and only if PL j= '0!. This implies that K ffi ' = K ffi '0.

R7 There are two cases: either Pl([[' ^ ]]) = ? or Pl([[' ^ ]]) ? ?. If Pl([['
^ ]]) =

?, then ' ^  is inconsistent. According to R2, we have that ' 2 K ffi '.
Thus, ' ^  2 Cl(K ffi ' [ fg). This implies that Cl(K ffi ' [ fg) contains
false, and thus K ffi (' ^ ) ` Cl(K ffi ' [ fg). If Pl([[' ^ ]]) ? ?, let
, 2 K ffi (' ^ ). We now show that , 2 Cl(K ffi ' [ fg). This will show that
K ffi (' ^ ) ` Cl(K ffi ' [ fg). Since , 2 K ffi (' ^ ), we get that PL j=
(' ^ )!,. Since Pl([[' ^ ]]) ? ?, we get that Pl([['^^,]]) ? Pl([['^^:,]]).
Then we have that Pl([['^( ) ,)]]) ? Pl([['^:( ) ,))]]), since (' ^  ^ ,)
) (' ^ ( ) ,)) and (' ^ :( ) ,)) ) (' ^  ^ :,). This also implies that Pl([[']])
? ?. Thus, PL j= '!( ) ,). So, ( ) ,) 2 K ffi ', and thus , 2 Cl(K ffi '
[ fg).

R8 Assume that : 62 K ffi '. Let , 2 Cl(K ffi ' [ fg). We now show that ,
2 K ffi (' ^ ).

This will show that Cl(K ffi ' [ fg) ` K ffi (' ^ ). Let A = [[' ^ :]], B
= [[' ^  ^ ,]], and C = [[' ^  ^ :,]]. It is easy to verify that these sets
are pairwise disjoint. Since ' ^ ( ) ,) j (' ^ :) . (' ^  ^ ,) and (' ^ :(
) ,)) j (' ^  ^ :,), we conclude that [[' ^ ( ) ,)]] = A [ B, and [[' ^ :(
) ,)]] = C. Since , 2 Cl(K ffi ' [ fg), we have that ( ) ,) 2 K ffi '. This
means that PL j= '!( ) ,). Thus, either

154

Modeling Belief in Dynamic Systems. Part II. Pl([[']]) = ? or Pl(A [ B) ?
Pl(C). If Pl([[']]) = ?, then according to A1, we get that Pl([[' ^ ]]) =
?. Thus, PL j= (' ^ )!, vacuously, and , 2 K ffi (' ^ ) as desired.

Now assume that Pl(A [ B) ? Pl(C). Since Pl is ranked, it satisfies A40 and
A50. According to A50, we get that either Pl(A) ? Pl(C) or Pl(B) ? Pl(C).
Assume that Pl(A) ? Pl(C) and Pl(B) 6? Pl(C). Then, using A40, we get that
Pl(A) ? Pl(B). Applying A2, we get that Pl(A) ? Pl(B [ C). However since
A = [[' ^ :]] and B [ C = [[' ^ ]], this implies that : 2 K ffi ', which
contradicts our assumption. Thus, we conclude that Pl(B) ? Pl(C). Since B
= [[' ^  ^ ,]] and C = [[' ^  ^ :,]], we get that PL j= (' ^ )!,, and thus
, 2 K ffi (' ^ ).

R3 and R4 Our definition of ffi implies that K ffi true = K. According to
R6, we have that

K ffi (true ^ ') = K ffi '. Combining these two facts, we get that R3 and
R4 are special cases of R7 and R8, respectively.

ut

These results show how to map between ranked plausibility structures and
AGM revision operators. We now relate systems in CR and ranked plausibility
structures. Let I = (R; ss; P) 2 CR. Recall that REV2 requires that the prior
of I be a ranking. Thus, we can construct a ranked plausibility structure
where worlds are runs in R. We define the characteristic structure of I to
be PLI = (R; Pla; ssPlI ), where Pla is the agent's prior over runs and ssPlI
(r)(p) = ss(r; 0)(p) for all p 2 Phi e. Note that [[']]PLI = R['].

We now use PLI to describe the beliefs of the agent in each local state.

Lemma A.4: Let I 2 CR and let sa = ho1; : : : ; omi. Then ' 2 Bel(I; sa)
if and only if PLI j= (Vmi=1 oi)!'. (By convention, if m = 0, we take (Vmi=1
oi) to be true.)

Proof: Let I 2 CR and let sa = ho1; : : : ; omi. There are two cases: either
sa is a local state in I, or it is not.

If sa is a local state in I, suppose that ra(m) = sa. Note that ' 2 Bel(I;
sa) if and only if Pl(r;m)([[']](r;m)) ? Pl(r;m)([[:']](r;m)). Recall that,
according to the definition of conditioning, Pl(r;m)(Delta ) is isomorphic
to Pla(Delta jR[Delta ; o1; : : : ; om]). Thus, Pl(r;m)([[']](r;m)) ? Pl(r;m)([[:']](r;m))
if and only if Pla(R['] j R[Delta ; o1; : : : ; om]) ? Pla(R[:'] j R[Delta
; o1; : : : ; om]). Using C1, this is true if and only if Pla(R['; o1; :
: : ; om]) ? Pla(R[:'; o1; : : :; om]). Using REV4, this is true if and only
if Pla(R[' ^ Vmi=1 oi]) ? Pla(R[:' ^ Vmi=1 oi]). We get that ' 2 Bel(I; sa)
if and only if Pla(R[' ^ Vmi=1 oi]) ? Pla(R[:' ^ Vmi=1 oi]). This implies
that ' 2 Bel(I; sa) if and only if PLI j= (Vmi=1 oi)!'.

If sa is not a local state in I, then R[Delta ; o1; : : : ; om] = ;, and
by definition Pla(R[Delta ; o1; : : : ; om]) = ?. Using C1 and REV4, we
get that PLa(R[Vmi=1 oi]) = ?, and thus PLI j= (Vmi=1 oi)!' for all ' 2 Le.
Since sa is not a local state in I, by definition Bel(I; sa) = Le. Hence,
we can conclude that ' 2 Bel(I; sa) if and only if PLI j= (Vmi=1 oi)!'. ut

We now show that given a ranked plausibility structure PL we can construct
a system whose characteristic structure is default-isomorphic to PL.

Lemma A.5: Let PLK = (WK; PlK; ssK) be a plausibility space that satisfies
the conditions of Lemma A.3. Then there is a system I 2 CR such that PLI
= PLK.

155

Friedman & Halpern Proof: Let PLK = (WK; PlK; ssK) be a plausibility space
that satisfies the conditions of Lemma A.3. For each world w 2 WK and sequence
of observations o1; o2; : : :, let rw;o1;o2;::: be the run defined so that
rw;o1;o2;:::e (m) = w and rw;o1;o2;:::a (m) = ho1; : : :; omi for all m.
Let R = frw;o1;o2;::: : ssk(w)(oi) = true for all ig. Define ss so that ss(r;
m)(p) = ssK(re(m))(p) for p 2 Phi e, and so that ss(r; m)(learn(')) = true
if o(r;m) = ' for ' 2 Le. Finally, define the prior plausibility Pla so that
Pla(R) = PlK(fw : 9r 2 R(w = re(0))g. It is easy to check that this definition
implies that Pla(R[']) = PlK([[']]PLK ). Thus, PLI = PLK . Since PlK is a
ranking, Pla is also a ranking and thus qualitative.

We now verify that the resulting interpreted system is indeed in CR. It is
easy to check that I is a belief change system; that is, it satisfies BCS1-BCS5.
The construction is such that re(m) = re(0) for all runs r and times m. Thus,
I satisfies REV1. Since the prior Pla is a ranking, this system also satisfies
REV2. Lemma A.2 implies that if ' is a consistent formula, then PlK([[']]PLK
) ? ?. This implies that Pla(R[']) ? ?, and thus the system satisfies REV3.
Finally, it is easy to show that Pla(R['; o1; : : : ; om]) = Pla(R[' ^ o1
^ : : : ^ om]) = PlK([[' ^ o1 ^ : : : ^ om]]PLK ). Thus, the system satisfies
REV4. ut

We are finally ready to prove Theorem 5.2. Theorem 5.2: Let ffi be an AGM
revision operator and let K ` Le be a consistent belief set. Then there is
a system I(ffi;K) 2 CR such that Bel(I(ffi;K); hi) = K and

Bel(I(ffi;K); hi) ffi ' = Bel(I(ffi;K); h'i) for all ' 2 Le. Proof: Let ffi
be an AGM revision operator and let K ` Le be a consistent belief set. By
Lemmas A.2 and A.5, there is a system I(ffi;K) = (R(ffi;K); ss(ffi;K); P(ffi;K))
2 CR such that PLI(ffi;K) j= '! if and only if  2 K ffi '. Our construction
is such that  2 K ffi ' if and only if PLI(ffi;K) j= '!. Using Lemma A.4,
we get that PLI(ffi;K) j= '! if and only if  2 Bel(I(ffi;K); h'i). Thus,
K ffi ' = Bel(I(ffi;K); h'i).

Finally, we show Bel(I(ffi;K); hi) = K. We start by showing that K ffi true
= K. Using R3, we get that K ffi true ` Cl(K [ ftrueg) = K. Since K is consistent,
by R4, Cl(K [ ftrueg) ` K ffi true. Thus, K ffi true = K. By Lemma A.4, we
have that Bel(I; hi) = Bel(I; htruei). Since Bel(I; htruei) = K ffi true,
we conclude that Bel(I(ffi;K); hi) = K. ut

We next prove Theorem 5.3. Theorem 5.3: Let I be a system in CR. Then there
is an AGM revision operator ffiI such that

Bel(I; hi) ffiI ' = Bel(I; h'i)

for all ' 2 Le.

Proof: Let I = (R; ss; P) be a system in CR. It is easy to verify that PLI
satisfies the conditions of Lemma A.3 with K = Bel(I; hi). This lemma implies
that there is a revision operator ffiI such that  2 K ffiI ' if and only
if PLI j= '!. Using Lemma A.4, we have that  2 Bel(I; h'i) if and only if
PlI j= '!. Thus, we have that K ffiI ' = Bel(I; h'i) for all formulas '.
ut

156

Modeling Belief in Dynamic Systems. Part II. Theorem 5.4: Let I be a system
in CR and sa = ho1; : : : ; omi be a local state in I. Then there is an AGM
revision operator ffiI;sa such that

Bel(I; sa) ffiI;sa ' = Bel(I; sa Delta  ') for all formulas ' 2 Le such
that o1 ^ : : : om ^ ' is consistent. Proof: The structure of the proof is
similar to that of Theorem 5.3. As in that proof, we construct a ranked plausibility
structure and use Lemma A.3 to find an AGM revision operator. The main difference
is that after observing '1; : : : ; 'k, some events are considered impossible.
Lemma A.3, however, requires that all possible formulas are assigned a positive
plausibility. We overcome this problem by assigning a "fictional" positive
plausibility to all non-empty events that are ruled out by the previous observations.

We proceed as follows. Let d0 be a new plausibility value that is less plausible
than all positive plausibilities in Pla; that is, if Pla(A) ? ?, then Pla(A)
? d0. Let I = (R; ss; P) 2 CR; let sa = ho1; : : :; omi. We define PL = (R;
Pl; ssPLI ), where Pl is such that Pl([[']]) = max(Pla(R[' ^ Vmi=1 oi]);
d0) for all consistent formulas '. This definition implies that if ' is consistent
with Vmi=1 oi, then Pl([[']]PL) = Pla(R['1 ^ Vmi=1 oi]).

We now prove that if ' is consistent with Vmi=1 oi, then PL j= '! if and
only if PLI j= (' ^ Vmi=1 oi)!.

For the "if" part, assume that PLI j= ('^Vmi=1 oi)!. Since ' is consistent
with Vmi=1 oi it follows, from REV3, that Pla(R[' ^ (Vmi=1 oi])) ? ?. Thus,
Pla(R[(' ^ (Vmi=1 oi)) ^ ]) ? Pla(R[(' ^ (Vmi=1 oi)) ^ :]) * ?. Thus, ' ^
is consistent with Vmi=1 oi. This implies that Pl([[' ^ ]]) = Pla(R[(' ^
(Vmi=1 oi)) ^ ] ? max(d0; Pla(R[(' ^ (Vmi=1 oi)) ^ :]) = Pl([[' ^ :]]). We
conclude that PL j= '!.

For the "only if" part, assume that PLI 6j= (' ^ (Vmi=1 oi))!. This implies
that Pla(R[(' ^ (Vmi=1 oi)) ^ ]) 6? Pla(R[(' ^ (Vmi=1 oi)) ^ :]). Since Pla
is a ranking, it follows that Pla(R[(' ^ (Vmi=1 oi))]) ^ Pla(R[(' ^ (Vmi=1
oi)) ^ :]). Since ? ! Pla(R[' ^ (Vmi=1 oi)]) = max(Pla(R[(' ^ (Vmi=1 oi))
^ ]); Pla(R[(' ^ (Vmi=1 oi)) ^ :])), we have that Pla(R[(' ^ (Vmi=1 oi))
^ :]) ? ?. We conclude that Pl([[' ^ :]]) * Pl([[' ^ ]]). Thus, PL 6j= '!.

It is easy to verify that PL is ranked, and satisfies the requirements of
Lemma A.3. Thus, there exists a revision operator ffiI;sa such that  2 K
ffiI;sa ' if and only if PL j= '!, where K = f' : PL j= true!'g. Moreover,
since for all ' consistent with Vmi=1 oi we have thatPL j= '! if and only
if PLI j= (' ^ (Vmi=1 oi))!, then, from Lemma A.4, it follows that K = Bel(I;
sa) and that if ' is consistent with Vmi=1 oi, then PL j= '! if and only
if  2 Bel(I; sa Delta  '). ut

Theorem 5.5: Let I be a system in CR whose local states are ELe. There is
a function BelI that maps epistemic states to belief states such that

ffl if sa is a local state of the agent in I, then Bel(I; sa) = BelI (sa),
and ffl (ffi; BelI ) satisfies R10-R80.

Proof: As we said earlier, roughly speaking, we define BelI (sa) = Bel(I;
sa) when sa is a local state in I. If sa is not in I, then we set BelI (sa)
= Bel(I; s0), where s0 is the longest

157

Friedman & Halpern consistent suffix of sa. We now make this definition precise,
and show that the resulting BelI satisfies R10-R80.

We proceed as follows. We define a function f (Delta ) that maps sequences
of observations to suffixes as follows:

f (ho1; : : : ; omi) =

8???!

???:

hi if m = 0, hfalsei if m ? 0 and om is inconsistent, hok; : : : ; omi otherwise,
with k ^ m the minimal index

s. t. 6`Le :(ok ^ : : : ^ om).

Aside from the special case where om is inconsistent, we simply choose the
longest suffix of sa that is still consistent. We define BelI (sa) = Bel(I;
f (sa)). Clearly, if sa is a local state in I, then f (sa) = sa, so BelI
(sa) = Bel(I; sa).

We now have to show that (ffi; BelI) satisfies R10-R80. The proof outline
is as follows. Given a particular state sa, we construct a ranked plausibility
structure that corresponds, in the sense of Lemma A.2, to belief change from
sa. We then use Lemma A.3 to show that belief changes from sa satisfies the
AGM postulates, i.e., R1-R8. Since this is true from any sa, we get that
BelI satisfies R10-R80.

Let sa = ho1; : : : ; omi. We define a ranked plausibility space that has
the following structure. The most plausible events are the ones consistent
with o1 ^ : : : ^ om. They are ordered according to the prior ranking conditioned
on o1 ^ : : : ^ om. The next tier of events are those that are inconsistent
with o1 ^ : : : ^ om but are consistent o2 ^ : : : ^ om. Again, these are
ordered according to the prior ranking conditioned on o2 ^ : : : ^ om. We
continue this way; the last tier consists of all events that are inconsistent
with om.

Formally, let PL = (R; Pl; ssPLI ), where Pl is such that Pl([[']]) * Pl([[]])
if Pla(R[' ^ (Vmi=k oi])) * Pla(R[ ^ (Vmi=k oi])) where k ^ m + 1 is the
greatest integer such that for all j ! k, ' and  are both inconsistent with
Vmi=j oi. It is easy to see that PL is ranked, and that if ' is consistent,
then Pl([[']]) ? ?.

Let ' 2 Le. We now show that PL j= '! if and only if  2 BelI (sa Delta 
'). If ' is inconsistent, then PL j= '! for all . Moreover, since ' is inconsistent,
f (saDelta ') = hfalsei, and thus BelI (sa Delta  ') = Le. We conclude
that '! if and only if  2 BelI (sa Delta  '). If ' is consistent, then let
k ^ m+1 be the greatest integer such that for all j ! k, ' is inconsistent
with Vmi=j oi. It is easy to verify that f (sa Delta ') = hok; : : :; om;
'i. From Lemma A.4, it follows that  2 BelI (sa Delta  ') = Bel(I; hok;
: : : ; om; 'i) if and only if Pla(R[(' ^ (Vmi=k oi)) ^ ]) ? Pla(R[(' ^ (Vmi=k
oi)) ^ :]). We now show that this is the case if and only if PL j= '!. Suppose
that PLa(R[(' ^ ^(Vmi=k oi)) ^ ]) ? PLa(R[(' ^ (Vmi=k oi)) ^ :]). Then, clearly,
Pla(R[(' ^ (Vmi=k oi)) ^ ]) ? ?, and thus ' ^  is consistent with ok; : :
: ; om. Since both ' ^  and ' ^ : are inconsistent with oj; : : : ; om for
all j ! k, we have that Pl([[' ^ ]]) ? Pl([[' ^ :]]). On other hand, if Pla(R[('
^ (Vmi=k oi)) ^ ]) 6? Pla(R[(' ^ (Vmi=k oi)) ^ :]), then since Pla is a ranking
PLa(R[(' ^ (Vmi=k oi)) ^ ]) ^ PLa(R[(' ^ (Vmi=k oi)) ^ :]). Moreover, since
' is consistent with ok ^ : : : ^ om, we have that Pla(R[' ^ (Vmi=k oi)])
? ?. This implies that Pla(R[(' ^ (Vmi=k oi)) ^ :]) ? ? and thus Pl([[' ^
]]) ^ Pl([[' ^ :]]). We conclude that PL j= '! if and only if  2 BelI (sa
Delta  ').

By Lemma A.3, there is a revision operator ffisa that satisfies R1-R8 such
that  2 K ffi ' if and only if PL j= '!. It is not hard to check that this
implies that the change from BelI (sa) to BelI (sa Delta  ') satisfies R10-R80.
ut

158

Modeling Belief in Dynamic Systems. Part II. Proposition 5.6: Let I be a
system in CR whose local states are ELe . There is a function BelI that maps
epistemic states to belief states such that

ffl if sa is a local state of the agent in I, then Bel(I; sa) = BelI (sa),
and ffl (ffi; BelI ) satisfies R10-R90.

Proof: As we said in the main text, we show that the function BelI defined
in the proof of Theorem 5.5 satisfies R90. Let sa = ho1; : : : ; omi, and
let ';  2 Le be formulas such that 6`Le :(' ^ ). Since ' is consistent with
, we get that f (sa Delta  ' Delta  ) = hok; : : : ; om; '; i, where k
^ m is the least integer such that ' ^  is consistent with ok; : : : ; om.
For the same reason, we get that f (sa Delta  ' ^ ) = hok; : : : ; om; '
^ i. Using Lemma A.4 we immediately get that Bel(I; hok; : : :; om; '; i)
= Bel(I; hok; : : :; om; ' ^ i). Thus, we conclude that BelI (sa Delta 
' Delta  ) = BelI(sa Delta  ' ^ ). ut

Theorem 5.7: Given a function BelLe mapping epistemic states in ELe to belief
sets over Le such that BelLe (hi) is consistent and (BelLe; ffi) satisfies
R10-R90, there is a system I 2 CR whose local states are in ELe such that
BelLe(sa) = Bel(I; sa) for each local state sa in I.

Proof: We show that Bel(I; sa) = BelLe(sa) for local states sa in I, where
I is the system guaranteed to exist by Theorem 5.2 such that Bel(I; hi) =
BelLe(hi) and Bel(I; h'i) = BelLe(h'i) for all ' 2 Le. We prove this by induction
on the length m of sa. For m ^ 1, this is true by our choice of I. For the
induction case, let sa = ho1; : : : ; omi be a local state in I. Thus,, o1
^ : : : ^ om is consistent. From R90, it follows that BelLe(ho1; : : : ;
omi) = BelLe(ho1; : : : ; omGamma 2; omGamma 1 ^ omi). Using the induction
hypothesis, we have that BelLe(ho1; : : : ; omGamma 2; omGamma 1 ^ omi)
= Bel(I; ho1; : : :; omGamma 2; omGamma 1 ^ omi). Using Lemma A.4, we get
that Bel(I; ho1; : : :; omGamma 2; omGamma 1 ^ omi) = Bel(I; ho1; : : :
; omi). Thus, we conclude that BelLe(ho1; : : :; omi) = Bel(I; ho1; : : :
; omi). ut

A.2 Proofs for Section 6 In this section we prove Theorem 6.2. We now show
that any system in CU corresponds to an update structure. Suppose that I
= (R; ss; P) 2 CU is such that the set of environment states is Se and the
prior of BCS5 is consistent with distance function d. Define an update structure
UI = (Se; sse; d), where for p 2 Phi e, sse(se)(p) = ss((se; sa))(p) for
some choice of sa. By BCS1, the choice of sa does not matter. It is easy
to see that UPD1 ensures that Se and sse satisfy the requirements of the
definition of update structures. We want to show that belief change in I
corresponds to belief change in UI in the sense of Theorem 6.1. Since Theorem
6.1 states that any belief change operation defined by an update structure
satisfies U1-U8, this will suffice to prove the "if" direction of Theorem
6.2. To prove the "only if" direction of Theorem 6.2, we show that that for
any update structure U , there is a system I 2 CU such that UI = U .

We start with preliminary definitions and lemmas for the "if" direction of
Theorem 6.2. Let sa = ho1; : : : ; omi. We define States(I; sa) = fs 2 Se
: s j= , for all , 2 Bel(I; sa)g. Clearly, if ' is such that Bel(I; sa) =
Cl('), then States(I; sa) = [[']]UI. To show that belief change in I corresponds
to belief change in UI we have to show that

States(I; sa Delta  ) = minUI (States(I; sa); [[]]UI):

159

Friedman & Halpern This is proved in Lemma A.8. To prove this lemma, we need
some preliminary lemmas. Lemma A.6: Let I 2 CU , and let sa = ho1; : : :;
omi. Then ' 2 Bel(I; sa) if and only if (I; r; 0) j= (flo1 ^ : : : ^ flmom)!flm'
for some run r in R.

Proof: The proof of this lemma is analogous to the proof of Lemma A.4, using
UPD3 and UPD4 instead of REV3 and REV4. We do not repeat the argument here.
ut

We now provide an alternative characterization of States(I; sa) in terms
of the agent's prior on run-prefixes.

Lemma A.7: Let I 2 CU and let sa = ho1; : : : ; omi. Then sm 2 States(I;
sa) if and only if there is a sequence of states [s0; : : : ; sm] ` R[true;
o1; : : : ; om] such that Pla([s0; : : : ; sm]) 6! Pla(R[true; o1; : : :
; om] Gamma  [s0; : : : ; sm]).

Proof: For the "if" direction, assume that there is a sequence s0; : : :
; sm such that [s0; : : :; sm] ` R[true; o1; : : : ; om], and Pla([s0; :
: : ; sm]) 6! Pla(R[true; o1; : : : ; om] Gamma  [s0; : : :; sm]). By way
of contradiction, assume that sm 62 States(I; m). Thus, there is a formula
, 2 Bel(I; m) such that sm j= :,. From Lemma A.6 it follows that since ,
2 Bel(I; sa), (I; r; 0) j= (flo1 ^: : :^flmom)!flm, for some run r in R.
From the definition of conditioning it follows that Pla(R[true; o1; : : :
; omGamma 1; om ^ ,]) ? Pla(R[true; o1; : : : ; omGamma 1; om ^ :,]). Since
sm j= :,, we get that [s0; : : : ; sm] ` R[true; o1; : : : ; omGamma 1;
om ^ :,] and that R[true; o1; : : :; omGamma 1; om ^ ,] ` R[true; o1; :
: : ; om] Gamma  [s0; : : : ; sm]. From A1, it follows that Pla([s0; : :
: ; sm]) ! Pla(R[true; o1; : : : ; om] Gamma  [s0; : : : ; sm]), which contradicts
our starting assumption. We conclude that sm 2 States(I; sa).

For the "only if" direction, assume that sm 2 States(I; a). Since Se is finite
and sse assigns a different truth assignment to each state in Se, there is
a formula , 2 Le that characterizes sm; that is, s j= , if and only if s
= sm. Since sm 2 States(I; sa), we have that :, 62 Bel(I; sa). Using Lemma
A.6, we get that (I; r; 0) 6j= (flo1 ^ : : : ^ flmom)!flm:, for all runs
r 2 R. By BCS5, this is true if and only if Pla(R[true; o1; : : : ; om])
? ? and Pla(R[true; o1; : : : ; omGamma 1; om ^ ,]) 6! Pla(R[true; o1; :
: :; omGamma 1; om ^ :,]). By UPD2, there is a sequence [s0; : : : ; sm]
` R[true; o1; : : : ; omGamma 1; om ^ ,] such that Pla([s0; : : : ; sm])
6! Pla([s00; : : : ; s0m]) for all [s00; : : : ; s0m] ` R[true; o1; : : :
; omGamma 1; om ^ :,]. Moreover, without loss of generality, we can assume
that Pla([s0; : : : ; sm]) 6! Pla([s00; : : :; s0m]) for all [s00; : : :;
s0m] ` R[true; o1; : : :; omGamma 1; om ^ ,], since there are only finitely
many such sequences. Thus, by UPD2, Pla([s0; : : : ; sm]) 6! Pla(R[true;
o1; : : : ; om] Gamma  [s0; : : : ; sm]). ut

We can now prove that belief change in I corresponds to belief change in
UI .

Lemma A.8: Let I = (R; ss; P) 2 CU Then

States(I; sa Delta  ) = minUI (States(I; sa); [[]]UI) for all local states
sa and formulas  2 Le. Proof: Let Pla be the prior in I; assume that Pla
consistent with a distance function d. Let sa = ho1; : : :; omi.

160

Modeling Belief in Dynamic Systems. Part II. To show that minUI (States(I;
sa); [[]]UI) ` States(I; sa Delta  ), suppose that s 2 minUI (States(I;
sa); [[]]UI). Thus, there is a state sm 2 States(I; sa) such that d(sm; s0)
6! d(sm; s) for all states s0 that satisfy . We want to show that s 2 States(I;
sa Delta  ). From Lemma A.7, it follows that, since sm 2 States(I; sa),
there is a sequence s0; : : : ; smGamma 1 such that [s0; : : : ; sm] 2 R[true;
o1; : : : ; omGamma 1; om] and Pla([s0; : : : ; sm]) 6! Pla(R[true; o1;
: : : ; omGamma 1; om] Gamma  [s0; : : :; sm]). We now show that Pla([s0;
: : : ; sm; s]) 6! Pla(R[true; o1; : : : ; om; ] Gamma  [s0; : : : ; sm;
s]). By Lemma A.7, this suffices to show that s 2 States(I; sa Delta  ).
Suppose that [s00; : : : ; s0m+1] ` R[true; o1; : : : ; om; ] Gamma  [s0;
: : :; sm; s]. If [s0; : : : ; sm] = [s00; : : :; s0m], then we have that
d(s0m; s0m+1) 6! d(sm; s). Since Pla is consistent with d, it follows that
Pla([s0; : : : ; sm; s]) 6! Pla([s00; : : : ; s0m; s0m+1]). If [s0; : : :
; sm] 6= [s00; : : :; s0m], then, since Pla([s0; : : :; sm]) 6! Pla([s00;
: : : ; s0m]) and Pla is consistent with d, we have that Pla([s0; : : : ;
sm; s]) 6! Pla([s00; : : :; s0m; s0m+1]).

Since Pla([s0; : : : ; sm; s]) 6! Pla([s00; : : : ; s0m; s0m+1]) for all
[s00; : : : ; s0m+1] ` R[true; o1; : : :; om; ] Gamma  [s0; : : :; sm; s]
and Pla is prefix-defined, we have that Pla([s0; : : : ; sm; s]) 6! Pla(R[true;
o1; : : :; om; ] Gamma  [s0; : : : ; sm; s]. By Lemma A.7, s 2 States(I;
sa Delta  ), as desired.

To show that States(I; sa Delta  ) ` minUI (States(I; sa); [[]]UI), suppose
that s 2 States(I; sa Delta  ). By Lemma A.7, there is a sequence s0; :
: : ; sm such that [s0; : : :; sm; s]) ` R[true; o1; : : :; om; ] and Pla([s0;
: : : ; sm; s]) 6! Pla(R[true; o1; : : : ; om; ] Gamma  [s0; : : : ; sm;
s]). We want to show that sm 2 States(I; sa) and that d(sm; s0) 6! d(sm;
s) for all s0 that satisfy . This suffices to prove that s 2 minUI (States(I;
sa); [[]]UI).

To show that sm 2 States(I; sa), by Lemma A.7, it suffices to show that Pla([s0;
: : : ; sm]) 6! Pla(R[true; o1; : : : ; om] Gamma  [s0; : : : ; sm]). Let
s00; : : : ; s0m be a sequence such that [s00; : : : ; s0m] ` R[true; o1;
: : :; om]. By definition, [s00; : : :; s0m; s] ` R[true; o1; : : : ; om;
]. Thus, from our choice of s0; : : : ; sm, it follows that Pla([s0; : :
: ; sm; s]) 6! Pla([s00; : : : ; s0m; s]). Since Pla is consistent with d,
it follows that Pla([s0; : : : ; sm]) 6! Pla([s00; : : : ; s0m]). Thus, by
Lemma A.7, sm 2 States(I; sa). To see that d(sm; s0) 6! d(sm; s) for all
s0 that satisfy , let s0 6= s be such that s0 j= . Thus, [s0; : : : ; sm;
s0] ` [true; o1; : : : ; om; ]. From our choice of s0; : : : ; sm, it follows
that Pla([s0; : : :; sm; s]) 6! Pla([s0; : : : ; sm; s0]). Since Pla is consistent
with d, it follows that d(sm; s0) 6! d(sm; s). We conclude that s 2 minUI
(States(I; sa); [[]]UI). ut

We now have the tools to prove the "if" direction of Theorem 6.2.

Lemma A.9: If I = (R; ss; P) 2 CU , then there is a belief change operator
Pi  that satisfies U1-U8 such that

Bel(I; sa) Pi   = Bel(I; sa Delta  )

for all local states sa and formulas  2 Le.

Proof: Let I 2 CU . Using the arguments we presented above, it easy to check
that UI is an update structure. By Theorem 6.1, there is a belief change
operator Pi  that satisfies U1-U8 such that [[' Pi  ]]UI = minUI ([[']]UI;
[[]]UI) for all ';  2 Le. From Lemma A.8, it follows that Bel(I; sa) Pi
= Bel(I; sa Delta  ): ut

We now prove the "only if" direction of Theorem 6.2. Suppose that Pi  is
a belief change operator that satisfies U1-U8. According to Theorem 6.1,
there is an update structure UPi  that corresponds to Pi . Thus, it suffices
to show that there is a system I such that UI = UPi .

161

Friedman & Halpern Lemma A.10: Let U = (W; d; ssU) be an update structure.
Then there is a system I 2 CU such that UI = U .

Proof: Given the sequences w0; w1; : : : 2 W and o1; o2; : : : 2 Le, let
rw0;w1;:::;o1;o2;::: be the run defined so that rw0;w1;:::;o1;o2;:::e (m)
= wm and rw0;w1;:::;o1;o2;:::a (m) = ho1; : : : ; omi. Let R = frw0;w1;:::;o1;o2;:::
: ssU (wm)(om) = true for all mg. Define ss such that ss(r; m)(p) = ssU (re(m))(p)
for p 2 Phi e and ss(r; m)(learn(')) = true if o(r;m) = ' for ' 2 Le.

It is clear that (R; ss) satisfies BCS1-BCS4 and UPD1. Thus, all that remains
to show is that there is a prior plausibility measure Pla that satisfies
UPD2-UPD4. This will ensure that (R; ss; P) 2 CU .

We proceed as follows. We define a preferential space (R; OE) where r OE
r0 if and only if there is some m such that re(k) = r0e(k) for all 0 ^ k
^ m, re(m + 1) 6= r0e(m + 1), and d(re(m); re(m+1)) ! d(r0e(m); r0e(m+1)).
Recall that r OE r0 denotes that r is preferred over r0. Thus, this ordering
is consistent with the comparison of events of the form [s0; : : :; sn] according
to UPD2.

Using the construction of Proposition 2.2, there is a plausibility space
(R; Pla) such that Pla(A) * Pla(B) if and only if for all r 2 B Gamma  A,
there is a run r0 2 A such that r0 OE r and there is no r00 2 B Gamma  A
such that r00 OE r0. By (Friedman & Halpern, 1998b, Theorem 5.5), Pla is
a qualitative plausibility measure. We now show that it satisfies UPD2-UPD4.

We start with UPD2. To show that PlA is consistent with d, we need to show
that Pla([s0; : : : ; sn]) ! Pla([s00; : : : ; s0n]) if and only if there
is some m ! n such that sk = s0k for all 0 ^ k ^ m, and d(sm; sm+1) ? d(s0m;
s0m+1). Suppose that Pla([s0; : : : ; sn]) ! Pla([s00; : : : ; s0n]). Let
r be some run in [s0; : : : ;0n ]. Without loss of generality we can assume
that re(m) = re(n) for all m ? n. Since Pla([s0; : : : ; sn]) ! Pla([s00;
: : :; s0n]), there is a run r0 2 [s00; : : :; s0n] such that r0 OE r. By
definition, this implies that there is an m such that re(k) = r0e(k) for
all 0 ^ k ^ m, and d(r0e(m); r0e(m + 1)) ! d(re(m); re(m + 1)). We claim
that m ! n. For if m * n, then re(m+1) = re(m) by construction, so d(re(m);
re(m+1)) = d(re(m); re(m)) ^ d(r0e(m); r0e(m + 1)) and r0 6OE r, a contradiction.
Thus, sk = s0k for all 0 ^ k ^ m, d(s0m; s0m+1) ! d(sm; sm+1).

For the converse, suppose that there is an m ! n such that sk = s0k for all
0 ^ k ^ m, and d(s0m; s0m+1) ! d(sm; sm+1). Let r0 be the run where r0e(k)
= s0k for k ^ n, r0e(k) = s0n for k * n, and o(r0;k) = true for all k. It
follows r0 OE r for all runs r0 2 [s0; : : :; sn]. Thus, Pla([s0; : : : ;
sn]) ! Pla([s00; : : : ; s0n]).

To show that Pla is prefix-defined, we must show that Pla(R['0; : : : ; 'n])
* Pla(R[0; : : : ; n]) if and only if for all [s0; : : : ; sn] ` R[0; : :
: ; n] Gamma  R['0; : : : ; 'n], there is some [s00; : : :; s0n] ` R['0;
: : :; 'n] such that Pla([s00; : : : ; s0n]) ? Pla([s0; : : :; sn]). Suppose
that Pla(R['0; : : : ; 'n]) * Pla(R[0; : : :; n]). Let [s0; : : : ; sn] `
R[0; : : :; n] Gamma  R['0; : : :; 'n]. Let r 2 [s0; : : : ; sn] be a run
such that re(m) = re(n) for all m * n. Since Pla(R['0; : : : ; 'n]) * Pla(R[0;
: : :; n]) there is a run r0 2 R['0; : : : ; 'n] such that r0 OE r. This
implies that there is an m such that re(k) = r0e(k) for all 0 ^ k ^ m, and
d(r0e(m); r0e(m + 1)) ! d(re(m); re(m + 1)). As before, we have that m !
n, and thus Pla([r0e(0); : : : ; r0e(n)]) ? Pla([s0; : : :; sn]). Since r0
2 R['0; : : :; 'n], we also have that [r0e(0); : : :; r0e(n)] ` R['0; : :
:; 'n], as desired.

For the converse, assume that for all [s0; : : : ; sn] ` R[0; : : : ; n]
Gamma  R['0; : : : ; 'n] there is some [s00; : : : ; s0n] ` R['0; : : :
; 'n] such that Pla([s00; : : : ; s0n]) ? Pla([s0; : : : ; sn]). This implies
that Pla(R['0; : : : ; 'n]) ? Pla([s0; : : : ; sn]) for all for all [s0;
: : : ; sn] ` R[0; : : :; n] Gamma 

162

Modeling Belief in Dynamic Systems. Part II. R['0; : : :; 'n]. Since there
are only finitely many sequences of states of length m, we can apply A2,
and conclude that Pla(R['0; : : :; 'n]) ? Pla(R[0; : : :; n] Gamma  R['0;
: : :; 'n]). Thus, Pla(R['0; : : :; 'n]) * Pla((R[0; : : : ; n])).

For UPD3, recall that the construction of Proposition 2.2 is such that Pla(R)
? ? for all non-empty R ` R. Since, by our construction, the set R['0; :
: : ; 'n] is non-empty for all sequences '0; : : : ; 'n of consistent formulas,
UPD3 must hold.

Finally, we consider UPD4. We have to show that Pla(R['0; : : :; 'n+1; o1;
: : : ; on]) * Pla(R[0; : : :; n+1; o1; : : :; on]) if and only if Pla(R['0;
'1^o1; : : : ; 'n^on; 'n+1]) * Pla(R[0; 1^ o1; : : : ; n^on; n+1]). By construction,
R['0; : : : ; 'n+1; o1; : : : ; on] ` R['0; '1^o1; : : : ; 'n^ on; 'n+1].
On the other hand, for each run r 2 R['0; '1 ^ o1; : : : ; 'n ^ on; 'n+1]
there is a run r0 2 R['0; : : : ; 'n+1; o1; : : :; on] such that r0e(m) =
re(m) for all m, and o(r;m) = om for 1 ^ m ^ n. Since the preference ordering
on runs is a function only of the environment states, it is clear that r
and r0 are compared in the same manner; that is for all r00, r00 OE r if
and only if r00 OE r0, and r OE r00 if and only if r0 OE r00. Thus, we conclude
that for the purposes of the preference ordering, both R['0; '1 ^ o1; : :
: ; 'n ^ on; 'n+1] and R['0; : : :; 'n+1; o1; : : : ; on] are compared in
the same manner to other sets. It easy to see that this suffices to show
that Pla satisfies UPD4. ut

Finally, we can prove Theorem 6.2. Theorem 6.2: A belief change operator
Pi  satisfies U1-U8 if and only if there is a system I 2 CU such that

Bel(I; sa) Pi   = Bel(I; sa Delta  )

for all epistemic states sa and formulas  2 Le.

Proof: The "if" direction follows from Lemma A.9. For the "only if" direction,
assume that Pi  satisfies U1-U8. By Theorem 6.1, there is an update structure
UPi  such that [[' Pi  ]]UI = minUI ([[']]UI; [[]]UI) for all ';  2 Le.
By Lemma A.10, there is a system I 2 CU such that UI = UPi . From Lemma
A.8, it follows that Bel(I; sa) Pi   = Bel(I; sa Delta  ) for all local
states sa and formulas  2 Le. ut

References Alchourr'on, C. E., G"ardenfors, P., & Makinson, D. (1985). On
the logic of theory change:

partial meet functions for contraction and revision. Journal of Symbolic
Logic, 50, 510-530.

Boutilier, C. (1992). Normative, subjective and autoepistemic defaults: adopting
the Ramsey test. In Principles of Knowledge Representation and Reasoning:
Proc. Third International Conference (KR '92), pp. 685-696. Morgan Kaufmann,
San Francisco, Calif.

Boutilier, C. (1994a). Conditional logics of normality: a modal approach.
Artificial Intelligence, 68, 87-154.

Boutilier, C. (1994b). Unifying default reasoning and belief revision in
a modal framework.

Artificial Intelligence, 68, 33-85.

163

Friedman & Halpern Boutilier, C. (1996a). Iterated revision and minimal change
of conditional beliefs. Journal

of Philosophical Logic, 25, 262-305.

Boutilier, C. (1996b). Abduction to plausible causes: An event-based model
of belief update.

Artificial Intelligence, 83, 143-166.

Boutilier, C. (1998). A unified model of qualitative belief change: A dynamical
systems

perspective. Artificial Intelligence, 98, 281-316.

Boutilier, C., Friedman, N., & Halpern, J. Y. (1998). Belief revision with
unreliable observations. In Proceedings, Fifteenth National Conference on
Artificial Intelligence (AAAI '96), pp. 127-134.

Burgess, J. (1981). Quick completeness proofs for some logics of conditionals.
Notre Dame

Journal of Formal Logic, 22, 76-84.

Darwiche, A., & Pearl, J. (1997). On the logic of iterated belief revision.
Artificial Intelligence, 89, 1-29.

Davis, R., & Hamscher, W. (1988). Model-based reasoning: troubleshooting.
In Shrobe,

H., & for Artificial Intelligence, T. A. A. (Eds.), Exploring AI, pp. 297-346.
Morgan Kaufmann, SF.

de Rijke, M. (1992). Meeting some neighbors. Research report LP-92-10, University
of

Amsterdam.

del Val, A., & Shoham, Y. (1992). Deriving properties of belief update from
theories of

action. In Proceedings, Tenth National Conference on Artificial Intelligence
(AAAI '92), pp. 584-589. AAAI Press, Menlo Park, CA.

del Val, A., & Shoham, Y. (1993). Deriving properties of belief update from
theories of action

(II). In Proc. Thirteenth International Joint Conference on Artificial Intelligence
(IJCAI '93), pp. 732-737 San Francisco. Morgan Kaufmann.

del Val, A., & Shoham, Y. (1994). A unified view of belief revision and update.
Journal of

Logic and Computation, 4.

Dubois, D., & Prade, H. (1990). An introduction to possibilistic and fuzzy
logics. In

Shafer, G., & Pearl, J. (Eds.), Readings in Uncertain Reasoning, pp. 742-761.
Morgan Kaufmann, San Francisco, Calif.

Dubois, D., & Prade, H. (1991). Possibilistic logic, preferential models,
non-monotonicity

and related issues. In Proc. Twelfth International Joint Conference on Artificial
Intelligence (IJCAI '91), pp. 419-424. Morgan Kaufmann, San Francisco.

Fagin, R., Halpern, J. Y., Moses, Y., & Vardi, M. Y. (1995). Reasoning about
Knowledge.

MIT Press, Cambridge, Mass.

Freund, M., & Lehmann, D. (1994). Belief revision and rational inference.
Tech. rep. TR

94-16, Hebrew University.

164

Modeling Belief in Dynamic Systems. Part II. Friedman, N. (1997). Modeling
Beliefs in Dynamic Systems. Ph.D. thesis, Stanford. Friedman, N., & Halpern,
J. Y. (1994). Conditional logics of belief change. In Proc. National

Conference on Artificial Intelligence (AAAI '94), pp. 915-921. AAAI Press,
Menlo Park, CA.

Friedman, N., & Halpern, J. Y. (1995). Plausibility measures: a user's manual.
In Besnard,

P., & Hanks, S. (Eds.), Proc. Eleventh Conference on Uncertainty in Artificial
Intelligence (UAI '95), pp. 175-184. Morgan Kaufmann, San Francisco.

Friedman, N., & Halpern, J. Y. (1996). A qualitative Markov assumption and
its implications for belief change. In Proc. Twelfth Conference on Uncertainty
in Artificial Intelligence (UAI '96), pp. 263-273.

Friedman, N., & Halpern, J. Y. (1997). Modeling belief in dynamic systems.
part I: foundations. Artificial Intelligence, 95 (2), 257-316.

Friedman, N., & Halpern, J. Y. (1998a). Belief revision: A critique. Journal
of Logic,

Language and Information, To appear. Also available at http://www.cs.huji.ac.
il/~nir. A preliminary version appeared in L. C. Aiello, J. Doyle, and S.
C. Shapiro (eds.) Principles of Knowledge Representation and Reasoning: Proc.
5'th International Conference, pp. 421-431, 1996.

Friedman, N., & Halpern, J. Y. (1998b). Plausibility measures and default
reasoning.

Journal of the ACM, To appear. Also available at http://www.huji.ac.il/~nir.
A preliminary version appeared in Proc., 13'th National Conference on Artificial
Intelligence, pp. 1297-1304, 1996.

Fuhrmann, A. (1989). Reflective modalities and theory change. Synthese, 81,
115-134. G"ardenfors, P. (1986). Belief revision and the Ramsey test for
conditionals. Philosophical

Review, 91, 81-93.

G"ardenfors, P. (1988). Knowledge in Flux. MIT Press, Cambridge, Mass. G"ardenfors,
P., & Makinson, D. (1988). Revisions of knowledge systems using epistemic

entrenchment. In Proc. Second Conference on Theoretical Aspects of Reasoning
about Knowledge, pp. 83-95. Morgan Kaufmann, San Francisco, Calif.

Goldszmidt, M., Morris, P., & Pearl, J. (1993). A maximum entropy approach
to nonmonotonic reasoning. IEEE Transactions of Pattern Analysis and Machine
Intelligence, 15 (3), 220-232.

Goldszmidt, M., & Pearl, J. (1996). Qualitative probabilities for default
reasoning, belief

revision, and causal modeling. Artificial Intelligence, 84, 57-112.

Grahne, G., Mendelzon, A., & Rieter, R. (1992). On the semantics of belief
revision systems.

In Moses, Y. (Ed.), know92, pp. 132-142. Morgan Kaufmann, San Francisco,
Calif.

Grove, A. (1988). Two modelings for theory change. Journal of Philosophical
Logic, 17,

157-170.

165

Friedman & Halpern Halpern, J. Y., & Fagin, R. (1989). Modelling knowledge
and action in distributed systems.

Distributed Computing, 3 (4), 159-179. A preliminary version appeared in
Proc. 4th ACM Symposium on Principles of Distributed Computing, 1985, with
the title "A formal model of knowledge, action, and communication in distributed
systems: preliminary report".

Halpern, J. Y., & Vardi, M. Y. (1989). The complexity of reasoning about
knowledge and

time, I: lower bounds. Journal of Computer and System Sciences, 38 (1), 195-237.

Katsuno, H., & Mendelzon, A. (1991a). On the difference between updating
a knowledge base and revising it. In Principles of Knowledge Representation
and Reasoning: Proc. Second International Conference (KR '91), pp. 387-394.
Morgan Kaufmann, San Francisco, Calif.

Katsuno, H., & Mendelzon, A. (1991b). Propositional knowledge base revision
and minimal

change. Artificial Intelligence, 52 (3), 263-294.

Katsuno, H., & Satoh, K. (1991). A unified view of consequence relation,
belief revision

and conditional logic. In Proc. Twelfth International Joint Conference on
Artificial Intelligence (IJCAI '91), pp. 406-412.

Kautz, H. A. (1986). Logic of persistence. In Proceedings, Fifth National
Conference on

Artificial Intelligence (AAAI '86), pp. 401-405. AAAI Press, Menlo Park,
CA.

Keller, A. M., & Winslett, M. (1985). On the use of an extended relational
model to handle

changing incomplete information. IEEE Transactions on Software Engineering,
SE11 (7), 620-633.

Kraus, S., Lehmann, D., & Magidor, M. (1990). Nonmonotonic reasoning, preferential

models and cumulative logics. Artificial Intelligence, 44, 167-207.

Lehmann, D. (1995). Belief revision, revised. In Proc. Fourteenth International
Joint

Conference on Artificial Intelligence (IJCAI '95), pp. 1534-1540. Morgan
Kaufmann, San Francisco.

Levi, I. (1988). Iteration of conditionals and the Ramsey test. Synthese,
76, 49-81. Lewis, D. K. (1973). Counterfactuals. Harvard University Press,
Cambridge, Mass. Manna, Z., & Pnueli, A. (1992). The Temporal Logic of Reactive
and Concurrent Systems,

Vol. 1. Springer-Verlag, Berlin/New York.

Nayak, A. C. (1994). Iterated belief change based on epistemic entrenchment.
Erkenntnis,

41, 353-390.

Pearl, J. (1989). Probabilistic semantics for nonmonotonic reasoning: a survey.
In Brachman, R. J., Levesque, H. J., & Reiter, R. (Eds.), Proc. First International
Conference on Principles of Knowledge Representation and Reasoning (KR '89),
pp. 505-516. Reprinted in Readings in Uncertain Reasoning, G. Shafer and
J. Pearl (eds.), Morgan Kaufmann, San Francisco, Calif., 1990, pp. 699-710.

166

Modeling Belief in Dynamic Systems. Part II. Rott, H. (1991). Two methods
of constructing contractions and revisions of knowledge

systems. Journal of Philosophical Logic, 20, 149-173.

Rott, H. (1992). Two methods of constructing contraction and revisions of
knowledge

systems. Journal of Logic, Language and Information, 1, 45-78.

Shafer, G. (1976). A Mathematical Theory of Evidence. Princeton University
Press, Princeton, N.J.

Shoham, Y. (1987). A semantical approach to nonmonotonic logics. In Proc.
2nd IEEE

Symp. on Logic in Computer Science, pp. 275-279. Reprinted in M. L. Ginsberg
(Ed.), Readings in Nonmonotonic Reasoning, Morgan Kaufman, San Francisco,
Calif., 1987, pp. 227-250.

Shoham, Y. (1988). Chronological ignorance: experiments in nonmonotonic temporal
reasoning. Artificial Intelligence, 36, 271-331.

Spohn, W. (1988). Ordinal conditional functions: a dynamic theory of epistemic
states.

In Harper, W., & Skyrms, B. (Eds.), Causation in Decision, Belief Change,
and Statistics, Vol. 2, pp. 105-134. Reidel, Dordrecht, Netherlands.

Wang, Z., & Klir, G. J. (1992). Fuzzy Measure Theory. Plenum Press, New York.
Williams, M. (1994). Transmutations of knowledge systems. In Principles of
Knowledge

Representation and Reasoning: Proc. Fourth International Conference (KR '94),
pp. 619-629. Morgan Kaufmann, San Francisco, Calif.

Winslett, M. (1988). Reasoning about action using a possible models approach.
In Proceedings, Seventh National Conference on Artificial Intelligence (AAAI
'88), pp. 89-93. AAAI Press, Menlo Park, CA.

167