Worst-case groundness analysis using positive Boolean functions

This note illustrates a theoretical worst-case scenario for groundness anal yses obtained through abstract interpretation over the abstract domain of p ositive Boolean functions. A sequence of programs is given for which any Po s-based abstract interpretation for groundness analysis follows an exponent ial chain. Another sequence of programs is given for which a state-of-the-a rt implementation based on ROBDDs gives a result of exponential size in onl y three iterations. The moral of the story is that a serious Pos analyser m ust incorporate some form of widening to protect itself from the inherent c omplexity of the underlying domain. (C) 1999 Elsevier Science Inc. All righ ts reserved.