Title :
A polynomial-time algorithm for deciding equivalence of normed context-free processes
Author :
Hirshfeld, Yoram ; Jerrum, Mark ; Moller, Faron
Author_Institution :
Sch. of Math. & Comput. Sci., Tel Aviv Univ., Israel
Abstract :
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
Keywords :
context-free grammars; decidability; equivalence classes; bisimilarity; context-free grammars; decidability; equivalence; language equivalence; normed context-free processes; polynomial-time algorithm; Algebra; Carbon capture and storage; Computer science; Context; Councils; Mathematics; Polynomials; Production;
Conference_Titel :
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location :
Santa Fe, NM
Print_ISBN :
0-8186-6580-7
DOI :
10.1109/SFCS.1994.365729
