Matching in the Pi-Calculus

Kirstin Peters
(TU Berlin)
Tsvetelina Yonova-Karbe
(TU Berlin)
Uwe Nestmann
(TU Berlin)

We study whether, in the pi-calculus, the match prefix—a conditional operator testing two names for (syntactic) equality—is expressible via the other operators. Previously, Carbone and Maffeis proved that matching is not expressible this way under rather strong requirements (preservation and reflection of observables). Later on, Gorla developed a by now widely-tested set of criteria for encodings that allows much more freedom (e.g. instead of direct translations of observables it allows comparison of calculi with respect to reachability of successful states). In this paper, we offer a considerably stronger separation result on the non-expressibility of matching using only Gorla's relaxed requirements.

In Johannes Borgström and Silvia Crafa: Proceedings Combined 21st International Workshop on Expressiveness in Concurrency and 11th Workshop on Structural Operational Semantics (EXPRESS/SOS 2014), Rome, Italy, 1st September 2014, Electronic Proceedings in Theoretical Computer Science 160, pp. 16–29.
Published: 6th August 2014.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: