论文标题
Cocke - Younger - Kasami-Schwartz- Zippel算法和亲戚
Cocke--Younger--Kasami--Schwartz--Zippel algorithm and relatives
论文作者
论文摘要
在形式语言理论中，明确语法的等效问题是一个重要但非常困难的开放问题。考虑明确的语法的\ emph {limited}等效问题 - 对于两个明确的语法$ g_1 $和$ g_2 $，请告诉他们是否描述了相同的长度单词$ n $。显然，天真的方法需要相对于$ n $的指数时间。通过结合两个经典的算法想法，我引入了$ o（{\ rm poly}（n，| g_1 |，| g_2 |））$算法。此外，算法背后的想法在其他各种情况下都有用。
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({\rm poly}(n, |G_1|, |G_2|))$ algorithm for this problem. Moreover, the ideas behind the algorithm prove useful in various other scenarious.
