An Inconsistency Tolerant Model for Belief Representation and Belief Revision

1 Introduction

This paper is motivated by several concerns in the area of belief representation and belief revision.

Minimal Change: When a belief structure is revised in the face of new information, we would like the new belief structure to be as similar to the old one as possible. This requirement goes back to Quine and has been repeatedly emphasized by Gardenfors as the preservation criterion (cf. [Gardenfors, 1988).)

Computational Tractability: Since we are seeking to represent the beliefs of real people, and since the satisfia­ bility problem is NP-complete, even at the propositional level we need to be aware of the computational limita­ tions of real people or even real computers and try, if possible, to take them into account in our belief repre­ sentation models.

Explicit vs Implicit Beliefs: There are beliefs which are explicit - they may be actually asserted or at least agreed to. Other beliefs are implicit in the sense that an agent can be made to agree to them after a discus­ sion. If the set of explicit beliefs is consistent, then we can define the set of implicit beliefs as just their logical consequences. However, this becomes implausible if - unknown to the agent - the explicit beliefs are inconsis­ tent.

Inconsistency Tolerance: The beliefs of real individ­ uals are usually inconsistent from a global point of view.

Rohit Parikh

Computer Science, Mathematics and Philosophy City University of New York (Brooklyn & GSUC) New York, NY, U.S.A ripbc@cunyvm.cuny.edu

This is also likely to be the case with large data bases. So we need to model how an agent deals with possible inconsistencies in its belief base.

In this paper we propose a model which comes to grips with all four issues. Our work is related to the split­ ting languages framework of [Parikh, 1996) . That paper showed how an agent's beliefs can be (uniquely) subdi­ vided into sub-areas and how this division can be used in belief revision. However, it did not address the issue of explicit vs implicit beliefs, not did it tackle the question of inconsistent explicit beliefs. In the current paper we do both.

We take the celebrated AGM axioms [Alchourron et. al, 1985) as our starting point, but modify them some­ what and represent an agent's beliefs, not by a theory as is usual, but by what we call a B-structure, a notion which generalizes the notion of a theory. We begin by giving some notation and re-stating the AGM axioms.

Notation: In the following, L is a finite propositional language. (However, most results continue to hold for a countably infinite first order language without equality.) The constants true, false are in L. The letter L stands both for a set of propositional symbols and for the for­ mulae generated by that set. It will be clear from the context which is meant. A {::} B means that A ++ B is a tautology, i.e. true under all truth assignments. Sim­ ilarly, A =} B means that A --+ B is a tautology. If X is a set of formulae then Cn(X) is the logical closure of X. Thus X is a theory iff X = Cn(X). Letters T, T' denote theories. T * A is the revision of T by A and finally, T -f.. A is Cn(T U {A}), i.e. the result of a ~rute addition of A to T (followed by logical closure) without considering the need for consistency. Slightly departing from the AGM usage, we always assume that both T and A are individually consistent, only their union might not be.

AGM have proposed the following widely accepted ax­ ioms for the revision operator *· We omit their axioms 7,8 _havin~ to do with conjunction. See [Parikh 1996) for a d1scuss1on of those two axioms and why they are less plausible than the other six.

1. T * A is a theory.

2. A E T* A

3. If A¢:? B, then T *A= T *B.

4. T*A c T.f-A

5. If A is-consistent with T, i.e. it is not the case that ·A E T , then T * A = T -f- A.

6. T * A is consistent if A is.

However, the AGM axioms are consistent with the trivial update, which is defined by:

If A is consistent with T, then T *A = T + A, otherwise T*A = Cn(A).

Thus in case A is inconsistent with T, under this update, all information in T is simply discarded, which is not in the spirit of the minimal change requirement. The work in [Parikh, 1996), discussed below, was motivated in part by a desire to block the trivial update.

We now give some details of the LS model on which our new notion of a B-structure is based.

2 The LS Model

[Parikh, 1996] introduced a language splitting model which addressed two of the four issues we mentioned at the beginning, namely minimal change and computa­ tional tractability. We review his results below before going on to describe our new B-structures model which addresses inconsistency tolerance as well.

