On ranking functions for single-path linear-constraint loops
文献类型：期刊论文
| 作者 | Li, Yi ; Wu, Wenyuan; Feng, Yong
|
| 刊名 | INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER
 |
| 出版日期 | 2019-11-13 |
| 页码 | 12 |
| 关键词 | Software reliability Program termination Linear ranking functions Farkas' lemma |
| ISSN号 | 1433-2779 |
| DOI | 10.1007/s10009-019-00549-9 |
| 通讯作者 | Li, Yi(zm_liyi@163.com) |
| 英文摘要 | Program termination is a fundamental research topic in program analysis. In this paper, we present a new complete polynomial-time method for the existence problem of linear ranking functions for single-path loops described by a conjunction of linear constraints, when variables range over the reals (or rationals). Unlike existing methods, our method does not depend on Farkas' Lemma and provides us with counterexamples to existence of linear ranking functions, when no linear ranking function exists. In addition, we extend our results established over the rationals to the setting of the integers. This deduces an alternative approach to deciding whether or not a given SLC loop has a linear ranking function over the integers. Finally, we prove that the termination of bounded single-path linear-constraint loops is decidable over the reals (or rationals). |
| 资助项目 | National Natural Science Foundation of China NNSFC[61572024] ; National Natural Science Foundation of China NNSFC[61103110] ; Natural Science Foundation of Chongqing[cstc2019jcyj-msxmX0638] |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000496208800001 |
| 出版者 | SPRINGER HEIDELBERG |
| 源URL | [http://119.78.100.138/handle/2HOD01W0/10304]  |
| 专题 | 中国科学院重庆绿色智能技术研究院 |
| 通讯作者 | Li, Yi |
| 作者单位 | Chinese Acad Sci, Chongqing Inst Green & Intelligent Technol, Chongqing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Li, Yi,Wu, Wenyuan,Feng, Yong. On ranking functions for single-path linear-constraint loops[J]. INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER,2019:12. |
| APA | Li, Yi,Wu, Wenyuan,&Feng, Yong.(2019).On ranking functions for single-path linear-constraint loops.INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER,12. |
| MLA | Li, Yi,et al."On ranking functions for single-path linear-constraint loops".INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER (2019):12. |
入库方式： OAI收割
来源：重庆绿色智能技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。