Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculi

Catuscia Palamidessi 1
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : The Asynchronous $\pi$-calculus, proposed by Honda and Tokoro (1991) and, independently, by Boudol (1992), is a subset of the $\pi$-calculus \cite{Milner:92:IC} which contains no explicit operators for choice and output-prefixing. The communication mechanism of this calculus, however, is powerful enough to simulate output-prefixing, as shown by Honda and Tokoro (1991) and by Boudol (1992), and input-guarded choice, as shown by Nestmann and Pierce (2000). A natural question arises, then, whether or not it is as expressive as the full $\pi$-calculus. We show that this is not the case. More precisely, we show that there does not exist any uniform, fully distributed translation from the $\pi$-calculus into the asynchronous $\pi$-calculus, up to any ''reasonable'' notion of equivalence. This result is based on the incapability of the asynchronous $\pi$-calculus to break certain symmetries possibly present in the initial communication graph. By similar arguments, we prove a separation result between the $\pi$-calculus and CCS, and between the $\pi$-calculus and the $\pi$-calculus with internal mobility, a subset of the $\pi$-calculus proposed by Sangiorgi where the output actions can only transmit private names.
Type de document :
Article dans une revue
Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2003, 13 (5), pp.685-719. 〈10.1017/S0960129503004043〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00201104
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 23 décembre 2007 - 18:10:07
Dernière modification le : jeudi 10 mai 2018 - 02:06:32
Document(s) archivé(s) le : mardi 13 avril 2010 - 15:32:17

Fichier

mscs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Catuscia Palamidessi. Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculi. Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2003, 13 (5), pp.685-719. 〈10.1017/S0960129503004043〉. 〈inria-00201104〉

Partager

Métriques

Consultations de la notice

615

Téléchargements de fichiers

273