Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 826-875 |
Number of pages | 50 |
Journal | ACM Transactions on Programming Languages and Systems (TOPLAS) |
Volume | 15 |
Issue number | 5 |
DOIs | |
State | Published - Jan 11 1993 |
Keywords
- PROLOG
- complexity
- program analysis
ASJC Scopus subject areas
- Software