Thomas Gawlitza, Jérôme Leroux, Jan Reineke, Helmut Seidl, Grégoire Sutre and Reinhard Wilhelm. Polynomial Precise Interval Analysis Revisited. In Susanne Albers, Helmut Alt and Stefan Näher, editors, Efficient Algorithms, pages 422-437, 2009. Springer, LNCS 5760.
We consider a class of arithmetic equations over the complete lattice of integers (extended with -∞ and ∞) and provide a polynomial time algorithm for computing least solutions. For systems of equations with addition and least upper bounds, this algorithm is a smooth generalization of the Bellman-Ford algorithm for computing the single source shortest path in presence of positive and negative edge weights. The method then is extended to deal with more general forms of operations as well as minima with constants. For the latter, a controlled widening is applied at loops where unbounded increase occurs. We apply this algorithm to construct a cubic time algorithm for the class of interval equations using least upper bounds, addition, intersection with constant intervals as well as multiplication.