Exploiting Goal Independence in the Analysis of Logic Programs

Michael Codish, María García de la Banda, Maurice Bruynooghe and Manuel Hermenegildo   

The Journal of Logic Programming; 32 (3): 247-261, 1997


This paper illustrates the use of a top-down framework to obtain goal independent analyses of logic programs, a task which is usually associated with the bottom-up approach. While it is well known that the bottom-up approach can be used, through the magic set transformation, for goal dependent analysis, it is less known that the top-down approach can be used for goal independent analysis. The paper describes two ways of doing the latter. % and argues that the more efficient approach corresponds closely to % the standard bottom-up approach. We show how the results of a goal independent analysis can be used to speed up subsequent goal dependent analyses. However this speed-up may result in a loss of precision. The influence of domain characteristics on this precision is discussed and an experimental evaluation using a generic top-down analyzer is described. Our results provide intuition regarding the cases where a two phase analysis might be worthwhile.

Available:    bibtex entry   compressed postscript

Related sites:   Abstract from the publisher   PDF from Scirus - scientific search engine

Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel

© copyright notice