Lower-bound Time-Complexity Analysis of Logic Programs

King, Andy and Shen, Kish and Benoy, Florence (1997) Lower-bound Time-Complexity Analysis of Logic Programs. In: Maluszynski, Jan, ed. Proceedings of the 1997 international symposium on Logic programming. MIT Press pp. 261-276. ISBN 0-262-63180-6.

Postscript
Download (170Kb)	Preview
PDF
Download (166Kb)	Preview

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.

Item Type:	Conference or workshop item (Paper)
Uncontrolled keywords:	abstract interpretation, logic programming
Subjects:	Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions:	Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User:	Mark Wheadon
Date Deposited:	02 Aug 2009 20:53
Last Modified:	06 Sep 2011 03:53
Resource URI:	http://kar.kent.ac.uk/id/eprint/21434 (The current URI for this page, for reference purposes)

• Depositors only (login required):