We present different constructions for nonprioritized belief revision, that is, belief changes in which the input sentences are not always accepted. First, we present the concept of explanation in a deductive way. Second, we define multiple revision operators with respect to sets of sentences (representing explanations), giving representation theorems. Finally, we relate the formulated operators with argumentative systems and default reasoning frameworks.

We present a general framework for representing belief-revision rules and use it to characterize Bayes's rule as a classical example and Jeffrey's rule as a non-classical one. In Jeffrey's rule, the input to a belief revision is not simply the information that some event has occurred, as in Bayes's rule, but a new assignment of probabilities to some events. Despite their differences, Bayes's and Jeffrey's rules can be characterized in terms of the same axioms: "responsiveness", which (...) requires that revised beliefs incorporate what has been learnt, and "conservativeness", which requires that beliefs on which the learnt input is "silent" do not change. To illustrate the use of non-Bayesian belief revision in economic theory, we sketch a simple decision-theoretic application. (shrink)

In this paper two systems of AGM-like Paraconsistent Belief Revision are overviewed, both defined over Logics of Formal Inconsistency (LFIs) due to the possibility of defining a formal consistency operator within these logics. The AGM° system is strongly based on this operator and internalize the notion of formal consistency in the explicit constructions and postulates. Alternatively, the AGMp system uses the AGM-compliance of LFIs and thus assumes a wider notion of paraconsistency - not necessarily related to the notion (...) of formal consistency. (shrink)

This is a survey paper. Contents: 1 Introduction -- 2 The representation of belief -- 3 Kinds of belief change -- 4 Coherence constraints for belief revision -- 5 Different modes of belief change -- 6 Two strategies for characterizing rational changes of belief - 6.1 The postulates strategy - 6.2 The constructive strategy -- 7 An abstract view of the elements of belief change -- 8 Iterated changes of belief -- 9 (...) Further developments - 9.1 Variants and extensions of belief revision - 9.2 Updates - 9.3 Default inferences as expectation revision - 9.4 Belief merging -- 10 Concluding remarks. (shrink)

Belief revision theory studies how an ideal doxastic agent should revise her beliefs when she receives new information. In part I, I have first presented the AGM theory of belief revision. Then I have focused on the problem of iterated belief revisions. In part II, I will first present ranking theory (Spohn 1988). Then I will show how it solves the problem of iterated belief revisions. I will conclude by sketching two areas of future (...) research. (shrink)

According to the cognitive model of psychopathology, maladaptive beliefs about oneself, others, and the world are the main factors contributing to the development and persistence of various forms of mental suffering. Therefore, the key therapeutic process of Cognitive Behavioral Therapy (CBT)—a therapeutic approach rooted in the cognitive model—is cognitive restructuring, i.e., a process of revision of such maladaptive beliefs. In this paper, I examine the philosophical assumptions underlying CBT and offer theoretical reasons to think that the effectiveness of (...) class='Hi'>belief revision in psychotherapy is very limited. This is the case, I argue, because the cognitive model wrongly assumes that our body of beliefs is unified, while it is in fact fragmented. (shrink)

The paper attacks the almost universally held view that belief revison theories, as they have been studied in the literature of the past two decades, are founded on a Principle of Minimal Change, or Principle of Informational Economy. The principle comes in two versions. According to the first, an agent should, when accepting new information, aim at a posterior belief set that minimizes the items on which it disagrees with the prior belief set. If there are different (...) ways to effect the belief change, then according to the second version, the agent should give up the beliefs that are least entrenched. Although widely endorsed and advertised by belief revision theorists, the paper argues that both versions of the principle are dogmas that are not in fact (and perhaps should not be) adhered to. Two simple mathematical observations substantiate this claim, and it is defended against four possible objections that involve contractions, reconstructions, dispositions, and truths. (shrink)

