A fundamental problem in program verification concerns the termination
of simple linear loops of the form:
x := u ; WHILE Bx ≥ c DO {x := Ax + a}
where x is a vector of variables, u, a, and c
are integer vectors, and A and B are integer matrices. Assuming the matrix A is
diagonalisable, we give a decision procedure for the problem of whether, for all initial integer
vectors u, such a loop terminates. The correctness of our algorithm relies on
sophisticated tools from algebraic and analytic number theory, Diophantine geometry, and real algebraic
geometry.
To the best of our knowledge, this is the first substantial advance on a 10-year-old open problem of
Tiwari and Braverman.
Proceedings of SODA 15, 2015. 13 pages.
PDF
© 2015 SIAM.