Equivalence problems in monadic recursion schemes
Emily P. Friedman · 1973
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.