Conditions for incremental iteration: Examples and counterexamples (Q1113663)

Given a problem (e.g., that of data-flow analysis) formulated as a set of (generally recursive) equations \(X=A(X)\), its solution can be found by iterative algorithms as an extreme (here the least) fixed point \(X^ m\) of the system as above. It is often too expensive to fully reanalyse a system each time it changes from \(X=A(X)\) onto \(Y=B(Y)\). The paper is concerned with correctness of the following strategy: use iteration and recompute the desired solution incrementally, by restarting iterations of B from \(X^*\) (or from some iterative \(X^ i=A^ i(\perp))\) rather than from the smallest element \(\perp\). Sufficient conditions for correctness of this incremental recomputations are given and, moreover, it is shown that these incremental iterations involve at most as many applications of B to attain its fixed point as standard successive applications of B starting with \(\perp\), i.e., \(<B^ j(A^ i(\perp))>_{j\to \infty}\) attains its limit at least as rapidly as the sequence \(<B^ j(\perp)>_{j\to \infty}\). A number of motivating/illustrating (counter) examples is given.