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 $\pi$ -calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of $\mbox{\em Horn clauses with sharing}$ and the $\mbox{\em use of tiling of Horn clauses}$ , for reducing the worst-case complexity of analyses. Applying these techniques to the $\pi$ -calculus and the ambient calculus we reduce the complexity from $\mathcal {O}(n^{5})$ to $\mathcal{O}(n^{3})$ in both cases.

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com