Computer Science – Programming Languages
Scientific paper
1998-09-02
Proc. of the 24th ACM Symposium on Principles of Programming Languages (POPL), pages 256--265, ACM, 1997
Computer Science
Programming Languages
10 pages. Proc. of the POPL'97 symposium
Scientific paper
The Asynchronous pi-calculus, as recently proposed by Boudol and, independently, by Honda and Tokoro, is a subset of the pi-calculus 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 Boudol, and input-guarded choice, as shown recently by Nestmann and Pierce. A natural question arises, then, whether or not it is possible to embed in it the full pi-calculus. We show that this is not possible, i.e. there does not exist any uniform, parallel-preserving, translation from the pi-calculus into the asynchronous pi-calculus, up to any ``reasonable'' notion of equivalence. This result is based on the incapablity of the asynchronous pi-calculus of breaking certain symmetries possibly present in the initial communication graph. By similar arguments, we prove a separation result between the pi-calculus and CCS.
No associations
LandOfFree
Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-263759