A Semantic Theory of Abstractions

Abstract

In this paper we present a semantic theory of abstractions based on viewing abstractions as model level mappings. This theory captures important aspects of abstractions not captured in the syntactic theory of abstractions presented by Giunchiglia and Walsh [1992]. Instead of viewing abstractions as syntactic mappings, we view abstraction as a two step process: first, the intended domain model is abstracted and then a set of (abstract) formulas is constructed to capture the abstracted domain model. Viewing and justifying abstractions as model level mappings is both natural and insightful. This basic theory yields abstractions that are weaker than the base theory. We show that abstractions that are tJtronger than the base theory are model level mappings under certain simplifying auumptions. We provide a precise characterization of the abstract theory that exactly implements an intended abstraction, and show that this theory, while being axiomatizable, is not always finitely axiomatizable. We present an algorithm that automatically constructs the strongest abstract theory that implements the intended abstraction.