| The topic of the dissertation is revision programming. It is a knowledge representation formalism 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 constraint. 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 program. 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 correspond to existing extensions of logic programming. More specific, a disjunctive and a nested versions of revision programming were introduced.; Also, we studied annotated revision programs, which allow annotations like confidence factors, multiple experts, etc. Annotations were assumed to be elements of a complete infinitely distributive lattice. We proposed a justified revisions semantics for annotated revision programs which agreed with intuitions.; Next, we introduced definitions of well-founded semantics for revision programming. It assigns to a revision problem a single “intended” model which is computable in polynomial time.; Finally, we extended syntax of revision problems by allowing variables and implemented translators of revision programs into logic programs and a grounder for revision programs. The implementation allows us to compute justified revisions using existing implementations of the stable model semantics for logic programs. |
