Abstract
Automatic complexity analysis of programs has been widely studied in the context of functional languages. This paper develops a method for automatic analysis of the worse-case complexity of a large class of logic programs. The primary contribution of this paper is that it shows how to deal with nondeterminism and the generation of multiple solutions via backtracking. One advantage of our method is that analyses for different complexity measures (e.g. time complexity, space complexity, number of solutions, etc) are performed in a unified framework that simplifies both formal reasoning about, and implementation of, the algorithms.
| Original language | English (US) |
|---|---|
| Pages | 599-613 |
| Number of pages | 15 |
| State | Published - 1991 |
| Event | Logic Programming - Proceedings of the 8th International Conference - Paris, Fr Duration: Jun 24 1991 → Jun 28 1991 |
Other
| Other | Logic Programming - Proceedings of the 8th International Conference |
|---|---|
| City | Paris, Fr |
| Period | 6/24/91 → 6/28/91 |
ASJC Scopus subject areas
- General Engineering