Martin, Jonathan.C. and King, Andy (2003) On Modular Termination Proofs. Technical report. University of Kent
| The full text of this publication is not available from this repository. (Contact us about this Publication) | |
| Official URL http://www.cs.kent.ac.uk/pubs/2003/1747 |
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. 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: | Monograph (Technical report) |
|---|---|
| Additional information: | Technical Report 13-03, Computing Laboratory, University of Kent, UK, October 2003. |
| Uncontrolled keywords: | logic programming, termination analysis, modularity |
| Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, |
| Divisions: | Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group |
| Depositing User: | Mark Wheadon |
| Date Deposited: | 24 Nov 2008 18:00 |
| Last Modified: | 15 Mar 2009 13:26 |
| Resource URI: | http://kar.kent.ac.uk/id/eprint/13891 (The current URI for this page, for reference purposes) |
- Depositors only (login required):
