A study in the logic of theory change, examining the properties of maxichoice contraction and revision operations.

This paper analyzes the notion of a minimal belief change that incorporates new information. I apply the fundamental decision-theoretic principle of Pareto-optimality to derive a notion of minimal belief change, for two different representations of belief: First, for beliefs represented by a theory – a deductively closed set of sentences or propositions – and second for beliefs represented by an axiomatic base for a theory. Three postulates exactly characterize Pareto-minimal revisions of theories, yielding a weaker (...) set of constraints than the standard AGM postulates. The Levi identity characterizes Pareto-minimal revisions of belief bases: a change of belief base is Pareto-minimal if and only if the change satisfies the Levi identity (for “maxichoice” contraction operators). Thus for belief bases, Pareto-minimality imposes constraints that the AGM postulates do not. The Ramsey test is a well-known way of establishing connections between belief revision postulates and axioms for conditionals (“if p, then q”). Pareto-minimal theory change corresponds exactly to three characteristic axioms of counterfactual systems: a theory revision operator that satisfies the Ramsey test validates these axioms if and only if the revision operator is Pareto-minimal. (shrink)

This paper analyzes the notion of a minimal belief change that incorporates new information. I apply the fundamental decisiontheoretic principle of Pareto-optimality to derive a notion of minimal belief change, for two different representations of belief: First, for beliefs represented by a theory –a deductively closed set of sentences or propositions–and second for beliefs represented by an axiomatic base for a theory. Three postulates exactly characterize Pareto-minimal revisions of theories, yielding a weaker set of constraints (...) than the standard AGM postulates. The Levi identity characterizes Pareto-minimal revisions of belief bases: a change of belief base is Pareto-minimal if and only if the change satisfies the Levi identity (for “maxichoice” contraction operators). Thus for belief bases, Pareto-minimality imposes constraints that the AGM postulates do not. Keywords: belief revision, decision theory.. (shrink)

This paper is concerned with the construction of a base contraction (revision) operation such that the theory contraction (revision) operation generated by it will be fully AGM-rational. It is shown that the theory contraction operation generated by Fuhrmann's minimal base contraction operation, even under quite strong restrictions, fails to satisfy the "supplementary postulates" of belief contraction. Finally Fuhrmann's construction is appropriately modified so as to yield the desired properties. The new construction may be described as involving a (...) modification of safe (base) contraction so as to make it maxichoice. (shrink)

The classical qualitative theory of belief change due to Alchourrón, Gärdenfors and Makinson has been widely known as being characterised by two packages of postulates. While the basic package consists of six postulates and is very weak, the full package that adds two further postulates is very strong. I revisit two classic constructions of theory contraction, viz., relational possible worlds contraction and entrenchment-based contraction and argue that four intermediate levels can be distinguished that play - or ought (...) to play - important roles within qualitative belief revision theory. Levels 3 and 4 encode two ways of interpreting the idea of imperfect discrimination of the plausibilities of possible worlds or propositions. (shrink)

The postulate of Recovery, among the six postulates for theory contraction, formulated and studied by Alchourrón, Gärdenfors and Makinson is the one that has provoked most controversy. In this article we construct withdrawal functions that do not satisfy Recovery, but try to preserve minimal change, and relate these withdrawal functions with the AGM contraction functions.

If we suppose that reasonable belief is reasonable not because it has a foundation but because it is self-correcting, and that bodies of reasonable belief are self-correctable in virtue of their web-like internal structure, then it becomes natural to ask for explicit accounts both of self-correction itself, and of the web-like internal structure that makes self-correction possible: The theory of rational belief change. ;In this essay we study qualitative, logical theories of rational belief change, in (...) particular the AGM account, and its offshoot, the theory base account. Throughout, however, we use quantitative, probabilistic models as foils. ;We first undertake a systematic, critical study of the AGM account, focusing especially on its "possible worlds" formulation and on its theory of belief revision. According to the AGM account we can represent AGM revision by simple computations over total preorders of possibilities. We investigate iterated AGM revision from this perspective, and prove that symmetry considerations familiar from social choice theory essentially determine a particular ordering dynamics. These symmetry arguments put an upper bound on the sorts of responsiveness we can expect from the AGM model of rational belief change. The most widely criticized feature of the AGM account is its "recovery" condition on belief contraction. We show how to deflect all existing criticisms to recovery by paying close to attention to exactly which beliefs are given up in a particular case. The principal cost of this strategy is that the AGM account becomes harder to apply and to test. ;Theory base accounts add a layer of syntactically-encoded information to the AGM model. We show that this approach fails comprehensively: that it cannot successfully coordinate the syntactic layer of information with underlying contents or with necessary ordering information, and that it sanctions demonstrably irrational belief changes. Our diagnosis is, in part, that the theory base account conflates two distinct sorts of nonmonotonic belief change. ;Lastly, we summarize our current research into quantitative accounts of rational belief change, focusing on a model that generalizes irreducibly two-place probability, and that has the AGM account as a limiting case. (shrink)

