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

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