Control-flow analysis in cubic time

Flemming Nielson, Helmut Seidl

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations

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 languageEnglish
Title of host publicationProgramming Languages and Systems - 10th European Symposium on Programming, ESOP 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001, Proceedings
EditorsDavid Sands
PublisherSpringer Verlag
Pages252-268
Number of pages17
ISBN (Print)3540418628
StatePublished - 2001
Externally publishedYes
Event10th European Symposium on Programming, ESOP 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 - Genova, Italy
Duration: 2 Apr 20016 Apr 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2028
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th European Symposium on Programming, ESOP 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001
Country/TerritoryItaly
CityGenova
Period2/04/016/04/01

Keywords

  • 0-CFA
  • Ambient calculus
  • Horn clauses with sharing
  • Program analysis
  • Tiling of Horn clauses
  • π-calculus

Fingerprint

Dive into the research topics of 'Control-flow analysis in cubic time'. Together they form a unique fingerprint.

Cite this