This paper reorganizes and further develops the theory of partial meet contraction which was introduced in a classic paper by Alchourron, Gardenfors, and Makinson. Our purpose is threefold. First, we put the theory in a broader perspective by decomposing it into two layers which can respectively be treated by the general theory of choice and preference and elementary model theory. Second, we reprove the two main representation theorems of AGM and present two more representation results for (...) the finite case that "lie between" the former, thereby partially answering an open question of AGM. Our method of proof is uniform insofar as it uses only one form of "revealed preference", and it explains where and why the finiteness assumption is needed. Third, as an application, we explore the logic characterizing theory contractions in the finite case which are governed by the structure of simple and prioritized belief bases. (shrink)

The 1985 paper by Carlos Alchourrón, Peter Gärdenfors, and David Makinson, “On the Logic of Theory Change: Partial Meet Contraction and Revision Functions” was the starting-point of a large and rapidly growing literature that employs formal models in the investigation of changes in belief states and databases. In this review, the first twenty-five years of this development are summarized. The topics covered include equivalent characterizations of AGM operations, extended representations of the belief states, change operators not included (...) in the original framework, iterated change, applications of the model, its connections with other formal frameworks, computatibility of AGM operations, and criticism of the model. (shrink)

Traditional accounts of belief change have been criticized for placing undue emphasis on the new belief provided as input. A recent proposal to address such issues is a framework for non-prioritized belief change based on default theories (Ghose and Goebel, 1998). A novel feature of this approach is the introduction of disbeliefs alongside beliefs which allows for a view of belief contraction as independently useful, instead of just being seen as an intermediate step in the process (...) of belief revision. This approach is, however, restrictive in assuming a linear ordering of reliability on the received inputs. In this paper, we replace the linear ordering with a preference ranking on inputs from which a total preorder on inputs can be induced. This extension brings along with it the problem of dealing with inputs of equal rank. We provide a semantic solution to this problem which contains, as a special case, AGM belief change on closed theories. (shrink)

The problems that surround iterated contractions and expansions of beliefs are approached by studying hypertheories, a generalisation of Adam Grove's notion of systems of spheres. By using a language with dynamic and doxastic operators different ideas about the basic nature of belief change are axiomatised. It is shown that by imposing quite natural constraints on how hypertheories may change, the basic logics for belief change can be strengthened considerably to bring one closer to a theory of iterated (...) belief change. It is then argued that the logic of expansion, in particular, cannot without loss of generality be strengthened any further to allow for a full logic of iterated belief change. To remedy this situation a notion of directed expansion is introduced that allows for a full logic of iterated belief change. The new operation is given an axiomatisation that is complete for linear hypertheories. (shrink)

Various representation results have been established for logics of belief revision, in terms of remainder sets, epistemic entrenchment, systems of spheres and so on. In this paper I present another representation for logics of belief revision, as an algebra of theories. I show that an algebra of theories, enriched with a set of rejection operations, provides a suitable algebraic framework to characterize the theory change operations of systems of belief revision. The theory change operations arise (...) as power operations of the conjunction and disjunction connectives of the underlying logic. (shrink)

The paper surveys some recent work on formal aspects of the logic of theory change. It begins with a general discussion of the intuitive processes of contraction and revision of a theory, and of differing strategies for their formal study. Specific work is then described, notably Gärdenfors'' postulates for contraction and revision, maxichoice contraction and revision functions and the condition of orderliness, partial meet contraction and revision functions and the condition of relationality, and finally the operations of (...) safe contraction and revision. Verifications and proofs are omitted, with references given to the literature, but definitions and principal results are presented with rigour, along with discussion of their significance. (shrink)

Describes and discusses the rather special behaviour of one of the postulates in the AGM account of theory change.

This thesis consists in six articles and a comprehensive summary. • The pourpose of the summary is to introduce the AGM theory of belief change and to exemplify the diversity and significance of the research that has been inspired by the AGM article in the last 25 years. The research areas associated with AGM was divided in three parts: criticisms, where we discussed some of the more common criticisms of AGM. Extensions where the most common extensions and variations (...) of AGM are presented and applications where we provided an overview of applications and connections with other areas of research. • Article I elaborates on the connection between partial meet contractions [AGM85] and kernel contractions [Han94a] in belief change theory. Also both functions are equivalent in belief sets, there are notequivalent in belief bases. A way to define incision functions from selection functions and vice versa is presented. It is explained under which conditions there are exact correspondences between selection and incision functions so that the same contraction operations can be obtained by using either of them. • Article II proposes an axiomatic characterization for ensconcement-based contraction functions, belief base functions proposed byWilliams and relates this function with other kinds of base contraction functions. • Article III adapts the Fermé and Hansson model of Shielded Contraction [FH01] as well as Hansson et all Credibility-Limited Revision [HFCF01] for belief bases, to join two of the many variations of the AGM model [AGM85], i.e. those in which knowledge is represented through belief bases instead of logic theories, and those in which the object of the epistemic change does not get the priority over the existing information as it is the case in the AGM model. • Article IV introduces revision by comparison a refined method for changing beliefs by specifying constraints on the relative plausibility of propositions. Like the earlier belief revision models, the method proposed is a qualitative one, in the sense that no numbers are needed in order to specify the posterior plausibility of the new information. The method uses reference beliefs in order to determine the degree of entrenchment of the newly accepted piece of information. Two kinds of semantics for this idea are proposed and a logical characterization of the new model is given. • Article V focuses on the extension of AGM that allows change for a belief base by a set of sentences instead of a single sentence. In [FH94], Fuhrmann and Hansson presented an axiomatic for Multiple Contraction and a construction based on the AGM Partial Meet Contraction. This essay proposes for their model another way to construct functions: Multiple Kernel Contraction, that is a modification of Kernel Contraction,proposed by Hansson [Han94a] to construct classical AGM contractions and belief base contractions. • Article VI relates AGM model with the DFT model proposed by Carlos Alchourrón [Alc93]. Alchourrón devoted his last years to the analysis of the notion of defeasible conditionalization. His definition of the defeasible conditional is given in terms of strict implication operator and a modal operator f which is interpreted as a revision function at the language level. This essay points out that this underlying revision function is more general than AGM revision. In addition, a complete characterization of that more general kind of revision that permits to unify models of revision given by other authors is given. (shrink)

The field of iterated belief change has focused mainly on revision, with the other main operator of AGM belief change theory, i.e. contraction, receiving relatively little attention. In this paper we extend the Harper Identity from single-step change to define iterated contraction in terms of iterated revision. Specifically, just as the Harper Identity provides a recipe for defining the belief set resulting from contracting A in terms of (i) the initial belief set and (ii) the (...) belief set resulting from revision by ¬A, we look at ways to define the plausibility ordering over worlds resulting from contracting A in terms of (iii) the initial plausibility ordering, and (iv) the plausibility ordering resulting from revision by ¬A. After noting that the most straightforward such extension leads to a trivialisation of the space of permissible orderings, we provide a family of operators for combining plausibility orderings that avoid such a result. These operators are characterised in our domain of interest by a pair of intuitively compelling properties, which turn out to enable the derivation of a number of iterated contraction postulates from postulates for iterated revision. We finish by observing that a salient member of this family allows for the derivation of counterparts for contraction of some well known iterated revision operators, as well as for defining new iterated contraction operators. (shrink)

Agents need to be able to change their beliefs; in particular, they should be able to contract or remove a certain belief in order to restore consistency to their set of beliefs, and revise their beliefs by incorporating a new belief which may be inconsistent with their previous beliefs. An influential theory of belief change proposed by Alchourron, G¨ardenfors and Makinson (AGM) [1] describes postulates which a rational belief revision and contraction operations should satisfy. The (...) AGM postulates have been perceived as characterising idealised rational reasoners, and the corresponding belief change operations are considered unsuitable for implementable agents due to their high computational cost [3]. The main result of this paper is showing that an efficient (linear time) belief contraction operation nevertheless satisfies all but one of the AGM postulates for contraction. This contraction operation is defined for a realistic rule-based agent which can be seen as a reasoner in a very weak logic; although the agent’s beliefs are deductively closed with respect to this logic, checking consistency and tracing dependencies between beliefs is not computationally expensive. Finally, we give a non-standard definition of belief revision in terms of contraction for our agent. (shrink)

Prioritized bases, i.e., weakly ordered sets of sentences, have been used for specifying an agent’s ‘basic’ or ‘explicit’ beliefs, or alternatively for compactly encoding an agent’s belief state without the claim that the elements of a base are in any sense basic. This paper focuses on the second interpretation and shows how a shifting of priorities in prioritized bases can be used for a simple, constructive and intuitive way of representing a large variety of methods for the change of (...) belief states—methods that have usually been characterized semantically by a system-of-spheres modeling. Among the methods represented are ‘radical’, ‘conservative’ and ‘moderate’ revision, ‘revision by comparison’ in its raising and lowering variants, as well as various constructions for belief expansion and contraction. Importantly, none of these methods makes any use of numbers. (shrink)

A model of coherentist belief contraction is constructed. The outcome of belief contraction is required to be one of the coherent subsets of the original belief set, and a set of plausible properties is proposed for this set of coherent subsets. The contraction operators obtained in this way are shown to coincide with well-known belief base operations. This connection between coherentist and "foundationalist" approaches to belief change has important implications for the philosophical interpretation of models (...) of belief change. (shrink)

The AGM theory of belief contraction is extended tomultiple contraction, i.e. to contraction by a set of sentences rather than by a single sentence. There are two major variants: Inpackage contraction all the sentences must be removed from the belief set, whereas inchoice contraction it is sufficient that at least one of them is removed. Constructions of both types of multiple contraction are offered and axiomatically characterized. Neither package nor choice contraction can in general be reduced to (...) contractions by single sentences; in the finite case choice contraction allows for reduction. (shrink)

