Fixed-Point Computations over Functions on Integers with Operations min, max and plus.
Yoshinori Tanabe, Masami Hagiya · 2009
Various kinds of graph problems, including shortest path computation, proof-number search, dataflow analysis, etc., can be solved by fixed-point computations over functions defined on natural numbers or integers. In this paper, we prove that fixed-point computations are possible for the algebra Z ∞ = Z∪{∞,−∞}, which has the operators min, max and plus. Since Z ∞ is not well-ordered, we formulate a kind of acceleration technique to guarantee termination of fixed-point computations. 1