On Hierarchical Communication Topologies in the \pi -calculus

Emanuele D'Osualdo, C.-h. Luke Ong

Abstract

This paper is concerned with the shape invariants satisfied by the communication topology of $$\pi \text {-term}$$ s, and the automatic inference of these invariants. A $$\pi \text {-term}$$ P is hierarchical if there is a finite forest $$\mathcal {T}$$ such that the communication topology of every term reachable from P satisfies a $$\mathcal {T}$$ -shaped invariant. We design a static analysis to prove a term hierarchical by means of a novel type system that enjoys decidable inference. The soundness proof of the type system employs a non-standard view of $$\pi \text {-calculus}$$ reactions. The coverability problem for hierarchical terms is decidable. This is proved by showing that every hierarchical term is depth-bounded, an undecidable property known in the literature. We thus obtain an expressive static fragment of the $$\pi \text {-calculus}$$ with decidable safety verification problems.
BibTeX
@inproceedings{dosualdo2016hierarchical,
  author = {Emanuele D'Osualdo and C.-H. Luke Ong},
  title = {{On Hierarchical Communication Topologies in the \textbackslash\{\}pi -calculus}},
  booktitle = {ESOP},
  year = {2016},
  doi = {10.1007/978-3-662-49498-1\_7},
}
Figure