In the logic of theory change, the standard model is AGM, proposed by Alchourrón et al. (J Symb Log 50:510–530, 1985 ). This paper focuses on the extension of AGM that accounts for contractions of a theory by a set of sentences instead of only by a single sentence. Hansson (Theoria 55:114–132, 1989 ), Fuhrmann and Hansson (J Logic Lang Inf 3:39–74, 1994 ) generalized Partial Meet Contraction to the case of contractions by (possibly non-singleton) sets of sentences. (...) In this paper we present the possible worlds semantics for partial meet multiple contractions. (shrink)

We present a decision-theoretically motivated notion of contraction which, we claim, encodes the principles of minimal change and entrenchment. Contraction is seen as an operation whose goal is to minimize loses of informational value. The operation is also compatible with the principle that in contracting A one should preserve the sentences better entrenched than A (when the belief set contains A). Even when the principle of minimal change and the latter motivation for entrenchment figure prominently among the basic intuitions (...) in the works of, among others, Quine and Ullian (1978), Levi (1980, 1991), Harman (1988) and Gärdenfors (1988), formal accounts of belief change (AGM, KM – see Gärdenfors (1988); Katsuno and Mendelzon (1991)) have abandoned both principles (see Rott (2000)). We argue for the principles and we show how to construct a contraction operation, which obeys both. An axiom system is proposed. We also prove that the decision-theoretic notion of contraction can be completely characterized in terms of the given axioms. Proving this type of completeness result is a well-known open problem in the field, whose solution requires employing both decision-theoretical techniques and logical methods recently used in belief change. (shrink)

I. Levi has advocated a decision-theoretic account of belief revision. We argue that the game-theoretic framework of Interrogative Inquiry Games, proposed by J. Hintikka, can extend and clarify this account. We show that some strategic use of the game rules generate Expansions, Contractions and Revisions, and we give representation results. We then extend the framework to represent explicitly sources of answers, and apply it to discuss the Recovery Postulate. We conclude with some remarks about the potential extensions of interrogative (...) games, with respect to some issues in the theory of belief change. (shrink)

Generalisations of theory change involving operations on arbitrary sets ofwffs instead of on belief sets (i.e., sets closed under a consequencerelation), have become known as base change. In one view, a base should bethought of as providing more structure to its generated belief set, whichmeans that it can be employed to determine the theory contraction operationassociated with a base contraction operation. In this paper we follow suchan approach as the first step in defining infobase change. We (...) think of an infobase as a finite set of wffs consisting of independently obtainedbits of information. Taking AGM theory change (Alchourrón et al. 1985) as the general framework, we present a method that uses the structure of aninfobase B to obtain an AGM theory contraction operation for contractingthe belief set Cn(B). Both the infobase and the obtained theory contraction operation then play a role in constructing a unique infobasecontraction operation. Infobase revision is defined in terms of an analogueof the Levi Identity, and it is shown that the associated theory revisionoperation satisfies the AGM postulates for revision. Because every infobaseis associated with a unique infobase contraction and revision operation, the method also allows for iterated base change. (shrink)

The book generalises earlier theories of belief change to cover all kinds of changes of sets by sets. The principal focus is still on changes of belief sets in response to new evidence, but the formal theory extends to all domains with a closure operation and a preference structure including, for example, systems of action. Contraction is the key notion; all other changes can be defined. Various new applications of the theory are outlined. A sentential version (...) of contraction, subtraction, is proposed as a formal counterpart to 'except'-locutions in natural language. Connections are emphasised with other areas at the interface between philosophical logic and artificial intelligence such as reasoning from default assumptions or from inconsistent premises. A relation of merge inference is proposed as a means of retrieving maximal but nontrivial information from inconsistent premises. Merge inference respects certain anti-Boolean intuitions while avoiding a revision of classical logic. (shrink)

The paper suggests a way of modeling belief changes within the tradition of formal belief revision theories. The present model extends the scope of traditional proposals, such as AGM, so as to take care of “structural belief changes” – a type of radical shifts that is best illustrated with, but not limited to, instances of scientific discovery; we obtain AGM expansions and contractions as limiting cases. The representation strategy relies on a non-standard use of a semantic machinery. (...) More precisely, the model seeks to correlate knowledge states with interpretations of a given formal language L, in such a way that the epistemic state of an agent at a given time gives rise to a picture of how things could be, if there weren’t anything else to know. Interpretations of L proceed along supervaluational ideas; hence, the model as a whole can be seen as a particular application of supervaluational semantics to epistemic matters. (shrink)

This paper extends the AGM theory of belief revision to accommodate infinitary belief change. We generalize both axiomatization and modeling of the AGM theory. We show that most properties of the AGM belief change operations are preserved by the generalized operations whereas the infinitary belief change operations have their special properties. We prove that the extended axiomatic system for the generalized belief change operators with a Limit Postulate properly specifies infinite belief change. (...) This framework provides a basis for first-order belief revision and the theory of revising a belief state by a belief state. (shrink)

