On the decidability of process equivalences for the π-calculus

✍ Scribed by Mads Dam

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 994 KB
• Volume: 183
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00325-8

✦ Synopsis

We present general results for showing process equivalences applied to the finite control fragment of the z-calculus decidable. Firstly, a Finite Reachability Theorem states that up to finite name spaces and up to a static normalisation procedure, the set of reachable agent expressions is finite. Secondly, a Boundedness Lemma shows that no potential computations are missed when name spaces are chosen large enough, but finite. We show how these results lead to decidability for a number of n-calculus equivalences such as strong or weak, late or early bismulation equivalence. Furthermore, for strong late equivalence we show how our techniques can be used to adapt the well-known PaigeTarjan algorithm. Strikingly, this results in a single exponential running time not much worse than the running time for the case of for instance CCS. Our results considerably strengthens previous results on decidable equivalences for parameter-passing process calculi.