Weak Relative Pseudo-Complements of Closure Operators

By: R. Giacobazzi, C. Palamidessi and F. Ranzato

Roberto Giacobazzi
Dip. di Informatica
Univ. di Pisa
Corso Italia 40, 56125 Pisa (Italy)


We define the notion of weak relative pseudo-complement on meet semi-lattices, and we show that it is strictly weaker than relative pseudo-complementation, but stronger than pseudo-complementation. Our main result is that if a complete lattice L is meet-continuous, then every closure operator on L admits weak relative pseudo-complements with respect to continuous closure operators on L.

This result has been applied in abstract interpretation in the following papers:
  • A Unifying View on Abstract Domain Design (ACM Comp. Surveys 28(2):333-336, 1996)
  • Complementation in Abstract Interpretation (ACM-TOPLAS 19(1):7-47, 1997)
  • Refining and compressing abstract domains (ICALP'97, 1997).

  • Available: DVI, PostScript, BibTeX Entry, Technical Report LIX/95/04 (file PostScript).