Date Available


Year of Publication


Document Type





Computer Science

First Advisor

Victor Marek

Second Advisor

Mirosław Truszczy´nski


The topic of the dissertation is revision programming. It is a knowledge representation formalismfor describing constraints on databases, knowledge bases, and belief sets, and providing acomputational 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, ifthese elements are present and those elements are absent, then this element must be absent). Inaddition 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 transitionfrom initial database to the revision are derived from revision rules.Revision programming and logic programming are closely related. We established an elegantembedding 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 logicprogram, but it is not represented in the logic program.The connection naturally led to extensions of revision programming formalism which correspondto existing extensions of logic programming. More specific, a disjunctive and a nestedversions 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 distributivelattice. We proposed a justified revisions semantics for annotated revision programs which agreedwith intuitions.Next, we introduced definitions of well-founded semantics for revision programming. It assignsto 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 translatorsof revision programs into logic programs and a grounder for revision programs. The implementationallows us to compute justified revisions using existing implementations of the stablemodel semantics for logic programs.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.