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

Vladislav Makarov

paper

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

arXiv:2212.03861

Abstract

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 (poly (n, ∣ G_{1} ∣, ∣ G_{2} ∣))$ algorithm for this problem. Moreover, the ideas behind the algorithm prove useful in various other scenarious.

11 pages