Flemming Nielson and Helmut Seidl. Control-Flow Analysis in Cubic Time. In David Sands, editor, Programming Languages and Systems, volume 2028 of Lecture Notes in Computer Science, pages 252-268, Genova, Italy, April 2001. Springer.
It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the -calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of
and the
, for reducing the worst-case complexity of analyses. Applying these techniques to the
-calculus and the ambient calculus we reduce the complexity from
to
in both cases.
Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com