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)

One of the standard principles of rationality guiding traditional accounts of belief change is the principle of minimal change: a reasoner's belief corpus should be modified in a minimal fashion when assimilating new information. This rationality principle has stood belief change in good stead. However, it does not deal properly with all belief change scenarios. We introduce a novel account of belief change motivated by one of Grice's maxims of conversational implicature: the reasoner's belief corpus is modified in a minimal (...) fashion to assimilate exactly the new information. In this form of belief change, when the reasoner revises by new information p ∨ q their belief corpus is modified so that p∨q is believed but stronger propositions like p∧q are not, no matter what beliefs are in the reasoner's initial corpus. We term this conservative belief change since the revised belief corpus is a conservative extension of the original belief corpus given the new information. (shrink)

This paper describes an approach for reasoning in a dynamic domain with nondeterministic actions in which an agent’s beliefs correspond to the simplest, or most plausible, course of events consistent with the agent’s observations and beliefs. The account is based on an epistemic extension of the situation calculus, a first-order theory of reasoning about action that accommodates sensing actions. In particular, the account is based on a qualitative theory of nondeterminism. Our position is that for commonsense reasoning, the world is (...) most usefully regarded as deterministic, and that nondeterminism is an epistemic phenomenon, arising from an agent’s limited awareness and perception. The account offers several advantages: an agent has a set of categorical beliefs, yet can deal with equally-likely outcomes or with outcomes of differing plausibility. The agent maintains as its set of contingent beliefs the most plausible, or simplest, picture of the world, consistent with its beliefs and actions it believes it executed; yet it may modify these in light of later information. (shrink)

The problem of knowledge evolution has received considerable attention over the years. Mainly, the study of the dynamics of knowledge has been addressed in the area of Belief Revision, a field emerging as the convergence of the efforts in Philosophy, Logic, and more recently Computer Science, where research efforts usually involve “flat” knowledge bases where there is no additional information about the formulas stored in it. Even when this may be a good fit for particular applications, in many real-world scenarios (...) different information items may be attached to formulas. For instance, when the reliability of the source of the piece of information is attached to it as a measure of some quality (e.g., strength) of the piece of information itself, or when some characteristic informs us on the desirability of the item (e.g., the potential benefit that could be obtained from it). If this type of information is available, we can use it to guide how the belief base is to be modified when new information arrives. In this work, we present a novel approach to the contraction of knowledge bases where formulas have values attached that measure some quality linked to those formulas, exploiting it to define their desirability, and uses such desirability to define which formulas need to be removed to solve conflicts. In this context, we introduce a set of properties for contraction operators by extending classic approaches. We also show how the local treatment of minimal conflicts can induce some counter-intuitive contractions, and we present a way to avoid them by considering optimal resolutions of conflicts using the additional information encoded. We show how the proposed formalization captures any contraction that is optimal under a set of features. Finally, we present a refinement based on the identification of related minimal conflicts that performs contraction in optimal ways without looking into the entire knowledge base. The approach is based on the use of the accrual of beliefs where several formulas collaboratively use their respective values to prevail in the resolution of conflicts. (shrink)

We show in this paper that the AGM postulates are too weak to ensure the rational preservation of conditional beliefs during belief revision, thus permitting improper responses to sequences of observations. We remedy this weakness by proposing four additional postulates, which are sound relative to a qualitative version of probabilistic conditioning. Contrary to the AGM framework, the proposed postulates characterize belief revision as a process which may depend on elements of an epistemic state that are not necessarily captured by a (...) belief set. We also show that a simple modification to the AGM framework can allow belief revision to be a function of epistemic states. We establish a model-based representation theorem which characterizes the proposed postulates and constrains, in turn, the way in which entrenchment orderings may be transformed under iterated belief revision. (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)

After a number of decades of research into the dynamics of rational belief, the belief revision theory community remains split on the appropriate handling of sequences of changes in view, the issue of so-called iterated revision. It has long been suggested that the matter is at least partly settled by facts pertaining to the results of various single revisions of one’s initial state of belief. Recent work has pushed this thesis further, offering various strong principles that ultimately result in a (...) wholesale reduction of iterated to one-shot revision. The present paper offers grounds to hold that these principles should be significantly weakened and that the reductionist thesis should ultimately be rejected. Furthermore, the considerations provided suggest a close connection between the logic of iterated belief change and the logic of evidential relevance. (shrink)

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)

