Unique parallel decomposition in branching and weak bisimulation semantics

DOI10.1016/J.TCS.2015.10.013zbMATH Open1332.68159arXiv1205.2117OpenAlexW1829189314MaRDI QIDQ896916FDOQ896916

Authors: Bas Luttik 

Publication date: 15 December 2015

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

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.

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

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 \(\pi\)-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

zbMATH Keywords

process calculusbranching bisimilarityunique 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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Realisability of global models of interaction
• Title not available (Why is that?)
• Unique parallel decomposition in branching and weak bisimulation semantics
• Decomposition orders -- another generalisation of the fundamental theorem of arithmetic

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)