Matching in the Pi-Calculus

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

Full description

Saved in:
Bibliographic Details
Published in:Electronic proceedings in theoretical computer science 2014-08, Vol.160 (Proc. EXPRESS/SOS 2014), p.16-29
Main Authors: Peters, Kirstin, Yonova-Karbe, Tsvetelina, Nestmann, Uwe
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2075-2180
2075-2180
DOI:10.4204/EPTCS.160.3