Paper #30

Author(s): Natasha Alechina, Mark Jago, and Brian Logan

Title: Resource-bounded Belief Revision and Contraction

Abstract: In this paper, we show that a resource-bounded agent capable of revising its beliefs in time polynomial in the size of the agen's state and program performs rational belief contraction as characterised by the AGM postulates. We present an algorithm for belief contraction and prove that the corresponding operator satisfies all but one of the basic AGM postulates. We show how to extend our approach to allow contraction by minimally entrenched beliefs, and how to recompute the entrenchment order efficiently. We discuss the problem of defining belief revision in terms of contraction for a resource-bounded agent, and give a definition of revision which can also be performed in polynomial time and satisfies all but one basic AGM postulates for belief revision.

Download: PDF