Termination Analysis of Linear-Constraint Programs

Abstract

This paper aims to provide 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 paper 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 paper also discusses non-termination witnesses, used to prove that a program will not halt. The authors examine the algorithmic and complexity aspects of these methods, showing how different approaches offer a trade-off between expressive power and computational complexity. The paper 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.