HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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

Catuscia Palamidessi 1
1 COMETE - Concurrency, Mobility and Transactions
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Document type :
Journal articles
Complete list of metadata

Contributor : Catuscia Palamidessi Connect in order to contact the contributor
Submitted on : Sunday, December 23, 2007 - 6:10:07 PM
Last modification on : Thursday, January 20, 2022 - 5:29:35 PM
Long-term archiving on: : Tuesday, April 13, 2010 - 3:32:17 PM


Files produced by the author(s)




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⟩



Record views


Files downloads