Roberto, Margherita and Beatrice

Home

Personal Info

Papers

Teaching

Links

A Correct, Precise and Efficient Integration of Set-Sharing, Freeness and Linearity for the Analysis of Finite and Rational Tree Languages

Patricia M. Hill
School of Computer Studies
University of Leeds
Leeds, LS2 9JT
United Kingdom

Enea Zaffanella
Dipartimento di Matematica e Informatica
Università di Parma
Parco Area delle Scienze 53/A
I-43124 Parma
Italy

Roberto Bagnara
Dipartimento di Matematica e Informatica
Università di Parma
Parco Area delle Scienze 53/A
I-43124 Parma
Italy

Abstract:

It is well-known that freeness and linearity information positively interact with aliasing information, allowing both the precision and the efficiency of the sharing analysis of logic programs to be improved. In this paper we present a novel combination of set-sharing with freeness and linearity information, which is characterized by an improved abstract unification operator. We provide a new abstraction function and prove the correctness of the analysis for both the finite tree and the rational tree cases. Moreover, we show that the same notion of redundant information as identified in (Bagnara et al. 2002; Zaffanella et al. 2002) also applies to this abstract domain combination: this allows for the implementation of an abstract unification operator running in polynomial time and achieving the same precision on all the considered observable properties.

Keywords: Abstract Interpretation; Logic Programming; Abstract Unification; Rational Trees; Set-Sharing; Freeness; Linearity.

References

Bagnara, R., Hill, P. M., and Zaffanella, E. 2002. Set-sharing is redundant for pair-sharing. Theoretical Computer Science 277, 1-2, 3-46.
Zaffanella, E., Hill, P. M., and Bagnara, R. 2002. Decomposing non-redundant sharing by complementation. Theory and Practice of Logic Programming 2, 2, 233-261.


Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, BibTeX entry.

[Page last updated on May 03, 2004, 15:37:39.]

© Roberto Bagnara
bagnara@cs.unipr.it

Home | Personal | Papers | Teaching | Links