.png){kind=icon}
返回
Targeting Completeness: Automated Complexity Analysis of Integer Programs
.png){kind=icon}
PRE
AI
DOI：10.1007/s10817-026-09751-2.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
存在几种自动推断整数程序运行时或资源界限的方法。本文研究周期有理可解循环（prs-循环）的子类，其中关于运行时和变量值大小的相关问题是可判定的，因此我们可以获得针对此类子类的完整技术。我们展示了如何将这些结果用于任意一般整数程序的复杂性分析。为此，我们提出了一种模块化方法，该方法计算对应于prs-循环的子程序的局部运行时和大小界限。然后，这些局部界限被提升为整个整数程序的全局运行时和大小界限。此外，我们引入了几种技术来将较大的程序转换为prs-循环，以扩大该方法的应用范围。该过程的强大功能通过我们在复杂性分析工具KoAT中的实现得以展示。
Keyword:
Automated Complexity Analysis
Runtime Bounds
Size Bounds
Decidability
Integer Programs
