Estimating the Computational Cost of Logic Programs
Saumya Debray Pedro
López-García Manuel
Hermenegildo Nai-Wei Lin
Abstract
Information about the computational cost of programs is potentially
useful for a variety of purposes, including selecting among different
algorithms, 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 solutions, making it necessary to estimate
the number of solutions in order to give nontrivial upper bound cost
estimates; on the other hand, the possibility of failure has to be taken
into account while estimating lower bounds. Here we discuss techniques
to address these problems to some extent.
