Weak Bisimilarity with Infinite-State Systems can be Decided in Polynomial Time
Abstract:
We prove that weak bisimilarity is decidable in polynomial time between BPA and finite-state processes, and between normed BPP and finite-state processes. To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity with infinite-state systems.
Keywords:
concurrency; infinite-state systems; process algebras; verification; bisimulation