ABSTRACT The major approaches to belief revision and non monotonic reasoning proposed in the literature differ along a number of dimensions, including whether they are ?syntax- based? or ?semantic-based?, ?foundational? or ?coherentist?, ?consistence-restoring? or ?inconsistency-tolerant?. Our contribution towards clarifying the connections between these various approaches is threefold: ?We show that the two main approaches to belief revision, the foundations and coherence theories, are mathematically equivalent, thus answering a question left open in [Gar90, Doy92], The distinction between syntax-based approaches to revision (...) and approaches based on (semantic) preferential structures falls along similar lines, and their expressive equivalence is a consequence of this result. ?We formally clarify the connection between belief revision and non monotonic reasoning, in a particularly simple way which also throws light on the connection between consistence- restoring and reasoning-from-inconsistency approaches [BDP95]. ?As a direct application of the above, we show that Poole's (syntax-based) system of default reasoning and Shoham's preferential semantic for non monotonic reasoning are also expressively equivalent, in that they can represent the same set of non monotonic consequence relations. (shrink)

In this paper we propose an approach to multi-source belief revision where the trust or credibility assigned to informant agents can be revised. In our proposal, the credibility of each informant represented as a strict partial order among informant agents, will be maintained in a repository called credibility base. Upon arrival of new information concerning the credibility of its peers, an agent will be capable of revising this strict partial order, changing the trust assigned to its peers accordingly. Our goal (...) is to formalize a set of change operators over the credibility base: expansion, contraction, prioritized, and non-prioritized revision. These operators will provide the capability of dynamically modifying the credibility of informants considering the reliability of the information. This dynamics will reflect a new perception of trust assigned to the informant, or extend the set of informants by admitting the addition of new informant agents. (shrink)

This paper is part of an on-going programme on the study of the logical aspects of social network formation. It recalls the so-called social network model, discussing the properties of a notion of closeness between agents ; then introduces an extended social network model in which different agents might assign different values to different traits, discussing the properties of the notion of weighted closeness that arises. These notions are used to define social network creation operations by means of a threshold (...) strategy. The paper studies the properties of the social networks the updates create, providing sound and complete axiom systems for formal languages describing these updates’ effects. (shrink)

We point out a simple but hitherto ignored link between the theoryof updates, the theory of counterfactuals, and classical modal logic: update is a classicalexistential modality, counterfactual is a classical universalmodality, and the accessibility relations corresponding to these modalities are inverses. The Ramsey Rule (often thought esoteric) is simply an axiomatisation of this inverse relationship. We use this fact to translate between rules for updates andrules for counterfactuals. Thus, Katsuno and Mendelzons postulatesU1--U8 are translated into counterfactual rules C1--C8(Table VII), and (...) many of the familiar counterfactual rulesare translated into rules for updates (Table VIII). Ourconclusions are summarised in Table V. (shrink)

According to the Ramsey Test, conditionals reflect changes of beliefs: α > β is accepted in a belief state iff β is accepted in the minimal revision of it that is necessary to accommodate α. Since Gärdenfors’s seminal paper of 1986, a series of impossibility theorems (“triviality theorems”) has seemed to show that the Ramsey test is not a viable analysis of conditionals if it is combined with AGM-type belief revision models. I argue that it is possible to endorse that (...) Ramsey test for conditionals while staying true to the spirit of AGM. A main focus lies on AGM’s condition of Preservation according to which the original belief set should be fully retained after a revision by information that is consistent with it. I use concrete representations of belief states and (iterated) revisions of belief states as semantic models for (nested) conditionals. Among the four most natural qualitative models for iterated belief change, two are identified that indeed allow us to combine the Ramsey test with Preservation in the language containing only flat conditionals of the form α > β. It is shown, however, that Preservation for this simple language enforces a violation of Preservation for nested conditionals of the form α > (β > γ). In such languages, no two belief sets are ordered by strict subset inclusion. I argue that it has been wrong right from the start to expect that Preservation holds in languages containing nested conditionals. (shrink)

