On language and bisimulation equivalence of context-free processes

Speaker(s)

Slawomir Lasota (joint work with Wojciech Rytter)

Affiliation

Uniwersytet Warszawski

Date

May 10, 2006, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

In contrast to language equivalence, being undecidable for (normed) context-free grammars, the bisimulation equivalence is decidable; and it is even polynomial for normed grammars.The fastest known algorithm for checking bisimulation equivalence worked in $O(n^{13})$ time. We give an alternative algorithm working in $O(n^8 \polylog\ n)$ and $O(n^2\;v)$ time, where $v$ is the maximum norm of a process. Thus we make a step towards a low complexity algorithmic solution of the bisimulation equivalence problem. As a side effect we improve the best known upper bound for testing equivalence of simple context-free grammars from $O(n^7 \polylog\ n)$ to $O(n^6 \polylog\ n)$.

---