Conditions for incremental iteration: Examples and counterexamples

AbstractIterative algorithms for fixed points of systems of equations are of importance in graph algorithms, data flow analysis and other areas of computer science. One commonly-sought extension is an incremental update procedure, which responds to small changes in problem parameters by obtaining the new fixed point from perturbation of the previous solution. One approach which has been suggested is to iterate for the new fixed point beginning at that previous solution, possibly after some small modifications. Our results show that this procedure is not in general correct. We give sufficient conditions for correctness, and give counterexamples in Boolean algebra and data flow analysis showing that difficulties with the proposed algorithms can occur in practice