© University of Kent - Contact | Feedback | Legal | FOI | Cookies
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}, }