New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

MultiAgent Systems

by: Alek Haley

MultiAgent Systems CS 6100

Alek Haley
Utah State University
GPA 3.58

Vicki Allan

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Vicki Allan
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 28 page Class Notes was uploaded by Alek Haley on Wednesday October 28, 2015. The Class Notes belongs to CS 6100 at Utah State University taught by Vicki Allan in Fall. Since its upload, it has received 22 views. For similar materials see /class/230445/cs-6100-utah-state-university in ComputerScienence at Utah State University.

Similar to CS 6100 at Utah State University

Popular in ComputerScienence


Reviews for MultiAgent Systems


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/28/15
Belief Revision An Introduction PETER GARDENFORS Cognitive Science Department of Philosophy Lund University S223 50 Lund Sweden 1 THE PROBLEMS OF BELIEF REVISION 11 An Example Suppose that you have a database that contains among other things the following pieces of information in some form of code All European swans are white 0L 5 The bird caught in the trap is a swan y The bird caught in the trap comes from Sweden 5 Sweden is part of Europe If your database is coupled with a program that can compute logical inferences in the given code the following fact is derivable from 0L 5 8 The bird caught in the trap is white Now suppose that as a matter of fact the bird caught in the trap turns out to be black This means that you want to add the fact c8 ie the negation of 8 to the database But then the database becomes inconsistent If you want to keep the database consistent which is normally a sound methodology you need to revise it This means that some of the beliefs in the original database must be retracted You don t want to give up all of the beliefs since this would be an unnecessary loss of valuable information So you have to choose between retracting 0L 5 y or 5 The problem of belief revision is that logical considerations alone do not tell you which beliefs to give up but this has to be decided by some other means What makes things more complicated is that beliefs in a database have logical consequences so when giving up a belief you have to decide as well which of the consequences to retain and which to retract For example if you decide to retract 0c in the situation described here 0L has as logical consequences among others the following two OL39 All European swans except the one caught in the trap are white and 0cquot All European swans except some of the Swedish are white Do you want to keep any of these sentences in the revised database 12 The Methodological Problems of Belief Revisions When trying to handle belief revisions in a computational setting there are three main methodological questions to settle 1 How are the beliefs in the database represented Most databases work with elements like facts and rules as primitive forms of representing information The code used to represent the beliefs may be more or less closely related to standard logical formalism A mechanism for belief revision is sensitive to the formalism chosen to represent the beliefs 2 What is the relation between the elements explicitly represented in the database and the beliefs that may be derived from these elements This relation is to a large extent dependent on the application area of the database In some cases the elements explicitly formulated in the database have a special status in comparison to the logical consequences of these beliefs that may be derived by some inference mechanism In other cases the formulation of the beliefs in the database is immaterial so that any representation that has the same logical consequences ie the same set of implicit beliefs is equivalent As will be seen in several papers in this volume the nature of the relation between explicit and implicit beliefs is of crucial importance for how the belief revision process is attacked 3 How are the choices concerning what to retract made Logic alone is not sufficient to decide between which beliefs to give up and which to retain when performing a belief revision What are the extralogical factors that determine the choices One idea is that the information lost when giving up beliefs should be kept minimal Another idea is that some beliefs are considered more important or entrenched than others and the beliefs that should be retracted are the least important ones Within computer science the use of integrity constraints is a common way of handling the problem Again the methodological rules chosen here are dependent on the application area 13 Three Kinds of Belief Changes A belief revision occurs when a new piece of information that is inconsistent with the present belief system or database is added to that system in such a way that the result is a new consistent belief system But this is not the only kind of change that can occur in a belief system Depending on how beliefs are represented and what kinds of inputs are accepted different typologies of belief changes are possible In the most common case when beliefs are represented by sentences in some code and when a belief is either accepted or rejected in a belief system K so that no degrees of belief are considered one can distinguish three main kinds of belief changes i Expansion A new sentence Q is added to a belief system K together with the logical consequences of the addition regardless of whether the larger set so formed is consistent The belief system that results from expanding K by a sentence Q will be denoted KQ ii Revision A new sentence that is inconsistent with a belief system K is added but in order to maintain consistency in the resulting belief system some of the old sentences in K are deleted The result of revising K by a sentence Q will be denoted KlQ iii Contraction Some sentence in K is retracted without adding any new facts In order for the resulting system to be closed under logical consequences some other sentences from K must be given up The result of contracting K with respect to Q will be denoted KQ Expansions of belief systems can be handled comparatively easily KQ can simply be de ned as the logical closure of K together with Q Dem K w K u m P w As is easily shown KQ de ned in this way will be closed under logical consequences and will be consistent when Q is consistent with K It is not possible to give a similar explicit de nition of revisions and contractions in logical and settheoretical notions only The problems for revisions were presented in the introductory example There is no purely logical reason for making one choice rather than the other among the sentences to be retracted but we have to rely on additional information about these sentences Thus from a logical point of view there are several ways of specifying the revision KiQ Though KiQ cannot be characterized uniquely in logical terms the general properties of a revision function can be investigated and 7 in some cases at least 7 algorithms can be found for computing revision functions These two goals will be handled technically by using the notion of a revision function quot4quot which has two arguments a belief system K and a sentence Q and which has as its value the revised belief system KlQ The contraction process faces parallel problems To give a simple example consider a belief system K which contains the sentences I V PAW gt X and their logical consequences among which is X Suppose that we want to contract K by deleting X Of course X must be deleted from K when forming K 39X but also at least one of the sentences I V or PAW gt X must be given up in order to maintain consistency Again there is no purely logical reason for making one choice rather than the other Another concrete example is provided by Fagin Ullman and Vardi 1983 p 353 The common denominator in both this example and the introductory one is that the database is not viewed merely as a collection of logically independent facts but rather as a collection of axioms from which other facts can be derived It is the interaction between the updated facts and the derived facts that is the source of the problem In parallel with revision we can introduce the concept of a contraction function quotLquot which has the same two arguments as before ie a belief system K and a sentence I to be retracted from K and which produces as its value the belief system K In Section 33 I shall show that the problems of revision and contraction are closely related 7 being two sides ofthe same coin 14 Two Approaches to Describing Belief Revisions When tackling the problem of belief revision there are two general strategies to follow namely to present explicit constructions of the revision process and to formulate postulates for such constructions For a computer scientist the ultimate solution to the problem about belief revision is to develop algorithms for computing appropriate revision and contraction functions for an arbitrary belief system In this volume several proposals for constructions of revision methods will be presented These methods are not presented as pure algorithms but on a slightly more general level However in order to know whether an algorithm is successful or not it is necessary to determine what an appropriate revision function is Our standards for revision and contraction functions will be various I 39 quot r The fui 39 quot of these postulates are given in a more or less equational form One guiding idea is that the revision K of K with respect to i should represent the minimal change of K needed to J I 39 quotJ The J ofthe r 39 will also be investigated Much of the theoretical work within belief revision theory consists of connecting the two approaches This is done via a number of representation theorems which show that the revision methods that satisfy a particular set of rationality postulates are exactly those that fall within some computationally well defined class of methods1 1For further discussion of the two strategies cf Makinson 1985 pp 350351 2 MODELS OF BELIEF STATES 2 1 Preliminaries Before we can start discussing models of belief revision we must have a way of modelling belief states since a revision method is defined as a function from one belief state into another The most common models of belief states in computational contexts are sentential or propositional in the sense that the elements constituting the belief systems are coded as formulas representing sentences This kind of model will be the focus of this introduction but some alternative types of models will be encountered in the volume But even if we stick to propositional models of belief systems there are many options First of all we must choose an appropriate language to formulate the belief sentences For example databases include some form of rules and there are many ways of formalizing these as quantified sentences in first order logic as PROLOG rules corresponding to Hornclauses as default statements eg in the style of Reiter 1980 as probability statements etc In this introduction I shall work with a language L which is based on first order logic The details of L will be left open for the time being It will be assumed that L is closed under applications of the boolean operators n negation A conjunction V disjunction and gt implication We will use I V X etc as variables over sentences in L It is also convenient to introduce the symbols T and J for the two sentential constants quottruthquot and quotfalsityquot What is accepted in a formal model of a belief state are not only the sentences that are explicitly put into the database but also the logical consequences of these beliefs Hence the second factor which has to be decided upon when modelling a belief state is what logic governs the beliefs In practice this depends on which theoremproving mechanism is used in combination with the database However when doing a theoretical analysis one wants to abstract from the idiosyncracies of a particular algorithm for theorem proving and start from a more general description of the logic If the logic is undecidable further complications will arise but we will ignore these for the time being I shall assume that the underlying logic includes classical propositional logic and that it is compact2 If K logically entails I we will write this as K i I Where K is a set of sentences we shall use the notation CnK for the set of all logical consequences of K ie CnK 1 K I All papers in this volume presume classical logic except the one by Cross and Thomason where a fourvalued logic is used instead 2 A logic is compact iff whenever A is a logical consequence of a set of sentence K then there is a nite subset K39 of K such that A is a logical consequence of K39 22 Belief Sets The simplest way of modelling a belief state is to represent it by a set of sentences from L Accordingly we define a belief set as a set K of sentences in L which satis es the following integrity constraint3 1 If K logically entails V then V e K In logical parlance I says that K is closed under logical consequences The interpretation of such a set is that it contains all the sentences that are accepted in the modelled belief state Consequently when Q e K we say that Q is accepted in K and when Q e K we say that Q is rejected in K It should be noted that a sentence being accepted does not imply that it has any form of justification or support4 A belief set can also be seen as a theory which is a partial description of the world quotPartialquot because in general there are sentences Q such that neither Q nor Q are in K By classical logic whenever K is inconsistent then K I Q for every sentence Q of the language L This means that there is exactly one inconsistent belief set under our definition namely the set of all sentences of L We introduce the notation K J for this belief set 23 Belief Bases Against modelling belief states as belief sets it has been argued Makinson 1985 Hansson 1990 1991 Nebel 1990 Fuhrmann 1991 that some of our beliefs have no independent standing but arise only as inferences from our more basic belief It is not possible to express this distinction in a belief set since there are no markers for which beliefs are basic and which are derived Furthermore it seems that when we perform revisions or contractions we never do it to the belief set itself which contains an infinite number of elements but rather on some finite base for the belief set Formally this idea can be modelled by saying that BK is a base for a belief set K iff BK is a finite subset of K and CnBK K Then instead of introducing revision and contraction functions that are defined on belief sets it is assumed that these functions are defined on bases Such functions will be called base revisions and base contractions respectively This approach introduces a more negrained structure since we can have two bases BK and CK such that CnBK CnCK but BK CK The papers by Nebel and Hansson in this volume concern base revisions They will be presented in Section 35 3Belief sets were called knowledge sets in Gardenfors and Makinson 1988 4For further discussion of the interpretation of belief sets cf Gardenfors 1988 There is no general answer to the question of which model is the best of full belief sets or bases but this depends on the particular application area Within computer science applications bases seem easier to handle since they are explicitly finite structures However it has been argued in Gardenfors 1990 that much of the computational advantages of bases for belief sets can be modelled by belief sets together with the notion of epistemic entrenchment of beliefs cf Section 41 24 Possible Worlds Models An obvious objection to using sets of sentences as models of belief states is that the objects of belief are normally not sentences but rather the contents of sentences that is propositions The characterization of propositions that has been most popular among philosophers during recent years is to identify them with sets of possible worlds The basic semantic idea connecting sentences with propositions is then that a sentence expresses a given proposition if and only if it is true in exactly those possible worlds that constitute the set of worlds representing the proposition By taking beliefs to be beliefs in propositions we can then model a belief state by a set WK of possible worlds The epistemic interpretation of WK is that it is the narrowest set of possible worlds in which the individual being in the modelled belief state is certain to find the actual world This kind of model of a belief state has been used by Harper 1977 Grove 1988 among others and in a generalized form by Spohn 1988 also cf the comparisons in Gardenfors 1978 In this volume Katsuno and Mendelzon and Morreau use this way of modelling belief states There is a very close correspondence between belief sets and possible worlds models For any set WK of possible worlds we can define a corresponding belief set K as the set of those sentences that are true in all worlds in WK assuming that the set of propositional atoms is finite It is easy to verify that K defined in this way satisfies the integrity constraint 1 so that it is indeed a belief set Conversely for any belief set K we can define a corresponding possible worlds model WK by identifying the possible worlds in WK with the maximal consistent extensions of K Then we say that a sentence I is true in such an extension w iff I e w Again it is easy to verify that this will generate an appropriate possible worlds model for details cf Grove 1988 From a computational point of view belief sets are much more tractable than possible worlds models So even though possible worlds models are popular among logicians the considerations here show that the two kinds of models are basically equivalent And if we want to implement belief revision systems sentential models like belief sets and in particular bases for belief sets are much easier to handle 25 Justifications vs Coherence Models Another question that has to be answered when modelling a state of belief is whether the justi cations for the beliefs should be part of the model or not With respect to this question there are two main approaches One is the foundations theory which holds that one should keep track of the justifications for one s beliefs Propositions that have no justification should not be accepted as beliefs The other is the coherence theory which holds that one need not consider the pedigree of one s beliefs The focus is instead on the logical structure of the beliefs 7 what matters is how a belief coheres with the other beliefs that are accepted in the present state5 The belief sets presented above clearly fall into the latter category It should be obvious that the foundations and the coherence theories have very different implications for what should count as rational changes of belief systems According to the foundations theory belief revision should consist first in giving up all beliefs that no longer have a satisfactory justification and second in adding new beliefs that have become justified On the other hand according to the coherence theory the objectives are first to maintain consistency in the revised epistemic state and second to make minimal changes of the old state that guarantee sufficient overall coherence Thus the two theories of belief revision are based on con icting ideas of what constitutes rational changes of belief The choice of underlying theory is of course also crucial for how a computer scientist will attack the problem of implementing a belief revision system Doyle s paper in this volume deals with the relations between justification theories and coherence theories of belief revision In an earlier paper Gardenfors 1990 I presented some arguments for preferring the coherence approach to the foundations approach Doyle argues that I have overemphasized the differences between the two approaches He also wants to show that the foundations approach represents the most direct way of making the coherence approach computationally accessible Galliers theory of autonomous belief revision also in this volume suggests in another way that the choice between coherence and foundational theories may not be exclusive her theory in fact represents a blend between the two approaches In a sense also the belief base models presented in Section 23 show traces of justif1cationalism 7 the beliefs in the base are thought of as more foundational than the derived beliefs 5Harman 1986 presents an analysis of the epistemological aspects of the two approaches 3 RATIONALITY POSTULATES FOR BELIEF REVISION 31 The AGM Postulates for Revision In this section it will be assumed that belief sets that is sets of sentences closed under logical consequences are used as models of belief states The goal is now to formulate postulates for rational revision and expansion functions de ned over such belief sets The underlying motivation for these postulates which are taken from Alchourron Gardenfors and Makinson 1985 hence the name is that when we change our beliefs we want to retain as much as possible from our old beliefs 7 we want to make a minimal change Information is in general not gratuitous and unnecessary losses of information are therefore to be avoided This heuristic criterion may be called the criterion of informational economy However it turns out to be difficult to give a precise quantitative definition of the loss of information see eg the discussion of minimality in Gardenfors 1988 pp 6668 Instead we shall follow another line of specifying 39minimal change39 We assume that the sentences in a belief set have different degrees of epistemic entrenchment and when we give up sentences when forming a revision or a contraction we give up those with the lowest degree of entrenchment The idea of epistemic entrenchment will be presented in greater detail in Section 41 It is assumed that for every belief set K and every sentence Q in L there is a unique belief set Kl39Q representing the revision of K with respect to Q In other words 391 is a function taking a belief set and a sentence as arguments and giving a belief set as a result This is admittedly a strong assumption since in many cases the information available is not sufficient to determine a unique revision However from a computational point of view this assumption is gratifying In Doyle 1991 and Galliers paper in this volume this assumption is not made The first postulate requires that the outputs of the revision function indeed be belief sets Kl 1 For any sentence Q and any belief set K KlQ is a belief set The second postulate guarantees that the input sentence Q is accepted in K39l39Q K2 Q e KQ The normal application area of a revision process is when the input Q contradicts what is already in K that is Q e K However in order to have the revision function defined for all arguments we can easily extend it to cover the case when Q E K In this case revision is identified with expansion For technical reasons this identification is divided into two parts Kl3 K l Q Q KQ Kl4 If oQ e K then KQ g KlQ The purpose of a revision is to produce a new consistent belief set Thus KlQ should be consistent unless Q is logically impossible KlS KlQ KJ if and only if I Q It should be the content of the input sentence Q rather than its particular linguistic formulation that determines the revision In other words belief revisions should be analysed on the knowledge level and not on the syntactic level This means that logically equivalent sentences should lead to identical revisions Kl6 If I Q H Q then KlQ KlQI The postulates Kll Kl6 are elementary requirements that connect K Q and KlQ This set will be called the basic set of postulates The final two conditions concern composite belief revisions The idea is that if KlQ is a revision of K and KQ is to be changed by a further sentence V such a change should be made by expansions of KlQ whenever possible More generally the minimal change of K to include both Q and V that is K39lQV ought to be the same as the expansion of K39l39Q by V so long as V does not contradict the beliefs in KlQ For technical reasons the precise formulation is split into two postulates Ki7 KQV g KQy Kl8 If cw E KlQ then KlQy Q KQV When ow e K then KlQV is KJ which is why the proviso is needed in Kl 8 but not in Kl7 We turn next to some consequences of the postulates It can be shown Gardenfors 1988 p 57 that in the presence of the basic set of postulates Kl7 is equivalent to 1 KlQ m K l QgKiQNQI Another principle that is use ll is the following factoring condition 2 KQVV KlQ or KlQVV KlQ or KlQVV KlQ m KlQI It can be shown that given the basic postulates 2 is in fact equivalent to the conjunction of K7 and K8 Furthermore Kl7 and Kl8 together entail the following identity criterion 3 KlQ KlQ ifand only ifW e KlQ and Q e KlQI The postulates Kll Ki 8 do not uniquely characterise the revision KlQ in terms of only K and Q This is however as it should be I believe it would be a mistake to expect that only logical properties are sufficient to characterise the revision process 32 The AGM Postulates for Contraction The postulates for the contraction function 39439 will to an even larger extent than for revisions be motivated by the princple of informational economy The first postulate is of a familiar kind K41 For any sentence Q and any belief set K KLQ is a belief set Because KLQ is formed from K by giving up some beliefs it should be required that no new beliefs occur in K Q K42 KLQ K When Q E K the criterion of informational economy requires that nothing be retracted from K K43 IfQ E K then KLQ K We also postulate that the sentence to be contracted not be a logical consequence of the beliefs retained in K4Q unless Q is logically valid in which case it can never be retracted because of the integrity constraint 1 K44 If not I Q then Q E K4Q From K41 to K44 it follows that 4 If Q E K then K 39QQ g K In other words if we first retract Q and then add Q again to the resulting belief set KLQ no beliefs are accepted that were not accepted in the original belief set The criterion of informational economy demands that as many beliefs as possible should be kept in K 39Q One way of guaranteeing this is to require that expanding KLQ by Q should take us back to exactly the same state as before the contraction that is K K45 IfQ e K then K E K QQ This is the so called recovery postulate which enables us to undo contractions It has turned out to be the most controversial among the AGM postulates for contraction The sixth postulate is analogous to K46 K46 If I Q H Q then KEQ KLQI Postulates K39 1 K 396 are called the basic set of postulates for contractions Again two further postulates for contractions with respect to conjunctions will be added The motivations for these postulates are much the same as for Kl7 and Ki 8 K 397 KLq m K39 V g KLko K48 Ifq e Kapmy then mey g K w It is interesting to note that K47 is in fact equivalent given the basic postulates to the seemingly weaker 5 144 0 Cn E K V In parallel with 2 it can be shown that KL7 and KL 8 are jointly equivalent to the following condition 6 K qmw K q or K omy K w or K qmw Kw m K w A useful consequence of 6 is the following which says that K39 V is 39covered either by KLQ or by KLW 7 Either K4 Aw E K4 or KL AW g KV The postulates for revision and contraction and their consequences are dicussed further in Chapter 3 of Gardenfors 1988 33 From Contractions t0 Revisions and Vice versa We turn next to a study of the connections between revision and contraction functions In the previous two sections they were characterized by two sets of postulates These postulates are independent in the sense that the postulates for revisions do not refer to contractions and vice versa A natural question is now whether either contraction or revision can be defined in terms of the other Here we shall present two positive answers to this question A revision of a knowledge set can be seen as a composition of a contraction and an expansion More precisely In order to construct the revision K411 one first contracts K with respect to WI and then expands KLW by I Formally we have the following definition which is called the Levi identity DefF K K That this definition is appropriate is shown by the following result Theorem 1 If a contraction function 394 satisfies K41 to K44 and K46 then the revision function i obtained from Def 4 satisfies Kil Ki6 Furthermore if K 397 also is satisfied Kl7 will be satisfied for the defined revision function and if K4 8 also is satisfied Kl 8 will be satisfied for the defined revision function This result supports Def l as an appropriate de nition of a revision function Note that the controversial recovery postulate K45 is not used in the theorem Conversely contractions can be de ned in terms of revisions The idea is that a sentence V is accepted in the contraction K Q if and only if V is accepted both in K and in Kl Q Formally this amounts to the following de nition which has been called the Harper identity Def K Q K m Kl Q Again this de nition is supported by the following result Theorem 2 If a revision function l satis es Kll to Kl6 then the contraction function 39439 obtained from Def satis es K41 K4 6 Furthermore if K7 is satisfied KL 7 will be satis ed for the de ned contraction function and if Kl 8 is satis ed K398 will be satis ed for the de ned contraction function The two theorems show that the de ned revision and contraction functions have the right properties Hence the two sets of postulates for revision and contraction functions are interchangeable and a method for constructing one of the functions would automatically via Def 4 or Def 4 yield a construction of the other function satisfying the desired set of postulates 34 Representation Theorems This section will introduce a rst kind of explicit modelling of a contraction function for belief sets Via the Levi identity Def 4 and Theorem 1 such a model can be used to de ne a revision function as well The problem in focus is how to de ne the contraction K4Q with respect to a belief set K and a proposition Q A general idea is to start from K and then give some recipe for choosing which propositions to delete from K so that KLQ does not contain Q as a logical consequence According to the criterion of informational economy we should look at as large a subset of K as possible The following notion is useful A belief set K39 is a maximal subset ofK thatfaz39ls to imply Q if and only if i K39 E K ii Q E CnK and iii for any Kquot such that K39C Kquotg K Q e CnKquot The last clause entails that if K39 were to be expanded by some sentence from KK it would entail Q The set of all belief sets that fail to imply Q will be denoted KJQ Using the assumption that I is compact it is easy to show that this set is nonempty unless Q is logically valid A rst tentative solution to the problem of constructing a contraction function is to identify KQ with one of the maximal subsets in KJQ Technically this can be done with the aid of a selection function 7 that picks out an element 7KJQ of KJQ for any K and any Q whenever KJQ is nonempty We then de ne KLQ by the following rule Maxichoz39ce KQ YKJQ when not lQ and K4Q K otherwise Contraction functions determined by some such selection function were called maxichoz39ce contraction functions in Alchourron Gardenfors and Makinson 1985 A first test for this construction is whether it has the desirable properties It is easy to show that any maxichoice contraction function satisfies KL 1 K46 But it will also satisfy the following fullness condition K4F Ifw e K and V E K Q then V gt Q e K4Q for any belief set K We can now show that K4 1 K46 and KLF characterizes maxichoice contraction function in the sense of the following representation theorem Let us say that a contraction function 39439 can be generated by a maxichoice contraction function iff there is some selection function 7 such that 394 is identical with the function obtained from y by the maxichoice rule above Theorem 3 Any contraction function that satisfies K 1 K46 and K4F can be generated by a maxichoice contraction function However in a sense maxichoice contraction functions in general produce contractions that are too large A result from Alchourron and Makinson 1982 is applicable here Let us say that a belief set K is maximal iff for every sentence V either V e K or ow e K One can now show the following discomforting result Theorem 4 If a revision function is defined from a maxichoice contraction function 39 by means of the Levi identity then for any Q such that Q e K KlQ will be maximal In a sense maxichoice contraction functions create maximal belief sets So a second tentative idea is to assume that K Q contains only the propositions that are common to all of the maximal subsets in KJQ Meet KLQ mKJQ whenever KJQ is nonempty and KLQ K otherwise This kind of function was called full meet contraction function in Alchourron Gardenfors and Makinson 1985 Again it is easy to show that any full meet contraction function satisfies KL 1 K46 They also satisfy the followingz39ntersectz39on condition KLI For all Q and V K QV KLQ m KLW We have the following representation theorem Theorem 5 A contraction function satis es K39l K 6 and K 39 1 iff it can be generated as a full meet contraction function The drawback of of full meet contraction is the opposite of maXichoice contraction 7 in general it results in contracted belief sets that are far too small The following result is proved in Alchourron and Makinson 1982 Theorem 6 If a revision function is defined from a full meet contraction function 394 by means of the Levi identity then for any I such that 11 e K Klq Cn In other words the revision will contain only I and its logical consequences A third attempt is to use only some of the maximal subsets in KJI when defining KLQ Technically a selection function y can be used to pick out a nonempty subset YKJ of KJI if the latter is nonempty and that puts 7KJ K in the limiting case when KJI is empty The contraction function can then be defined as follows Partial meet K4 myKJl Such a contraction function was called a partial meet contraction function in Alchourron Gardenfors and Makinson 1985 The following representation theorem shows that K41 K46 indeed characterizes the class of partial meet contraction functions Theorem 7 For every belief set K 4 is a partial meet contraction function i l satisfies postulates K41 K46 So far we have put no constraints on the selection function y The idea of y picking out the 39best elements of KJI can be made more precise by assuming that there is an ordering of the maximal subsets in KJI that can be used to pick out the top elements Technically we do this by introducing the notation MK for the union of the family of all the sets KJI where I is any proposition in K that is not logically valid Then it is assumed that there eXists a transitive anal re exive ordering relation S on MK When KJI is nonempty this relation can be used to de ne a selection function that picks out the top elements in the ordering Defy 7KJ K 6 KM Kquot s K for all Kquot e KJ A contraction function that is determined from S via the selection function 7 given by Def y will be called a transitively relational partial meet contraction function This way of defining the selection function constrains the class of partial meet contraction functions that can be generated Theorem 8 For any belief set K 39439 satisfies K41 K4 8 iff 39439 is a transitively relational partial meet contraction function Thus we have found a way of connecting the rationality postulates with a general way of modelling contraction functions The drawback of the construction is that the computa tional costs involved in determining the content of the relevant maximal subsets of a belief set K are so overwhelming that we should take a look at some other possible solutions to the problem of constructing belief revisions and contractions 35 Contraction and Revision of Bases As a generalization of the AGM postulates several authors have suggested postulates for revisions and contractions of bases for belief sets rather than the belief sets themselves In this volume the papers by Hansson and Nebel see also Fuhrmann 1989 Hansson 1989 1991 Makinson 1987 Nebel 1990 use this kind of model As Hansson writes in his paper quotthis model is based on the intuition that some of our beliefs have no independent standing but arise only as inferences from our more basic beliefsquot Hansson and Nebel analyse various forms of base revision and base contractions Nebel evaluates his models in a number of theorems in relation to the AGM postulates but Hansson also introduces some postulates that are special for base revision For example his postulate of relevance can slightly simplified be written as follows in my terminology 8 If V e H but V e H then there is some H39 such that H q C H H and I E CnH but I e CnH U Here H denotes a nite base for a belief state consisting of sentences from L The logical closure of H that is CnH will be a belief set The intuition behind this postulate is that if a sentence V is retracted from H when I is rejected then V plays some role in the fact that H but not HLQ logically entails I On the basis of relevance and other postulates for base contraction Hansson proves several representation theorems and further results can be found in Hansson 1991 An interesting feature of Nebel s paper is that he investigates the computational complexity of different belief revision procedures As far as I know he is the first one to attack these issues An initial problem is that already the trivial case of deciding whether V e Cn0 is coNPcomplete so that a more finegrained set of complexity classes are needed than just saying that belief revision is NPhard Nebel solves this problem by using the polynomial hierarchy of complexity classes Garey and Johnson 1979 On the basis of this hierarchy he is then able to prove a number of results concerning the complexity of various revision methods The analysis shows that all base revision methods analyzed in his paper that satisfy the full set of AGM postulates turn out to be no harder than ordinary propositional derivability 4 CONSTRUCTIVE MODELS 41 Epistemic Entrenchment Even if all sentences in a belief set are accepted or considered as facts so that they are assigned maximal probability this does not mean that all sentences are are of equal value for planning or problemsolving purposes Certain pieces of our knowledge and beliefs about the world are more important than others when planning future actions conducting scientific investigations or reasoning in general We will say that some sentences in a belief system have a higher degree of epistemic entrenchment than others This degree of entrenchment will intuitively have a bearing on what is abandoned from a belief set and what is retained when a contraction or a revision is carried out This section begins by presenting a set ofr 39 for If t which will serve as a basis for a constructive definition of appropriate revision and contraction functions I The guiding idea for the construction is that when a belief set K is revised or contracted the sentences in K that are given up are those having the lowest degrees of epistemic entrenchment Fagin Ullman and Vardi 1983 pp 358 ff introduce the notion of quotdatabase prioritiesquot which is closely related to the idea of epistemic entrenchment and is used in a similar way to update belief sets However they do not present any aXiomatization of this notion Section 5 of Nebel s paper in this volume provides a precise characterization of the relationship between epistemic entrenchment and database priorities We will not assume that one can quantitatively measure degrees of epistemic entrenchment but will only work with qualitative properties of this notion One reason for this is that we want to emphasise that the problem of uniquely specifying a revision function or a contraction function can be solved assuming only very little structure on the belief sets apart from their logical properties IfQ and V are sentences in L the notation Q S V will be used as a shorthand for quotV is at least as epistemically entrenched as Qquot The strict relation Q lt V representing quotV is epistemically more entrenched than Qquot is defined as Q S V and not V S Q Postulates for epistemic entrenchment EEl If Q S V and V S X then Q S X transitivity EE2 If Q l W then Q S V dominance EE3 For any Q and V Q S QV or V S QV conjunctiveness EE4 When K i K i Q E K iff Q S V for all V minimality EES If V S Q for all V then I Q maximality The justification for EE2 is that if Q logically entails V and either Q or V must be retracted from K then it will be a smaller change to give up Q and retain V rather than to give up V because then Q must be retracted too if we want the revised belief set to satisfy the integrity constraint 1 The rationale for EE3 is as follows If one wants to retract QV from K this can only be achieved by giving up either Q or V and consequently the informational loss incurred by giving up QV will be the same as the loss incurred by giving up Q or that incurred by giving up W Note that it follows already from EE2 that QV S Q and QV S V The postulates EE4 and EES only take care of limiting cases EE4 requires that sentences already not in K have minimal epistemic entrenchment in relation to K and EES says that only logically valid sentences can be maximal in S The converse of EES follows from EE2 since ifl Q then V I Q for all V It should be noted that the relation S is only defined in relation to a given K 7 different belief sets may be associated with dilTerent orderings of epistemic entrenchment6 We mention the following simple consequences of these postulates Lemma Suppose the ordering S satisfies EEl EE3 Then it also has the following properties i Q S V or V S Q connectivity ii If VAX S Q then V S Q or X S Q iii Q lt V ifoy lt Q1 iv IfX S Q and X S V then X S QV v IfQ S V then Q S QV The main purpose of this section is to show the connections between orderings of epistemic entrenchment and the AGM contraction and revision functions presented in Sections 31 and 32 We will accomplish this by providing two conditions one of which determines an ordering of epistemic entrenchment assuming a contraction function and a belief set as given and the other of which determines a contraction function assuming an ordering of epistemic entrenchment and a belief set as given The first condition is CS Q S V if and only ifQ E K4QV or I QAV The idea underlying this definition is that when we contract K with respect to QV we must give up Q or V or both and Q should be retracted just in case V is at least as epistemically entrenched as Q In the limiting case when both Q and V are logically valid they are of equal epistemic entrenchment in conformity with EE2 The second and from a constructive point of view most central condition gives an explicit definition of a contraction function in terms of the relation of epistemic entrenchment C4 V e KLQ ifand only ifw e K and either Q lt Q V V or lQ 6Rott 1992 has developed a generalized notion of epistemic entrenchment which is not dependent on a particular K Condition C39 provides us with a tool for explicitly de ning a contraction function in terms of the ordering S An encouraging test of the appropriateness of such a de nition is the following theorem proved in Gardenfors and Makinson 1988 Theorem 9 If an ordering S satis es EEl EES then the contraction function which is uniquely determined by C4 satis es K41 K4 8 as well as the condition CS Conversely we can show that if we start from a given contraction function and determine an ordering of epistemic entrenchment with the aid of condition CS the ordering will have the desired properties Theorem 10 If a contraction function 3939 satis es K 39 1 K 39 8 then the ordering S that is uniquely determined by CS satis es EEl EES as well as the condition C4 These results suggest that the problem of constructing appropriate contraction and revision functions can be reduced to the problem of providing an appropriate ordering of epistemic entrenchment Furthermore condition C39 gives an explicit answer to which sentences are included in the contracted belief set given the initial belief set and an ordering of epistemic entrenchment From a computational point of view applying C4 is trivial once the ordering S of the elements of K is given The comparison Q lt Q V V in C4 is somewhat counterintuitive Rott 1991 has investigated the following more natural version of the condition C R V e K4RQ if and only ifw e K and either Q lt V or lQ He then shows that the contraction function LR defined in this way has the following properties Theorem 11 Let R39 be the contraction function defined in C R If S satis es EEl EES then 39R39 satis es K41 KL4 and K46 KL 8 but not K45 Since LR does not satisfy the controversial recovery39 postulate K45 it follows that LR de ned by CLR is in general not identical to 39L de ned by C47 However let lR and 4 be the revision functions de ned from 394R39 and 39439 by the Levi identity Rott proves Theorem 12 lR and l are identical revision functions A consequence of this theorem is that if we are only interested in modelling revisions and not contractions we can use the extremely simple test CLR when computing the revision functions without having to bother about the disjunctions in CL 42 Safe Contraction 739R39 is a 39withdrawal function39 in the sense of Makinson 1987 20 Yet another approach to the problem of constructing contraction functions was introduced by Alchourron and Makinson 1985 and is called safe contraction Their contraction procedure can be described as follows Let K be a belief set and suppose that we want to contract K with respect to Q Alchourron and Makinson postulate a quothierarchyquot lt over K that is assumed to be acyclical that is for no Q1 Q2 Qn in K is it the case that Q1lt Q2 lt lt Qn lt Q1 Given such a hierarchy we say that an element V is safe with respect to Q iff V is not a minimal element under lt of any minimal subset K39 of K such that K39 1 Q Equivalently every minimal subset K39 of K such that K39 1 Q either does not contain V or else contains some X such that X lt V Intuitively the idea is that V is safe if it can never be quotblamedquot for the implication of Q Note that in contrast to the earlier constructions this definition uses minimal subsets of K that entail Q rather than maximal subsets of K that do not entail Q Rott39s paper in this volume concerns the relation between orderings of epistemic entrenchment and the hierarchies over K used in the definition of safe contraction He presents ways of translating between the types of orderings and proves that they are equivalent This is in contrast to what was conjectured by Alchourron and Makinson 1985 and Gardenfors 1988 In this way he completes the map of correspondences between 1 the AGM postulates for contractions 2 the AGM postulates for revisions 3 relational partial meet contractions functions 4 epistemic entrenchment contractions and 5 safe contractions 43 Possibility Theory Apart from the five areas mentioned in the previous paragraph possibility theory can be added as a sixth area which can be connected to epistemic entrenchment relations in the first place and thereby also indirectly with belief revisions and contraction This is the topic of Dubois and Prade s contribution to the volume Perhaps the best way of relating possibility theory to the theory of belief revision is to start with the qualitative necessity relation Dubois 1986 which is an ordering 20 and the corresponding strict relation gt0 of sentences satisfying the following axioms A0 T gtc J A1 ZCWOTWZC A2 chandW20XimPIY ZcX A3 I 2c J C ifQ 20 V then for all X Q A X 20 V A X A qualitative necessity relation can be generated from a necessity measure N so that Q 20 V if and only if NQ 2 NW where N satisfies the following characteristic property 9 NQ A W minN 5NI 21 Dually one can de ne a possibility measure H as a function satisfying 10 1 101 V W maXH Hl Indeed possibility measures are related to necessity measures through the relationship N l H The dual qualitative possibility ordering 211 can be related to 20 by the following equivalence 11 1 211 V ifand only if w 20 11 It has been shown by Dubois and Prade 1991 that a qualitative necessity ordering is almost identical to an epistemic entrenchment relation The exception is that for epistemic entrenchment it is requested that T gt0 1 instead of A0 This connection between possibility theory and epistemic entrenchment forms the starting point for the paper by Dubois and Prade in this volume They represent belief states by necessity measures and rewrite the rationality postulates for revision and contraction accordingly They also show how this model of a belief state can be used to describe updating with uncertain pieces of evidence They make some interesting comparisons with Spohn39s 1988 ordinal conditional functions which form a different way of introducing degrees of belief 44 Updates vs Revisions Katsuno and Mendelzon present an interesting alternative to revision in their contribution to this volume This alternative method is called updating and is also used by Morreau in his paper on planning The basic idea is that one needs to make a distinction between two kinds of information and the corresponding changes On the one hand there is new information about a static world For this kind of information the revision process as it has been described is appropriate On the other hand there is new information about changes in the world brought about by some agent For both types the new piece of information may be inconsistent with the current state of belief However Katsuno Mendelzon and Morreau argue that the revision process is inadequate as a model of rational belief change caused by the second type of information For this kind of change an updating procedure is appropriate To illustrate their argument let me borrow an example from Winslett 1988 Suppose that all we know in K about a particular room is that there is a table a book and a magazine in it and that either 5 the book is on the table or u the magazine is on the table but not both ie the belief state K is essentially CnB u V uA B A robot is then ordered to put the book on the table and as a consequence we learn that If we change our beliefs by revision we should according to Kl 4 end up in a belief state that contains BA u since 5 is consistent with K But why should we conclude that the magazine is not on the table 22 In order to describe how updating works we must present their version of a possible worlds model for belief states Let L be the language of standard propositional logic and let P be the set of propositional letters in L An interpretation of L is a function I from P to the set TF of truth values This function is extended to L recursively in the standard way so that IQil T iff IQ T and IV T etc A model of a sentence Q is an interpretation I such that IQ T A model of a set of sentences K is an interpretation I such that IQ T for all Q e K ModK denotes the set of all models of K Instead of using an ordering of KJSQ the maximal consistent subsets of K that don t entail Q when determining KlQ Katsuno and Mendelzon and several other researchers see Katsuno and Mendelzon s 1989 survey have proposed to look at an ordering of the set of all interpretations and then use this ordering to decide which interpretations should constitute models of KlQ and thus indirectly determine KlQ in this way The intended meaning of such an ordering is that some interpretations that are models of Q but not of K are closer to models of K than other interpretations Such an ordering of interpretations should of course be dependent on K Technically we assign to each belief set K a preordering SK over the set of interpretations of L and a corresponding strict ordering ltK8 Following Katsuno and Mendelzon we say that SK is zithful9 if these conditions hold i SK is transitive and re exive ii If I J e ModK then I ltK J does not hold iii If I e ModK and J E ModK then I ltK J If M is a set of interpretations of L we let MinMSK denote the set of interpretations I which are minimal in M with respect to SK K39lQ can now be determined from SK as the belief set which has exactly MinModQSK as its set of models Katsuno and Mendelzon 1989 prove the following general result Theorem 13 A revision function l satisfies Kl l Kl 8 if and only if there exists a total faithful ordering SK such ModKl39Q MinModQSK This theorem gives a representation of belief revision in their terminology Using this terminology the difference between revising and updating can be described as follows Methods for revising K by Q that satisfy Kl l Kl 8 are exactly those that select from the models of Q that are 39closest39 to the models of K In contrast update models select for 8To be precise Katsuno and Mendelson only consider belief sets that can be represented by a single sentence from L ie the conjunction of all the beliefs in K 9This condition is called 39persistent in Katsuno and Mendelzon 1989 23 each model I of K the set of models of Q that are closest to 110 The update KQ is then characterized by the union of all such models The difference between the methods may seem marginal at a first glance but the properties of updating are in general quite different from those of revision In connection with the example above we have already noted that updating violates Kl4 On the other hand updating satis es the following postulate which is violated by revision 12 K V K Q KlQ V K Q This postulates presumes that belief states are modelled by single sentences so that disjunctions of belief states are well defined Morreau s paper in this volume is an application to planning of the updating procedure Using this method he presents a framework for modelling reasoning about action The language he uses includes a conditional operator gt which is used to represent statements of the form 39If the agent were to do 0L this would result in Q being true The conditionals are analyzed both semantically and axiomatically By nesting conditionals of this kind he can describe the content of sequences of actions and in this way obtain an elegant way of representing planning 45 Autonomous Belief Revision and Communication Postulate Kl 2 requires that an input Q given to a belief state K must be accepted in the revision KiQ Galliers argues in her paper in this volume that this is in con ict with the autonomy of the agents having the various belief states In communication one agent informs another about something aiming at changing the receiver39s belief state It remains however the decision of the autonomous receiver whether the information should be accepted or not As Gallier s puts it quotAutonomous agents may or may not comply with the recognised intended effects of an utterance on their cognitive states There are no specialised rules dictating what is a cooperative response Rational communicative action must therefore be planned not only as purposive but as strategicquot So in order to model belief revisions in a communicative setting one must be able to specify whether to accept the contents of an utterance from another agent as well as how to perform the possible revisions caused by the utterance The underlying principle for Galliers is that the acceptability of a new utterance is dependent on the degree of coherence of the belief state that would result if the utterance were added Her model of revision is essentially determined by such a coherence ordering where the degree of coherence is defined as maximal derivability of core beliefs It is not required that there be a unique 10This method is essentially equivalent to 39imaging as introduced in a probabilistic context by Lewis 1976 and generalized to the context of belief sets in Gardenfors 1988 24 revision and furthermore it is not required that any preferred revision incorporate the communicated information Galliers then adds a foundational aspect to the belief revision model by working with assumptions of various kinds and justi cations for the assumptions For example the endorsement of an assumption depends on whether it is communicated by a reliable source or a spurious source In this way her model model of autonomous belief revision is a mixture of coherence and foundationalism The model has been implemented as a component of a strategic planner for cooperative dialogue 46 Conditionals and the Ramsey Test There is a close connection between belief revisions and the meaning of conditional sentences The carrying hypothesis is that conditional sentences in various forms are about changes of states of belief The form of conditional sentence that is central is quotif Q were the case then B would be the casequot or quotifQ is the case then B is will be the casequot where Q may or may not contradict what is already accepted in a given epistemic state K If Q contradicts what is accepted in K the conditional is called a counterfactual relative to K otherwise it is called an open conditional relative to K The epistemic semantics for counterfactuals and open conditionals will be based on F P Ramsey s test for evaluating a conditional sentence His test can be described as follows In order to find out whether a conditional sentence is acceptable in a given state of belief one first adds the antecedent of the conditional hypothetically to the given stock of beliefs Second if the antecedent together with the formerly accepted sentences leads to a contradiction then one makes some adjustments as small as possible without modifying the hypothetical belief in the antecedent such that consistency is maintained Finally one considers whether or not the consequent of the conditional is accepted in this adjusted state of belief Given the analysis of belief revisions in Section 2 we see that it is very natural to reformulate the Ramsey test in a more condensed way RT QgtBeKiffBeKlQ This test has attracted a great deal of attention as a possible starting point for a formal semantics of conditionals Ginsberg 1986 argues that a formal semantics for counter factuals is of great value for many problem areas within AI in particular since they form the core of nonmonotonic inferences Note that the formulation of RT presupposes that sentences of the form Q gt B belong to the object language and that they can be elements of the belief sets in a belief revision model Let us call this extended object language L39 25 Some results in Gardenfors 1978 seem to justify the claim that the Ramsey test can be used as a basis for an epistemic semantics of conditionals However the list of conditions that were used to generate the logic of conditionals does not include K39l4 or the full strength of Kl 8 An interesting question is whether it is possible to use RT together with K4 when analysing the logic of conditionals With minor quali cations the answer turns out to be no In order to put the result as strongly as possible one can start from the following preservation condition KP If Q E K and V e K then V e KlQ It is easy to show that the preservation criterion is essentially equivalent to K4 The Ramsey test and the preservation criterion are each of considerable interest for the analysis of the dynamics of belief Unfortunately it can be proved that on the pain of triviality the Ramsey test and the preservation criterion are inconsistent with each other Gardenfors 1986 Let us formulate this result with some care A background assumption is that the revision function is defined for all belief sets11 Note that in L39 sentences containing the conditional connective gt will be treated on a par with sentences without this operator The Ramsey test RT is of course dependent on this assumption A consequence of RT that is crucial is the following monotonicz39ty criterion KM For all belief sets K and K39 and all Q ifK E K39 then KQ E K lQ The conditions on the revision function that will be needed for the proof are KlZ and the following very weak criterion which is one half of KlS K5w IfK KJ and KlQ KJ then I Q The final assumption that will be needed for the inconsistency result is that the belief revision system is nontrivial As usual two propositions Q and V are said to be disjoint iff l Q A V A belief revision system will be said to be nontrivial iff there are at least three pairwise disjoint sentences Q V and X and some belief set K which is consistent with all three sentences ie vQ E K ow E K and x E K Theorem 14 There is no nontrivial belief revision system that satisfies all the conditions K2 K5w KM and KP It should be noted that the conditional connective gt is used neither in the formulation of the theorem nor in its proof If KlP is replaced by Kl4 then Ki2 is not needed for the proof of the theorem 11What is needed for the proof is only the assumption that if K is in the domain of the revision function so are are all expansions KQ 26 Corollary There is no nontrivial belief revision system that satis es all the conditions KlZ Kl Sw RT and KlP The theorem and its corollary show that the Ramsey test RT and the preservation condition KlP or equivalently Ki4 cannot both be rational criteria for belief revisions However the Ramsey test has a great deal of appeal and several ways of getting around the impossibility result have been tried In his paper in this volume Morreau uses updating instead of revision in formulating the Ramsey test as was noted above updating does not satisfy Kl4 and it is easy to show that this combination is consistent Another approach is taken by Cross and Thomason in their paper in this volume They also retain the Ramsey test but they work with a different logical framework than what has been used above Firstly they use a fourvalued logic which changes the accompanying proof theory Secondly they restrict revision to atomistic inputs ie the only sentences for which the revision process is defined are either atomic sentences or negated atomic sentences By restricting the revision procedure in this way Cross and Thomason show that it is now possible to work out a theory of conditionals that satisfies the Ramsey test Furthermore they show that the theory of nonmonotonic inheritance from Horty Thomason and Touretzky 1990 can be interpreted as a special case of their logic of conditionals In this way we find yet another connection between the theory of belief revision and other areas of computer science Acknowledgements I wish to thank Hirofumi Katsuno Michael Morreau Bernhard Nebel Richmond Thomason and Hans Rott for helpful comments on an earlier version of this paper 27 REFERENCES Alchourron C E P Gardenfors and D Makinson 1985 quotOn the logic of theory change Partial meet contraction and revision functionsquot The Journal of Symbolic Logic 50 510530 Alchourron C E and Makinson D 1985 quotOn the logic of theory change Safe contractionquot Studia Logica 44 405422 Doyle J 1991 quotRational belief reVision Preliminary reportquot Principles of Knowledge Representation and Reasoning ed by J Allen R Fikes and E Sandewall Los Altos CA Morgan Kaufmann 163174 Dubois D 1986 quotBelief structures possibility theory and decomposable con dence measures on nite setsquot Computers and Artificial Intelligence 5 403416 Dubois D and H Prade 1991 quotEpistemic entrenchment and possibility logicquot to appear in Artificial Intelligence Fagin R Ullman J D and Vardi M Y 1983 quotOn the semantics of updates in databasesquot Proceedings ofSecondACM SIGACT SIGMOD Atlanta pp 352365 Fuhrmann A 1991 quotTheory contraction through base contractionquot Journal of Philosophical Logic 20 175203 Gardenfors P 1978 quotConditionals and changes of beliefquot in The Logic and Epistemology of Scientific Change ed by I Niiniluoto and R Tuomela Acta Philosophica Fennica 30 381404 Gardenfors P 1986 quotBelief reVisions and the Ramsey test for conditionalsquot The Philosophical Review 95 8193 Gardenfors P 1988 Knowledge in Flux Modeling the Dynamics opristemic States Cambridge MA The MIT Press Bradford Books Gardenfors P and D Makinson 1988 quotRevisions of knowledge systems using epistemic entrenchmentquot in Proceedings of the Second Conference on TheoreticalAspects of Reasoning about Knowledge M Vardi ed Los Altos CA Morgan Kaufmann Garey M R and Johnson D S 1979 Computers and Intractability 7A Guide to the Theory of NP Completeness San Francisco Freeman Ginsberg M L 1986 quotCounterfactualsquot Artificial Intelligence 30 3579 Grove A 1988 quotTwo modellings for theory changequot Journal ofPhilosophical Logic I 7 157170 Hansson S O 1989 quotIn defense of base contractionquot to appear in Synthese 28 Hansson S O 1991 BeliefBase Dynamics Uppsala Acta Universitatis Upsaliensis Harman G 1986 Change in Viev Principles of Reasoning Cambridge MA The MIT Press Bradford Books Harper W L 1977 quotRational conceptual changequot in PSA 1976 East Lansing Mich Philosophy of Science Association vol 2 462494 Horty J F Thomason R H and Touretsky D S 1990 quotA skeptical theory of inheritance in nomonotonic semantic networksquot Arti cial Intelligence 42 311348 Katsuno H and Mendelzon A O 1989 quotA unified view of propositional knowledge base updatesquot Proceedings of the 11th Internationsl Joint Conference on Artificial Intelligence San Mateo CA Morgan Kaufmann 269276 Lewis D K 1976 quotProbabilities of conditionals and conditional probabilitiesquot The Philosophical Review 85 297315 Makinson D 1985 quotHow to give it up A survey of some formal aspects ofthe logic of theory changequot Synthese 62 347363 Makinson D 1987 quotOn the status of the postulate of recovery in the logic of theory changequot Journal ofPhilosophical Logic 16 383394 Nebel B 1990 Reasoning anal Revision in Hybrid Representation Systems Lecture Notes in Computer Science vol 422 Berlin Springer Reiter R 1980 quotA logic for default reasoningquot Artificial Intelligence 13 81132 Rott H 1991quotTwo methods of constructing contractions and revisions of knowledge systemsquot Journal of Philosophical Logic 20 149173 Rott H 1992 Preferential belief change using generalized epistemic entrenchment to appear in Journal of Logic Language and Information Spohn W 1988 quotOrdinal conditional functions A dynamic theory of epistemic statesquot in W L Harper and B Skyrms eds Causation in Decision Belief Change and Statistics vol 2 Dordrecht Reidel 105134 Winslett M 1988 quotReasoning about action using a possible models approachquot Proceedings of the Seventh National Conference onArtificial Intelligence 8993


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.