The intuition behind the LS model is that our beliefs are subdivided into disjoint areas which do not affect each other. This separation allows us to revise our beliefs locally and to minimize the amount of computation we have to do when we receive a new piece of information, both in checking whether it is consistent with the old set of beliefs and in revising our beliefs in view of the new information.

Definition LSl: 1) Suppose T is a theory in the language L and let £ 1 , L2, .. , Ln be a partition of L. Then £ 1 , ... , Ln split the theory T if there exist formulae Ai ELi such that T = Cn(A1, ... ,An)· We may also say that {£1 , ... , Ln} is aT-splitting.

2) If £ 1 c L then we say that T is confined to £1 if T = Cn(T n Lt).

In part 1 of the definition, we can think of T as be­ ing generated by the various Ti in languages Li . Then the condition implies that T contains no "cross-talk" be­ tween Li and Li for distinct i,j. Part 2 of the definition says that T knows nothing about the part L - £1 of L.

Example: Let T be Cn(R V C, B -+ S). Then L(T) = { R, C, B, S} can be split into { R, C} and { B, S} with corresponding theories Cn(RVC) and Cn(B-+ S) . Further splitting is now impossible. Suppose I believe that it will be either raining or clear tomorrow and that if I eat bananas then I will get a stomach ache. These beliefs can then be separated.

Lemma LSl: [Parikh, 1996] Given a theory Tin the language L, there is a unique finest T-splitting of L, i.e. one which refines every other T -splitting.

Lemma 1 says that there is a unique way to think ofT as being composed of disjoint information about certain subject matters.

Lemma LS2: Given a formula A, there is a smallest language L' in which A can be expressed, i.e., there is L' C L and a formula B E L' with A ¢:? B, and for all L" and B" such that B" E L" and A ¢:? B", L' ~ L".

Although A is equivalent to many different formulas in different languages, lemma 2 tells us that nonethe­ less, the question, "What is A actually about?" can be uniquely answered by providing a smallest language in which (a formula equivalent to) A can be stated. For example if A is the formula P 1\ (Q V -.Q), then A¢:? P and hence L(A) = {P}. The language L' will be referred to as L(A). If A¢:? B, then L(A) = L(B).

The general rationale for axiom P, below, is that if we have information about two or more subject mat­ ters which, as far as we know, are unrelated (are split) then when we receive information about one of them, we should only update our information in that subject and leave the rest of our beliefs unchanged.

Axiom P: If T = Cn(A, B) where A, B are in £1,£2 respectively and Cis in £1, then T*C = Cn(A)*'C + B, where *' is a (local) update operator for £1.

It follows from axiom P that if T is split between £ 1 and £2, A, B are in £1 and £2 respectively, then T * A * B = T * B * A. While axiom P looks binary, it implies the n-ary case. Axiom P is independent of the AGM axioms. We now get

Theorem: [Parikh, 1996] There is an update procedure which satisfies the six AGM axioms and axiom P. More­ over, the trivial update procedure does not satisfy axiom P.

2.1 Comments on the LS Model

The LS model insists that the division of our beliefs uses disjoint sub-languages. But then global inconsistencies cannot be represented. Suppose an agent believes theo­ ries Ti in languages Li and the Li are mutually disjoint. Then if the Ti are individually consistent, they are also jointly consistent. Thus the LS model cannot explain how an agent can be locally logically omniscient - i.e. derive logical consequences within each Li but still fail to be globally consistent.

We would like to model a more realistic agent, i.e. one who is locally logically omniscient, who does not be­ lieve any outright inconsistencies, but whose global belief structure might well be inconsistent without his being aware of it. This means that the languages Li must be allowed to overlap on occasion. The B-structure model which we introduce below does just that and shows how the logic is handled using Belnap's four truth values, {l., true, false, T} [Belnap, 1977].

We feel that this relaxation is psychologically realis­ tic. E.g. we may imagine that Clinton's problems with Lewinsky might be connected with the bombing of Iraq, which may affect the price of oil and which in turn may affect our airfare to a conference. But it is unrealistic to think that we might reason with all these beliefs together at one time. Rather they will be separated, though only partially; the connections may be noticed on occasion, if there is an article in the newspaper connecting a price hike in airfares with the bombing of Iraq.

