SODA

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

Hirshfeld, Yoram and Jerrum, Mark and Moller, Faron (1994) A polynomial algorithm for deciding bisimilarity of normed context-free processes. [SICS Report]

[img]Postscript
88Kb

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 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
ID Code:2129
Deposited By:Vicki Carleson
Deposited On:22 Oct 2007
Last Modified:18 Nov 2009 16:00

Repository Staff Only: item control page