Cost Analysis of Logic Programs

Saumya K. Debray, Nai Wei Lin

Research output: Contribution to journalArticlepeer-review

91 Scopus citations


Cost analysis of programs has been studied in the context of imperative and functional programming languages. For logic programs, the problem is comphcated by the fact that programs may be nondeterministic and produce multiple solutions. A related problem is that because failure of execution is not an abnormal situation, it is possible to write programs where irnphclt failures have to be dealt with exphcitly in order to get meaningful results. This paper addresses these problems and develops a method for (semi-)automatlc analysls of the worst-case cost of a large class of logic programs. The prl mary contribution of this paper is the development of techmques to deal with nondeterminism and the generation of multiple solutions via backtracking. Apphcations include program transformation and synthesis, software engineering, and in parallelizing compilers.

Original languageEnglish (US)
Pages (from-to)826-875
Number of pages50
JournalACM Transactions on Programming Languages and Systems (TOPLAS)
Issue number5
StatePublished - Jan 11 1993


  • complexity
  • program analysis

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Cost Analysis of Logic Programs'. Together they form a unique fingerprint.

Cite this