Book chapter · Conference paper
Control-flow analysis in cubic time
In
Esop 2001 - European Symposium on Programming, Genova, Italy, April 2-6
—
2001, pp. 252-268
Abstract
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 Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n5) to O(n3) in both cases.
| Language: | English |
|---|---|
| Publisher: | Springer Verlag |
| Year: | 2001 |
| Pages: | 252-268 |
| Proceedings: | European Symposium on Programming |
| ISBN: | 3540418628 , 3540453091 , 9783540418627 and 9783540453093 |
| ISSN: | 03029743 |
| Types: | Book chapter and Conference paper |
| DOI: | 10.1007/3-540-45309-1_17 |
| ORCIDs: | Nielson, Flemming |
