Comparing the expressiveness of the -calculus and CCS

DOI10.1007/978-3-030-99336-8_20MaRDI QIDQ6166803zbMATH OpenOpenAlexFDO

Authors Rob van Glabbeek

Publication date 3 August 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(3)

• Comparing the expressive power of the synchronous and asynchronous \(\pi\)-calculi
• On the expressiveness of mixed choice sessions
• 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)