On the complexity of bisimilarity of normed probabilistic context-free processes
D.T. Huynh, Lu Tian · 2002
We show that probabilistic bisimulation equivalence for normed probabilistic context-free processes is in /spl Sigmasub 2sup p/, the second level of the polynomial-time hierarchy, and hence in PSPACE. We also show that minimization of a normed probabilistic context-free process graph with respect to probabilistic bisimulation equivalence is in PSPACE.>