Estimating the Computational Cost of Logic Programs

Information about the computational cost of programs is potentially useful for a variety of purposes, including selecting among dierent al-gorithms, guiding program transformations, in granularity control and mapping decisions in parallelizing compilers, and query optimization in deductive databases. Cost analysis of logic programs is complicated by nondeterminism: on the one hand, procedures can return multiple solu-tions, making it necessary to estimate the number of solutions in order to give nontrivial upper bound cost estimates; on the other hand, the possi-bility of failure has to be taken into account while estimating lower bounds. Here we discuss techniques to address these problems to some extent.