Young Researchers' Seminar

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

by Mr Vladislav Makarov (SPbU and EIMI)

Europe/Moscow
201 (SPbU Math & CS Dept)

201

SPbU Math & CS Dept

Description

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.