Title :
On the complexity of bisimilarity of normed probabilistic context-free processes
Author :
Huynh, Dung T. ; Tian, Lu
Author_Institution :
Comput. Sci. Program, Texas Univ., Dallas, TX, USA
Abstract :
We show that probabilistic bisimulation equivalence for normed probabilistic context-free processes is in Σ2p , 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
Keywords :
computational complexity; context-free languages; decidability; graph theory; minimisation; probability; PSPACE; bisimilarity complexity; context-free process graph; minimization; normed probabilistic context-free processes; polynomial-time hierarchy; probabilistic bisimulation equivalence; Computer science; Polynomials; Upper bound; Writing;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315412
