On language and bisimulation equivalence of context-free processes

Prelegent(ci)

Slawomir Lasota (joint work with Wojciech Rytter)

Afiliacja

Uniwersytet Warszawski

Termin

10 maja 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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

---