Scholarlink

<p>There exist several approaches to infer runtime or resource bounds for integer programs automatically. In this paper, we study the subclass of <i>periodic rational solvable loops (prs-loops)</i>, where questions regarding the runtime and the size of variable values are decidable and where we can therefore obtain techniques that are “complete” for such subclasses. We show how to use these results for the complexity analysis of arbitrary general integer programs. To this end, we present a modular approach which computes local runtime and size bounds for subprograms which correspond to <i>prs</i>-loops. These local bounds are then lifted to global runtime and size bounds for the whole integer program. Furthermore, we introduce several techniques to transform larger programs into <i>prs</i>-loops to increase the scope of the approach. The power of the procedure is shown by our implementation in the complexity analysis tool <Emphasis FontCategory="SansSerif">KoAT</Emphasis>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Targeting Completeness: Automated Complexity Analysis of Integer Programs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月4日

查看全文
  • Nils Lommen,
  • Éléanore Meyer,
  • Jürgen Giesl

摘要

There exist several approaches to infer runtime or resource bounds for integer programs automatically. In this paper, we study the subclass of periodic rational solvable loops (prs-loops), where questions regarding the runtime and the size of variable values are decidable and where we can therefore obtain techniques that are “complete” for such subclasses. We show how to use these results for the complexity analysis of arbitrary general integer programs. To this end, we present a modular approach which computes local runtime and size bounds for subprograms which correspond to prs-loops. These local bounds are then lifted to global runtime and size bounds for the whole integer program. Furthermore, we introduce several techniques to transform larger programs into prs-loops to increase the scope of the approach. The power of the procedure is shown by our implementation in the complexity analysis tool KoAT.