AGM-theory, named after its founders Carlos Alchourrón, Peter Gärdenfors and David Makinson, is the leading contemporary paradigm in the theory of belief-revision. The theory is reformulated here so as to deal with the central relational notions 'J is a contraction of K with respect to A' and 'J is a revision of K with respect to A'. The new theory is based on a principal-case analysis of the domains of definition of the three main kinds (...) of theory-change (expansion, contraction and revision). The new theory is stated by means of introduction and elimination rules for the relational notions. In this new setting one can re-examine the relationship between contraction and revision, using the appropriate versions of the so-called Levi and Harper identities. Among the positive results are the following. One can derive the extensionality of contraction and revision, rather than merely postulating it. Moreover, one can demonstrate the existence of revision-functions satisfying a principle of monotonicity. The full set of AGM-postulates for revision-functions allow for completely bizarre revisions. This motivates a Principle of Minimal Bloating, which needs to be stated as a separate postulate for revision. Moreover, contractions obtained in the usual way from the bizarre revisions, by using the Harper identity, satisfy Recovery. This provides a new reason (in addition to several others already adduced in the literature) for thinking that the contraction postulate of Recovery fails to capture the Principle of Minimal Mutilation. So the search is still on for a proper explication of the notion of minimal mutilation, to do service in both the theory of contraction and the theory of revision. The new relational formulation of AGM-theory, based on principal-case analysis, shares with the original, functional form of AGM-theory the idealizing assumption that the belief-sets of rational agents are to be modelled as consistent, logically closed sets of sentences. The upshot of the results presented here is that the new relational theory does a better job of making important matters clear than does the original functional theory. A new setting has been provided within which one can profitably address two pressing questions for A GM-theory: (1) how is the notion of minimal mutilation (by both contractions and revisions) best analyzed? and (2) how is one to rule out unnecessary bloating by revisions? (shrink)

The most controversial condition that the AGM theory of rational belief change places on belief contraction is the recovery condition. The condition is controversial because of a series of putative counterexamples due (separately) to I. Levi and S. O. Hansson. In this paper we show that the conflicts that Levi and Hansson arrange between AGM contraction and our intuitions about how to give up beliefs are merely apparent. We argue that these conflicts disappear once we attend more (...) closely to the identification of the beliefs contracted away in each counterexample case. Since, on our view, speakers" belief contraction intentions are often more complicated than they may first appear, we are led to develop apparatus for thinking about the communication and identification of those intentions. Our argument refocuses attention on the difficult question of how to apply the AGM theory to particular cases. (shrink)

In this paper we investigate AGM belief contraction operators by using the tools of algebraic logic. We generalize the notion of contraction to arbitrary finitary propositional logics, and we show how to switch from a syntactic-based approach to a semantic one. This allows to build a solid bridge between the validity of AGM postulates in a propositional logic and specific algebraic properties of its intended algebraic counterpart. Such a connection deserves particular attention when we deal with maxichoice contractions, (...) as studied in the final part of the paper. (shrink)

In this paper we study AGM contraction and revision of rules using input/output logical theories. We replace propositional formulas in the AGM framework of theory change by pairs of propositional formulas, representing the rule based character of theories, and we replace the classical consequence operator Cn by an input/output logic. The results in this paper suggest that, in general, results from belief base dynamics can be transferred to rule base dynamics, but that a similar transfer of AGM (...) class='Hi'>theory change to rule change is much more problematic. First, we generalise belief base contraction to rule base contraction, and show that two representation results of Hansson still hold for rule base contraction. Second, we show that the six so-called basic postulates of AGM contraction are consistent only for some input/output logics, but not for others. In particular, we show that the notorious recovery postulate can be satisfied only by basic output, but not by simple-minded output. Third, we show how AGM rule revision can be defined in terms of AGM rule contraction using the Levi identity. We highlight various topics for further research. (shrink)

In this paper we compare central elements of Dialogue Logic and Belief Revision theory. Dialogue Logic of the Hamblin/Mackenzie style, or Formal Dialectic, contains three main features. First, there is a rule governed interaction between dialogue participants—the minimal case being two participants. Second, each participant has a commitment store which changes as the dialogue progresses. Third, the changes in the commitment store are governed by rules for additions and withdrawals of material. Withdrawal of material is one major source (...) of difficulty in proposing rules for commitment store change. The classic Belief Revision theory is the AGM theory. AGM theory is a theory about ideal rational believers who change their sets of beliefs by either expansion or contraction. Contraction is a major source of difficulty in belief revision theory. We claim that the commitment stores of dialogue logic include, in a sense, the belief sets of belief revision theory. Further, withdrawal and contraction are essentially the same process. We consider various kinds of withdrawal and contraction, and show how approaches to these processes illuminate certain of the formal fallacies. (shrink)

We propose a new class of multiple contraction operations — the system of spheres-based multiple contractions — which are a generalization of Grove’s system of spheres-based (singleton) contractions to the case of contractions by (possibly non-singleton) sets of sentences. Furthermore, we show that this new class of functions is a subclass of the class of the partial meet multiple contractions.

