[Submitted on 8 Sep 2025 (v1), last revised 24 Jul 2026 (this version, v3)]

View PDF

Abstract:This paper provides an overview of techniques in termination analysis for programs with numerical variables and transitions defined by linear constraints. This subarea of program analysis is challenging due to the existence of undecidable problems, and this Survey systematically explores approaches that mitigate this inherent difficulty. These include foundational decidability results, the use of ranking functions, and disjunctive well-founded transition invariants. The Survey also discusses non-termination witnesses, used to prove that a program will not halt. We examine the algorithmic and complexity aspects of these methods, showing how different approaches offer a trade-off between expressive power and computational complexity. The Survey does not discuss how termination analysis is performed on real-world programming languages, nor does it consider more expressive abstract models that include non-linear arithmetic, probabilistic choice, or term rewriting systems.

Submission history

From: Samir Genaim [view email]
[v1] Mon, 8 Sep 2025 14:40:34 UTC (122 KB)
[v2] Sun, 25 Jan 2026 21:15:08 UTC (134 KB)
[v3] Fri, 24 Jul 2026 10:59:54 UTC (135 KB)