On the least complete extension of complete subsemilattices

By: R. Giacobazzi and F. Ranzato

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


For a complete sublattice X of a complete lattice C, we consider the problem of the existence of the least complete meet subsemilattice of C having as least complete extension (i.e. the least complete sublattice of C containing it) X. We argue that this problem is not trivial, and we provide two results that, under certain conditions on C and X, give a positive answer to it.

Mathematics Subject Classification 06A12, 06A15, 06A23.

Available: DVI, PostScript, BibTeX Entry.

This result has been applied in abstract interpretation theory in the following papers:
  • A Unifying View on Abstract Domain Design (ACM Comp. Surveys 28(2):333-336, 1996)
  • Optimal domains for disjunctive abstract interpretation (To appear in Sci. of Comp. Prog.)
  • Refining and compressing abstract domains (ICALP'97, 1997).

  • giaco@sci.univr.it