The sort of model we are considering will also apply to group reasoning. Each agent will have its own language and be individually consistent in it. But the languages of different agents may overlap and a particular question A may be resolved by consulting those agents whose lan­ guages overlap with the language of A. Options A and B discussed below will show how this is handled at a technical level. Even a single agent may be thought of as consisting of a collective entity, see [Minsky, 1986).

3 The B-structure model

Definition 1: a belief structure B on L is a set {(L1, T1), ... , (Ln, Tn)} such that L = U Li : i ~ n, and each Ti is a theory in Li. (We can

imagine that Ti = Cn(ri) where the ri are the explicit beliefs of some agent in language Li. If n = 1, then B will be just a theory.)

As in the case of belief bases, the object of revision is a set of beliefs that is not necessarily logically closed.

While we are not requiring the Li to be disjoint, we do want to retain some amount of disjointness. The following notion does that.

Definition 2: Given a finite propositional language L and languages {L1 ... Ln} such that L = L1 U ... U Ln, {L1 ... Ln} is a k-partition of L if any propositional sym­ bol q occurs in at most k of the Li.

The presence of such an overlap of symbols may be thought of as "cross-talk" amongst the Ti; beliefs in some of the Ti may be relevant or related to beliefs in others. A k-partition with a smaller k will be more disjoint than one with a larger k and indicates a finer partitioning of her beliefs by the agent. In particular, a normal partition is just a !-partition. A k-partition is a fortiori a k + !­ partition and hence, for instance, a maximally fine 2partition will usually be finer than the finest !-partition whose existence is guaranteed by lemma LS 1. Tolerating some overlap makes it easier to organize one's beliefs in smaller chunks. For example, if Tis axiomatized by the formula (P V Q) /\ (....,Q V R) then L(T) = {P, Q, R} has only a triviall-partition. However, there is a 2-partition into sets { P, Q} and { Q, R} with the two theories being generated by P V Q and --,Q V R respectively.

Definition 3: B as in definition 1 is m-consistent if any m of the Ti are jointly consistent.

We do not require that the whole collection be consis­ tent, but the amount of inconsistency is limited by this requirement. The larger the m, the stronger the require­ ment imposed by m-consistency. Thus, for instance, B is !-consistent iff the Ti are individually consistent, but B = { (L1, TI), ... , (Ln, Tn)} is n-consistent iff UTi is con­ sistent.

A very natural example of such a collection with the bald person paradox. Suppose that a person with 10,000

hairs is not bald but that a person with 0 hairs is bald. Also, suppose that a non-bald person cannot become bald through the removal of just one hair. This gives us the axioms B(O), B(n) -+ B(n + 1), for n = 0 to n = 9, 999, and --,B(IO, 000). These 10,002 axioms are inconsistent, but any 10,001 of them are consistent. This gives us a 10,001-consistent, inconsistent collection of ax­ ioms, all of which are accepted, and used.

For a more practical example, consider an airline which has 100 seats on a flight, and accepts 120 reser­ vations. If Ci says that customer number i has a seat, then the airline is asserting ci for 1 ~ i ~ 120, and also that at most 100 of the Ci hold. This gives a B-structure B with 121languages: {Cl}, ... {C12o}, {C1, ... , C12o} and theories T1, ... , T120, T121· Here, for i ~ 120, Ti is gener­ ated by Ci and T121 is generated by a gigantic formula which says that at most 100 of the Ci are true. This B-structure is 100-consistent, but inconsistent. But its inconsistency will not matter if fewer than 100 of the customers claim their seats.

To represent how an agent uses his B-structure and re­ vises it, we make use of the four valued semantics [Bel­ nap, 1977), [Fitting,1989), where the four truth values ..l, true, false T stand for, respectively, no information, true, false, and over-defined (or inconsistent). The first three truth values are intuitively obvious. The last, over­ defined, can arise when we are given contradictory infor­ mation by two people both of whom are trustworthy. In this four valued hi-lattice there are two orderings, the knowledge ordering under which ..l <k true, false <k T and the truth ordering under which false <t ..l, T <k true. true is truer than T which is truer than false. But ..l, T are incomparable under the truth ordering. Simi­ larly, true, false are incomparable under the knowledge ordering. The truth values with their orderings are dis­ played in the double Hasse diagram below.

