On the Decidability of Fragments of the Asynchronous Pi-Calculus - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2001

On the Decidability of Fragments of the Asynchronous Pi-Calculus

Charles Meyssonnier
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-4241.pdf (283.91 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00072346 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00072346 , version 1

Citer

Roberto M. Amadio, Charles Meyssonnier. On the Decidability of Fragments of the Asynchronous Pi-Calculus. RR-4241, INRIA. 2001. ⟨inria-00072346⟩
117 Consultations
198 Téléchargements

Partager

Gmail Facebook X LinkedIn More