School Homepage

Papers of Patricia M. Hill

Software Support for CLP: Papers

Technical Reports at Leeds

A Simple Polynomial Groundness Analysis for Logic Programs

[Page last updated on 2000/10/25.]

Andrew Heaton
School of Computing
The University of Leeds
Leeds LS2 9JT
England

Muhamed Abo-Zaed
Department of Mathematics and Computer Science
Ben-Gurion University
PoB 653
Beer-Sheba
Israel

Michael Codish
Department of Computer Science and Software Engineering
Ben-Gurion University
The University of Melbourne
Parkville 3052
Australia

Andy King
Computing Laboratory
The University of Kent at Canterbury
Canterbury CT2 7NF
England

Abstract:

The domain of positive Boolean functions, Pos, is by now well established for the analysis of the variable dependencies that arise within logic programs. Analyses based on Pos that use binary decision diagrams have been shown to be efficient for a wide range of practical programs. However, independent of the representation, a Pos analysis can never come with any efficiency guarantees because of its potential exponential behaviour. This paper considers groundness analysis based on a simple subdomain of Pos and compares its precision with that of Pos.

In:

Journal of Logic Programming, February 2000.

Available: BibTeX entry.