Estimating the computational cost of logic programs

S. K. Debray, P. López Garćia, M. Hermenegildo, N. W. Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationStatic Analysis - 1st International Static Analysis Symposium, SAS '94, Proceedings
EditorsBaudouin Le Charlier
Number of pages11
ISBN (Print)9783540584858
StatePublished - 1994
Externally publishedYes
Event1st International Static Analysis Symposium, SAS 1994 - Namur, Belgium
Duration: Sep 28 1994Sep 30 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume864 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st International Static Analysis Symposium, SAS 1994

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Estimating the computational cost of logic programs'. Together they form a unique fingerprint.

Cite this