Relationships between monadic recursion schemes and deterministic context-free languages
Emily P. Friedman · 1974
The equivalence problem for languages accepted by deterministic pushdown automata is shown to be decidable if and only if the strong equivalence problem for monadic recursion schemes is decidable. The proof is obtained through a series of reductions, and several different classes of acceptors are introduced.