Comparing the expressiveness of the π-calculus and CCS

Rob van Glabbeek

doi:10.1007/978-3-030-99336-8_20

Comparing the expressiveness of the π-calculus and CCS

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Programming 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
Editors	Ilya Sergey
Place of Publication	Cham
Publisher	Springer
Pages	548-574
Number of pages	27
ISBN (Electronic)	978-3-030-99336-8
ISBN (Print)	978-3-030-99335-1
DOIs	https://doi.org/10.1007/978-3-030-99336-8_20
Publication status	Published - 29 Mar 2022
Event	31st European Symposium on Programming - Munich, Germany Duration: 2 Apr 2022 → 7 Apr 2022 Conference number: 31 https://etaps.org/2022/esop

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Cham
Volume	13240
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	31st European Symposium on Programming
Abbreviated title	ESOP 2022
Country/Territory	Germany
City	Munich
Period	2/04/22 → 7/04/22
Internet address	https://etaps.org/2022/esop

Access to Document

10.1007/978-3-030-99336-8_20Licence: Creative Commons: Attribution (CC-BY)

Comparing the Expressiveness_VAN GLABBEEK_DOA23122021_VOR_CC-BYFinal published version, 563 KBLicence: Creative Commons: Attribution (CC-BY)

https://link.springer.com/chapter/10.1007/978-3-030-99336-8_20Licence: Creative Commons: Attribution (CC-BY)

Cite this

van Glabbeek, R. (2022). Comparing the expressiveness of the π-calculus and CCS. In I. Sergey (Ed.), Programming 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 (pp. 548-574). (Lecture Notes in Computer Science; Vol. 13240). Springer. https://doi.org/10.1007/978-3-030-99336-8_20

van Glabbeek, Rob. / Comparing the expressiveness of the π-calculus and CCS. Programming 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. editor / Ilya Sergey. Cham : Springer, 2022. pp. 548-574 (Lecture Notes in Computer Science).

@inproceedings{5bd4be19f81f47699f137ffb5736d2b3,

title = "Comparing the expressiveness of the π-calculus and CCS",

abstract = "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{\^o}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.",

author = "{van Glabbeek}, Rob",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s).; 31st European Symposium on Programming, ESOP 2022 ; Conference date: 02-04-2022 Through 07-04-2022",

year = "2022",

month = mar,

day = "29",

doi = "10.1007/978-3-030-99336-8_20",

language = "English",

isbn = "978-3-030-99335-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "548--574",

editor = "Ilya Sergey",

booktitle = "Programming 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",

address = "United Kingdom",

url = "https://etaps.org/2022/esop",

}

van Glabbeek, R 2022, Comparing the expressiveness of the π-calculus and CCS. in I Sergey (ed.), Programming 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. Lecture Notes in Computer Science, vol. 13240, Springer, Cham, pp. 548-574, 31st European Symposium on Programming, Munich, Bavaria, Germany, 2/04/22. https://doi.org/10.1007/978-3-030-99336-8_20

Comparing the expressiveness of the π-calculus and CCS. / van Glabbeek, Rob.
Programming 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. ed. / Ilya Sergey. Cham: Springer, 2022. p. 548-574 (Lecture Notes in Computer Science; Vol. 13240).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Comparing the expressiveness of the π-calculus and CCS

AU - van Glabbeek, Rob

N1 - Conference code: 31

PY - 2022/3/29

Y1 - 2022/3/29

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

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

U2 - 10.1007/978-3-030-99336-8_20

DO - 10.1007/978-3-030-99336-8_20

M3 - Conference contribution

SN - 978-3-030-99335-1

T3 - Lecture Notes in Computer Science

SP - 548

EP - 574

BT - Programming 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

A2 - Sergey, Ilya

PB - Springer

CY - Cham

T2 - 31st European Symposium on Programming

Y2 - 2 April 2022 through 7 April 2022

ER -

van Glabbeek R. Comparing the expressiveness of the π-calculus and CCS. In Sergey I, editor, Programming 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. Cham: Springer. 2022. p. 548-574. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-99336-8_20

Comparing the expressiveness of the π-calculus and CCS

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this