Richard Bradley has initiated a new debate, with Brian Hill and Jake Chandler as further participants, about the implications of a number of so-called triviality results surrounding the Ramsey test for conditionals. I comment on this debate and argue that ‘Inclusion’ and ‘Preservation’, which were originally introduced as postulates for the rational revision of factual beliefs, have little to recommend them in the first place when extended to languages containing conditionals. I question the philosophical method of postulation that was applied (...) in the new debate, and instead base my arguments on explicit representations of belief states and canonical constructions of belief state revisions. (shrink)

In this paper I discuss the foundations of a formal theory of coherent and conservative belief change that is (a) suitable to be used as a method for constructing iterated changes of belief, (b) sensitive to the history of earlier belief changes, and (c) independent of any form of dispositional coherence. I review various ways to conceive the relationship between the beliefs actually held by an agent and her belief change strategies (that also deal with potential belief sets), show the (...) problems they suffer from, and suggest that belief states should be represented by unary revision functions that take sequences of inputs. Three concepts of coherence implicit in current theories of belief change are distinguished: synchronic, diachronic and dispositional coherence. Diachronic coherence is essentially identified with what is known as conservatism in epistemology. The present paper elaborates on the philosophical motivation of the general framework; formal details and results are provided in a companion paper. (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)

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations (...) from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction. (shrink)

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations (...) from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction. This paper deals mainly with technical aspects of our dynamic modal logic. It gives an exact description of the expressive power of this language; it also contains results on decidability for the language with 'arbitrary' structures and for the special case with a restricted class of admissible structures. In addition, a complete axiomatization is given. The paper concludes with a remark about the modal algebras appropriate for our dynamic modal logic, and some questions for further work. The paper only contains some sketchy examples showing how the logic can be used to capture situations of dynamic interest, far more detailed applications are given in a companion to this paper (De Rijke [33]). (shrink)

Alchourrón, Gärdenfors and Makinson have developed and investigated a set of rationality postulates which appear to capture much of what is required of any rational system of theory revision. This set of postulates describes a class of revision functions, however it does not provide a constructive way of defining such a function. There are two principal constructions of revision functions, namely an epistemic entrenchment and a system of spheres. We refer to their approach as the AGM paradigm. We provide a (...) new constructive modeling for a revision function based on a nice preorder on models, and furthermore we give explicit conditions under which a nice preorder on models, an epistemic entrenchment, and a system of spheres yield the same revision function. Moreover, we provide an identity which captures the relationship between revision functions and update operators (as defined by Katsuno and Mendelzon). (shrink)

Although AGM theory contraction (Alchourrón et al., 1985; Alchourrón and Makinson, 1985) occupies a central position in the literature on belief change, there is one aspect about it that has created a fair amount of controversy. It involves the inclusion of the postulate known as Recovery. As a result, a number of alternatives to AGM theory contraction have been proposed that do not always satisfy the Recovery postulate (Levi, 1991, 1998; Hansson and Olsson, 1995; Fermé, 1998; Fermé and Rodriguez, 1998; (...) Rott and Pagnucco, 1999). In this paper we present a new addition, systematic withdrawal, to the family of withdrawal operations, as they have become known. We define systematic withdrawal semantically, in terms of a set of preorders, and show that it can be characterised by a set of postulates. In a comparison of withdrawal operations we show that AGM contraction, systematic withdrawal and the severe withdrawal of Rott and Pagnucco (1999) are intimately connected by virtue of their definition in terms of sets of preorders. In a future paper it will be shown that this connection can be extended to include the epistemic entrenchment orderings of Gärdenfors (1988) and Gärdenfors and Makinson (1988) and the refined entrenchment orderings of Meyer et al. (2000). (shrink)

