Unique parallel decomposition in branching and weak bisimulation semantics

DOI10.1016/J.TCS.2015.10.013MaRDI QIDQ896916zbMATH OpenOpenAlexFDO

Authors Bas Luttik

Publication date 15 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

branching bisimilarityprocess calculusunique parallel decompositionweak bisimilarity

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We consider the property of unique parallel decomposition modulo branching and weak bisimilarity. First, we show that infinite behaviours may fail to have parallel decompositions at all. Then, we prove that totally normed behaviours always have parallel decompositions, but that these are not necessarily unique. Finally, we establish that weakly bounded behaviours have unique parallel decompositions. We derive the latter result from a general theorem about unique decompositions in partial commutative monoids.

Recommendations

• Unique parallel decomposition in branching and weak bisimulation semantics
• Unique parallel decomposition for the \(\pi\)-calculus
• On unique decomposition of processes in the applied -calculus
• On the existence and decidability of unique decompositions of processes in the applied \(\pi\)-calculus
• Decomposition orders -- another generalisation of the fundamental theorem of arithmetic

Cites work

• A Distribution Law for CCS and a New Congruence Result for the pi-calculus
• A finite equational base for CCS with left merge and communication merge
• A geometric approach to the problem of unique decomposition of processes
• Branching bisimilarity is an equivalence indeed!
• Branching time and abstraction in bisimulation semantics
• CCS with Hennessy's merge has no finite-equational axiomatization
• Decomposition orders -- another generalisation of the fundamental theorem of arithmetic
• Distributed bisimulations
• scientific article; zbMATH DE number 1670866 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 48157 (Why is no real title available?)
• scientific article; zbMATH DE number 177854 (Why is no real title available?)
• scientific article; zbMATH DE number 1142329 (Why is no real title available?)
• scientific article; zbMATH DE number 1405656 (Why is no real title available?)
• Normed processes, unique decomposition, and complexity of bisimulation equivalences
• On the expressiveness and decidability of higher-order process calculi
• On unique decomposition of processes in the applied -calculus
• Proving termination with multiset orderings
• Unique decomposition of processes
• Unique parallel decomposition in branching and weak bisimulation semantics

Cited in

(7)

• Decomposition orders -- another generalisation of the fundamental theorem of arithmetic
• Unique parallel decomposition in branching and weak bisimulation semantics
• Distribution of behaviour into parallel communicating subsystems
• Unique parallel decomposition for the \(\pi\)-calculus
• Realisability of global models of interaction
• Non finite axiomatisability of weak bisimulation-based congruences
• Axiomatising weak bisimulation congruences over CCS with left merge and communication merge

This page was built for publication: Unique parallel decomposition in branching and weak bisimulation semantics

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