In this paper we study AGM contraction and revision of rules using input/output logical theories. We replace propositional formulas in the AGM framework of theory change by pairs of propositional formulas, representing the rule based character of theories, and we replace the classical consequence operator Cn by an input/output logic. The results in this paper suggest that, in general, results from belief base dynamics can be transferred to rule base dynamics, but that a similar transfer of AGM (...) class='Hi'>theory change to rule change is much more problematic. First, we generalise belief base contraction to rule base contraction, and show that two representation results of Hansson still hold for rule base contraction. Second, we show that the six so-called basic postulates of AGM contraction are consistent only for some input/output logics, but not for others. In particular, we show that the notorious recovery postulate can be satisfied only by basic output, but not by simple-minded output. Third, we show how AGM rule revision can be defined in terms of AGM rule contraction using the Levi identity. We highlight various topics for further research. (shrink)

This thesis deals with the theory of interrogative belief revision, a recent development in the subfield of philosophical logic known as belief revision theory. While classical belief revision theory deals with the dynamics of an agent’s beliefs, interrogative belief revision aims to describe the dynamics of the agent’s questions about the world, or research agenda, as well. Great emphasis is put on the interaction between belief change and changes in the research agenda. (...) I develop both the technical framework for this theory by constructing and investigating modal logics for reasoning about the dynamics of research interests, as well as pursuing further the philosophical foundations and applications of the theory. Among the contributions of the thesis are: - a novel interpretation of the theory founded on a notion of epistemic strategies - a solution to the previously open problem of contraction and revision in this context - several systems of modal logic that can be used to reason about interrogative belief revision - completeness results and decidability results for these logics - a characterization of a class of relevant conditionals based on a notion of agenda relevance. (shrink)

The process of completing, correcting and prioritising specifications is an essential but very complex task for the maintenance and improvement of software systems. The preservation of functionalities and the ability to accommodate changes are main objectives of the software development cycle to guarantee system reliability. Logical theories able to fully model such processes are still insufficient. In this paper we propose a full formalisation of such operations on software systems inspired by the Alchourrón–Gärdenfors–Makinson paradigm for belief revision of human (...) epistemic states. We represent specifications as finite sets of formulas equipped with a priority relation that models functional entrenchment of properties. We propose to handle specification incompleteness through ordered expansion, inconsistency through ordered safe contraction and prioritisation through revision with reordering, and model all three in an algorithmic fashion. We show how the system satisfies basic properties of the AGM paradigm, including Levi’s and Harper’s identities. We offer a concrete example and complexity results for the inference and model checking problems on revision. We conclude by describing resilience and evolvability of software systems based on such revision operators. (shrink)

The most controversial condition that the AGM theory of rational belief change places on belief contraction is the recovery condition. The condition is controversial because of a series of putative counterexamples due (separately) to I. Levi and S. O. Hansson. In this paper we show that the conflicts that Levi and Hansson arrange between AGM contraction and our intuitions about how to give up beliefs are merely apparent. We argue that these conflicts disappear once we attend more (...) closely to the identification of the beliefs contracted away in each counterexample case. Since, on our view, speakers' belief contraction intentions are often more complicated than they may first appear, we are led to develop apparatus for thinking about the communication and identification of those intentions. Our argument refocuses attention on the difficult question of how to apply the AGM theory to particular cases. (shrink)

We consider the connections between belief revision, conditional logic and nonmonotonic reasoning, using as a foundation the approach to theory change developed by Alchourrón, Gärdenfors and Makinson (the AGM approach). This is first generalized to allow the iteration of theory change operations to capture the dynamics of epistemic states according to a principle of minimal change of entrenchment. The iterative operations of expansion, contraction and revision are characterized both by a set of postulates and by Grove's construction (...) based on total pre-orders on the set of complete theories of the belief logic. We present a sound and complete conditional logic whose semantics is based on our iterative revision operation, but which avoids Gärdenfors's triviality result because of a severely restricted language of beliefs and hence the weakened scope of our extended postulates. In the second part of the paper, we develop a computational approach to theory dynamics using Rott's E-bases as a representation for epistemic states. Under this approach, a ranked E-base is interpreted as standing for the most conservative entrenchment compatible with the base, reflecting a kind of foundationalism in the acceptance of evidence for a belief. Algorithms for the computation of our iterative versions of expansion, contraction and revision are presented. Finally, we consider the relationship between nonmonotonic reasoning and both conditional logic and belief revision. Adapting the approach of Delgrande, we show that the unique extension of a default theory expressed in our conditional logic of belief revision corresponds to the most conservative belief state which respects the theory: however, this correspondence is limited to propositional default theories. Considering first order default theories, we present a belief revision algorithm which incorporates the assumption of independence of default instances and propose the use of a base logic for default reasoning which incorporates uniqueness of names. We conclude with an examination of the behavior of an implemented system on some of Lifschitz's benchmark problems in nonmonotonic reasoning. (shrink)

Since the early 1980s, logical theories of belief revision have offered formal methods for the transformation of knowledge bases or “corpora” of data and beliefs. Early models have dealt with unconditional acceptance and integration of potentially belief-contravening pieces of information into the existing corpus. More recently, models of “non-prioritized” revision were proposed that allow the agent rationally to refuse to accept the new information. This paper introduces a refined method for changing beliefs by specifying constraints on the relative (...) plausibility of propositions. Like the earlier belief revision models, the method proposed is a qualitative one, in the sense that no numbers are needed in order to specify the posterior plausibility of the new information. We use reference beliefs in order to determine the degree of entrenchment of the newly accepted piece of information. We provide two kinds of semantics for this idea, give a logical characterization of the new model, study its relation with other operations of belief revision and contraction, and discuss its intuitive strengths and weaknesses. (shrink)

