Belief change studies how to update knowledge bases used for reasoning. Traditionally belief revision has been based on full propositional logic. However, reasoning with full propositional knowledge bases is computationally hard, whereas reasoning with Horn knowledge bases is fast. In the past several years, there has been considerable work in belief revision theory on developing a theory of belief contraction for knowledge represented in Horn form. Our main focus here is the computational complexity of belief contraction, and, in particular, of various methods and approaches suggested in the literature.

In this paper, we address the problem of applying AGM-style belief revision to non-classical logics. We discuss the idea of minimal change in revision and show that for non-classical logics, some sort of minimality postulate has to be explicitly introduced. We also present two constructions for revision which satisfy the AGM postulates and prove the representation theorems including minimality postulates.

Belief revision is an operation that aims at modifying old beliefs so that they become consistent with new ones. The issue of belief revision has been studied in various formalisms, in particular, in qualitative algebras (QAs) in which the result is a disjunction of belief bases that is not necessarily representable in a QA. This motivates the study of belief revision in formalisms extending QAs, namely, their propositional closures: in such a closure, the result of belief revision belongs to the formalism. Moreover, this makes it possible to define a contraction operator thanks to the Harper identity. Belief revision in the propositional closure of QAs is studied, an algorithm for a family of revision operators is designed, and an open-source implementation is made freely available on the web.

In this paper we develop a general framework that allows for both knowledge acquisition and forgetting in the Situation Calculus. Based on the Scherl and Levesque (Scherl and Levesque 1993) possible worlds approach to knowledge in the Situation Calculus, we allow for both sensing as well as explicit forgetting actions. This model of forgetting is then compared to existing frameworks. In particular we show that forgetting is well-behaved with respect to the contraction operator of the well-known AGM theory of belief revision (Alchourron, Gardenfors, and Makinson 1985) but that knowledge forgetting is distinct from the more commonly known notion of logical forgetting (Lin and Reiter 1994).

A central result in the AGM framework for belief revision is the construction of revisionfunctions in terms of total preorders on possible worlds. These preorders encode comparative plausibility: r r' states that the world r is at least as plausible as r'. Indifference in the plausibility of two worlds, r, r', denoted r r', is defined as the absence of a preference between r and r'. Herein we take a closer look at plausibility indifference. We contend that the transitivity of indifference assumed in the AGM framework is not always a desirable property for comparative plausibility. Our argument originates from similar concerns in preference modelling, where a structure weaker than a total preorder, called a semiorder, is widely consider to be a more adequate model of preference.

A strong intuition for AGM belief change operations, Gärdenfors suggests, is that formulas that are independent of a change should remain intact. Based on this intuition, Fariñas and Herzig axiomatize a dependence relation w.r.t. a belief set, and formalize the connection between dependence and belief change. In this paper, we introduce base dependence as a relation between formulas w.r.t. a belief base. After an axiomatization of base dependence, we formalize the connection between base dependence and a particular belief base change operation, saturated kernel contraction. Moreover, we prove that base dependence is a reversible generalization of Fariñas and Herzig's dependence. That is, in the special case when the underlying belief base is deductively closed (i.e., it is a belief set), base dependence reduces to dependence. Finally, an intriguing feature of Fariñas and Herzig's formalism is that it meets other criteria for dependence, namely, Keynes' conjunction criterion for dependence (CCD) and Gärdenfors' conjunction criterion for independence (CCI). We show that our base dependence formalism also meets these criteria. More interestingly, we offer a more specific criterion that implies both CCD and CCI, and show our base dependence formalism also meets this new criterion.

In this paper, we investigate the revision of argumentation systems à la Dung. We focus on revision as minimal change of the arguments status. Contrarily to most of the previous works on the topic, the addition of new arguments is not allowed in the revision process, so that the revised system has to be obtained by modifying the attack relation only. We introduce a language of revision formulae which is expressive enough for enabling the representation of complex conditions on the acceptability of arguments in the revised system. We show how AGM belief revision postulates can be translated to the case of argumentation systems. We provide a corresponding representation theorem in terms of minimal change of the arguments statuses. Several distance-based revision operators satisfying the postulates are also pointed out, along with some methods to build revised argumentation systems. We also discuss some computational aspects of those methods.

This paper tackles the problem of evaluating the degree of inconsistency in spatial and temporal qualitative reasoning. We first introduce postulates to propose a formal framework for measuring inconsistency in this context. Then, we provide two inconsistency measures that can be useful in various AI applications. The first one is based on the number of constraints that we need to relax to get a consistent qualitative constraint network. The second inconsistency measure is based on variable restrictions to restore consistency. It is defined from the minimum number of variables that we need to ignore to recover consistency. We show that our proposed measures satisfy required postulates and other appropriate properties. Finally, we discuss the impact of our inconsistency measures on belief merging in qualitative reasoning.

Formalizing dynamics of argumentation has received increasing attention over the last years. While AGM-like representation results for revision of argumentation frameworks (AFs) are now available, similar results for the problem of merging are still missing. In this paper, we close this gap and adapt model-based propositional belief merging to define extension-based merging operators for AFs. We state an axiomatic and a constructive characterization of merging operators through a family of rationality postulates and a representation theorem. Then we exhibit merging operators which satisfy the postulates. In contrast to the case of revision, we observe that obtaining a single framework as result of merging turns out to be a more subtle issue. Finally, we establish links between our new results and previous approaches to merging of AFs, which mainly relied on axioms from Social Choice Theory, but lacked AGM-like representation theorems.

Belief propagation over Markov random fields has been successfully used in many AI applications since it yields accurate inference results by iteratively updating messages between nodes. However, its high computation costs are a barrier to practical use. This paper presents an efficient approach to belief propagation. Our approach, Quiet, dynamically detects converged messages to skip unnecessary updates in each iteration while it theoretically guarantees to output the same results as the standard approach used to implement belief propagation. Experiments show that our approach is significantly faster than existing approaches without sacrificing inference quality.