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.
| Original language | English |
|---|---|
| Title of host publication | ESOP 2001 - European Symposium On Programming, Genova, Italy, April 2-6 |
| Publisher | Springer Verlag |
| Publication date | 2001 |
| Pages | 252-268 |
| Publication status | Published - 2001 |
| Event | 10th European Symposium on Programming - Genova, Italy Duration: 2 Apr 2001 → 6 Apr 2001 Conference number: 10 |
Conference
| Conference | 10th European Symposium on Programming |
|---|---|
| Number | 10 |
| Country/Territory | Italy |
| City | Genova |
| Period | 02/04/2001 → 06/04/2001 |
| Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2028 |
| ISSN | 0302-9743 |