Now we consider how a B-structure responds to queries and how it is revised.

4 Answering queries

Given a formula A and B-structure B the query "A?" is answered by giving the value vs(A) - abbreviated as v(A) - which is defined as follows: Let r A = UTi : Li n L(A) =f. 0, where L(A) is the smallest language in which A can be expressed (cf. Lemma LS2).

If fA is consistent, then

If r A is inconsistent, then v(A) = T.

if r A f- A, then v(A) = true if r A f- -.A, then v(A) = false, and v(A) = ..i otherwise.

Intuitively we see which of the theories Ti could be relevant to A and put them together to get r A· r A is used to answer questions about A and the rest of the theories Tj are not brought into play.

Controlling Inconsistency: Our approach, while seeking to handle this problem, is distinct from the usual paraconsistent approach in that we do allow full use of classical logic, albeit locally.

Limited consistency: Suppose that A has at most l distinct symbols, the Li are a k-partition, and m ~ k x l. Then r A will be a union of at most m of the theories Ti· If the collection {Ti : i :::; n} ism-consistent, then fA will be consistent and exactly one of the first three values will be given. In other words, an agent whose B-structure is fairly consistent, and who is responding to a short query, will always give a consistent response.

We say that the person with belief base B implicitly believes A if v(A) = true. If so, it is true that A fol­ lows from her explicit beliefs but the converse does not hold in general. If the explicit beliefs are jointly incon­ sistent, then their consequences will include all formulae, but the agent may still have implicit beliefs which are a reasonable set . The implicit beliefs will always include the explicit ones and will be locally closed under logical rules.

What about adjunction? If an agent implicitly be­ lieves A and B, i.e. if the answers to A and B are both true and L(AI\B) has no more than l symbols, then the answer to A 1\ B will also be true. However, cases can arise where the longer formula A 1\ B forces the agent to simultaneously consider several of his beliefs and the underlying inconsistency is detected. Let £1 = { P, R}, L2 = {Q, R}, T1 = Cn(P, R) and T2 = Cn(Q, -.R) . Then the answers to the queries 'P?' and 'Q?' will both be yes, but to 'P 1\ Q?' it will be T.

5 Base Refinement

A person who has explicit beliefs r in language L may or­ ganize these beliefs in smaller or larger chunks. Clearly if r is inconsistent , then it is un-workable to organize them in a single chunk. Moreover, organizing in larger chunks can make the computational problems harder. On the other hand it does have the advantage that more implicit beliefs can be derived in the sense described below.

Definition 4: A B-structure B refines another, B' if (i) every language Li is a subset of another Lj, (ii) every Lj = ULi iLi ~ Lj, and (iii) every Tj = Cn(UTiiLi ~ Lj).

Example: Suppose that the B-structure B has the three languages { P, Q}, { Q, R}, { R, S} and theories Ti : i:::; 3 generated by the formulae P--+ Q, -.QI\R and Rl\ S respectively. the B-structure B' has the two languages {P, Q, R}, {R, S}. and theories Tj : j :::; 2 generated by the formulae -.P 1\ -.Q 1\R and RI\S respectively. Clearly B refines B'. Now to the query 'P?', B will give the answer ..i and B' will give the answer 'yes' or true.

Theorem 1: Let B refine B' and A be a formula. Then v(A) :::;k v' (A) where v(A), v' (A) respectively stand for VB(A) and VB' (A).

Proof: Given a formula A and B-structure B the query "A?" is answered by giving the value VB(A) = v(A) which is defined using r A = UTi : Lin L(A) =f. 0, where L(A) is the language of A. Similarly for B'.

Now we note that if Li ~ Lj and L(A) intersects Li then it also intersects Lj. Hence r A ~ r~. This imme­ diately yields v(A) :::;k v'(A). D

