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

The previous best upper bound on the complexity of deciding bisimilarity between normed context-free processes is due to Huynh and Tian (1994), who put the problem in Σ 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 describing a polynomial-time algorithm which solves this problem. As a corollary, we have a polynomial algorithm for the equivalence problem for simple grammars.

Authors

• Yoram Hirshfeld
• Mark Jerrum
• Faron Moller

Keywords

No keywords are indexed for this paper.