Seminár z teoretickej informatiky - Petr Jančar (4.12.2015)

v piatok 4.12.2015 o 11:00 hod. v miestnosti M/213

30. 11. 2015 13.14 hod.
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

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

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php