Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus
The Asynchronous ¿-calculus, as recently proposed by Boudol and, independently, by Honda and Tokoro, is a subset of the ¿-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 ¿-calculus. We show that this is not possible, i.e. there does not exist any uniform, parallel-preserving, translation from the ¿-calculus into the asynchronous ¿-calculus, up to any "reasonable" notion of equivalence. This result is based on the incapablity of the asynchronous ¿-calculus of breaking certain symmetries possibly present in the initial communication graph. By similar arguments, we prove a separation result between the ¿-calculus and CCS.