Ranking Functions for Loops with Disjunctive Exit-Conditions
Rody Kersten, M.C.J.D. van Eekelen · 2011
Abstract. Finding ranking functions for the loops in a program is a prerequisite for proving its termination and analysing its resource usage. From its ranking function one easily derives a symbolic upper bound on the number of iterations of a loop. Such symbolic loop bounds can be used to derive concrete time and memory-usage bounds for complete programs. This paper builds upon an earlier paper in which a polynomial interpolation based ranking function inference method is introduced for loops with exit conditions that are expressions in propositional logic over arithmetical (in)equalities. We show that this earlier method is not applicable for certain loops: loops in which so-called condition jumping can occur. We define condition jumping and give an algorithm to detect it using symbolic execution and an SMT solver. We show how the earlier method can be adapted to be applicable also in the presence of condition jumping. As a result polynomial interpolation can be applied on a larger class of programs to infer polynomial ranking functions.