Belief Change, from AGM to Realistic Models

Andreas Herzig and Renata Wassermann
Section: Logic and Computation
Level: Introductory


Belief revision has been extensively studied during the last twenty years. Given an agent with a set of beliefs, how should he change his beliefs when confronted with new information? An agent may be a human being, a computer program or any kind of system to which one can ascribe beliefs and from which one would expect rational reactions.

The aim of the course is to provide the students a basic background in the existing theories of belief revision and update as well as to give an overview of current research in the area. We will start from the by now standard paradigm for belief revision, due to Alchourrón, Gärdenfors and Makinson (AGM). AGM theory provides good formal results, but it deals with very idealized agents. We will proceed presenting alternatives and refinements that have been proposed in order to model more realistic agents. We will present models that represent the agent's belief state by finite sets of formulas (belief bases) and that deal with limitations of available resources (time, memory, logical ability).

These theories deal with the case where the world has not changed, only the agent got to know more about it. But an agent may also receive new information concerning changes that have occurred in the world. The operation of accommodating such information is called update. Katsuno and Mendelzon have provided a formal analysis of updates. Their approach generalizes several update operations that have been proposed in the field of database theory.

Course Outline

Lecture 1: Standard AGM theory

In this first lecture, we motivate the course by means of examples and introduce the standard theory for belief revision. We present the AGM postulates for revision and contraction and some of the construction that were proposed in the literature. We then discuss the shortcomings of the AGM paradigm as a model for realistic agents.

Lecture 2: Base revision

In the second lecture, we deal with models of belief revision in which the belief state of an agent is represented by a finite set of formulas - a belief base. This has advantages in terms of expressivity and computability. We present several operations for changing belief bases.

Lecture 3: New trends in belief revision

In this lecture, we discuss recent works that address some of the problems found when trying to apply belief revision theory to real problems. One such problem is the limitation in the availability of resources such as memory, time, and logical ability. We present some proposals to solve this problem which involve inconsistency tolerance, approaches based on relevance, and approximate reasoning.

Lecture 4: The theory of update

We discuss the difference between revision and update, and establish the link with conditional logics. We introduce the KM postulates for update, and the construction based on partial preorders. We finally discuss some shortcomings.

Lecture 5: Computational models of update

The last lecture addresses more practical issues of update, including complexity results, decision procedures, and algorithms.


Propositional logic.


[1] Peter Gärdenfors and Hans Rott. Belief revision. In Handbook of Logic in
     Artificial Intelligence and Logic Programming, volume IV, chapter
     4.2. Oxford University Press, 1995.
[2] Sven Ove Hansson. A Textbook of Belief Dynamics. Kluwer Academic Press,
[3] A. Herzig and O. Rifi. Propositional belief base update and minimal
     change.  Artificial Intelligence Journal, dec. 1999.
[4] Andreas Herzig. Logics for belief base updating. Handbook of defeasible
     reasoning and uncertainty management, vol.3 - Belief Change, pages
     189-231. Kluwer Academic Publishers, 1998.
[5] Renata Wassermann. Resource-Bounded Belief Revision. Erkenntnis, 1999.
[6] Renata Wassermann. On Structured Belief Bases. In Frontiers in Belief
     Revision. Kluwer Academic Publishers, 2000.



Andreas Herzig
IRIT - Université Paul Sabatier
118 route de Narbonne
F-31062 Toulouse Cedex 4 (France)
phone: +33 56155-6344
fax: +33 56155-6258

Renata Wassermann
Department of Computer Science
Instituto de Matemáticae Estatística
Universidade de São Paulo
Rua do Matão, 1010
Cidade Universitária
05508-900 São Paulo - SP
phone: +55-11-38186202
fax: +55-11-38186134