Lower bound cost estimation for logic programs

Debray, S.K. and López García, Pedro and Hermenegildo, Manuel V. and Lin, Nai-Wei (1997). Lower bound cost estimation for logic programs. In: "International Logic Programming Symposium 1997", Oct 12-17 1997, Island N.Y. ISBN 9780262631808.


Title: Lower bound cost estimation for logic programs
  • Debray, S.K.
  • López García, Pedro
  • Hermenegildo, Manuel V.
  • Lin, Nai-Wei
Item Type: Presentation at Congress or Conference (Article)
Event Title: International Logic Programming Symposium 1997
Event Dates: Oct 12-17 1997
Event Location: Island N.Y
Title of Book: Logic Programming
Date: October 1997
ISBN: 9780262631808
Freetext Keywords: Cost analysis, Lower bound estimation, Granularity control, Parallelism, Análisis de costes, Estimación del límite inferior, Paralelismo.
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (931kB) | Preview


It is generally recognized that information about the runtime cost of computations can be useful for a variety of applications, including program transformation, granularity control during parallel execution, and query optimization in deductive databases. Most of the work to date on compile-time cost estimation of logic programs has focused on the estimation of upper bounds on costs. However, in many applications, such as parallel implementations on distributed-memory machines, one would prefer to work with lower bounds instead. The problem with estimating lower bounds is that in general, it is necessary to account for the possibility of failure of head unification, leading to a trivial lower bound of 0. In this paper, we show how, given type and mode information about procedures in a logic program, it is possible to (semi-automatically) derive nontrivial lower bounds on their computational costs. We also discuss the cost analysis for the special and frequent case of divide-and-conquer programs and show how —as a pragmatic short-term solution —it may be possible to obtain useful results simply by identifying and treating divide-and-conquer programs specially.

More information

Item ID: 14401
DC Identifier: http://oa.upm.es/14401/
OAI Identifier: oai:oa.upm.es:14401
Official URL: http://mitpress.mit.edu/books/logic-programming
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 03 Feb 2013 10:58
Last Modified: 21 Apr 2016 14:02
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM