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