Relationships between monadic recursion schemes and deterministic context-free languages
- 1 October 1974
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 43-51
- https://doi.org/10.1109/swat.1974.24
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Recursive schemes, algebraic trees and deterministic languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Decidable Properties of Monadic Functional SchemasJournal of the ACM, 1973
- Program schemes, recursion schemes, and formal languagesJournal of Computer and System Sciences, 1973
- Properties of deterministic top-down grammarsInformation and Control, 1970
- Simple deterministic languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1966