School of Computing

Depth-k Sharing and Freeness

A. King and P. Soper

In P. Van Hentenryck, editor, International Conference on Logic Programming, pages 182-196. MIT Press, January 1994.

Abstract

Analyses for variable sharing and freeness are important both in the automatic parallelisation and in the optimisation of sequential logic programs. In this paper, a new analysis is described which can infer sharing and freeness information to an unusually high degree of accuracy. By encoding structural properties of substitutions in a sharing group fashion, a powerful depth-(unknown variable k)$ sharing and freeness analysis is synthesised which exploits the synergy between tracing sharing information and tracking term structure. The analysis propagates groundness with the accuracy of sharing groups and yet can precisely infer sharing and freeness. Correctness is formally proven.

Download publication 366 kbytes (PostScript)

Bibtex Record

@inproceedings{1321,
author = {A.~King and P.~Soper},
title = {Depth-(unknown variable k)$ {S}haring and {F}reeness},
month = {January},
year = {1994},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1994/1321},
    publication_type = {inproceedings},
    submission_id = {9253_1011197369},
    other_year = {1994},
    booktitle = {International Conference on Logic Programming},
    editor = {P. Van Hentenryck},
    publisher = {MIT Press},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014