Abstract:
In this paper we study fixpoints of operators on
lattices and bilattices in a systematic and principled way. The key
concept is that of an approximating operator, a monotone
operator on the product bilattice, which gives approximate
information on the original operator in an intuitive and well-defined
way. With any given approximating operator our theory associates
several different types of fixpoints, including the Kripke-Kleene
fixpoint, stable fixpoints and the well-founded fixpoint, and relates
them to fixpoints of operators being approximated. Compared to our
earlier work on approximation theory, the contribution of this paper
is that we provide an alternative, more intuitive and better motivated
construction of the well-founded and stable fixpoints. In addition, we
study the space of approximating operators by means of a precision ordering and show that each lattice operator O has a
unique most precise — we call it ultimate —
approximation. We demonstrate that fixpoints of this ultimate
approximation provide useful insights into fixpoints of the operator
O. We then discuss applications of these results in logic
programming.
Published: M. Denecker, V. Marek, en M. Truszczynski, Ultimate approximation and its application in nonmonotonic knowledge representation systems, Information and Computation 192 (1), pp. 84-121, 2004.