Hirshfeld, Yoram and Jerrum, Mark and Moller, Faron (1994) A polynomial algorithm for deciding bisimilarity of normed context-free processes. [SICS Report]
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 the second level of the polynomial hierarchy: 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.
|Item Type:||SICS Report|
|Uncontrolled Keywords:||Process algebra, Formal languages, Analysis of algorithms|
|Deposited By:||Vicki Carleson|
|Deposited On:||22 Oct 2007|
|Last Modified:||18 Nov 2009 16:00|
Repository Staff Only: item control page