A polynomial-time algorithm for deciding equivalence of normed context-free processes
Yoram Hirshfeld, Mark Jerrum, Faron Moller · 2002
A polynomial-time procedure is presented for deciding bisimilarity of normed context-free processes. It follows as a corollary that language equivalence of simple context-free grammars is decidable in polynomial time.>