On linear recurrence sequences and loop termination (a survey)

Joel Ouaknine and James Worrell

A sequence of real numbers is said to be positive if all terms are positive, and ultimately positive if all but finitely many terms are positive. In this article we survey recent progress on long-standing open problems concerning deciding the positivity and ultimate positivity of integer linear recurrence sequences. We briefly discuss some of the many contexts in which these problems arise, and relate them to the well-known Skolem Problem, which asks whether a given linear recurrence sequence has a zero term. We also highlight some of the mathematical techniques that have been used to obtain decision procedures for these problems, pointing out obstacles to further progress.

In the second half of this survey we move on to closely related questions concerning the termination of linear while loops. This is a well-studied subject in software verification and by now there is rich toolkit of techniques to prove termination in practice. However the decidability of termination for some of the most basic types of loop remains open. Here again we discuss recent progress and remaining open problems.

ACM SIGLOG News 2(2), 2015. 9 pages.

PDF © 2015 Joel Ouaknine and James Worrell.