Please use this identifier to cite or link to this item: https://doi.org/10.1145/1706356.1706369
Title: Regular approximation and bounded domains for size-change termination
Authors: Anderson, H.
Khoo, S.-C. 
Keywords: Affine size-change termination
Termination analysis
Issue Date: 2010
Source: Anderson, H., Khoo, S.-C. (2010). Regular approximation and bounded domains for size-change termination. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation : 53-62. ScholarBank@NUS Repository. https://doi.org/10.1145/1706356.1706369
Abstract: The size-change principle devised by Lee, Jones and Ben-Amram, provides an effective method of determining program termination for recursive functions. It relies on a regular approximation to the call structure of the program, operates only over variables whose "size" is well-founded, and ignores the conditionals and return values in the program. The main contribution of our paper is twofold: firstly we improve size-change termination analysis by using better regular approximations to program flow, and secondly we extend the analysis beyond the original well-founded variables to include integer variables. In addition, we pay attention to program conditionals that are expressed by linear constraints and support the analysis of functions in which the return values are relevant to termination. Our analysis is entirely mechanical, exploits the decidability and expressive power of affine constraints and extends the set of programs that are size-change terminating. Copyright © 2010 ACM.
Source Title: Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
URI: http://scholarbank.nus.edu.sg/handle/10635/41433
ISBN: 9781605587271
DOI: 10.1145/1706356.1706369
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 14, 2017

Page view(s)

52
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.