A simple polynomial groundness analysis for logic programs

The domain of positive Boolean functions, Pos, is by now well established f or the analysis of the variable dependencies that arise within logic progra ms. Analyses based on Pos that use binary decision diagrams (BDDs) have bee n shown to be efficient for a wide range of practical programs. However, in dependent of the representation, a Pos analysis can never come with any eff iciency guarantees because of its potential exponential behaviour. This pap er considers groundness analysis based on a simple subdomain of Pos and com pares its precision with that of Pos. (C) 2000 Elsevier Science Inc. All ri ghts reserved.