Abstract

This dissertation is a contribution to the study of belief change from both a formal and computational perspective. Theories of belief change address the following general question: Given an initial database $\Gamma$ and a new piece of information $\mu$ to be incorporated into it, what should the new database be? In this study we focus on two specific types of belief change, revision and update. We ground each of them on a solid semantic foundation, and develop syntactic characterizations and algorithms to compute a number of specific belief change operators instantiating these semantics. ;The study is divided into two parts. The first part addresses the foundational aspects of belief change, specifically the definition of appropriate semantics for revision and update operators. We encode belief update in a non-monotonic temporal framework for reasoning about action and change that makes explicit the temporal evolution of the database, and use this framework to show both the applicability and the limits of some of the most important update proposals in the literature. A very similar approach can be used to capture revision. We develop a "mental situation calculus" to encode the agent's beliefs, and capture revision in terms of the effects of learning the new information in a theory of action very similar to the one used for update, and that allows for a unified treatment of both types of belief change within a single formalism. As with update, we show that the most important proposals for revision found in the literature can be captured in our construction. ;Part 2 is devoted to the computation of updates and revisions of knowledge bases under a variety of specific operators, most of which are special cases of the framework developed in part 1. We develop techniques to systematically characterize all the operators considered, and use the resulting syntactic characterizations to design algorithms for revision and update of CNF, NNF and DNF databases. The algorithms for update are the first of their kind which do not need explicit manipulation or storage of complete models of the knowledge base, and its usefulness for updating large knowledge bases is experimentally demonstrated