线性循环程序的终止性判定  

TERMINATION ANALYSIS OF LINEAR LOOP PROGRAMS

作　　者：李轶[1] 

机构地区：[1]中国科学院重庆绿色智能技术研究院,重庆401122

出　　处：《系统科学与数学》2013年第5期626-638,共13页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(61103110);国家自然科学基金重点项目(91018012);国家973计划项目(2011CB302400);重庆市科技攻关项目(cstc2012ggB40004)资助课题

摘　　要：对赋值矩阵仅为一个Jordan块的特殊线性循环,构造了不可终止点集的一个子集,证明了此类循环的终止性可仅由该子集是否为空来判定.除此之外,该类循环的终止性被证明也可通过比较几个系数的符号来判定.而对一般的线性循环程序,提出了递归判定算法,使得这类循环的终止性可转化为上述特殊循环的终止性判定.最后,对N-不可终止点,给出了计算N的方法.Termination of linear programs proposed by Tiwari is analyzed in this paper.Especially for a special class of linear loops,two different methods are presented to determine its termination.Moreover,it is shown that the determination of termination of general linear programs can be converted to the determination of termination of this special class of loops.Finally,for an N-nonterminating point X, a method is given to compute N＇s value such that this point eventually becomes a nonterminating point after N loop iterations.

关 键 词：可信计算 线性循环 终止性分析 N-不可终止点 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]