Lower-bound Time-Complexity Analysis of Logic Programs

Part of book or chapter of book English OPEN
King, Andy ; Shen, Kish ; Benoy, Florence (1997)
  • Publisher: MIT Press
  • Subject: QA76

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.
  • References (22)
    22 references, page 1 of 3

    [1] R. Barbuti, M. Codish, R. Giacobazzi, and M. Maher. Oracle Semantics for Prolog. Information and Computation, 22(2):178-200, 1992.

    [2] F. Benoy and A. King. Inferring Argument Size Relationships with CLP(R). In LOPSTR'96. Springer-Verlag, 1996.

    [3] A. Bossi, M. Gabbrielli, G. Levi, and M. Martelli. The s-semantics approach: theory and applications. Journal of Logic Programming, 1991.

    [4] P. Cousot and N. Halbwachs. Automatic discovery of linear restraints among variables of a program. In POPL'78, pages 84-97, 1978.

    [5] B. De Backer and H. Beringer. A CLP language handling disjunctions of linear constraints. In ICLP'93, pages 550-563. MIT Press, 1993.

    [6] S. Debray and N.-W. Lin. Cost Analysis for Logic Programs. ACM TOPLAS, July 1992.

    [7] S. Debray, N.-W. Lin, and M. Hermenegildo. Task Granularity Analysis in Logic Programs. In PLDI'90, White Plains, New York, 1990. ACM.

    [8] S. Debray, P. Lo´pez Garc´ıa, and M. Hermenegildo. Non-Failure Analysis of Logic Programs. In ICLP'97. MIT Press, 1997.

    [9] S. Debray, P. Lo´pez Garc´ıa, M. Hermenegildo, and N. Lin. Lower Bound Cost Estimation for Logic Programs. Technical Report TR Number CLIP20/95.0, T.U. of Madrid (UPM), Facultad Informa´tica UPM, 28660-Boadilla del Monte, Madrid-Spain, 1995.

    [10] S. Decorte, D. De Schreye, and M. Fabris. Automatic Inference of Norms: A Missing Link in Termination Analysis. In ICLP'93, pages 420-436. MIT Press, 1993.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Kent Academic Repository - IRUS-UK 0 14
Share - Bookmark