Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus
<|reference_start|>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.<|reference_end|>
@article{palamidessi1998comparing,
    title={Comparing the expressive power of the Synchronous and the Asynchronous
  pi-calculus},
    author={Catuscia Palamidessi},
    journal={Proc. of the 24th ACM Symposium on Principles of Programming
  Languages (POPL), pages 256--265, ACM, 1997},
    year={1998},
    archivePrefix={arXiv},
    eprint={cs/9809008},
    primaryClass={cs.PL cs.LO}
}