This paper is about the situation in which an author (writer or speaker) presents a deductively invalid argument, but the addressee aims at a charitable interpretation and has reason to assume that the author intends to present a valid argument. How can he go about interpreting the author’s reasoning as enthymematically valid? We suggest replacing the usual find-the-missing-premise approaches by an approach based on systematic efforts to ascribe a belief state to the author against the background of which the argument (...) has to be evaluated. The suggested procedure includes rules for recording whether the author in fact accepts or denies the premises and the conclusion, as well as tests for enthymematic validity and strategies for revising belief state ascriptions. Different degrees of interpretive charity can be exercised. This is one reason why the interpretation or reconstruction of an enthymematic argument typically does not result in a unique outcome. (shrink)

Modal accounts of normality in non-monotonic reasoning traditionally have an underlying semantics based on a notion of preference amongst worlds. In this paper, we motivate and investigate an alternative semantics, based on ordered accessibility relations in Kripke frames. The underlying intuition is that some world tuples may be seen as more normal, while others may be seen as more exceptional. We show that this delivers an elegant and intuitive semantic construction, which gives a new perspective on defeasible necessity. Technically, the (...) revisited logic does not change the expressive power of our previously defined preferential modalities. This conclusion follows from an analysis of both semantic constructions via a generalisation of bisimulations to the preferential case. Reasoners based on the previous semantics therefore also suffice for reasoning over the new semantics. We complete the picture by investigating different notions of defeasible conditionals in modal logic that can also be captured within our framework. (shrink)

Most approaches to iterated belief revision are accompanied by some motivation for the use of the proposed revision operator (or family of operators), and typically encode enough information in the epistemic state of an agent for uniquely determining one-step revision. But in those approaches describing a family of operators there is usually little indication of how to proceed uniquely after the first revision step. In this paper we contribute towards addressing that deficiency by providing a formal framework which goes beyond (...) the first revision step in two ways. First, the framework is obtained by enriching the epistemic state of an agent starting from the following intuitive idea: we associate to each world x two abstract objects x⁺ and x⁻, and we assume that, in addition to preferences over the set of worlds, we are given preferences over this set of objects as well. The latter can be considered as meta-information encoded in the epistemic state which enables us to go beyond the first revision step of the revision operator being applied, and to obtain a unique set of preferences over worlds. We then extend this framework to consider, not only the revision of preferences over worlds, but also the revision of this extended structure itself. We look at some desirable properties for revising the structure and prove the consistency of these properties by giving a concrete operator satisfying all of them. Perhaps more importantly, we show that this framework has strong connections with two other types of constructions in related areas. Firstly, it can be seen as a special case of preference aggregation which opens up the possibility of extending the frame-work presented here into a full-fledged framework for preference aggregation and social choice theory. Secondly, it is related to existing work on the use of interval orderings in a number of different contexts. (shrink)

Most belief change operators in the AGM tradition assume an underlying plausibility ordering over the possible worlds which is transitive and complete. A unifying structure for these operators, based on supplementing the plausibility ordering with a second, guiding, relation over the worlds was presented in Booth et al. (Artif Intell 174:1339-1368, 2010). However it is not always reasonable to assume completeness of the underlying ordering. In this paper we generalise the structure of Booth et al. (Artif Intell 174: 1339-1368, 2010) (...) to allow incomparabilities between worlds. We axiomatise the resulting class of belief removal functions, and show that it includes an important family of removal functions based on finite prioritised belief bases. (shrink)

We establish a correspondence between the rationalizability of choice studied in the revealed preference literature and the notion of minimal belief revision captured by the AGM postulates. A choice frame consists of a set of alternatives , a collection E of subsets of (representing possible choice sets) and a function f : E ! 2 (representing choices made). A choice frame is rationalizable if there exists a total pre-order R on..

In an earlier paper [Rational choice and AGM belief revision, _Artificial Intelligence_, 2009] a correspondence was established between the set-theoretic structures of revealed-preference theory (developed in economics) and the syntactic belief revision functions of the AGM theory (developed in philosophy and computer science). In this paper we extend the re-interpretation of those structures in terms of one-shot belief revision by relating them to the trichotomous attitude towards information studied in Garapa (Rev Symb Logic, 1–21, 2020) where information may be either (...) (1) fully accepted or (2) rejected or (3) taken seriously but not fully accepted. We begin by introducing the syntactic notion of _filtered belief revision_ and providing a characterization of it in terms of a mixture of both AGM revision and contraction. We then establish a correspondence between the proposed notion of filtered belief revision and the above-mentioned set-theoretic structures, interpreted as semantic _partial_ belief revision structures. We also provide an interpretation of the trichotomous attitude towards information in terms of the degree of implausibility of the information. (shrink)

