It is known that a static analysis of pi-calculus can be done rather simply and also efficiently, i.e. in cubic time. Clearly, a static analysis should be as precise as possible. We show that it is not only desirable, but also possible to improve the precision of the analysis without worsening its asymptotic complexity. We illustrate the main principles of this efficient algorithm, we prove that it is indeed cubic and we also show that it is correct. The technique introduced here appears to be useful also for other applications, in particular, for the static analysis of languages that extend the pi-calculus.

Precise Analysis of pi-Calculus in Cubic Time

COLUSSI, LIVIO;FILE', GILBERTO;
2004

Abstract

It is known that a static analysis of pi-calculus can be done rather simply and also efficiently, i.e. in cubic time. Clearly, a static analysis should be as precise as possible. We show that it is not only desirable, but also possible to improve the precision of the analysis without worsening its asymptotic complexity. We illustrate the main principles of this efficient algorithm, we prove that it is indeed cubic and we also show that it is correct. The technique introduced here appears to be useful also for other applications, in particular, for the static analysis of languages that extend the pi-calculus.
2004
Exploring New Frontiers of Theoretical Informatics
3rd IFIP World Computer Congress
1402081405
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/1345244
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact