Towards decidability of weak bisimilarity on BPP

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

Uniwersytet Warszawski

Termin

30 marca 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Consider transition system generated by commutative context-free grammar,
so called BPP. Strong bisimilarity is known to be PSPACE-complete on this class
of infinite graphs, weak bisimilarity (with possible epsilon transitions) is important and long
standing open problem.
I will show the new technique which allows us to solve the problem for the
slightly different version of weak bisimilarity and may be helpful for the main one.

---