Inferring Lower Runtime Bounds for Integer Programs

doi:10.1145/3410331

Inferring Lower Runtime Bounds for Integer Programs

2020-10-15

0

OA

AI

DOI：10.1145/3410331

原文链接

查看原文

摘要

En 中文

我们提出了一种推断整数程序最坏情况运行时复杂度下界的技术，与以往研究不同，我们的方法不受限于尾递归。我们的技术使用迭代、下界逼近的程序简化框架来构建程序执行过程的符号表示。简化的核心是一种基于递归求解和排名函数变体的（下界逼近）程序加速方法。随后，我们使用一种专用演算和SMT编码，从简化后的程序推导出渐近下界。我们在工具LoAT中实现了该技术，并证明它能够为一大类示例推断出非平凡的下界。

Inferring Lower Runtime Bounds for Integer Programs

摘要

AI总结

期刊

机构

引用论文