• DocumentCode
    2202791
  • Title

    Equivalence problems in monadic recursion schemes

  • Author

    Friedman, Emily P.

  • fYear
    1973
  • fDate
    15-17 Oct. 1973
  • Firstpage
    26
  • Lastpage
    33
  • Abstract
    The inclusion problem for the class of monadic recursion schemes is shown to be undecidable, thus answering an open question of Paterson [5]. The proof depends upon a construction similar to one used showing that the question "is L1 ⊆ L2 ?" is undecidable for context-free languages L1, L2.
  • Keywords
    Computers; Context modeling; Testing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Switching and Automata Theory, 1973. SWAT '08. IEEE Conference Record of 14th Annual Symposium on
  • Conference_Location
    USA
  • ISSN
    0272-4847
  • Type

    conf

  • DOI
    10.1109/SWAT.1973.8
  • Filename
    4569725
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2202791