Since belief revision deals with the interaction of belief and information over time, branching-time temporal logic seems a natural setting for a theory of belief change. We propose two extensions of a modal logic that, besides the next-time temporal operator, contains a belief operator and an information operator. The first logic is shown to provide an axiomatic characterization of the first six postulates of the AGM theory of belief revision, while the second, stronger, logic provides an axiomatic characterization of the (...) full set of AGM postulates. © 2006 Elsevier B.V. All rights reserved. (shrink)

Dung’s argumentation frameworks have been applied for over twenty years to the analysis of argument justification. This representation focuses on arguments and the attacks among them, abstracting away from other features like the internal structure of arguments, the nature of utterers, the specifics of the attack relation, etc. The model is highly attractive because it reduces most of the complexities involved in argumentation processes. It can be applied to different settings, like the argument evaluation of an individual agent or the (...) case of dialectic disputes between two agents (pro and con), or even in multi-agent collective argumentation. The latter case involves agents with possibly different arguments and/or opinions on how to evaluate them, leading to the possibility of considering multiple sets of arguments and attack relations. Two basic questions can be asked here, namely ‘what to aggregate’ and ‘how to aggregate’. The former concerns what kinds of entities do the agents intend to choose (arguments, attacks, assessments, etc.), while the second one focuses on which aggregation mechanisms yield rational choices (voting on arguments, merging procedures to obtain a common argumentation framework, deliberation processes, etc.). In particular, the question about the rationality of a collective argument choice relates this topic to Social Choice and Judgment Aggregation theories, while its associated strategic issues relate it to Game Theory. The research efforts on the disparate problems elicited by collective argumentation have generated a considerable corpus of literature that deserves an orderly evaluation. This survey is intended as a contribution to that end. (shrink)

Several tasks in artificial intelligence require the ability to find models about knowledge dynamics. They include belief revision, fusion and belief merging, and abduction. In this paper, we exploit the algebraic framework of mathematical morphology in the context of propositional logic and define operations such as dilation or erosion of a set of formulas. We derive concrete operators, based on a semantic approach, that have an intuitive interpretation and that are formally well behaved, to perform revision, fusion and abduction. Computation (...) and tractability are addressed, and simple examples illustrate the main results. (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)

Dynamic Epistemic Logic (DEL) deals with the representation and the study in a multi-agent setting of knowledge and belief change. It can express in a uniform way epistemic statements about: 1. what is true about an initial situation 2. what is true about an event occurring in this situation 3. what is true about the resulting situation after the event has occurred. We axiomatize within the DEL framework what we can infer about (iii) given (i) and (ii). Given three formulas (...) φ,φ' and φ" describing respectively (i), (ii) and (iii), we also show how to build a formula φ ? φ' which captures all the information which can be inferred about (iii) from φ and φ'. We show how our results extend to other modal logics than K. In our proofs and definitions, we resort to a large extent to the normal form formulas for modal logic originally introduced by Kit Fine. In a companion paper (Aucher, 2012), we axiomatize what we can infer about (ii) given (i) and (iii), and what we can infer about (i) given (ii) and (iii), and show how to build two formulas φ ? φ" and φ' ? φ" which capture respectively all the information which can be inferred about (ii) from φ and φ", and all the information which can be inferred about (i) from φ' and φ". (shrink)

Belief Revision is a well-established field of research that deals with how agents rationally change their minds in the face of new information. The milestone of Belief Revision is a general and versatile formal framework introduced by Alchourrón, Gärdenfors and Makinson, known as the AGM paradigm, which has been, to this date, the dominant model within the field. A main shortcoming of the AGM paradigm, as originally proposed, is its lack of any guidelines for relevant change. To remedy this weakness, (...) Parikh proposed a relevance-sensitive axiom, which applies on splittable theories; i.e., theories that can be divided into syntax-disjoint compartments. The aim of this article is to provide an epistemological interpretation of the dynamics of splittable theories, from the perspective of Kuhn's inuential work on the evolution of scientific knowledge, through the consideration of principal belief-change scenarios. The whole study establishes a conceptual bridge between rational belief revision and traditional philosophy of science, which sheds light on the application of formal epistemological tools on the dynamics of knowledge. (shrink)

The process [by which any individual settles into new opinions] is always the same. The individual has a stock of old opinions already, but he meets a new experience that puts them to a strain…. The result is an inward trouble to which his mind till then had been a stranger, and from which he seeks to escape by modifying his previous mass of opinions. He saves as much of it as he can, for in this matter of belief we (...) are all extreme conservatives. So he tries to change first this opinion, and then that (for they resist change very variously), until at last some new idea comes up which he can graft upon the ancient stock with a minimum of disturbance of the latter, some idea that mediates between the stock and the new experience and runs them into one most felicitously and expediently.The new idea is then adopted as the true one. It preserves the older stock of truths with a minimum of modification, stretching them just enough to make them admit the novelty, but conceiving that in ways as familiar as the case leaves possible. (William James, Lectures on Pragmatism, 1907). (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)

