Ultimate approximations

We present {\em Approximation theory}, an extension of Tarski's least fixpoint theory for nonmonotone operators in lattices. The key notion in our theory is that of an {\em approximating operator} $A$ of an operator $O$ on a lattice $L$. This is a monotone operator on the product lattice $L^2$ whose fixpoints approximate the fixpoints of the operator $O$. With each approximation of $O$, a unique well-founded and a collection of stable models can be associated. We show that by increasing the precision of the approximation of $O$, we augment the set of stable models and the precision of the well-founded fixpoint. In the limit, we obtain for each lattice operator $O$ a unique {\em ultimate well-founded fixpoint} and a collection of {\em ultimate stable fixpoints}. We investigate the properties of this class of fixpoints. We show that this theory extends Tarski's least fixpoint theory in the sense that the ultimate well-founded fixpoint of a monotone operator $O$ is its least fixpoint. The theory provides the algebraic foundations of the semantics of nonmonotonic knowledge representation formalisms, such as logic programming, autoepistemic logic and default logic.nrpages: 23status: publishe