# 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)$.