Skip to Main content Skip to Navigation
New interface

On the Decidability of Fragments of the Asynchronous Pi-Calculus

Roberto M. Amadio 1 Charles Meyssonnier 
1 MIMOSA - Migration and mobility : semantics and applications
CRISAM - Inria Sophia Antipolis - Méditerranée , Université de Provence - Aix-Marseille 1, Mines Paris - PSL (École nationale supérieure des mines de Paris)
Abstract : We study the decidability of a reachability problem for various fragments of the asynchronous $\pi$-calculus. We consider the combination of three main features: name generation, name mobility, and unbounded control. We show that the combination of name generation with either name mobility or unbounded control leads to an undecidable fragment. On the other hand, we prove that name generation without name mobility and with bounded control is decidable by reduction to the coverability problem for Petri Nets.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 8:28:53 PM
Last modification on : Tuesday, October 25, 2022 - 4:23:50 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:44:52 PM


  • HAL Id : inria-00072346, version 1


Roberto M. Amadio, Charles Meyssonnier. On the Decidability of Fragments of the Asynchronous Pi-Calculus. RR-4241, INRIA. 2001. ⟨inria-00072346⟩



Record views


Files downloads