## User login## Navigation |
## Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus
Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus
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.Quite an important result for those who care about pi. The others may just enjoy the use of symmetry in the proof. As CiteSeer is down this weekend, I used a link to CiteBase. [on edit: CiteSeer is back] |
## Browse archives## Active forum topics |

## Recent comments

3 hours 41 min ago

14 hours 37 min ago

15 hours 52 min ago

16 hours 1 min ago

17 hours 52 sec ago

17 hours 19 min ago

19 hours 46 min ago

21 hours 14 min ago

22 hours 49 min ago

1 day 28 min ago