School of Computing

Detecting Determinacy in Prolog Programs

Andy King, Lunjin Lu, and Samir Genaim

In Sandro Etalle and Mirek Truszczynski, editors, Twenty Second International Conference on Logic Programming, volume 4079 of Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, August 2006.

Abstract

In program development it is useful to know that a call to a Prolog program will not inadvertently leave a choice-point on the stack. Determinacy inference has been proposed for solving this problem yet the analysis was found to be wanting in that it could not infer determinacy conditions for programs that contained cuts or applied certain tests to select a clause. This paper shows how to remedy these serious deficiencies. It also addresses the problem of identifying those predicates which can be rewritten in a more deterministic fashion. To this end, a radically new form of determinacy inference is introduced, which is founded on ideas in ccp, that is capable of reasoning about the way bindings imposed by a rightmost goal can make a leftmost goal deterministic.

Download publication 360 kbytes (PostScript)

Bibtex Record

@inproceedings{2372,
author = {Andy King and Lunjin Lu and Samir Genaim},
title = {Detecting {D}eterminacy in {P}rolog {P}rograms},
month = {August},
year = {2006},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2006/2372},
    publication_type = {inproceedings},
    submission_id = {6006_1145478420},
    booktitle = {Twenty Second International Conference on Logic Programming},
    editor = {Sandro Etalle and Mirek Truszczynski},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer-Verlag},
    refereed = {yes},
    volume = {4079},
}

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

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

Last Updated: 21/03/2014