Revisions of knowledge systems using epistemic entrenchment

TLDR

Revising a knowledge system when new information conflicts with existing knowledge, and contracting by removing information, are major challenges in knowledge representation. The study tackles modelling revisions and contractions through two complementary approaches. The authors introduce rationality postulates for revisions and contractions and a constructive method that orders epistemic entrenchments via computationally tractable constraints. They prove a natural correspondence between revisions and contractions, establish a representation theorem linking postulates to entrenchment orderings, and show that the required ordering can be determined with linear information in the number of atomic facts.

Abstract

A major problem for knowledge representation is how to revise a knowledge system in the light of new information that is inconsistent with what is already in the system. Another related problem is that of contractions, where some of the information in the knowledge system is taken away. Here, the problems of modelling revisions and contractions are attacked in two ways. First, two sets of rationality postulates or integrity constraints are presented, one for revisions and one for contractions. On the basis of these postulates it is shown that there is a natural correspondence between revisions and contractions. Second, a more constructive approach is adopted based on the of the facts in a knowledge system which determines their priority in revisions and contractions. We introduce a set of computationally tractable constraints for an ordering of epistemic entrenchments. The key result is a representation theorem which says that a revision method for a knowledge system satisfies the set of rationality postulates, if and only if, there exists an ordering of epistemic entrenchment satisfying the appropriate constraints such that this ordering determines the retraction priority of the facts of the knowledge system. We also prove that the amount of information needed to uniquely determine the required ordering is linear in the number of atomic facts of the knowledge system.