The well known AGM framework for belief revision has recently been extended to include a model of the research agenda of the agent, i.e. a set of questions to which the agent wishes to find answers (Olsson & Westlund in Erkenntnis , 65 , 165–183, 2006 ). The resulting model has later come to be called interrogative belief revision . While belief revision has been studied extensively from the point of view of modal logic, (...) so far interrogative belief revision has only been dealt with in the metalanguage approach in which AGM was originally presented. In this paper, I show how to model interrogative belief revision in a modal object language using a class of operators for questions. In particular, the solution I propose will be shown to capture the notion of K-truncation , a method for agenda update in the case of expansion constructed by Olsson & Westlund. Two case studies are conducted: first, an interrogative extension of Krister Segerberg’s system DDL, and then a similar extension of Giacomo Bonanno’s modal logic for belief revision. Sound and complete axioms will be provided for both of the resulting logics. (shrink)

We show how belief revision can be treated systematically in the format of dynamicepistemic logic, when operators of conditional belief are added. The core engine consists of definable update rules for changing plausibility relations between worlds, which have been proposed independently in the dynamic-epistemic literature on preference change. Our analysis yields two new types of modal result. First, we obtain complete logics for concrete mechanisms of belief revision, based on compositional reduction axioms. Next, we show (...) how various abstract postulates for belief revision can be analyzed by standard modal frame correspondences for model-changing operations. (shrink)

We propose a dynamic hyperintensional logic of belief revision for non-omniscient agents, reducing the logical omniscience phenomena affecting standard doxastic/epistemic logic as well as AGM belief revision theory. Our agents don’t know all a priori truths; their belief states are not closed under classical logical consequence; and their belief update policies are such that logically or necessarily equivalent contents can lead to different revisions. We model both plain and conditional belief, then focus on (...) dynamic belief revision. The key idea we exploit to achieve non-omniscience focuses on topic- or subject matter-sensitivity: a feature of belief states which is gaining growing attention in the recent literature. (shrink)

This paper presents a probabilist paraconsistent theory of belief revision. This theory is based on a very general theory of probability, that fits with a wide range of classical and nonclassical logics. The theory incorporates a version of Jeffrey conditionalisation as its method of updating. A Dutch book argument is given, and the theory is applied to the problem of choosing a logical system.

The Bayesian maxim for rational learning could be described as conservative change from one probabilistic belief or credence function to another in response to newinformation. Roughly: ‘Hold fixed any credences that are not directly affected by the learning experience.’ This is precisely articulated for the case when we learn that some proposition that we had previously entertained is indeed true (the rule of conditionalisation). But can this conservative-change maxim be extended to revising one’s credences in response to entertaining propositions (...) or concepts of which one was previously unaware? The economists Karni and Vierø (2013, 2015) make a proposal in this spirit. Philosophers have adopted effectively the same rule: revision in response to growing awareness should not affect the relative probabilities of propositions in one’s ‘old’ epistemic state. The rule is compelling, but only under the assumptions that its advocates introduce. It is not a general requirement of rationality, or so we argue. We provide informal counterexamples. And we show that, when awareness grows, the boundary between one’s ‘old’ and ‘new’ epistemic commitments is blurred. Accordingly, there is no general notion of conservative change in this setting. (shrink)

This is a discussion of the problem of extending the basic AGM belief revision theory to iterated belief revision: the problem of formulating rules, not only for revising a basic belief state in response to potential new information, but also for revising one’s revision rules in response to potential new information. The emphasis in the paper is on foundational questions about the nature of and motivation for various constraints, and about the methodology of the (...) evaluation of putative counterexamples to proposed constraints. Some specific constraints that have been proposed are criticized. The paper emphasizes the importance of meta-information—information about one’s sources of information—and argues that little of substance can be said about constraints on iterated belief revision at a level of abstraction that lacks the resources for explicit representation of meta-information. (shrink)

I develop a dynamic logic for reasoning about "interrogative belief revision", a new branch of belief revision theory that has been developed in a small number of papers, beginning with E. J. Olsson and D. Westlund's paper "On the role of the research agenda in epistemic change" [12]. In interrogative belief revision, epistemic states are taken to include a research agenda, consisting of questions the agent seeks to answer. I present a logic for (...) class='Hi'>revision of such epistemic states based on the notion of an epistemic strategy, a stable plan of action that determines changes in the agent's research agenda. This idea is a further development of an idea put forward in [6], that changes in the research agenda of an agent should be determined by stable, "long term" research interests. I provide complete axioms and a decidability result for the logic. (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)

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)