Belief revision (BR) and truthlikeness (TL) emerged independently as two research programmes in formal methodology in the 1970s. A natural way of connecting BR and TL is to ask under what conditions the revision of a belief system by new input information leads the system towards the truth. It turns out that, for the AGM model of belief revision, the only safe case is the expansion of true beliefs by true input, but this is not very interesting or realistic as (...) a model of theory change in science. The new accounts of non-prioritized belief revision do not seem more promising in this respect, and the alternative BR account of updating by imaging leads to other problems. Still, positive results about increasing truthlikeness by belief revision may be sought by restricting attention to special kinds of theories. Another approach is to link truthlikeness to epistemic matters by an estimation function which calculates expected degrees of truthlikeness relative to evidence. Then we can study how the expected truthlikeness of a theory changes when probabilities are revised by conditionalization or imaging. Again, we can ask under what conditions such changes lead our best theories towards the truth. (shrink)

Various semantics for studying the square of opposition have been proposed recently. So far, only [14] studied a probabilistic version of the square where the sentences were interpreted by (negated) defaults. We extend this work by interpreting sentences by imprecise (set-valued) probability assessments on a sequence of conditional events. We introduce the acceptability of a sentence within coherence-based probability theory. We analyze the relations of the square in terms of acceptability and show how to construct probabilistic versions of the square (...) of opposition by forming suitable tripartitions. Finally, as an application, we present a new square involving generalized quantifiers. (shrink)

Darwiche and Pearl’s seminal 1997 article outlined a number of baseline principles for a logic of iterated belief revision. These principles, the DP postulates, have been supplemented in a number of alternative ways. Most suggestions have resulted in a form of ‘reductionism’ that identifies belief states with orderings of worlds. However, this position has recently been criticised as being unacceptably strong. Other proposals, such as the popular principle (P), aka ‘Independence’, characteristic of ‘admissible’ operators, remain commendably more modest. In this (...) paper, we supplement the DP postulates and (P) with a number of novel conditions. While the DP postulates constrain the relation between a prior and a posterior conditional belief set, our new principles notably govern the relation between two posterior conditional belief sets obtained from a common prior by different revisions. We show that operators from the resulting family, which subsumes both lexicographic and restrained revision, can be represented as relating belief states associated with a ‘proper ordinal interval’ (POI) assignment, a structure more fine-grained than a simple ordering of worlds. We close the paper by noting that these operators satisfy iterated versions of many AGM era postulates, including Superexpansion, that are not sound for admissible operators in general. (shrink)

The volume analyses and develops David Makinson’s efforts to make classical logic useful outside its most obvious application areas. The book contains chapters that analyse, appraise, or reshape Makinson’s work and chapters that develop themes emerging from his contributions. These are grouped into major areas to which Makinsons has made highly influential contributions and the volume in its entirety is divided into four sections, each devoted to a particular area of logic: belief change, uncertain reasoning, normative systems and the resources (...) of classical logic. Among the contributions included in the volume, one chapter focuses on the “inferential preferential method”, i.e. the combined use of classical logic and mechanisms of preference and choice and provides examples from Makinson’s work in non-monotonic and defeasible reasoning and belief revision. One chapter offers a short autobiography by Makinson which details his discovery of modern logic, his travels across continents and reveals his intellectual encounters and inspirations. The chapter also contains an unusually explicit statement on his views on the role of logic in philosophy. (shrink)

There have been a number of publications in recent years on generalising the AGM paradigm to the Horn fragment of propositional logic. Most of them focused on adapting AGM contraction and revision to the Horn setting. It remains an open question whether the adapted Horn contraction and Horn revision are inter-definable as in the AGM case through the Levi and Harper identities. In this paper, we give a positive answer by providing methods for generating contraction and revision from their dual (...) operations. Noticeably, we cannot apply the Levi and Harper identities directly in such methods as the Horn fragment does not fully support negation. To overcome this difficulty, a Horn approximation technique called Horn strengthening is used. We show that Horn contraction generated from Horn revision is always plausible whereas Horn revision generated from Horn contraction is, in general, implausible and, to regain plausibility, the generating contraction has to be properly restricted. (shrink)

In this paper I propose violation games as the basis of formal logics to represent and reason about norms, i.e. as the foundation of deontic logic. Deontic logic is an applied non-classical logic reflecting a way in which we conceptualize normative reasoning. By introducing violation games as a fundamental principle of deontic logic, I am introducing a new way of looking at familiar problems in normative reasoning, with the aim of introducing a new approach for handling norms in intelligent systems.