joint work with Petr Jancar

Speaker(s)

Wojciech Czerwiński

Affiliation

Uniwersytet Warszawski

Date

May 14, 2014, 2:15 p.m.

Room

room 5870

Title in Polish

Deciding branching bisimilarity on BPA in NEXPTIME

Seminar

Seminar Automata Theory

---

Branching bisimilarity is a variant of the weak bisimilarity. Recently there was a big progress in deciding bisimilarity on context-free systems: decidability was shown. I will present the main ideas of this result and explain how to improve it to NEXPTIME.

---