Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus

Computer Science – Programming Languages

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-263759

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.