In other words, B' always yields more information than B. The downside is that B' may give the inconsistent an­ swer T to a query A whereas B may have given a true or false answer to it. The partitioning of information into separate languages may on occasion miss some answers which might have been obtained without such partition­ ing, but it is more likely to be consistent in particular queries.

6 B-Structure Revision

What will happen to a B-structure when an agent receives some information which overlaps two sub­ languages? One possibility is that the agent accepts the consequences within each sub-language while still keeping them separate. If I learn that both Beijing and London had cold winters, I am not likely to merge all my other beliefs about the two cities. However, if I repeatedly receive information which overlaps two sub­ languages, I may decide that the division is artificial and should be abandoned. Options A and B below corre­ spond to these two different attitudes.

option A - the non-merging option: Assume that each of the languages Li. has its own AGM style revision operator. Given a belief structure B and a new input A, define, for each i, the i-shadow of A to be the set {BIB ELi 1\ A f- B}. This will be a theory Tf in Li · Tf is what A has to say about the language Li . Let Ai ELi be such that Tf = Cn(Ai )· Now define the theories Tf' by:

Tf' = Ti -i- Ai if Ai is consistent with Ti, and Tf' = Ti *i Ai otherwise where *i is a local revision op­

erator for Li.

Then the revised B-structure B * A will equal { (£1, T{'), ... , (Ln, r;n }.

In practice, if L(A) n Li is empty, we can just leave Ti unchanged, saving computational time. We define B -i- A analogously, except that we use the operator -i­ on the various Ti.

option B - the merging option: Given a formula A as input and a belief base B, assume without loss of generality that A has been written in the smallest language in which it can be expressed [Parikh, 1996]. Let as before r A = UTi : Li n L(A) f: 0, where L(A) is the language of A. Let TA be Cn(r A) and LA = U LilLi n L(A) f: 0. Now replace all those languages Li such that Lin L(A) f: 0 by the single language U Li : Lin L(A) f: 0, which is their union. At the same time, replace all the corresponding Ti by the theory TA * A. This new way will specialize to the procedure in [Parikh, 1996] where the languages were all assumed to be disjoint but the receipt of information resulted in joining those theories whose languages overlapped the language of the new information.

6.1 Properties of B-structure revision

Both options A and B are computationally efficient. Generally we assume that each Li has relatively small size, say under some fixed p, while the cardinality n of the whole language L = U Li might be quite large. Then given a k-partition and a formula A with at most l dis­ tinct symbols, the query answering procedures run in time which is exponential in l x k x p, but linear in n. (For option A, the procedure is linear in n, k and expo­ nential only in l + p). Thus if k x l x p - the number of atomic propositions relevant to A - is small compared to n, as is usually the case, the computational cost will be much smaller than that of usual update procedures which are exponential in n.

The update procedures need not preserve refinements. If B refines B' and there is new information A, it may re­ veal an inconsistency in B', even though B is unfazed. It may seem foolish not to notice one's own inconsistencies, but these are often unavoidable, as with the well known Preface and Lottery paradoxes [Kyburg, 1961], [Kyburg, 1997]. The ability to retain a measure of consistency and act on the basis of one's implicit beliefs may have much to say in its favour. ·

Option B results in two formally distinct subject areas merging as the result of some new information which straddles them. In real life this is likely to happen only occasionally. Suppose I have a B-structure which keeps my beliefs about Turkey, Iraq and Iran separate. If I now receive a great many piecP" of information about the Kurds who are scattered over these three countries then I may simply create the new subject Asia Minor and give up my attempt to deal with the three countries separately.

6.2 Analogues of the AGM axioms

Let B * A denote the revision of B-structure B by the formula A according to option B. The axioms B1-B5 be­ low hold. The set theoretic notions E, ~ used in stating the AGM axioms are now replaced by more sophisticated generalizations which enter in with Belnap's four truth values. For option A, axiom B2 needs the caveat that A E Li for some i or, at least that A {:} B1 1\ .. : 1\ Bp where each Bk is in some Li and pis small. However disjunctive information which straddles two of the Li may be lost if we insist, as we do in option A, on keeping the Li separate.

Let B be a belief structure, A a new piece of informa­ tion, * the revision operator. We then have the following axioms: (read A E Bas 'A is an implicit belief according to B'.)

Bl. B *A, the revision of B by A, is a belief structure.

B2. A E B*A

B3. If A¢? B, then B *A= B * B

B4. B *A ~ B -f.. A. i.e. if B *A and B -f.. A give values v, v' to A, then v <k v'.

B5. If A is consistent with B, i.e it is not the case that vB(A) E {false, T}, then B *A = B -f.. A

Other Issues: Issues commonly raised in belief revision literature include, for instance, the axiom of recovery, re­ vision by conjunctions, by sets of propositions etc. Most of these properties will hold at the local level provided that the original local operations have them. At the non-local level when several of the Ti interact in a par­ ticular case of a belief revision, more complex patterns of behaviour will emerge. These require further investi­ gation.

6.3 Review of Previous Work

We briefly discuss how other authors have addressed the issues mentioned at the outset.

Work on the minimal change model has concentrated on minimizing the number of beliefs given up during the contraction operation. To this end, operations such as partial meet contraction using selection functions were defined in [Alchourron et. al, 1985]. A moti­ vation for the choice of beliefs to be dropped is given by the notion of epistemic entrenchment introduced by [Gardenfors and Makinson, 1988] and refined for iterated belief change by [Nayak, 1994], [Darwiche and Pearl, 1994], [Lehmann, 1995]. [Williams, 1996] uses the con­ cept of maxi-adjustment to achieve maximal inertia of information under iterated belief revision. [Georgatos , 1999] presents a generalization of entrenchment that serves as a representation of the AGM axioms. The notion of epistemic relevance is used for minimal con­ traction in [Hansson, 1992] and [Nebel, 1992].

The distinction between implicit and explicit beliefs, has been explored by the proponents of the belief base method such as [Fuhrmann, 1991], [Nebel, 1992], [Hans­ son 1991;1992]. [Rott, 1992] combines some intuitions in showing how epistemic entrenchment orderings can be carried out for safe contractions for belief bases.

Belief revision for inconsistent belief bases has been studied in an alternative approach by [Brewka, 1991] . The possibility of paraconsistent belief revision is ex­ plored by [Tanaka, 1997] while [Restall and Slaney, 1995] have developed a paraconsistent semantical representa­ tion based on the revision of models approach suggested in [Grove, 1988]. The work of [Schotch and Jennings,

1980] predates the AGM approach to belief revision. They consider an approach based on giving up the ad­ junction rule: from r 1- A and r 1- B concluder 1- AI\B. As we saw, our treatment retains this rule at the local level.

The investigation of complexity procedures in [Nebel, 1992], via a fine-grained set of complexity classes, has shown that the complexity of base revision procedures satisfying AGM postulates is that of ordinary proposi­ tional derivability. Nebel's comparison of different revi­ sion methods shows that model-based revision methods such as those of [Dalal, 1988] have a complexity which exceeds both NP and co-NP.

Conclusion: We started this paper by indicating four desiderata which a framework for answering queries and for belief revision should try to meet. The B-structures framework meets all four. In future work we intend to carry out a thorough study of this interesting new model for belief representation and revision and to implement the query answering and revision procedures.

Acknowledgements: This research was supported in part by a grant from the Research Foundation of CUNY. We thank Ron Fagin, Melvin Fitting, Konstanti­ nos Georgatos, Henry Kyburg, Graham Priest and the referees for helpful comments.

References:

[Alchourron et. al, 1985] Alchourron, C., Gardenfors, P. and Makinson, D. (1985) On the logic of theory Change: partial meet functions for contraction and re­ vision. Journal of Symbolic Logic, Vol 580, pp 510-530.

[Belnap, 1977] Belnap, N.D. A useful four-valued logic. Modern Uses of Multiple- Valued Logic, J.M Dunn and G. Epstein eds. , D. Reidel.

[Brewka, 1991] Brewka, G., Belief revision in a frame­ work for default reasoning. The Logic of Theory Change, A. Fuhrmann and M Morreau, editors, LNAI 465, Springer.

[Dalal, 1988] Dalal, M. Investigations into a theory of knowledge base revision. Proceedings of the Seventh Na­ tional Conference of the American Association for Arti­ ficial Intelligence, Saint-Paul, MN, pp 475-479.

[Darwiche and Pearl, 1994] Darwiche, A, Pearl J. On the logic of iterated belief revision. Proceedings of Theoretical Aspects of Rationality and Knowledge, 1994, pages 5-23.

[Fitting, 1989] Fitting, Melvin. Bilattices and the the­ ory of truth. Journal of Philosophical Logic, Vol18, 225256, 1989.

[Fuhrmann, 1991] Fuhrmann, Andre. Theory con­ traction through base revision. Journal of Philosophical Logic, Vol 20, pp175-203, 1991.

[Gardenfors and Makinson, 1988] Gardenfors P., Makinson, D. Revisions of knowledge systems using epis­ temic entrenchment. Proceedings of Theoretical As­ pects of Reasoning about Knowledge, Moshe Vardi ed., Morgan-Kaufrhann, pp 83-96, 1988.

[Gardenfors, 1988] Gardenfors, Peter. Knowledge in Flux: Modeling the Dynamics of Belief States, Bradford Books, MIT Press, Cambridge, MA, 1988.

[Georgatos, 1999] Georgatos, Konstantinos. To pref­ erence via entrenchment. Annals of Pure and Applied Logic, to appear.

[Grove, 1988] Grove, A. Two modellings for theory change. Journal of Philosophical Logic, 17:157-170, 1988.

[Hansson, 1992] Hansson, S.O. A dyadic representa­ tion of belief. Belief Revision, Gardenfors, P. ed., Cam­ bridge, 1992.

(Hansson, 1991] Hansson, S.O. In defense of base con­ traction. Synthese, 91:239-245, 1992.

(Kyburg, 1961] Kyburg, Henry, Probability and the Logic of Rational Belief, Middletown, CT: Wesleyan, 1961

(Kyburg, 1997] Kyburg, Henry. The rule of adjunction and reasonable inference. Journal of Philosophy, XCIV, 3, 1997, pages 109-125.

(Lehmann, 1995] Lehmann, D. Belief revision, revised. Proceedings of the Fourteenth International Joint Con­ ference on Artificial Intelligence 1995, pages 1534-1540.

(Minsky, 1986] Minsky, M., The Society of Mind, Si­ mon and Schuster.

[Nayak, 1994] Nayak, Abhaya. Foundational belief change. Journal of Philsophical Logic, Vol. 23, pp 495533, 1994

(Nebel, 1992] Nebel, B. Syntax based approaches to belief revision. Belief Revision, Gardenfors, P. ed., Cam­ bridge, 1992.

[Parikh, 1996] Parikh, Rohit. Beliefs, belief revision and splitting languages. Preliminary Proceedings of In­ formation Theoretic Approaches to Logic, Language and Computation, 1996, editors L. Moss, M. de Rijke and J . Ginzburg. Final version to appear, CSLI, 1999.

[Restall and Slaney, 1995] Restall, G and Slaney, J. Realistic belief revision. Technical Report: TR- ARP-295, Automated Reasoning Project, Australian National University, 1995.

[Rott, 1992] Rott, Hans. Preferential belief change using generalized epistemic entrenchment, Journal of Logic, Language and Information, 1:45-78, 1992.

(Schotch and Jennings, 1980] Schotch P.K, Jennings R. Inference and necessity. Journal of Philosophical Logic, 9 (1980) , 327-340.

(Tanaka, 1997] Tanaka, Koji. What does paraconsis­ tency do? The case of belief revision. The Logica Year­ book, Timothy Childers ed., Praha, 1997, pp 188-197.

[Williams, 1996] Williams, Mary-Anne. A practical approach to belief revision: Reason-based change, in L. Aiello and S. Shapiro eds. Principles of Knowledge Rep­ resentation and Reasoning: Proceedings of the Fifth In­ ternational Conference, Morgan-Kaufmann, San Mateo, CA, 412-421, 1996.