I present a possible worlds semantics for a hyperintensional belief revision operator, which reduces the logical idealization of cognitive agents affecting similar operators in doxastic and epistemic logics, as well as in standard AGM belief revision theory. (Revised) belief states are not closed under classical logical consequence; revising by inconsistent information does not perforce lead to trivialization; and revision can be subject to ‘framing effects’: logically or necessarily equivalent contents can lead to different revisions. (...) Such results are obtained without resorting to non-classical logics, or to non-normal or impossible worlds semantics. The framework combines, instead, a standard semantics for propositional S5 with a simple mereology of contents. (shrink)

Krister Segerberg proposed irrevocable belief revision, to be contrasted with standard belief revision, in a setting wherein belief of propositional formulas is modelled explicitly. This suggests that in standard belief revision is revocable: one should be able to unmake (‘revoke’) the fresh belief in the revision formula, given yet further information that contradicts it. In a dynamic epistemic logical setting for belief revision, for multiple agents, we investigate what the (...) requirements are for revocable belief revision. By this we not merely mean recovering belief in non-modal propositions, as in the recovery principle for belief contraction, but recovering belief in modal propositions: beliefs about beliefs. These requirements are almost never met, a surprising result. (shrink)

Belief revision theory studies how an ideal doxastic agent should revise her beliefs when she receives new information. In part I I will first present the AGM theory of belief revision (Alchourrón & Gärdenfors & Makinson 1985). Then I will focus on the problem of iterated belief revisions.

This is a short version of Lindström & Rabinowicz 1991.In earlier papers, we proposed a generalization of the AGM approach to belief revision. The proposal was to view belief revision as a relation rather than as a function on theories (or belief sets). Going relational means that one allows for several equally reasonable revisions of a theory with a given proposition. In the present paper, we show that the relational approach is the natural result of (...) generalizing in a certain way an approach to belief revision due to Adam Grove. In his (1988) paper, Grove presented two closely related modelings of functional belief revision, one in terms of a family of "spheres" around the agent's theory G and the other in terms of an epistemic entrenchment ordering of propositions. The "sphere"-terminology is natural when one looks upon theories and propositions as sets of possible worlds. Grove's spheres may be thought of as possible "fallback" theories relative to the agent's original theory: theories that he may reach by deleting propositions that are not "sufficiently" entrenched (according to standards of sufficient entrenchment of varying stringency). The entrenchment ordering can be recovered from the family of fallbacks by the definition: A is at least as entrenched as B iff A belongs to every fallback to which B belongs. To revise a theory T with a proposition A, we go to the smallest sphere that contain A-worlds and intersect it with A. The relational notion of belief revision that we are interested in, results if one allows that some propositions may be incomparable with respect to epistemic entrenchment. As a result, the family of fallbacks around a given theory will no longer have to be nested. This change opens up the possibility for several different ways of revising a theory with a given proposition. (shrink)

Hans Rott has argued, most recently in his book Change, Choice and Inference, that certain formal correspondences between belief revision and rational choice have important philosophical implications, claiming that the former strongly indicate the unity of practical and theoretical reason as well as the primacy of practical reason. In this paper, I confront Rott's argument with three serious challenges. My conclusion is that, while Rott's work is indisputable as a formal achievement, the philosophical consequences he wants to draw (...) are not forthcoming. (shrink)

The Egli-Milner power-ordering is used to define verisimilitude orderings on theories from preference orderings on models. The effects of the definitions on constraints such as stopperedness and soundness are explored. Orderings on theories are seen to contain more information than orderings on models. Belief revision is defined in terms of both types of orderings, and conditions are given which make the two notions coincide.

In this paper we present a new modeling for belief revision that is what we term irrevocable. This modeling is of philosophical interest since it captures some features of suppositional reasoning, and of formal interest since it is closely connected with AGM, yet provides for iterated belief revision. The analysis is couched in terms of dynamic doxastic logic.

Hans Rott has argued, most recently in his book Change, Choice and Inference, that certain formal correspondences between belief revision and rational choice have important philosophical implications, claiming that the former strongly indicate the unity of practical and theoretical reason as well as the primacy of practical reason. In this paper, I confront Rott's argument with three serious challenges. My conclusion is that, while Rott's work is indisputable as a formal achievement, the philosophical consequences he wants to draw (...) are not forthcoming. (shrink)

