Exploiting Goal Independence in the Analysis of Logic Programs
The Journal of Logic Programming;
32 (3): 247-261,
Abstract: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.
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel