School of Computing

On the Inference of Natural Level Mappings

Jonathan C. Martin and Andy King

In Maurice Bruynooghe and Kung-Kiu Lau, editors, Program Development in Computational Logic, volume 3049 of Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, May 2004 Also see http://www.springer.de/comp/lncs/index.html.

Abstract

Reasoning about termination is a key issue in logic program development. One classic technique for proving termination is to construct a well-founded order on goals that decreases between successive goals in a derivation. In practise, this is achieved with the aid of a level mapping that maps atoms to natural numbers. This paper examines why it can be difficult to base termination proofs on natural level mappings that directly relate to the recursive structure of the program. The notions of bounded-recurrency and bounded-acceptability are introduced to alleviate these problems. These concepts are equivalent to the classic notions of recurrency and acceptability respectively, yet provide practical criteria for constructing termination proofs in terms of natural level mappings for definite logic programs. Moreover, the construction is entirely modular in that termination conditions are derived in a bottom-up fashion by considering, in turn, each the strongly connected components of the program.

Download publication 338 kbytes (PostScript)

Bibtex Record

@inproceedings{1785,
author = {Jonathan C. Martin and Andy King},
title = {On the {I}nference of {N}atural {L}evel {M}appings},
month = {May},
year = {2004},
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/2004/1785},
    publication_type = {inproceedings},
    submission_id = {28940_1075395365},
    booktitle = {Program Development in Computational Logic},
    editor = {Maurice Bruynooghe and Kung-Kiu Lau},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer-Verlag},
    refereed = {yes},
    volume = {3049},
}

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

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

Last Updated: 21/03/2014