Why the equivalence problem for unambiguous grammars has not been solved back in 1966?

2022/12/07 by Makarov, Vladislav
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2212.03786

Abstract

In 1966, Semenov, by using a technique based on power series, suggested an algorithm that tells apart the languages described by an unambiguous grammar and a DFA. At the first glance, it may appear that the algorithm can be easily modified to yield a full solution of the equivalence problem for unambiguous grammars. This article shows why this hunch is, in fact, incorrect.

Related

• Cocke--Younger--Kasami--Schwartz--Zippel algorithm and relatives
• Detecting and Explaining (In-)equivalence of Context-Free Grammars
• A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
• On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
• An undecidable property of context-free languages