View in EDS

Termination proofs for linear simple loops.

Saved in:

Bibliographic Details
Title:	Termination proofs for linear simple loops.
Authors:	Chen, Hong¹ hchen11@lsu.edu, Flur, Shaked² fshaked@cs.technion.ac.il, Mukhopadhyay, Supratik¹ supratik@csc.lsu.edu
Source:	International Journal on Software Tools for Technology Transfer. Feb2015, Vol. 17 Issue 1, p47-57. 11p.
Subjects:	Loops (Group theory), Computer software termination, Computer programming, Lexicography, Polynomials
Abstract:	Analysis of termination and other liveness properties of a program can be reduced to termination proof synthesis for simple loops, i.e., loops with only variable updates in the loop body. Among simple loops, the subset of linear simple loops (LSLs) is particularly interesting because it is common in practice and expressive in theory. Existing techniques can successfully synthesize a linear ranking function for an LSL if there exists one. However, when a terminating LSL does not have a linear ranking function, these techniques fail. In this paper, we describe an automatic method that generates proofs of (universal) termination for LSLs based on the synthesis of disjunctive ranking relations. The method repeatedly finds linear ranking functions on partitions of the state space and checks whether the transitive closure of the transition relation is included in the union of the ranking relations. Our method extends the work of Podelski and Rybalchenko (A complete method for the synthesis of linear ranking functions. In: Proceedings of the 5th international conference on VMCAI, Jan 2004, Venice, Italy, pp 239-251, ). We have implemented a prototype of the method and have shown experimental evidence of the effectiveness of our method. [ABSTRACT FROM AUTHOR]
	Copyright of International Journal on Software Tools for Technology Transfer is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Analysis of termination and other liveness properties of a program can be reduced to termination proof synthesis for simple loops, i.e., loops with only variable updates in the loop body. Among simple loops, the subset of linear simple loops (LSLs) is particularly interesting because it is common in practice and expressive in theory. Existing techniques can successfully synthesize a linear ranking function for an LSL if there exists one. However, when a terminating LSL does not have a linear ranking function, these techniques fail. In this paper, we describe an automatic method that generates proofs of (universal) termination for LSLs based on the synthesis of disjunctive ranking relations. The method repeatedly finds linear ranking functions on partitions of the state space and checks whether the transitive closure of the transition relation is included in the union of the ranking relations. Our method extends the work of Podelski and Rybalchenko (A complete method for the synthesis of linear ranking functions. In: Proceedings of the 5th international conference on VMCAI, Jan 2004, Venice, Italy, pp 239-251, ). We have implemented a prototype of the method and have shown experimental evidence of the effectiveness of our method. [ABSTRACT FROM AUTHOR]
ISSN:	14332779
DOI:	10.1007/s10009-013-0288-8