Annotated Revision Programs: A Study on the Consistency of Belief Updates

Title: Annotated Revision Programs: A Study on the Consistency of Belief Updates

Abstract: This research article explores the concept of annotated revision programs, which are used to describe and enforce updates of belief sets and databases. Annotations provide a way to quantify the confidence (or probability) that a revision atom holds. The main goal of the paper is to reexamine the work of Fitting, argue that his semantics do not always provide results consistent with intuition, and to propose an alternative treatment of annotated revision programs. The approach differs from Fitting's in two key aspects: the definition of a model of a program and the definition of a justified revision. The paper shows that fundamental properties of justified revisions of standard revision programs extend to the annotated case under this new approach.

Keywords: Knowledge representation, database updates, belief revision, revision programming, annotated programs

Introduction: Revision programming is a formalism used to specify and enforce constraints on databases, belief sets, and, more generally, on arbitrary sets. It was introduced and studied in [MT95, MT98]. The formalism was found to be closely related to logic programming with stable model semantics [MT98, PT97]. In [MPT99], a simple correspondence of revision programming with the general logic programming system of Liufschitz and Woo [LW92] was discovered. Roots of another recent formalism of dynamic logic programming [ALP+98] can also be traced back to revision programming.

The research article discusses the extension of revision programming to the case of annotated revision programs, where revision atoms are assigned annotations. These annotations can be interpreted as the degree of confidence that a revision atom holds. The paper defines annotated revision programs, justified revisions of a database by an annotated revision program, and studies properties of these notions.

The paper argues that Fitting's semantics do not always provide results consistent with intuition and proposes an alternative treatment. The approach changes the notion of a model of a program and the notion of a justified revision. It shows that fundamental properties of justified revisions of standard revision programs extend to the annotated case under this new approach.

Implications: The research has implications for knowledge representation, database updates, and belief revision. It provides a more accurate and flexible way to model situations where membership status of atoms is not precisely known, and constraints reflect this imprecise knowledge. The use of annotations allows for a broader range of intuitions to be captured within a single algebraic formalism.

Link to Article: https://arxiv.org/abs/0107026v1 Authors: arXiv ID: 0107026v1