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

The equivalence problem for unambiguous grammars is an important, but very difficult open question in formal language theory. Consider the \emph{limited} equivalence problem for unambiguous grammars – for two unambiguous grammars $G_1$ and $G_2$, tell whether or not they describe the same set of words of length $n$. Obviously, the naive approach requires exponential time with respect to $n$. By combining two classic algorithmic ideas, I introduce a $O(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n,\mathrm{\mid }{G}_1\mathrm{\mid },\mathrm{\mid }{G}_2\mathrm{\mid }))$ algorithm for this problem. Moreover, the ideas behind the algorithm prove useful in various other scenarious.