Comparing the expressiveness of the π-calculus and CCS

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

This paper shows that the π-calculus with implicit matching is no more expressive than CCSγ, a variant of CCS in which the result of a synchronisation of two actions is itself an action subject to relabelling or restriction, rather than the silent action τ. This is done by exhibiting a compositional translation from the π-calculus with implicit matching to CCSγ that is valid up to strong barbed bisimilarity.

The full π-calculus can be similarly expressed in CCSγ enriched with the triggering operation of MEIJE.

I also show that these results cannot be recreated with CCS in the rôle of CCSγ, not even up to reduction equivalence, and not even for the asynchronous π-calculus without restriction or replication.

Finally I observe that CCS cannot be encoded in the π-calculus.
Original languageEnglish
Title of host publicationProgramming Languages and Systems: 31st European Symposium on Programming, ESOP 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2–7, 2022, Proceedings
EditorsIlya Sergey
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Pages548-574
Number of pages27
ISBN (Electronic)978-3-030-99336-8
ISBN (Print)978-3-030-99335-1
DOIs
Publication statusPublished - 29 Mar 2022
Event31st European Symposium on Programming - Munich, Germany
Duration: 2 Apr 20227 Apr 2022
Conference number: 31
https://etaps.org/2022/esop

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume13240
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference31st European Symposium on Programming
Abbreviated titleESOP 2022
Country/TerritoryGermany
CityMunich
Period2/04/227/04/22
Internet address

Fingerprint

Dive into the research topics of 'Comparing the expressiveness of the π-calculus and CCS'. Together they form a unique fingerprint.

Cite this