We argued that Algorithm 9.25 converges if the framework is monotone and of finite height. Here is an example of a framework that shows monotonicity is essential; finite height is not enough. The...

We argued that Algorithm 9.25 converges if the framework is monotone and of finite height. Here is an example of a framework that shows monotonicity is essential; finite height is not enough. The domain V is {1,2}, the meet operator is min, and the set of functions F is only the identity (/j) and the "switch" function (fs(x) — 3 — x) that swaps 1 and 2.


a) Show that this framework is of finite height but not monotone.

b) Give an example of a flow graph and assignment of transfer functions so that Algorithm 9.25 does not converge.

Algorithm 9.25

Algorithm 9.25 : Iterative solution to general data-flow frameworks.