|
|||||
|
|
Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time |
|
| Authors: | Antonín Ku era Richard Mayr |
| Affiliation: | a Faculty of Informatics, Masaryk University, Botanická 68a, 60200 Brno, Czech Republic b LIAFA-Université Denis Diderot-Case 7014-2, place Jussieu, F-75251 Paris, Cedex 05, France |
| Abstract: | We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes and normed basic parallel processes (normed BPP). To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems. |
| Keywords: | Concurrency Infinite-state systems Process algebras Verification Bisimulation |
| 本文献已被 ScienceDirect 等数据库收录！ | |