Iterated Theory Base Change: A Computational Model

1 Introduction

Information systems can be used to represent a reasoning agent's view of the world. Unless the agent has perfect and complete information it will require a mechanism to support the modification of its view as more information about the world is acquired. Moreover, a computational model to support the acquisition of new information requires a finite representation of the information held by the agent. This representation must capture the information content, the agent's committment to this information, and an encoding of how the information should change upon the intrusion of new information.

The AGM paradigm was originally developed by Alchourron, Gardenfors and Makinson [1985] and has become one of the standard frameworks for information change. It provides formal mechanisms for modeling the rational evolution of an ideal reasoner's view of the world. In particular, it provides operators for modeling the revision and contraction of information. Within the AGM paradigm the family of revision operators, and the family of contraction operators are circumscribed by sets of by rationality postulates. The logical properties of a body of information are not strong enough to uniquely determine a revision or contraction operator, therefore the principal constructions for these operators rely on some form of underlying preference relation, such as a family of selection functions [ Alchourron et al. 1985], a system of spheres (Grove, 1988] a nice preorder on models (Katsuno and Mendelzon 1992; Peppas and Williams, 1995], or an epistemic entrenchment ordering (Gardenfors and Makinson, 1988] .

From a theoretical point of view the AGM paradigm they are related to epistemic entrenchment orderings. In section 4 we describe iterated theory base change using transmutations of partial entrenchment rankings. In section 5 we describe a simple computational model that implements a transmutation of a partial entrenchment ranking. The transmutation employed is an adjustment hence the proposed computational model uses an absolute minimal measure of change. In section 6 we explore the connection between our theory base change operators using an adjustment and the standard AGM theory change operators, and we argue that the established relationships demonstrate that our proposed theory base change operators exhibit desirable behaviour. In particular they maintain as much of the theory base as would be retained in the corresponding theory change, thus propagating as much explicit information as possible. Related work is discussed in section 7, and a summary of our results is given section 8.

2 The AGM Paradigm

Let C denote a countable language which is closed under a complete set of Boolean connectives. We will denote sentences in C by lower case Greek letters. We assume C is governed by a logic that is identified with its consequence relation f- which is assumed to satisfy the following conditions [Gardenfors 1988]: (a) If a is a truth-functional tautolo~y, then f- a, (b) Iff- a - f3 and f- a, then f- {3, (c) f- is consistent, that is, lf.l, where .l denotes the inconsistent theory, (d) f- satisfies the deduction theorem, and {e) f- is compact.

The set of all logical consequences of a set f ~ C, that is {a : r f- a}, is denoted by Cn{f). A theory of C is any subset of C, closed under Cn. Let Kc denote the set of all theories of C. For a theory T, if T = Cn{f), then we refer to f a theory base for T. We denote the set of all consistent nontautological sentences in C, that is, the set of contingent sentences, by C". Finally, a well-ranked preorder on a set r is a preorder such that every nonempty subset of f has a minimal member. We denote the domain of a function B, and the range of B by dom(B) and range(B), respectively.

2.1 The Postulates

Within the AGM paradigm a body of information is represented as a theory, and changes are regarded as transformations on theories. There are three principal types of AGM transformations; expansion, contraction and revision. We note that Peppas and Williams [1995] have shown that a form of update [Katsuno and Mendelzon, 1992] can be incorporated into the AGM paradigm. These transformations allow us to model changes of information based on the principle of minimal change [Gardenfors, 1988] . Expansion is the simplest change, it models the acquiescence of information without the removal of any inconsistent information. More formally, the expansion of a theory T with respect to a sentence a, denoted as T;%, is defined to be the logical closure of T and a, that is T;t = Cn{TU {a}) .

A contraction of T with respect to a, T;, involves the removal of a set of sentences from T so that a is no longer implied. Formally, a well-behaved contraction operator- is any function from Kc x C to Kc, mapping (T, a) to T; which satisfies the postulates {-1) - (- 9) , below, and a very well-behaved contraction operator satisfies the postulates {-1)- {-lo).

• {-1) For any a E C and any T E Kc, T; E Kc
• {-2) T; ~T
• (- 3) If a ¢ T then T; = T
• {-4) If If a then a¢ T;
• {-5) T ~ (T;)t
• (-7) r- nr-c ra fJ - aAfJ
• {-6) Iff- a= f3 then T; = Ti
• (- 8) If a ¢ T;,..fJ then T;,._fJ ~ T;
• {-9) For every nonempty set f of nontautological sentences, there exists a sentence a E f such that a ¢ T;,..fJ for every f3 E f.
• {-lo) For every nonempty set r of nontautological sentences, there exists a sentence a Ef such that f3 ¢ T;,..fJ for every f3 E f.

A revision attempts to transform a theory in order to incorporate a sentence so that the resultant theory is consistent. Formally, a well-behaved revision operator · is any function from Kc. x C to Kc., mapping (T, a) toT~ which satisfies the postulates (·1)- e9), below, and a very well-behaved revision operator · satisfies the postulates (·1)- (·lo).

