I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free grammars"). I wonder what the best algorithm for this problem is, and what the computational complexity of the algorithm is. Thank you.

  • 1
    $\begingroup$ This was an open problem in the 1976 classic On the equivalence, containment, and covering problems for the regular and context-free languages paper by Hunt, Rosenkrantz, and Szymanski (dx.doi.org/10.1016/S0022-0000(76)80038-4). There is a paper titled The complexity of structural containment and equivalence by Hunt and Rosenkrantz in a book dedicated to Ginsburg, Theoretical studies in computer science, Academic Press 1992, but I have never read it. $\endgroup$ – Sylvain Jan 22 '13 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.