## A polynomial algorithm for deciding bisimilarity of normed
context-free processes

**Yoram Hirshfeld, Mark Jerrum and Faron Moller**
*Dedicated to Robin Milner on the occasion of his 60th
birthday.*

*Abstract:* The previous best upper bound on the complexity
of deciding bisimilarity between normed context-free processes, due
to Huynh and Tian, is that the problem lies in *Sigma_2^P =
NP^NP*: their algorithm guesses a proof of equivalence and
validates this proof in polynomial time using oracles freely
answering questions which are in NP. In this paper we improve on
this result by presenting a polynomial-time algorithm which solves
this problem. As a corollary, we have a polynomial algorithm for
the equivalence problem for simple context-free grammars.

*LFCS report ECS-LFCS-94-286,
March 1994.*

Previous |

Index |

Next