Intelligent agents are often faced with the problem of trying to combine possibly conflicting pieces of information obtained from different sources into a coherent view of the world. We propose a framework for the modelling of such combination operations with roots in the work of Spohn [Spo88, Spo91]. We construct a number of combination operations and we measure them against various properties that such operations ought to satisfy. We conclude by discussing the connection between combination operations and the use of (...) infobases [Mey99, MLH00]. (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)

We introduce a new operator – belief fusion– which aggregates the beliefs of two agents, each informed by a subset of sources ranked by reliability. In the process we definepedigreed belief states, which enrich standard belief states with the source of each piece of information. We note that the fusion operator satisfies the invariants of idempotence, associativity, and commutativity. As a result, it can be iterated without difficulty. We also define belief diffusion; whereas fusion generally produces a belief state with (...) more information than is possessed by either of its two arguments, diffusion produces a state with less information. Fusion and diffusion are symmetric operators, and together define a distributive lattice. Finally, we show that AGM revision can be viewed as fusion between a novice and an expert. (shrink)

We discuss similarities and residual differences, within the general semantic framework of minimality, between defeasible inference, belief revision, counterfactual conditionals, updating — and also conditional obligation in deontic logic. Our purpose is not to establish new results, but to bring together existing material to form a clear overall picture.

Most of the work in default logic is about default theories that are completely specified. In this category are the proposals of appropriate semantics for default logic, the characterizations of the complexity of reasoning with a default theory, the algorithms for finding consequences of default theories, etc. Relatively little attention has been paid to the process of building a default theory, and most of the work on this topic is about translating knowledge bases from other formalisms (such as circumscription, autoepistemic (...) logic, and action description languages) into default logic. This paper is about expressing knowledge in default logic. In particular, we assume that defaults are initially formulated as normal, and are then corrected using specific inference examples. (shrink)

Merging beliefs depends on the relative reliability of their sources. When this is information is absent, assuming equal reliability is unwarranted. The solution proposed in this article is that every reliability profile is possible, and only what holds according to all of them is accepted. Alternatively, one source is completely reliable, but which one is not specified. These two cases motivate two existing forms of merging: maxcons-based merging and disjunctive merging.

In this paper, we formulate some approaches to belief fusion and revision using epistemic logic semantics. Fusion operators considered in this paper are majority merging, arbitration, and general merging. Some modalities corresponding to belief fusion and revision operators are incorporated into epistemic logics. The Kripke semantics of these extended logics are presented. While most existing approaches treat belief fusion and revision operators as meta-level constructs, we directly incorporate these operators into our object logic language. By doing so, we both extend (...) the expressive power of epistemic logic and enhance the techniques of information fusion. (shrink)

Belief revision theories standardly endorse a principle of intensionality to the effect that ideal doxastic agents do not discriminate between pieces of information that are equivalent within classical logic. I argue that this principle should be rejected. Its failure, on my view, does not require failures of logical omniscience on the part of the agent, but results from a view of the update as _mighty_: as encoding what the agent learns might be the case, as well as what must be. (...) The view is motivated by consideration of a puzzle case, obtained by transposing into the context of belief revision a kind of scenario that Kit Fine has used to argue against intensionalism about counterfactuals. Employing the framework of truthmaker semantics, I go on to develop a novel account of belief revision, based on a conception of the update as mighty, which validates natural hyperintensional counterparts of the usual AGM postulates. (shrink)

Belief merging aims at combining several pieces of information coming from different sources. In this paper we review the works on belief merging of propositional bases. We discuss the relationship between merging, revision, update and confluence, and some links between belief merging and social choice theory. Finally we mention the main generalizations of these works in other logical frameworks.

We propose in this paper a new family of belief merging operators, that is based on a game between sources : until a coherent set of sources is reached, at each round a contest is organized to find out the weakest sources, then those sources has to concede. This idea leads to numerous new interesting operators and opens new perspectives for belief merging. Some existing operators are also recovered as particular cases. Those operators can be seen as a special case (...) of Booth's Belief Negotiation Models [BOO 02], but the achieved restriction forms a consistent family of merging operators that worths to be studied on its own. (shrink)

