• People
• Events
• Research

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

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.