Seminár z teoretickej informatiky - Petr Jančar (4.12.2015)
v piatok 4.12.2015 o 11:00 hod. v miestnosti M/213
Od: Rastislav Královič
Prednášajúci: Petr Jančar
Názov prednášky: Behavioural Equivalences of Processes Generated by Context-Free Grammars
Termín: 4.12.2015, 11:00 hod., M/213
The plan is first to give a short survey of some recent results (including those presented in the papers P.J.: Equivalences of Pushdown Systems Are Hard. FoSSaCS 2014: 1-28, LNCS 8412 and P.J.: Bisimulation Equivalence of First-Order Grammars. ICALP (2) 2014:232-243, LNCS 8573), and then to explain why finite transducers are a natural device for deciding branching bisimilarity of so called normed BPA processes. There has been a recent revival of the research interest in this intriguing equivalence on infinite-state systems, and the proposed talk is based on the paper "Branching Bisimilarity of Normed BPA Processes is in NEXPTIME" by W. Czerwinski and P.J. that was presented at LiCS 2015.