School of Computing

Lower-bound time-complexity analysis of logic programs

Andy King, Kish Shen, and Florence Benoy

In Jan Maluszynski, editor, International Symposium on Logic Programming, pages 182-196. MIT Press, November 1997.

Abstract

The paper proposes a technique for inferring conditions on goals that, when satisfied, ensure that a goal is sufficiently coarse-grained to warrant parallel evaluation. The method is powerful enough to reason about divide-and-conquer programs, and in the case of quicksort, for instance, can infer that a quicksort goal has a time complexity that exceeds 64 resolution steps (a threshold for spawning) if the input list is of length 10 or more. This gives a simple run-time tactic for controlling spawning. The method has been proved correct, can be implemented straightforwardly, has been demonstrated to be useful on a parallel machine, and, in contrast with much of the previous work on time-complexity analysis of logic programs, does not require any complicated difference equation solving machinery.

Download publication 170 kbytes (PostScript)

Bibtex Record

@inproceedings{506,
author = {Andy King and Kish Shen and Florence Benoy},
title = {Lower-bound Time-Complexity Analysis of Logic Programs},
month = {November},
year = {1997},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1997/506},
    ISBN = {0-262-63180-6},
    ISSN = {1061-0464},
    booktitle = {International  Symposium on Logic Programming},
    editor = {Jan Maluszynski},
    publisher = {MIT Press},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014