Efficient Abstract Interpretation using Component-Wise Homomorphism

Jörg Köller and Markus Mohnen

To appear at the 2nd International Conference on Principles and Practice of Declarative Programming (PPDP 2000), Montreal, Canada, September 20-22, 2000


Fixed point based abstract interpretation requires compact representations of functions. In general, finding a fixed point requires exponential time. Good representations allow the reduction of the fixed point solvers computational complexity. One approach for obtaining compact representations is the use of special classes of functions. In this paper, we focus on the class of component-wise homomorphisms. We show that this class of functions gives more compact representations than component-wise additive functions.