Weak Bisimilarity with Infinite-State Systems can be Decided in Polynomial Time

Title:: Weak Bisimilarity with Infinite-State Systems can be Decided in Polynomial Time
Document type:: Technical Report
Author(s):: Antonin Kucera; Richard Mayr
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
Year:: 1998
Year / month:: 1998-12-01 00:00:00
Pages:: 30
BibTeX

Occurrences: