Hardness results for weak bisimilarity of simple process algebras
Jitka StříAbrná · Electronic Notes in Theoretical Computer Science · 1998
We do not know whether weak bisimilarity (denoted ≈) is decidable for general BPA and BPP but we may try to estimate what would be a least complexity of a decision procedure that might exist. That is achieved by taking problems complete for some complexity classes and reducing them to ≈. In this way we will show that the problem of deciding weak bisimilarity would be NP-hard for BPP, and PSPACE-hard for BPA.