The paper attacks the widely held view that belief revision theories, as they have been studied in the past two decades, are founded on the Principle of Informational Economy. The principle comes in two versions. According to the first, an agent should, when accepting a new piece of information, aim at a minimal change of his previously held beliefs. If there are different ways to effect the belief change, then the agent should, according to he second version, give (...) up those beliefs that are least entrenched. Although widely proclaimed by belief revision theorists, I argue that both versions of the principle are dogmas that are not (and perhaps should not be) adhered to. I substantiate this claim with two simple mathematical observations, and I defend it against four possible objections that involve contractions, reconstructions, dispositions, and truths. (shrink)

Carlos Alchourrón, Peter Gärdenfors and David Makinson published in 1985 a seminal article on belief change in the Journal of Symbolic Logic. Researchers from various disciplines, from computer science to mathematical economics to philosophical logic, have continued the work first presented in this seminal paper during the last two decades. This paper explores some salient foundational trends that interpret the act of changing view as a decision. We will argue that some of these foundational trends are already present, although (...) only tacitly, in the original article by the AGM trio. Other accounts decidedly depart from the view of contraction and revision presented in this seminal paper. I shall survey various types of theories that progressively depart form the axiomatic treatment defended by AGM. First, I consider theories where rational agents are considered as maximizers as opposed to optimizers ). Second, I consider which feasible set to use in contraction understood as a cognitive decision. This leads to rethink the very notion of what minimal change in contraction is. I shall conclude with some philosophical reflections concerning the sort of epistemological voluntarism that is tacit in seeing change in view as a rational choice. Carlos Alchourrón, Peter Gärdenfors y David Makinson publicaron en 1985 un artículo seminal sobre cambio de creencias en Journal of Symbolic Logic. Investigadores de varias disciplinas, desde la ciencia de la computación hasta la economía matemática y la lógica filosófica, han continuado en las dos últimas décadas esta línea de investigación. Este trabajo explora algunos aspectos fundacionalmente salientes que interpretan el acto de cambio de vista como una decisión. Argumentaremos que algunos de esos aspectos fundacionales ya estaban presentes, aunque solo tácitamente, en el artículo original del trío AGM. Otros abordajes parten decididamente de la contracción y revisión tal como fueran presentadas en el trabajo seminal. Inspeccionaré varios tipos de teorías que progresivamente parten del tratamiento axiomático defendido por AGM. Primero, considero teorías donde los agentes racionales aparecen como maximizadres opuestos a los optimiadores ). Segundo, me pregunto cuál conjunto derrotable debe usarse en una contracción entendida como una decisión cognitiva, lo cual lleva a repensar la importante cuestión de en qué consiste la noción de cambio mínimo en la contracción. Concluiré con algunas reflexiones filosóficas acerca de la suerte de voluntarismo epistemológico que está tácito en la concepción del cambio como una opción racional. (shrink)

It was shown that finite P-recovery holds for partial meet package contraction in Furhmann and Hansson (1994). However, it is not known if recovery holds for partial meet package contraction in the infinite case. In this paper, I show that recovery does not hold for partial meet package contraction in the infinite case.

The AGM theory of belief revision provides a formal framework to represent the dynamics of epistemic states. In this framework, the beliefs of the agent are usually represented as logical formulas while the change operations are constrained by rationality postulates. In the original proposal, the logic underlying the reasoning was supposed to be supraclassical, among other properties. In this paper, we present some of the existing work in adapting the AGM theory for non-classical logics and discuss their (...) interconnections and what is still missing for each approach. (shrink)

This work explores the conceptual and empirical issues of the concept of knowledge and its relation to the pattern of our belief change, from formal and experimental perspectives. Part I gives an analysis of knowledge (called Sustainability) that is formally represented and naturalistically plausible at the same time, which is claimed to be a synthesized view of knowledge, covering not only empirical knowledge, but also knowledge of future, practical knowledge, mathematical knowledge, knowledge of general facts. Part II tries to (...) formalize the natural pattern of belief change assumed in Sustainability in terms of a specific formal theory of belief change, after carefully examining the notions of belief, belief change, and Information, from which the cognitive function F in Chapter 3 is actually constructed, which is later implemented by a computer program and its behavior against random input is demonstrated. In Part III we proceed to examine the analysis empirically. In particular, we will investigate Sustainability from the developmental point of view. We first justify experimental approach in philosophy as a legitimate method of philosophical investigation, and then developmental approach in particular. The specific proposal of experiment here is what we call the Gettier Task, an analogue of the famous false-belief task in developmental psychology, which has been much discussed in philosophy of mind. Two versions of the Gettier Task were tested on children aged from 6 to 12, and we claim that the data obtained empirically supports our analysis of knowledge, or Sustainability. (shrink)

