Complexity of checking bisimilarity between sequential and parallel processes

DOI10.1007/978-3-642-40313-2_28MaRDI QIDQ2849919zbMATH OpenOpenAlexFDO

Authors Wojciech Czerwiński, Martin Kot, Zdeněk Sawa, Petr Jančar

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40313-2_28

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• On the complexity of bisimulation problems for basic parallel processes
• Decidability of bisimilarity for one-counter processes.
• The complexity of bisimilarity-checking for one-counter processes.
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• Deciding bisimilarity between BPA and BPP processes.

Cited in

(4)

• A complexity analysis of bisimilarity for value-passing processes
• Deciding Bisimilarity of Full BPA Processes Locally
• Sequencing and intermediate acceptance: Axiomatisation and decidability of bisimilarity
• Correctness and concurrent complexity of the black-white bakery algorithm

This page was built for publication: Complexity of checking bisimilarity between sequential and parallel processes

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