Iterated Belief Revision: A Computational Approach
Yi Jin, Michael Thielscher · 2005
The capability of revising its beliefs upon new information in a rational and ecien t way is crucial for an intelligent agent. The classic AGM theory studies mathematically idealized models of belief revision in two aspects: the properties (i.e., the AGM postulates) a rational re- vision operator should satisfy; and how to construct concrete revision operators. In scenarios where new information arrives in sequence, ratio- nal revision operators should also respect postulates for iterated revision (e.g., the DP postulates). When applications are concerned, the idealiza- tion of the AGM theory has to be lifted, in particular, beliefs of an agent should be represented by a nite belief base. In this paper, we present a computational base revision operator, which satises the AGM pos- tulates and postulates for iterated revision. We will show that our base revision operator is almost optimal in terms of computational complex- ity. Furthermore, the base revision operator's degrees of syntax relevance and minimal change are also formally analyzed.