• DocumentCode
    2357242
  • 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
  • fYear
    1994
  • fDate
    20-22 Nov 1994
  • Firstpage
    623
  • Lastpage
    631
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
  • Conference_Location
    Santa Fe, NM
  • Print_ISBN
    0-8186-6580-7
  • Type

    conf

  • DOI
    10.1109/SFCS.1994.365729
  • Filename
    365729
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2357242