Craig Boutilier, Moisés Goldszmidt
Both the dynamics of belief change and the process of reasoning by default can be based on the conditional belief set of an agent, represented as a set of "if-then" rules. In this paper we address the open problem of formalizing the dynamics of revising this conditional belief set by new if-then rules, be they interpreted as new default rules or new revision policies. We start by providing a purely semantic characterization, based on the semantics of conditional rules, which induces logical constraints on any such revision process. We then introduce logical (syntax-independent) and syntax-dependent techniques, and provide a precise characterization of the set of conditionals that hold after the revision. In addition to formalizing the dynamics of revising a default knowledge base, this work also provides some of the necessary formal tools for establishing the truth of nested conditionals, and attacking the problem of learning new defaults.