In this paper, we address the problem of truth approximation through theory change, asking whether revising our theories by newly acquired data leads us closer to the truth about a given domain. More particularly, we focus on “nomic conjunctive theories”, i.e., theories expressed as conjunctions of logically independent statements concerning the physical or, more generally, nomic possibilities and impossibilities of the domain under inquiry. We define both a comparative and a quantitative notion of the verisimilitude of such theories, and (...) identify suitable conditions concerning the (partial) correctness of acquired data, under which revising our theories by data leads us closer to “the nomic truth”, construed as the target of scientific inquiry. We conclude by indicating some further developments, generalizations, and open issues arising from our results. (shrink)

In the tradition of Stalnaker there is a number of well-known problems that need to be addressed, because revision of iterated belief modalities is required in this case. These problems have already been investigated in detail in recent works on DDL Leitgeb/Segerberg 2007)and DEL see e.g. Ditmarsch et. Another strategy would be to maintain and revise assumptions independently of the beliefs of an agent.I will briefly discuss the advantages and disadvantages of each of these views. In both views, assumptions (...) constitute the subjective context in which an agent interprets an utterance and encounters the world. The result of an interpretation is in turn checked against the agent’s original beliefs, and if the checking operation succeeds the agent revises his beliefs by the result in the normal way described by the AGM paradigm. The second of the above questions needs to be addressed on the basis of concrete examples. Considering utterance like David is ready’ or ‘John is tall’that from a contextualist viewpoint express semantically incomplete content in the sense of Bach is needed in order to obtain a useful model of the checking step, since fortunately not everybody believes everything that other people say. These requirements put the theory of interpretation based on assumptions in the frontline of ongoing research on the implementation of belief revision and update in dynamic logics. Such a theory might also be useful for contextualist accounts of strong knowledge, as it can be argued convincingly that when a knowledge ascription appears to be context-sensitive, this is so because the embedded proposition is context-sensitive and not because knowledge itself is context-sensitive. Hence,the context-sensitivity of embedded propositions in knowledge claims and how different agents in the same situation arrive at different assessments about them may be explained by an inferential theory of interpretation similar to the one outlined here but with another underlying concept of assumptions. Literature Alchourrón, C. E. ; Gärdenfors, P. & Makinson, D., 'On the logic of theory change: partial meet contraction and revision functions', Journal of Symbolic Logic, 510-530. Bach, K., 'Minimalism for Dummies: Reply to Cappelen and Lepore', Technical report, University of San Fransisco, Department of Philosophy. Bach, K., Context ex Machina, in án Gendler Szabó, ed.,'Semantics versus Pragmatics', Oxford UP, Oxford, pp. 16-44. Ditmarsch, H. v. ; Hoek, W. v. d. & Kooi, B., Dynamic Epistemic Logic, Kluwer. Gärdenfors, P., Knowledge in Flux, MIT Press. Leitgeb, H. & Segerberg, K., 'Dynamic doxastic logic: why, how, and where to? ', Synthese155, 167-190. Stalnaker, R., Assertion, in. Cole, ed.,'Pragmatics', Academic Press, New York, pp. 315-332. Stalnaker, R., 'Common Ground', Linguistics and Philosophy25, 701- -721. (shrink)

An operator of contraction for a belief set (a theory) can be obtained by assigning to it a belief base and an operator of partial meet contraction for that base. It is argued that closure of the base under disjunction is an intuitively reasonable condition. Axiomatic characterizations are given of the contractions of belief sets that can be generated by (various types of) partial meet contraction on disjunctively closed bases. The corresponding revision operators are also characterized. (...) Finally, some results are reported on operations on bases that are closed under material implication. (shrink)

It is natural and important to have a formal representation of plain belief, according to which propositions are held true, or held false, or neither. (In the paper this is called a deterministic representation of epistemic states). And it is of great philosophical importance to have a dynamic account of plain belief. AGM belief revision theory seems to provide such an account, but it founders at the problem of iterated belief revision, since it can generally (...) account only for one step of revision. The paper discusses and rejects two solutions within the confines of AGM theory. It then introduces ranking functions (as I prefer to call them now; in the paper they are still called ordinal conditional functions) as the proper (and, I find, still the best) solution of the problem, proves that conditional independence w.r.t. ranking functions satisfies the so-called graphoid axioms, and proposes general rules of belief change (in close analogy to Jeffrey's generalized probabilistic conditionalization) that encompass revision and contraction as conceived in AGM theory. Indeed, the parallel to probability theory is amazing. Probability theory can profit from ranking theory as well since it is also plagued by the problem of iterated belief revision even if probability measures are conceived as Popper measures (see No. 11). Finally, the theory is compared with predecessors which are numerous and impressive, but somehow failed to explain the all-important conditional ranks in the appropriate way. (shrink)

This chapter contains sections titled: Belief Revision in Latin America: The Legacy of Carlos Alchourrón The AGM Approach The Logic of Theory Change and Epistemology What Is an Epistemic State? Departures from AGM References.