``Optimal'' Collecting Semantics for Analysis in a Hierarchy of Logic Program Semantics

By: R. Giacobazzi

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


In this paper we apply abstract interpretation to systematically derive, compose and compare semantics according to their expressive power. The main results are: (1) a definition of a hierarchy of collecting semantics, including well known semantics for logic programs, where semantics can be related to each other by abstract interpretation; (2) a characterization of collecting and abstract semantics in terms of collecting and abstract models for a program; (3) a correspondence between collecting and abstract models providing a ``logical'' interpretation of the typical loss of precision of abstract interpretation-based analysis; (4) a systematic approach to derive and compose collecting semantics in a lattice-theoretic environment; (5) a constructive characterization for the ``best'' collecting semantics for analysis.

Available: DVI, PostScript, BibTeX Entry.