2APL: Expressiveness in Concurrency: The Case of Session-Typed Processes

The expressiveness of models of concurrency has intrigued researchers for a number of years now. In particular, studies on the expressiveness of process calculi (such as CCS and the pi-calculus) have had considerable impact. The interest is in questions such as, e.g., under what conditions two process languages C and C' can express the same behaviors? It is fair to say that formal answers to such questions are (still) quite relevant in concurrency theory at large.

Now, process models are increasingly being developed with (behavioral) typed systems that discipline the behavior of processes. This raises, once again, the issue of their expressiveness, now with an additional dimension (i.e., types) playing an explicit role. We would like to know, e.g., when is that two typed process languages L and L' can express the same behaviors, but also how their associated type systems influence expressiveness relations.

In this talk, I will discuss the general problem of "typed expressiveness" in concurrency. In particular, I will describe recent works in which we formally compare the expressiveness of the pi-calculus coupled with session type systems for structured communications. If time permits, I will discuss some open challenges.

hosted by