Journal of Software:2011.22(9):1973-1984

(国防科学技术大学 计算机学院,湖南 长沙 410073;北京航空航天大学 计算机学院,北京 100191)
Computing Symbolic Complexity Bounds of Loops by Recurrence Solution
XING Jian-Ying,LI Meng-Jun,LI Zhou-Jun
(College of Computer, National University of Defense Technology, Changsha 410073, China;School of Computer Science and Engineering, BeiHang University, Beijing 100191, China)
Chart / table
Similar Articles
Article :Browse 3939   Download 2911
Received:November 16, 2009    Revised:April 14, 2010
> 中文摘要: 计算程序中循环的程序复杂度符号化上界可以验证程序的停机性.基于差分方程和最优化问题求解技术,给出了一种计算P*-solvable 循环程序复杂度符号化上界的有效方法.分别针对含有赋值语句的循环和带条件分支的循环,提出了其程序复杂度符号化上界计算方法.与其他工作相比,该方法能够计算得到更精确的循环复杂度符号化上界,实验结果证明了该方法的有效性.
Abstract:Computing symbolic complexity bounds of loops can prove program’s termination. Based on the solving techniques of recurrence equations and optimization problems, this paper presents a practical approach for computing complexity bounds of loops called P*-solvable loops. Two algorithms are given for loops with assignments only and loops with conditional branches respectively. Compared with some other works, this approach can attain more complexity bounds of loops. The experimental results demonstrate the practicality of this approach.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60703075, 60973105, 90718017); 国家教育部博士点专项基金(20070006055) 国家自然科学基金(60703075, 60973105, 90718017); 国家教育部博士点专项基金(20070006055)
Foundation items:
Reference text:


XING Jian-Ying,LI Meng-Jun,LI Zhou-Jun.Computing Symbolic Complexity Bounds of Loops by Recurrence Solution.Journal of Software,2011,22(9):1973-1984