Helmut Seidl. Fast and Simple Nested Fixpoints. , volume 59 of Forschungsbericht, pages 303-308, 1996. Inf. Process. Lett..

We give an alternative proof of the result of Long et al. (1994) that nested fixpoint expressions e of alternation depth d > 1 can be evaluated over a complete lattice of height h in time O(d · (h · ¦e¦/(d − 1))upper left cornerd/2upper right corner+1). The advantage of our proof is that it is both extremely short and extremely simple. We give an alternative proof of the result of Long et al. in [12] that nested fixpoint expressions $e$ of alternation depth $d>1$ can be evaluated over a complete lattice of height $h$ in time $O(d \cdot (\frac{h \cdot |e|}{d-1})^{\lceil d/2 \rceil +1})$. The advantage of our proof is that it is both extremely short and extremely simple.

Reference: Bibtex