Skip to main content
Kent Academic Repository

On the Inference of Natural Level Mappings: A Decade of Research Advances in Logic-Based Program Development

Martin, Jonthan C. and King, Andy (2004) On the Inference of Natural Level Mappings: A Decade of Research Advances in Logic-Based Program Development. In: Bruynooghe, Maurice and Lau, Kung-Kiu, eds. Program Development in Computational Logic,. Lecture Notes in Computer Science, 3049 . Springer, pp. 432-452. ISBN 978-3-540-22152-4. (doi:10.1007/978-3-540-25951-0_13) (KAR id:37609)


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.

Item Type: Book section
DOI/Identification number: 10.1007/978-3-540-25951-0_13
Subjects: A General Works
A General Works > AC Collections. Series. Collected works
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 13 Dec 2013 08:41 UTC
Last Modified: 16 Nov 2021 10:14 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.