On Hierarchical Communication Topologies in the \pi -calculus
Lists
Only you see this
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},
}| A Type System for proving Depth Boundedness in the pi-calculus | arXiv · 2015 |
| Safety Verification of Asynchronous Pushdown Systems with Shaped Stacks | arXiv · 2014 |
| Leafy automata for higher-order concurrency | arXiv · 2021 |
| CCS for Trees | arXiv · 2013 |
| Weak and Nested Class Memory Automata | arXiv · 2014 |
| Hide and New in the Pi-Calculus | arXiv · 2012 |