We are fallible creatures, prone to making all sorts of mistakes. So, we should be open to evidence of error. But what constitutes such evidence? And what is it to rationally accommodate it? I approach these questions by considering an evolutionary debunking argument according to which (a) we have good, scientific, reason to think our moral beliefs are mistaken, and (b) rationally accommodating this requires revising our confidence in, or altogether abandoning the suspect beliefs. I present a dilemma for such (...) debunkers, which shows that either we have no reason to worry about our moral beliefs, or we do but we can self-correct. Either way, moral skepticism doesn’t follow. That the evolutionary debunking argument fails is important; also important, however, is what its failure reveals about rational belief revision. Specifically, it suggests that getting evidence of error is a non-trivial endeavor and that we cannot learn that we are likely to be mistaken about some matter from a neutral stance on that matter. (shrink)

We investigate the discrete (finite) case of the Popper–Renyi theory of conditional probability, introducing discrete conditional probabilistic models for knowledge and conditional belief, and comparing them with the more standard plausibility models. We also consider a related notion, that of safe belief, which is a weak (non-negatively introspective) type of “knowledge”. We develop a probabilistic version of this concept (“degree of safety”) and we analyze its role in games. We completely axiomatize the logic of conditional belief, knowledge (...) and safe belief over conditional probabilistic models. We develop a theory of probabilistic dynamic belief revision, introducing probabilistic “action models” and proposing a notion of probabilistic update product, that comes together with appropriate reduction laws. (shrink)

