A framework for comparison of update semantics

Abstract

Scattered across the scientific literature of three or more disciplines appears a profusion of proposals for semantics of updates to logical theories. Because no previous work has compared these proposals with one another, the merits and demerits of the various approaches are not well known. Since the semantics differ from one another in systematic ways, it is possible to generalize from existing proposals and speak of the properties of classes of update semantics. In this paper we suggest a two-dimensional taxonomy for characterizing semantics, and describe the properties inherent to the classes implicit therein. Our discussion includes measurement of the computational complexity of the different classes.