Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time

zbMATH Open1272.68309MaRDI QIDQ2851063FDOQ2851063

Authors: Martin Kot, Zdeněk Sawa 

Publication date: 2 October 2013

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S157106610505200X

Recommendations

• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• scientific article; zbMATH DE number 1361133
• Normed BPA vs. Normed BPP Revisited
• CONCUR 2004 - Concurrency Theory

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)

Cited In (6)

• Title not available (Why is that?)
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system
• Mathematical Foundations of Computer Science 2003
• Bisimilarity on basic parallel processes

This page was built for publication: Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time

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