ABSTRACT We consider in this work the problem of iterated belief revision. We propose a family of belief revision operators called revision with memory operators and we give a logical (both syntactical and semantical) characterization of these operators. They obey what we call the principle of strong primacy of update: when one revises his beliefs by a new evidence, then all possible worlds that satisfy this new evidence become more reliable than those that do not. We show that those operators (...) have a satisfying behaviour concerning the iteration of the revision process. Then we provide four particular operators of this family. (shrink)

The idea of preserving conditional beliefs emerged recently as a new paradigm apt to guide the revision of epistemic states. Conditionals are substantially different from propositional beliefs and need specific treatment. In this paper, we present a new approach to conditionals, capturing particularly well their dynamic part as revision policies. We thoroughly axiomatize a principle of conditional preservation as an indifference property with respect to conditional structures of worlds. This principle is developed in a semi-quantitative setting, so as to reveal (...) its fundamental meaning for belief revision in quantitative as well as in qualitative frameworks. In fact, it is shown to cover other proposed approaches to conditional preservation. (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)

When a group of agents attempts to reach an agreement on certain issues, it is usually desirable that the resulting consensus be as close as possible to the original judgments of the individuals. However, when these judgments are logically connected to further beliefs, the notion of closeness should also take into account to what extent the individuals would have to revise their entire belief set to reach an agreement. In this work, we present a model for generation of agreement with (...) respect to a given agenda which allows individual epistemic entrenchment to influence the value of the consensus. While the postulates for the transformation function and their construction resemble those of AGM belief revision, the notion of an agenda is adapted from the theory of judgment aggregation. This allows our model to connect both frameworks. (shrink)

A number of seminal papers on the logic of belief change by Alchourrön, Gärden-fors, and Makinson have given rise to what is now known as the AGM paradigm. The present discussion note is a response to Neil Tennant's [1994], which aims at a critical appraisal of the AGM approach and the introduction of an alternative approach. We show that important parts of Tennants's critical remarks are based on misunderstandings or on lack of information. In the course of doing this, we (...) attend to some central philosophical issues in the theory of belief change, such as the choice of a representation for belief states and the meaning of an idealized rational agent. (shrink)

While the theory of belief change has attracted a lot of interest from researchers, work on implementing belief change and actually putting it to use in real-world problems is still scarce. In this paper, we present an implementation of propositional belief change using Binary Decision Diagrams. Upper complexity bounds for the algorithm are presented and discussed. The approach is presented both in the general case, as well as on specific belief change operators from the literature. In an effort to gain (...) a better understanding of the empirical efficiency of the algorithms involved, a fault diagnosis problem on combinational circuits is presented, implemented and evaluated. (shrink)

The semantics for counterfactuals due to David Lewis has been challenged by appealing to miracles. Miracles may skew a given similarity order in favour of those possible worlds which exhibit them. Lewis responded with a system of priorities that mitigates the significance of miracles when constructing similarity relations. We propose a prioritised ceteris paribus analysis of counterfactuals inspired by Lewis’ system of priorities. By analysing the couterfactuals with a ceteris paribus clause one forces out, in a natural manner, those possible (...) worlds which do not satisfy the requirements of the clause, thus excluding miracles. If no world can satisfy the ceteris paribus clause in its entirety, then prioritisation is triggered to select worlds that maximise agreement on those things which are favoured most. (shrink)

In this article, we propose a belief revision approach for families of (non-classical) logics whose semantics are first-order axiomatisable. Given any such (non-classical) logic , the approach enables the definition of belief revision operators for , in terms of a belief revision operation satisfying the postulates for revision theory proposed by Alchourrrdenfors and Makinson (AGM revision, Alchourrukasiewicz's many-valued logic. In addition, we present a general methodology to translate algebraic logics into classical logic. For the examples provided, we analyse in what (...) circumstances the properties of the AGM revision are preserved and discuss the advantages of the approach from both theoretical and practical viewpoints. (shrink)