School of Computing

Determinacy Inference for Logic Programs

Lunjin Lu and Andy King

In Mooly Sagiv, editor, European Symposium on Programming, volume 3444, pages 182-196. Springer-Verlag, April 2005 Also see http://www.springer.de/comp/lncs/index.html.

Abstract

This paper presents a determinacy inference analysis for logic programs. The analysis infers determinacy conditions that, if satisfied by a call, ensures that it computes at most one answer and that answer is generated only once. The principal component of the technique is a goal-independent analysis of individual clauses. This derives a condition for a call that ensures only one clause in the matching predicate possesses a successful derivation. Another key component of the analysis is backwards reasoning stage that strengthens these conditions to derive properties on a call that assure determinacy. The analysis has applications in program development, implementation and specialisation.

Download publication 315 kbytes (PostScript)

Bibtex Record

@inproceedings{2026,
author = {Lunjin Lu and Andy King},
title = {Determinacy {I}nference for {L}ogic {P}rograms},
month = {April},
year = {2005},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {Also see http://www.springer.de/comp/lncs/index.html},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2005/2026},
    publication_type = {inproceedings},
    submission_id = {22238_1103273128},
    booktitle = {European Symposium on Programming},
    editor = {Mooly Sagiv},
    publisher = {Springer-Verlag},
    refereed = {yes},
    volume = {3444},
}

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

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

Last Updated: 21/03/2014