Anytime Belief Revision

Abstract

Belief Revision is a ubiquitous process underlying many forms of intelligent behaviour. The AGM paradigm is a powerful framework for modeling and implementing belief revision systems based on the principle of Minimal Change; it provides a rich and rigorous foundation for computer-based belief revision architectures. Maxi-adjustment is a belief revision strategy for theory bases that can be implemented using a standard theorem prover, and one that has been used successfully for several applications. In this paper we provide an anyt i me decision procedure for maxi-adjustments, and study its complexity. FUrthermore, we outline a set of guidelines that serve as a protomethodology for building belief revision systems employing a maxi-adjustment . The algorithm is under development in the belief revision module of the CIN Project .