School of Computing

Practical dependency analysis through a share quotient

Andy King, Pat Hill, and Jan Smaus

Technical Report 11-98, Computing Laboratory, May 1998.

Abstract

Def, the domain of definite Boolean functions, expresses (sure) dependencies between the program variables of, say, a constraint program. The domain Share, on the other hand, captures the (possible) variable sharing between the variables of a logic program. The connection between these domains has been explored in the domain comparison, quotienting and decomposition literature. We develop this link further and show how the meet (as well as the join) of Def can be modelled with efficient (quadratic) operations on Share. We show how the connection leads to an attractive way of constructing a dependency analysis and how widening can make the approach practical.

Download publication 338 kbytes (PostScript)

Bibtex Record

@techreport{587,
author = {Andy King and Pat Hill and Jan Smaus},
title = {Practical Dependency Analysis through a Share Quotient},
month = {May},
year = {1998},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1998/587},
    institution = {Computing Laboratory},
    number = {11-98},
}

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

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

Last Updated: 21/03/2014