Deciding Branching Bisimilarity of Normed Context-Free Processes Is in Σ2

We show that the problem of deciding branching bisimulation equivalence for normed context-free processes is in Σ^p₂, the second level of the polynomial-time hierarchy, and hence in PSPACE. We also show that minimization of normed context-free process graphs is in PSPACE.