Date: Wed 12 Jun
Time: 14.30
Place: room 214

Speaker: Catuscia Palamidessi
Title: Comparing the Expressive Power of Pi-Calculus, Asynchronous Pi-Calculus, and CCS

Abstract. Asynchronous pi-calculus, 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 showed by Boudol, and input-guarded choice, as shown recently by Nestmann and Pierce. A natural question is, then, whether or not it is possible to embed in it the full pi-calculus. In this talk, we argue that this is not possible, i.e. there does not exists any uniform, parallel-preserving, translation from the pi-calculus into asynchornous pi-calculus, up to any "reasonable" notion of equivalence. This result is based on the impossibility of asynchronous pi-calculus to break certain simmetries possibly present in the initial communication graph. By similar arguments, we prove a separation between the pi-calculus and CCS.