Domain Compression for Complete Abstractions

We introduce the operation of domain compression for complete refinements of finite abstract domains. This provides a systematic method for simplifying abstract domains in order to isolate the most abstract domain, when it exists, whose refinement toward completeness for a given semantic function returns a given domain. Domain compression is particularly relevant to compare abstractions in static program analysis and abstract model checking. In this latter case we consider domain compression in predicate abstraction of transition systems.