Can I read Why the Equivalence Problem for Unambiguous Grammars Has Not Been Solved Back in 1966? on EtoBox?

Why the Equivalence Problem for Unambiguous Grammars Has Not Been Solved Back in 1966? by Makarov, Vladislav is a scholarly article available to read on EtoBox.

What is Why the Equivalence Problem for Unambiguous Grammars Has Not Been Solved Back in 1966? about?

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.

Author

Makarov, Vladislav

Published

2022

Language

EN