On the power of abstract interpretation

R.C. Sekar et al. (1991) studied the power of strictness analysis techniques and showed that strictness analysis is perfect up to variations in constants. The authors generalize this approach to abstract interpretation in general by defining a notion of similarity semantics. This semantics associates with a program a collection of interpretations all of which are obtained by blurring the distinctions that a particular static analysis ignores. The authors define completeness with respect to similarity semantics and obtain two completeness results. For first-order languages, abstract interpretation is complete with respect to a standard similarity semantics, provided the base abstract domain is linearly ordered. For typed higher-order languages, it is complete with respect to a logical similarity semantics again under the condition of a linearly ordered base abstract domain