ABSTRACT OF DISSERTATION REVISION PROGRAMMING: A KNOWLEDGE REPRESENTATION FORMALISM

The topic of the dissertation is revision programming. It is a knowledge representation for-malism for describing constraints on databases, knowledge bases, and belief sets, and providing a computational mechanism to enforce them. Constraints are represented by sets of revision rules. Revision rules could be quite complex and are usually in a form of conditions (for instance, if these elements are present and those elements are absent, then this element must be absent). In addition to being a logical constraint, a revision rule specify a preferred way to satisfy the con-straint. Justified revisions semantics assigns to any database a set (possibly empty) of revisions. Each revision satisfies the constraints, and all deletions and additions of elements in a transition from initial database to the revision are derived from revision rules. Revision programming and logic programming are closely related. We established an elegant embedding of revision programs into logic programs, which does not increase the size of a pro-gram. Initial database is used in transformation of a revision program into the corresponding logic program, but it is not represented in the logic program. The connection naturally led to extensions of revision programming formalism which corre-spond to existing extensions of logic programming. More specific, a disjunctive and a neste