The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper (Friedman & Halpern, 1997), we introduce a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the change of beliefs over time. In this paper, we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method, and to better understand the principles underlying them. In particular, it shows that Katsuno and Mendelzon's notion of belief update (Katsuno & Mendelzon, 1991a) depends on several strong assumptions that may limit its applicability in artificial intelligence. Finally, our analysis allow us to identify a notion of minimal change that underlies a broad range of belief change operations including revision and update.

Starting with a likelihood or preference order on worlds, we extend it to a likelihood ordering on sets of worlds in a natural way, and examine the resulting logic. Lewis earlier considered such a notion of relative likelihood in the context of studying counterfactuals, but he assumed a total preference order on worlds. Complications arise when examining partial orders that are not present for total orders. There are subtleties involving the exact approach to lifting the order on worlds to an order on sets of worlds. In addition, the axiomatization of the logic of relative likelihood in the case of partial orders gives insight into the connection between relative likelihood and default reasoning.

What criteria should be used to select one semantic formalism over another? However, the scope of analyze and gain insight into (that is, models for circumscription, perfect convergence results linking aspects of not just model) such a task. Although much basic problems are NP hard (at best). Ginsberg and Hugh Holbrook work remains to be done, the consensus His point was that just confirming (Stanford University) showed seems to be that there is sufficient that this problem is indeed potentially that default reasoning could be used common ground to warrant serious nasty is not really surprising. Marco Cadoli and as well as to somehow cope with the significant computational advantages.

Truth maintenance is a collection of techniques for doing belief revision. A truth maintenance system's task is to maintain a set of beliefs in such a way that they are not known to be contradictory and no belief is kept without a reason. Truth maintenance systems were introduced in the late seventies by Jon Doyle and in the last five years there has been an explosion of interest in this kind of systems. In this paper we present an annotated bibliography to the literature of truth maintenance systems, grouping the works referenced according to several classifications.

Truth maintenance is a collection of techniques for doing belief revision. A truth maintenance system's task is to maintain a set of beliefs in such a way that they are not known to be contradictory and no belief is kept without a reason. Truth maintenance systems were introduced in the late seventies by Jon Doyle and in the last five years there has been an explosion of interest in this kind of systems. In this paper we present an annotated bibliography to the literature of truth maintenance systems, grouping the works referenced according to several classifications.

Co-winner of The 2005 AAAI Classic Paper Awards. Summary of Significance by Hector Levesque. Proc. AAAI-86

Raymond Reiter' Department of Computer Science University of Toronto Toronto, Ontario, Canada M5S-1A4 Johan de Kleer Intelligent Systems Laboratory XEROX Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304 ABSTRACT In this paper we (1) define the concept of a Clause Managetnent System (CMS) A Problem-Solving Architecture Figure 1 illustrates an architecture for a problem solving system consisting of a domain dependent Reasoner coupled to a domain independent Clause Management System (CMS). For our present purposes, the Reasoner is a black box which, m the process of doing whatever it does, occasionally transmits a propositional clause 2 to the CMS.

Proceedings of AAAI-84.

The first is to have an adequate model of the cognitive state of other agents. The second is to form plans under the constraint of resource limitations: i.e., an agent does not always have an infinite amount of time to sit and think of plans while the world changes under him; he must act. These two problems are obviously interlinked since, to have a realistic model of the cognitive states of other agents, who are presumably similar to himself, an agent must reason about the resource limitations they are subject to in reasoning about the world. In this paper we address both problems with reference to AI planning system robots and one part of their cognitive state, namely beliefs. Our goal is to pursue what might be called robot psychology: to construct a plausible model of robot beliefs by examining robots' internal representations of the world.

In Proceedings of the Eighth IJCAI, pages 272-279. IJCAI, Karlsruhe, West Germany, August, 1983. Volume 1.