Cocke-Kasami-Younger-Schwartz-Zippel algorithm and its relatives

by Mr Vladislav Makarov (SPbU and EIMI)

Friday 14 Jan 2022, 12:50 → 13:20 Europe/Moscow

201 (SPbU Math & CS Dept)

I will talk about a fast algorithm for a "limited" version of equivalence problem for unambiguous grammars. Moreover, I will explain how the ideas behind the algorithm can be used in other contexts, for example, for proving lower bound results.