Making abstract interpretations complete

Completeness in abstract interpretation is an ideal situation where the abstract semantics is able to take full advantage of the power of representation of the underlying abstract domain. Thus, complete abstract interpretations can be rightfully considered as optimal. In this article, we develop a general theory of completeness in abstract interpretation, also dealing with the most frequent case of least fixpoint semantics. We show that both completeness and least fixpoint completeness are properties that only depend on the underlying abstract domain. In this context, we demonstrate that there always exist both the greatest complete and least fixpoint complete restrictions of any abstract domain, and for continuous semantic functions, the least complete extension exists as well. Also, under certain hypotheses, a constructive characterization of the least complete extensions and restrictions of abstract domains is given as solutions of simple abstract domain equations. These methodologies provide advanced algebraic tools for manipulating and comparing abstract interpretations, which can be fruitfully used both in program analysis and in semantics design. A number of examples illustrating these techniques are given in the fields of integer variable and logic program analysis.