• (·1) For any a E C and any T E Kc, T~ E Kc
• (·2) a E T~
• (·7) T~AfJ ~ (T~)t

(·3) T~ ~ T;t ! · 4l If -.a ¢ T then T;% ~ T~ · 5 T~ =.l if and only iff- -.a · 6 If f- a ::: {3 then T~ = Tp

• (·8) If -.{3 ¢ T~ then (T~)t ~ r;,..fJ
• (·9) For every nonempty set r of nontautological sentences, there exists a sentence a E r such that a rt. T~aV-.fJ for every f3 E r.
• (·10) For every nonempty set r of nontautological sentences, there exists a sentence a E f such that f3 ¢ T~av-.p for every {3 E f .

2.2 Epistemic Entrenchment

An epistemic entrenchment [Gardenfors and Makinson, 1988] is an ordering of the sentences in C which attempts to capture the relative importance of information in the face of change. In order to determine a unique revision or contraction operation a theory is endowed with an epistemic entrenchment ordering, which can be used to determine the information to be retracted, retained, and acquired during the contraction of old information and the acceptance of new information.

Definition: Given a theory T of C, an epistemic entrenchment related to T is any binary relation ~ on C satisfying {EEl)- (EE5), below:

• ! EEll If a ~ f3 and f3 ~ "/, then a ~ "/. EE2 For 'all a, f3 E C, if a f- f3 then a~ {3. EE3 For all a, f3 E C, a ~ a /1. f3 or f3 ~ a /1. {3. EE4 When T l.i, a rf. T if and only if a ~ f3 for all f3 E C.
• (EE5) If f3 ~a for all f3 E C, then f-a .

We define a< {3, as a~ f3 and not f3 ~a. An epistemic entrenchment that possesses a finite number of natural partitions is finite .

Gardenfors and Makinson [1988] showed that, for every contraction operator - there exists an epistemic entrenchment < related to T such that the condition (E-) below, is true for every a E C, and conversely.

Their representation result was extended by Williams (1994c] to well-behaved and very well-behaved operators m the following theorem.

Theorem 1: Let T be a theory of C . For every well-behaved contraction (very well-behaved contraction) operator - for T there exists a well-ranked epistemic entrenchment (finite epistemic entrenchment} ~ related to T such that (E-) is true for every a E C, and conversely.

From the work of Gardenfors and Makinson [1988] and the Levi Identity it is straightforward to derive a similar representation result for revision using (E·) below.

Peppas [1993] was the first to identify the class of well­ behaved revision operators and he obtains an analogous representation result for well-behaved revision based on a well-ordered system of spheres [Grove, 1988] .

3 Representing Theory Bases

Identical canonical representations of epistemic en­ trenchment orderings were developed independently by Rott [1991a] and Williams f1992; 1994c]. Rott's specifi­ cation is an E-Base and Williams' an ensconcement.

An E-Base is a preference relation that provides a canonical representation of an epistemic entrenchment and a theory base. Williams showed that an E-Base is capable of uniquely determining theory base change operators, as well as theory change operators. However, the theory base operations provided do not take an E-Base to an E-Base. In other words, the preference relation on the theory base is not propagated during the process of change, and hence iteration is not supported.

Williams [1994a] extended the work of Spohn [1988], based on observations in [Gardenfors, 1988], to arbitrary iterated revision operators for theories, and referred to the process of changing an epistemic entrenchment ordering as a transmutation.

In this section we demonstrate that a partial entrenchment ranking which is a ranking of a theory base can specify a well-ranked (or finite) epistemic entrenchment ordering on a theory.

A partial entrenchment ranking formally defined below, maps a set of sentences in C to ordinals. Intuitively, the higher the ordinal assigned to a sentence the more firmly held it is. Throughout the remainder of the paper it will be understood that 0 is an ordinal chosen to be sufficiently large for the purpose of the discussion.

Definition: A partial entrenchment ranking is a function B from a subset of sentences in C into 0 such that the following conditions are satisfied for all a E dom(B) :

PERll {.8 E dom(B) : B(a) < B(,B)} ~a,

PER2 /fl- -,a, then B(a) = 0.

[ PER3 B(a) = 0 if and only ifl- a .

(PERl) says that the sentences which are assigned ordinals higher than an arbitrary sentence a , do not entail a, and (PER2) says inconsistent sentences are assigned zero. · (PER3) says that tautologies in the domain of B are assigned the largest ordinal , this is not unduly restrictive as the language is countable, hence the cardinality of the range of B will always be bounded. If r is a nonempty set of sentences, then we define B(r) = min({B(a): a E r}) .

As noted in numerous other works (see [Gardenfors and Makinson, 1994]) the ordinal assignment can be viewed in two distinct ways: (i) qualitatively, where the relative ordering of sentences is used, or (ii) quantitatively, where ordinals have some extra meaning, and a calculus based on their numerical value adopted.

We refer to a partial entrenchment ranking with a finite range as a finite partial entrenchment ranking. A finite ranking does not imply that the language is finite. We denote the family of all partial entrenchment rankings by B.

The intended interpretation of a partial entrenchment ranking is that sentences mapped to ordinals greater than zero represent the explicit beliefs of the reasoning agent , and their logical closure represents the agent's set of implicit beliefs.

Definition: Define the explicit information set repre­ sented by B E B to be {a E dom(B) : B(a) > 0}, and denote it by exp(B) . Similiarly, define the implicit infor­ mation set represented by B E B to be Cn(exp(B)), and denote it by imp(B) . A sentence a is an explicit belief if and only if a E exp(B).

We now describe the relationship between a partial entrenchment ranking and an epistemic entrenchment ordering. First we define the notion of a cut which has been used by numerous authors under various guises; most notably by Rott [199la] and Gardenfors and Makinson [1994] .

Definition:For a partial entrenchment ranking, B, and a sentence a E imp(B) we define the a cut of B as {.8 E exp(B) : {! E exp(B) : B(.B) < B(r)} ~a}, and denote it by cut(B, a) .

Cuts are always subsets of exp(B) , and for contingent a E exp(B) the a cut of B contains all sentences in exp(B) that are assi~ned ordinals at least as large as B(a), thus if a E exp(B) , then a is in its own cut . Note, if 1- a then cut(B, a)= 0.

The following theorem provides an explicit construc­ tion of an epistemic entrenchment ordering from a partial entrenchment ranking based on cuts.

Theorem 2: ForB E B and a , .B E C, define ~B to be given by a ~a .B if and only if either (i} a (/. imp(B), or (ii} cut(B, .B) ~ cut(B, a) . Then ~a is a well-ranked epistemic entrenchment ordering related to imp(B) .

We refer to ~8 as the epistemic entrenchment ordering generated from B. From Theorem 2 we see that the tautologies are maximal, and sentences not in imp(B) are minimal with respect to ~8 . If B is finite then the epistemic entrenchment ordering it generates is finite. An epistemic entrenchment ordering is finitely representable if and only if every cut is finitely axiomatizable. Consequently, ~ is finitely representable if and only if there exists a B such that ~=~a and exp(B) is finite .

Intuitively, Theorem 3, below, says given a well­ ranked epistemic entrenchment ordering there exists a partial entrenchment ranking that can be used to generate it. Theorems 2 and 3 tell us that a partial entrenchment ranking can be considered to be a (possibly minimal) specification of a well-ranked epistemic entrenchment ordering.

Theorem 3: Let T be a theory in C, and r ~ T. Let ~ be a well-ranked epistemic entrenchment related toT. Let To , T1. T2 , .. . be the natural partitions of~ indexed so that a E Ts and {3 E 1j whenever i < j implies a < {3. For all a E T, if {{3 E f : a ~ {3} f- a, then the mapping of each sentence in r from the natural partition Ts to i for all i is a partial entrenchment ranking, B, that generates ~' that is, ~8=~.

The r referred to in the theorem above is the explicit information set of the partial entrenchment ranking that generates the epistemic entrenchment and while obviously not unique, it must contain enough sentences of 'the right stuff' in each natural partition of the epistemic entrenchment ordering to enable its regeneration. In particular, it must satisfy the condition in the theorem; at least one such r exists, namely T itself.

Stepwise constructions of epistemic entrenchment orderings from partial entrenchment rankings, and vice versa, can be derived from the those provided in [Rott, 1991b; Williams, 1994c].

Definition: We define, the degree of acceptance of a E C with respect to B E 8 to be, degree~B, a) = B( cut(B, a)) whenever 'r/ a and a E imp(B . If f­ a then degree(B, a) = 0, and if a fl. imp B) then degree(B, a)= 0.

Note, degree(B, a)~ degree(B, {3) if and only if a ~B {3. EXAMPLE: Let B be given by B(a - {3) = 3, B('y) = 2, B(a) = 1. Then we have degree(B,{J) = 1, degree(B, a - 1) = 2, de~ree(B, -.a) = 0, degree(B, -.{3) = 0, and degree(B, -.I) = 0.

4 Iterated Change for Theory Bases

Recall from our previous discussion that from a practical perspective the AGM paradigm does not provide a policy to support the iteration of its change operations. In this section we show how transmutations of partial entrenchment rankings can be used to support iterated theory base change, and we provide existence theorems that demonstrate how transmutations are related to the AGM theory revision and theory contraction operators.

For revision and contraction operators the informa-­ tion input is a sentence. We now define a transmutation of partial entrenchment rankings where the information input is a contingent sentence a and an ordinal i. The interpretation [Gardenfors 1988] of this is that the sen­ tence a is the information to be accepted, and i is the degree of firmness with which it is to be incorporated into the transmuted partial entrenchment ranking.

Definition: We define a transmutation schema for partial entrenchment rankings, *, to be an operator from 8 x C" x 0 to 8, such that (B, a , i) t-+ B*(a, i) which satisfies (i) B*(a, i)(a) = i, and (ii) imp(B*(a, i))

We say B*(a, i) is an (a, i)- transmutation of B, and we note that a transmutation is not defined for inconsistent, or tautological sentences. An inconsistent sentence is not considered acceptable information [Spohn 1988], and the exclusion of tautological sentences is for technical convenience allowing us to focus on the principal case, however the definition can easily be extended to include both tautological and inconsistent sentences. Intuitively, if i > 0 then B*(a, i) embodies a theory base revision, and similarly B*(a, 0) represents a theory base contraction. It is interesting to note that imp(B) t-+

imp(B*(a, 0)) defines a withdrawal function [Makinson, 1987].

If eks(B) is a theory then the transmutation schema for partial entrenchment rankings is precisely the same as the transmutation schema for ordinal epistemic entrenchment functions which is given in [Williams 1994al for the theory change setting. Theorems 4 and 5, befow, demonstrate how transmutations of partial entrenchment rankings are related to theory revision and theory contraction operators within the AGM paradigm. They are existence theorems, we provide explicit constructions based on a particular form of transmutation in section 6.

Theorem 4: LetT be a theory in C. For every (very) well-behaved theory revision operator · forT, there exists a (finite) B E 8 such that im~B) = T and T~ = imp(B*(a, i)) for every a E C and 0 . < i < 0 . Conversely, for every (finite} B E 8, there exists a (very) well-behaved theory revision operator · for imp(B) such that (imp(B)l;. = imp(B*(a, i)) is true for every a E C" andO<i<v.

Theorem 5: Let T be a theory in C. For every (very) well-behaved theory contraction operator - for T, there exists a (finite) B E 8 such that imp(B) = T, and r- = Cn( exp(B*( a, 0)) U {-.a}) n T) for every a E C". Conversely, for every (finite) B E 8, there exists a (very) well-behaved theory contraction operator - for imp(B) such that (imp(B ));:; = · Cn( exp(B*( a, 0)) U {-.a}) n imp(B) for every a E C".

The definition of a transmutation schema forces the contraction of a theory base to be a subset of the ori~inal theory base, that is, for all a E C", exp(B*(a, 0)) ~ exp(B). Consequently, the recovery postulate (- 5) is not necessarily satisfied [Makinson, 1987]. If it is desirable to satisfy recovery then certain sentences identified by Nebel [1991] and Foo can be added to the partial entrenchment ranking in a contraction to ensure its satisfaction. For a more elaborate discussion of this issue see Williams [1994c]. We note that the definitions and theorems presented in this paper can be modified to capture recovery in a straightforward manner. We adopt the definition as given because it is more consistent with our interpretation of a partial entrenchment ranking being an explicit representation of an agent's information.

5 A Computational Model

In this section we describe a particular type of transmutation called an adjustment which uses a policy for change based on an absolute minimal measure. In particular, it involves the absolute minimal change of a partial entrenchment ranking that is required to incorporate the desired new information. A semantic account of adjustments can be found in [Williams, 1994a].

We present a computational model for adjustments which can be used as the basis for a computer-based implementation. Any theorem prover can be used to realize it. The model itself is stated in its most perspicuous form, and can be optimised in several obvious ways, see [Williams, 1993] for details. For the purpose of our model we focus on finite epistemic rankings, and the following theorem describes the degree of acceptance of sentences with respect to finite rankings. Theorem 6: Let a be a nontautological sentence. If BE 8 is finite, then degree(B, a)

Based on Theorem 6 the following function uses a simple procedural algorithm to determine the degree of a sentence with respect to a finite partial entrenchment ranking. The function takes two input parameters, namely a finite partial entrenchment ranking, B, and a nontautological sentence, a, it calculates and returns the degree of acceptance of a in B. The algorithm requires the support of your favourite theorem prover to implement the logical implication relation, f-.

FUICTIOI degree(B,a)

degree(B,a) ~ max(range(B)) + 1

do degree(B,a) ~ degree(B,a) - 1

until degree(B,a) ~ 0 or

{bE dom(B): B(b) ~ degree(B,a)} f- a

This algorithm can compute the generated epistemic entrenchment ordering of sentences based on the information encoded in a partial entrenchment ranking.

A transmutation which is suitable for theory base change is an adjustment defined in the theorem below. When B is finite then its definition constitutes a computational model which, loosely speaking, involves successive calls to the function degree for each sentence in the domain of B.

Theorem 7: Let B E 8, a E £", and i < 0. Then B*(a, i) defined below is a transmutation.

for all {3 E dom(B U {a}).

Hans Rott has pointed out that the a+(a, i) operation can be traced back to Rescher [1976]. Intuitively, an (a, i)-adjustment of B involves minimal changes to B such that the sentence a is accepted with degree i. In particular, each sentence {3 E dom(B) is reassigned an ordinal closest to B({3) in the adjusted partial entrenchment ranking B*(a, i) under the guiding principle that if we reduce the degree of an accepted sentence a to i, say, then we also reduce the degree of each sentence that would be retracted in a's contraction to i as well.

The following theorem illustrates the interrelation­ ships between theory base revision and theory base con­ traction based on adjustments. In particular, Theorem 8(i) is analogous to the Harper Identity and it captures the dependence of theory base contraction on the in­ formation content of the theory base, that is, the ex­ plicit information set, exp(B). Similarly Theorem S(ii) is analogous to the Levi Identity, and S(iii) says that a Levi Identity also exists at the deeper preference relation level. In particular, precisely the same partial entrench­ ment ranking is obtained when a partial entrenchment ranking is adjusted to accept new information a with firmness 0 < i < 0, as when we adjust the partial en­ trenchment ranking to remove -.a, and then adjust the resultant partial entrenchment ranking to accept new information a with firmness i. Similarly, S(v) establishes a Harper Identity at the preference relation level where the functions, B and B*, have been identified with the set of ordered pairs (a, B(a)) and (a, B*(a)), respectively, such that a E dom(B).

Theorem 8: Let B E 8, let the transmutation schema

* be an adjustment, and let 0 < i < 0. Then (~i) ex~(B*(a, i) ~ exp(B*}-.a,_d)) U {a}, (i} exp(B*(a, 0)~ = exp(B*( -.a, i)) n exp(B) (iv exp(B*(a, 0 ) = exp(B*(a, 0) n B) (u~ B (a, i) = B (-.a, 0)) (a, a), and (v B*(a, 0) n B = B*(-.a, max(l, degree(B, -.a))) n B.

We illustrate the adjustment of a theory base in the example below.

EXAMPLE: Let B be given by B(a -+ {3) = 3, B(r) = 2, B(a) = 1.

(a) Consider the reorganization of B where more compelling evidence for a is acquired, and we decide to increase the degree of acceptance of a from 1 to 3, that is, B*(a, 3). Then we have B*(a, 3)(a) = 3, B*(a, 3)(a-+ {3) = 3, B*(a, 3)(r) = 2, degree!B*!a, 3l, {3) = 3, degree B* a, 3 , a-+ r) = 2, degree B* a, 3 , -.a = 0, degree~B*~a, 3~, -.{3) = 0, and degree B* a , 3 , -.r~ = 0. (b) Now let's consider the contraction of a, that is, B (a, 0). Then we have B*(a, O)(a) = 0, B*(a, O)(a-+ degree B* a, 0 , a -+ r) = 2, degree B* a, 0 , -.a = 0, {3) = 3, B*(a,O)(r) = 2, degree!B*!a,Ol,{3) = 0, degree~B*~a, 0~, -.{3) = 0, and degree B* a, 0 , -.r~ = 0. (c) Finally, we consider the acceptance of -.a with degree 4, that is, B*(-.a,4). Then we have B*(-.a, 1)(-.a) = 4, B*(-.a, 1)la -+ ~ = 4, degree(B*(-.a, 1),r) = 2, degree!B* -.a, 1l, = 0, degree(B*(-.a, 1), a-+ r) = 4, degree B* -.a, 1 , a = 0 degree(B*(-.a, 1), -.p) = 0, degree B* -.a, 1 , -.r) = 0.

Adjustments use the relative ordering encoded in a par­ tial entrenchment ranking, and they preserve finiteness with respect to both revisions and contractions; adjust­ ing a finite partial entrenchment ranking results in a fi­ nite ranking, and if exp(B) is finite then exp(B*(a, i)) is

finite.

6 Connections with Theory Change

The theorems in this section establish the explicit relationship between theory base change operators based on adjustments and theory change operators based on the generated epistemic entrenchment ordering.

Theorem 9: Let B E 8, let the transmutation schema * be an adjustment, and let 0 < i < 0 . Let - be the contraction operator for imp(B) uniquely determined by (E-) and ~8 . Then {i} exp(B*(a, 0) = (imp(B));; n exp(B), (ii) (imp(B));; = Cn(exp(B*(a,O)) U {-.a}) n imp(B).

Theorem 10: Let B E 8, let the transmutation schema * be an adjustment, and let 0 < i < 0. Let · be the revision operator for imp(B) uniquely determined by (E·) and <8 . Then (i) exp(B*(a, i)) = (imp(B))~ n {exp(B) U "fa}}, and {ii) (imp(B))~ = imp(B*(a, i)).

Theorem 9(i) captures the dependence of a theory base contraction on the content of the theory base, that is, exp(B) . In particular, a sentence is retained in the theory base contraction if and only if it is a member of the theory base and it would be retained in the corresponding theory contraction. Theorem 10(i) establishes a similar result for revision. This substantiates our claim that adjustments retain as 'much as possible' of the original theory base.

Consequently, a partial entrenchment ranking can be used to model belief change for a limited reasoner. In particular, partial entrenchment rankings can be used to represent the reasoner's explicit information, its commitment to that information, and an encapsulation of the desired dynamic behaviour. In fact, depending on the nature of the theorem prover adopted for an implementation some resource bounds could also be introduced (Williams, 1993]. Theorems 9(i) and lO(i) clearly demonstrate that theory base adjustments contain as many of the explicit beliefs as would be retained in the corresponding theory change operations. In particular, we have established that each explicit belief retained in a theory change is also retained via theory base adjustments.

Theorems 9(ii) and lO(ii) show that theory change operators can be formulated in terms of theory base change using adjustments, and they provide explicit constructions for the Theorems 4 and 5, respectively.

We define two partial entrenchment rankings to be equivalent whenever they generate the same epistemic entrenchment ordering. It is obvious that, if B1 and B2 are equivalent, then for all a E C Cn(cut(B1, a))= Cn(cut(B2, a)), and imp(BI) = imp(B2). For example, ifB1 is given by B1(a- /3) = 2, B1(a) = 2, B1(-y) = 1, and B2 is given by B2(/3) = 2, B2(a) = 2, B2(a- 1) = 1, then B1 and B2 are equivalent .

For revision the adjustments of equivalent partial entrenchment rankings result in equivalent implicit information sets. Furthermore, it turns out that the second parts of Theorems 9 and 10 can be generalised to equivalent partial entrenchment rankings, however we provided the current readings to for the sake of simplicity.

7 Related Work

Gii.rdenfors and Rott (1992] provide a comprehensive analysis of various prominent approaches (Hansson 1989; Fuhrmann 1991; Nebel, 1991] to theory base change, and the interested reader should consult their work.

Nayak (1993] and Boutilier (1993] explore iterated theory change, and their approaches are closely related to transmutations because they focus on changes at the preference relation level, and as a consequence if the underlying preference relation is well-ranked then both of their procedures can be expressed as transmutations. Boutilier's natural revision being a special case of adjustment, and Nayak's method being a special case of conditionalization. For example, if we use Theorem 3 to capture the relationship between an epistemic entrenchment ordering and a partial entrenchment ranking, then Boutilier's approach can be characterized as an (a, I)-adjustment .

Boutilier's new information is always accepted mini­ mally firmly (Spohn 1988, p114], and Nayak's new in­ formation is always accepted maximally firmly (Spohn 1988, pll4]. In other words, they both suffer from prob­ lems described by Spohn, since their representation is essentially a simple conditional function, and their in­ formation input a sentence alone. Spohn claims that both of these extreme schemes are undesirable because we don't always want to accept new information with the same degree of firmness.

In defense of Nayak and Boutilier we should point out that the degree of firmness for new information may not always be available, in which case we could adopt default firmnesses for newly acquired information when the quality of the evidence is unknown.

If the underlying preference relation is well-ranked then transmutation schemas can capture any conceivable change within the AGM paradigm. For the purpose of an implementation we will almost certainly be dealing with a well-ranked, probably finite, preference relation.

An alternative approach to the problem of iterated revision is adopted by Darwiche and Pearl (1994], and Freund and Lehmann (1994] . In particular, they have studied the iterated revision problem at the axiomatic level, and they suggest new meta-postulates for iterated revision rather than constraints on the modification of preference relations.

Williams et al. (1995b] capture Spohn's notion of reason for (1983] using adjustments of entrenchment rankings, and the computational model provided in section 5 can be used to implement Spohnian reasons.

Finally, we highlight some connections with nonmono­ tonic reasoning. Gii.rdenfors and Makinson (1994] use an comparative expectation ordering to construct a non­ monotonic inference relation. Williams f1995a] defines a partial expectation ranking to be is a function B from a subset of sentences in C into 0 such that (PERl) and (PER2) are satisfied. We also note that Rescher's plausibility indexes (1976] are essentially partial expecta­ tion rankings. Given a partial expectation ranking B, if we define a nonmonotonic inference relation 1--, as ar.-.B if and only if exp(B*(a, i)) I- f3 where 0 < i, then r­ is consistency preserving and rational, and the associ­ ated model structure is nice (Gii.rdenfors and Makinson, 1994] .

Williams (1995a] shows that adjustments can be applied to partial expectation rankings thus providing a mechanism for changing nonmonotonic inference relations in an absolute and minimal way.

Boutilier (1993], Pearl (1994], Freund and Lehmann (1994] also address the idea of changing default information, arguing that default information is usually quite stable, for example although our information about the flight coefficient of a particular bird may change dramatically, the default that typically birds fly will invariably remain unchanged, therefore changes should maintain as much default information as possible. An adjustment not only concords with this perspective, but it preserves the properties of consistency perservation and rationality of the inference relation.

8 Discussion

We have shown that the AGM paradigm can be extended to solve two outstanding practical problems that arise in the development of a computational model for belief revision. Tl:iis extension focuses on a finite representation of an epistemic entrenchment ordering, and the determination of a policy for change based on the principle of minimal change.

We established that partial entrenchment rankings can be used to construct theory base change operators, theory change operators, as well as nonmonotonic infer­ ence relations. Moreover, we provided representation re­ sults for the construction of well-behaved and very well­ behaved theory change operators based on partial en­ trenchment rankings.

We used partial entrenchment rankings to represent a well-ranked epistemic entrenchment ordering, and we provided a computational model for modifying partial entrenchment rankings based on an absolute measure of minimal change which dealt with the removal of old information and the acquiescence of new information.

We established that theory base revision and theory base contraction operators based on adjustments are related via Levi and Harper Identities at both the information content and the preference relation levels. Finally, we demonstrated that theory base operators based on an adjustment maintain as much explicit information as is retained by the corresponding tlieory change operator.

Acknowledgements

The author gratefully acknowledges, Peter Gardenfors for suggesting how Spohn's work might be used in the development of a computational model, David Makinson for a myriad of insightful suggestions concerning theory base change. Many thanks are also due to Craig Boutilier, Didier Dubois, Norman Foo, Georg Gottlob, Abhaya Nayak, Bernhard Nebel, Erik Olsson, Maurice Pagnucco, Judea Pearl, Pavlos Peppas, Wlodek Rabinowicz and Hans Rott for their helpful comments.