Comparing the expressiveness of the -calculus and CCS

DOI10.1007/978-3-030-99336-8_20zbMATH Open1528.68258arXiv2203.11519OpenAlexW4225805607MaRDI QIDQ6166803FDOQ6166803

Authors: Rob van Glabbeek 

Publication date: 3 August 2023

Published in: Programming Languages and Systems (Search for Journal in Brave)

Abstract: This paper shows that the $pi$-calculus with implicit matching is no more expressive than CCS$gamma$, 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 $au$. This is done by exhibiting a compositional translation from the $pi$-calculus with implicit matching to CCS$gamma$ that is valid up to strong barbed bisimilarity. The full $pi$-calculus can be similarly expressed in CCS$gamma$ enriched with the triggering operation of Meije. I also show that these results cannot be recreated with CCS in the role of CCS$gamma$, not even up to reduction equivalence, and not even for the asynchronous $pi$-calculus without restriction or replication. Finally I observe that CCS cannot be encoded in the $pi$-calculus.

Full work available at URL: https://arxiv.org/abs/2203.11519

Recommendations

• Comparing the expressive power of the synchronous and asynchronous \(\pi\)-calculi
• scientific article; zbMATH DE number 2059568
• Matching in the pi-calculus
• On the expressiveness of interaction
• Matching systems for concurrent calculi

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Higher-level synchronising devices in Meije-SCCS
• Title not available (Why is that?)
• Functions as processes
• Title not available (Why is that?)
• Modal logics for mobile processes
• Calculi for synchrony and asynchrony
• A calculus of mobile processes. I
• A calculus of mobile processes. II
• Branching time and abstraction in bisimulation semantics
• A Theory of Communicating Sequential Processes
• Process Algebra
• Title not available (Why is that?)
• Algèbre de processus et synchronisation
• The \(\pi\)-calculus: A theory of mobile processes
• Modeling and analysis of communicating systems
• Barbed bisimulation
• Towards a unified approach to encodability and separation results for process calculi
• On cool congruence formats for weak bisimulations
• Symbolic bisimulations
• A theory of bisimulation for the \(\pi\)-calculus
• On distributability in process calculi
• Title not available (Why is that?)
• Welcome to the Jungle: A Subjective Guide to Mobile Process Calculi
• Musings on encodings and expressiveness
• A \(\pi\)-calculus with explicit substitutions
• A theory of encodings and expressiveness (extended abstract)
• On the expressiveness of choice quantification
• CSP is expressive enough for \(\pi\)
• Full abstraction for expressiveness: history, myths and facts
• General conditions for full abstraction

Cited In (3)

• On the expressiveness of mixed choice sessions
• Comparing the expressive power of the synchronous and asynchronous \(\pi\)-calculi
• Mixed choice in session types

This page was built for publication: Comparing the expressiveness of the \(\pi \)-calculus and CCS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166803)