期刊导航

论文摘要

一类循环条件非线性的程序终止性

Termination of a Class of Nonlinear Loop Programs

作者:李骏(中国科学院成都计算机应用研究所, 四川 成都 610041);李轶(中国科学院成都计算机应用研究所, 四川 成都 610041);冯勇(中国科学院成都计算机应用研究所, 四川 成都 610041)

Author:(Chengdu Inst. of Computer Application, Chinese Academy of Sciences,Chengdu 610041,China);(Chengdu Inst. of Computer Application, Chinese Academy of Sciences,Chengdu 610041,China);(Chengdu Inst. of Computer Application, Chinese Academy of Sciences,Chengdu 610041,China)

收稿日期:2007-10-29          年卷(期)页码:2009,41(1):129-133

期刊名称:工程科学与技术

Journal Name:Advanced Engineering Sciences

关键字:非线性程序;终止性;程序验证;Jordan标准型

Key words:nonlinear programs; termination; program verification; Jordan form

基金项目:国家科委973资助项目(2004CB318003);中国科学院知识创新重要方向资助项目 (KJCX2-YW-S02);国家自然科学基金资助项目(10771205)

中文摘要

针对Tiwari提出的线性循环程序的终止性判定问题,提出了循环条件为齐次多项式的非线性程序的不可中止性判定的理论证明,然后将程序终止性判定问题转化为参数半代数系统的求解。在求解中,借助强有力的代数符号工具DISCOVERER,解决了计算机浮点计算所造成的近似误差,精确地判定这类程序的不可终止性。最后,通过计算代数理论,把循环条件推广到了非齐次多项式,并且进行了验证。通过理论的证明和实验的验证,解决循环条件是非线性的一类循环程序的方法是高效合理的。

英文摘要

For termination of linear loop programs proposed by Tiwari,the proof that the non linear programs of cycle conditions is the homogeneous polynomial and can not be terminated was put forward.Then the program termination was transformed as the solution of a system of semi algebra.A powerful algebraic symbols tool DISCOVERER was used to solve the approximate error caused by floating point calculations, and accurately determinate that such programs can not be terminated. Finally, by the computation algebra theory,the cycle conditions was extended to non homogeneous polynomial.Through theoretical and experimental proof, for a kind of cycle programs that cycle condition is non linear,these solutions is efficient and reasonable.

关闭

Copyright © 2020四川大学期刊社 版权所有.

地址:成都市一环路南一段24号

邮编:610065