User: Guest  Login
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