计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2013年
11期
2245-2256
,共12页
姬秀娟%杨巨峰%许静%李晓虹%封磊
姬秀娟%楊巨峰%許靜%李曉虹%封磊
희수연%양거봉%허정%리효홍%봉뢰
死循环检测%静态分析%递推链代数%迭代函数收敛性%软件工程
死循環檢測%靜態分析%遞推鏈代數%迭代函數收斂性%軟件工程
사순배검측%정태분석%체추련대수%질대함수수렴성%연건공정
infinite loop detection%static analysis%chains of recurrence algebra%convergence of iterative function%software engineering
该文针对两大类循环分别给出了非终止性判定的数学方法.首先,针对基本迭代关系为线性或几何性的循环提出了基于递推链代数的分析方法.通过递推链代数将循环变量进行统一表示,根据运算规则推导出循环条件关于迭代次数的闭形式函数,然后通过约束求解以及单调性判断循环的非终止性.其次,针对一元非线性循环提出了基于迭代序列敛散性的分析方法.根据迭代函数以及不动点判断迭代函数产生的迭代序列的敛散性来判断循环的非终止性.实验部分采用Velroyen[20]的52组循环、文献[18-19,21-23]的23组循环、文献[3]以及自组的13组循环进行分析验证,结果表明该文所提出的方法能有效地判断循环的非终止性:若循环无法终止,可以推导出循环无法终止的变量约束；若循环可终止,则可以估算循环的迭代次数.
該文針對兩大類循環分彆給齣瞭非終止性判定的數學方法.首先,針對基本迭代關繫為線性或幾何性的循環提齣瞭基于遞推鏈代數的分析方法.通過遞推鏈代數將循環變量進行統一錶示,根據運算規則推導齣循環條件關于迭代次數的閉形式函數,然後通過約束求解以及單調性判斷循環的非終止性.其次,針對一元非線性循環提齣瞭基于迭代序列斂散性的分析方法.根據迭代函數以及不動點判斷迭代函數產生的迭代序列的斂散性來判斷循環的非終止性.實驗部分採用Velroyen[20]的52組循環、文獻[18-19,21-23]的23組循環、文獻[3]以及自組的13組循環進行分析驗證,結果錶明該文所提齣的方法能有效地判斷循環的非終止性:若循環無法終止,可以推導齣循環無法終止的變量約束；若循環可終止,則可以估算循環的迭代次數.
해문침대량대류순배분별급출료비종지성판정적수학방법.수선,침대기본질대관계위선성혹궤하성적순배제출료기우체추련대수적분석방법.통과체추련대수장순배변량진행통일표시,근거운산규칙추도출순배조건관우질대차수적폐형식함수,연후통과약속구해이급단조성판단순배적비종지성.기차,침대일원비선성순배제출료기우질대서렬렴산성적분석방법.근거질대함수이급불동점판단질대함수산생적질대서렬적렴산성래판단순배적비종지성.실험부분채용Velroyen[20]적52조순배、문헌[18-19,21-23]적23조순배、문헌[3]이급자조적13조순배진행분석험증,결과표명해문소제출적방법능유효지판단순배적비종지성:약순배무법종지,가이추도출순배무법종지적변량약속；약순배가종지,칙가이고산순배적질대차수.
