Normed Processes, Unique Decomposition, and Complexity of Bisimulation Equivalences

DOI10.1016/j.entcs.2009.05.028zbMath1347.68264OpenAlexW2044322035MaRDI QIDQ5179048

Sibylle Fröschle, Sławomir Lasota

Publication date: 19 March 2015

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2009.05.028

zbMATH Keywords

weak bisimulationbranching bisimulationbisimulation equivalenceunique decompositionbasic parallel processesdistributed bisimulation

Mathematics Subject Classification ID

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

Related Items (8)

Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems ⋮ Partially-Commutative Context-Free Processes ⋮ Unique parallel decomposition in branching and weak bisimulation semantics ⋮ Partially-commutative context-free processes: expressibility and tractability ⋮ Decidability of branching bisimulation on normed commutative context-free processes ⋮ Decidability of Branching Bisimulation on Normed Commutative Context-Free Processes ⋮ Bisimilarity on basic parallel processes ⋮ Non-interleaving bisimulation equivalences on basic parallel processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronization trees
• Branching bisimilarity is an equivalence indeed!
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• Decomposition orders -- another generalisation of the fundamental theorem of arithmetic
• Commutative grammars: The complexity of uniform word problems
• Branching time and abstraction in bisimulation semantics
• Complexity of weak bisimilarity and regularity for BPA and BPP
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Mathematical Foundations of Computer Science 2003

This page was built for publication: Normed Processes, Unique Decomposition, and Complexity of Bisimulation Equivalences