In this study, we examine the problem of belief revision, defined as deciding whic h of several initially-accepted sentences to disbelieve, when new information presents a l ogical inconsistency with the initial set. In the first three experiments, the initial sentence set included a conditional sentence, a non-conditional sentence, and an inferred conclusi on drawn from the first two. The new information contradicted the inferred conclusion. Results indicated that the conditional sentences were more readily abandoned than non-c onditional (...) sentences, even when either choice would lead to a consistent belief state, and that this preference was more pronounced when problems used natural language cover sto ries rather than symbols. The pattern of belief revision choices differed depending on whe ther the contradicted conclusion from the initial belief set had been a modus ponens or m odus tollens inference. Two additional experiments examined alternative model-theoretic definitions of minimal change to a belief state, using problems that contained multiple mo dels of the initial belief state and of the new information that provided the contradiction. The results indicated that people did not follow any of four formal definitions of minimal change on these problems. The new information and the contradiction it offered was not, for example, used to select a particular model of the initial belief state as a way of reconci ling the contradiction. The preferred revision was to retain only those initial sentences th at had the same, unambiguous truth value within and across both the initial and new info rmation sets. The study and results are presented in the context of certain logic-based for malizations of belief revision, syntactic and model-theoretic representations of belief stat es, and performance models of human deduction. Principles by which some types of sent ences might be more "entrenched" than others in the face of contradiction are also discuss ed from the perspective of induction and theory revision. (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 present paper aims at a synthesis of belief revision theory with the Sneed formalism known as the structuralist theory of science. This synthesis is brought about by a dynamisation of classical structuralism, with an abductive inference rule and base generated revisions in the style of Rott (2001). The formalism of prioritised default logic (PDL) serves as the medium of the synthesis. Why seek to integrate the Sneed formalism into belief revision theory? With the hybrid system (...) of the present investigation, a substantial simplification of the ranking information that is necessary to define revisions and contractions uniquely is achieved. This system is, furthermore, expressive enough to capture complex and non-trivial scientific examples. It is thus closely related to a novel research area within belief revision theory which addresses the dynamics of scientific knowledge. (shrink)

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change carefully, we must be quite explicit about the ontology or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken (...) for granted: the first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called beyond controversy are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by and then by ¬. (shrink)

Abduction was first introduced in the epistemological context of scientific discovery. It was more recently analyzed in artificial intelligence, especially with respect to diagnosis analysis or ordinary reasoning. These two fields share a common view of abduction as a general process of hypotheses formation. More precisely, abduction is conceived as a kind of reverse explanation where a hypothesis H can be abduced from events E if H is a good explanation of E. The paper surveys four known schemes for abduction (...) that can be used in both fields. Its first contribution is a taxonomy of these schemes according to a common semantic framework based on belief revision. Its second contribution is to produce, for each non-trivial scheme, a representation theorem linking its semantic framework to a set of postulates. Its third contribution is to present semantic and axiomatic arguments in favor of one of these schemes, ordered abduction, which has never been vindicated in the literature. (shrink)

This is a survey paper. Contents: 1 Introduction ― 2 Preliminary remarks on information, truth and mind - 2.1 Remarks on information and truth - 2.2 Some clues from the philosophy of mind - 2.3 Functionalism as applied to belief revision - 2.4 Filling in the parameters ― 3 Belief change = revision + reflection - 3.1 Foundationalism - 3.2 Coherentism ― 4 Inference operations for simple change operations: three examples - 4.1 Example 1: flat data (...) bases - 4.2 Example 2: up-sets in prioritized data bases - 4.3 Example 3: maximal-consistent sets in prioritized data bases ― 5 Representing coherentist belief change by operations on prioritized data bases - 5.1 Moderate revision - 5.2 Revision by comparison ― 6 A very brief history of belief revision - 6.1 The 1980s: AGM's classical model - 6.2 The 1990s: iteration - 6.3 The 2000s: merging ― 7 Conclusion. (shrink)

A general criterion for the theory of belief revision is that when we revise a state of belief by a sentence A, as much of the old information as possible should be retained in the revised state of belief. The motivating idea in this paper is that if a belief B is irrelevant to A, then B should still be believed in the revised state. The problem is that the traditional definition of statistical relevance suffers (...) from some serious shortcomings and cannot be used as a tool for defining belief revision processes. In particular, the traditional definition violates the requirement that if A is irrelevant to C and B is irrelevant to C, then A&B is irrelevant to C. In order to circumvent these drawbacks, I develop an amended notion of relevance which has the desired properties. On the basis of the new definition, I outline how it can be used to simplify a construction of a belief revision method. (shrink)

Belief revision theory concerns methods for reformulating an agent's epistemic state when the agent's beliefs are refuted by new information. The usual guiding principle in the design of such methods is to preserve as much of the agent's epistemic state as possible when the state is revised. Learning theoretic research focuses, instead, on a learning method's reliability or ability to converge to true, informative beliefs over a wide range of possible environments. This paper bridges the two perspectives by (...) assessing the reliability of several proposed belief revision operators. Stringent conceptions of minimal change are shown to occasion a limitation called inductive amnesia: they can predict the future only if they cannot remember the past. Avoidance of inductive amnesia can therefore function as a plausible and hitherto unrecognized constraint on the design of belief revision operators. (shrink)

This paper aims at comparing and relating belief revision and argumentation as approaches to model reasoning processes. Referring to some prominent literature references in both fields, we will discuss their (implicit or explicit) assumptions on the modeled processes and hence commonalities and differences in the forms of reasoning they are suitable to deal with. The intended contribution is on one hand assessing the (not fully explored yet) relationships between two lively research fields in the broad area of defeasible (...) reasoning and on the other hand pointing out open issues and potential directions for future research. (shrink)

In this rather technical paper we establish a useful combination of belief revision and verisimilitude according to which better theories provide better predictions, and revising with more verisimilar data results in theories that are closer to the truth. Moreover, this paper presents two alternative definitions of refined verisimilitude, which are more perspicuous than the algebraic version used in previous publications.

Discussions of the issue of iterated belief revision are commonly accompanied by the presentation of three “concrete” operators: natural, restrained and lexicographic. This raises a natural question: What is so distinctive about these three particular methods? Indeed, the common axiomatic ground for work on iterated revision, the AGM and Darwiche-Pearl postulates, leaves open a whole range of alternative proposals. In this paper, we show that it is satisfaction of an additional principle of “Independence of Irrelevant Alternatives”, inspired (...) by the literature on Social Choice, that unites and sets apart our three “elementary” revision operators. A parallel treatment of iterated belief contraction is also given, yielding a family of elementary contraction operators that includes, besides the well-known “conservative” and “moderate” operators, a new contraction operator that is related to restrained revision. (shrink)

Postulational approaches attempt to understand the dynamics of belief revision by appealing to no more than the set of beliefs held by an agent and the logical relations between them. It is argued there that such an approach cannot work. A proper account of belief revision must also appeal to the arguments supporting beliefs, and recognize that those arguments can be defeasible. If we begin with a mature epistemological theory that accommodates this, it can be seen (...) that the belief revision operators on which the postulational theories are based are ill-defined. It is further argued that there is no way to repair the definitions so as to retain the spirit of those theory. Belief revision is better studied from within an independently motivated epistemological theory. (shrink)

The theory of belief revision deals with (rational) changes in beliefs in response to new information. In the literature a distinction has been drawn between belief revision and belief update (see [6]). The former deals with situations where the objective facts describing the world do not change (so that only the beliefs of the agent change over time), while the letter allows for situations where both the facts and the doxastic state of the agent change (...) over time. We focus on belief revision and propose a temporal framework that allows for iterated revision. We model the notion of “minimal” or “conservative” belief revision by considering logics of increasing strength. We move from one logic to the next by adding one or more axioms and show that the corresponding logic captures more stringent notions of minimal belief revision. The strongest logic that we propose provides a full axiomatization of the well-known AGM theory of belief revision. (shrink)

Philosophical logicians proposing theories of rational belief revision have had little to say about whether their proposals assist or impede the agent's ability to reliably arrive at the truth as his beliefs change through time. On the other hand, reliability is the central concern of formal learning theory. In this paper we investigate the belief revision theory of Alchourron, Gardenfors and Makinson from a learning theoretic point of view.

We introduce a new operator, called rational evaluation, in belief change. The operator evaluates new information according to the agent’s core beliefs, and then exports the plausible part of the new information. It belongs to the decision module in belief change. We characterize rational evaluation by axiomatic postulates and propose two functional constructions for it, based on the well-known constructions of kernel sets and remainder sets, respectively. The main results of the paper are two representation theorems with respect (...) to the two functional constructions. We also compare and connect the evaluation operator with some related operators in belief revision, including contraction, set contraction, and prioritized multiple revision. (shrink)

Agents which perform inferences on the basis of unreliable information need an ability to revise their beliefs if they discover an inconsistency. Such a belief revision algorithm ideally should be rational, should respect any preference ordering over the agent’s beliefs (removing less preferred beliefs where possible) and should be fast. However, while standard approaches to rational belief revision for classical reasoners allow preferences to be taken into account, they typically have quite high complexity. In this paper, (...) we consider belief revision for agents which reason in a simpler logic than full first-order logic, namely rule-based reasoners. We show that it is possible to define a contraction operation for rule-based reasoners, which we call McAllester contraction, which satisfies all the basic Alchourrón, Gärdenfors and Makinson (AGM) postulates for contraction (apart from the recovery postulate) and at the same time can be computed in polynomial time. We prove a representation theorem for McAllester contraction with respect to the basic AGM postulates (minus recovery), and two additional postulates. We then show that our contraction operation removes a set of beliefs which is least preferred, with respect to a natural interpretation of preference. Finally, we show how McAllester contraction can be used to define a revision operation which is also polynomial time, and prove a representation theorem for the revision operation. (shrink)

This chapter discusses an account of belief-revision that is compatible with the rational belief of contradictions. In the process, a formal account of the model of rationality of the preceding chapter is provided. The account of belief-revision is contrasted with the familiar AGM account.

The standard theory for belief revision provides an elegant and powerful framework for reasoning about how a rational agent should change its beliefs when confronted with new information. However, the agents considered are extremely idealized. Some recent models attempt to tackle the problem of plausible belief revision by adding structure to the belief bases and using nonstandard inference operations. One of the key ideas is that not all of an agent's beliefs are relevant for an (...) operation of belief change.In this paper we incorporate the insights pertaining to local change and relevance sensitivity with the use of approximate inference relations. These approximate inference relations offer us partial solutions at any stage of the revision process. The quality of the approximations improves as we allow for more and more resources to be used. We are provided with upper and lower bounds to what would be obtained with the use of classical inference. (shrink)