Helmut Seidl. Fast and Simple Nested Fixpoints. Universität Trier, Mathematik/Informatik, Forschungsbericht, 96-05, 1996.

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.

Download: PDF Reference: Bibtex