Worst-Case Groundness Analysis using Positive Boolean Functions

Michael Codish   

The Journal of Logic Programming; 41 (1): 125--128, 1999


This note illustrates a theoretical worst-case scenario for groundness analyses obtained through abstract interpretation over the abstract domain of positive Boolean functions. A sequence of programs is given for which any Pos-based abstract interpretation for groundness analysis follows an exponential chain. Another sequence of programs is given for which a state-of-the-art implementation based on ROBDDs gives a result of exponential size in only three iterations. The moral of the story is that a serious Pos analyser must incorporate some form of widening to protect itself from the inherent complexity of the underlying domain.

Available:    bibtex entry   compressed postscript

Related sites:   PDF 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