Towards decidability of weak bisimilarity on BPP

Speaker(s)

Wojciech Czerwiński

Affiliation

Uniwersytet Warszawski

Date

March 30, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---