**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.