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

2022/12/07 by В. С. Макаров, Makarov, Vladislav
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2212.03861

openalex publication_date 2022/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The equivalence problem for unambiguous grammars is an important, but very difficult open question in formal language theory. Consider the limited equivalence problem for unambiguous grammars -- for two unambiguous grammars G₁ and G₂, 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₁|, |G₂|)) algorithm for this problem. Moreover, the ideas behind the algorithm prove useful in various other scenarious.

Related

• Why the equivalence problem for unambiguous grammars has not been solved back in 1966?
• Simple grammar bisimilarity, with an application to session type equivalence
• On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
• A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
• O₂ is a multiple context-free grammar: an implementation-, formalisation-friendly proof