Recursive schemes, algebraic trees and deterministic languages
- 1 October 1974
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The equivalence problems for uninterpreted recursive program schemes and deterministic pushdown automata are reducible to each other. The equivalence class of a scheme is characterized by an infinite tree which is generated by the scheme as a language by a context-free grammar and which satisfies the equations of the system. Such trees are called algebraic. Roughly speaking, a tree is algebraic iff the set of its finite branches is a deterministic language. The interreducibility of the two equivalence problems for schemes and DPDA's follows.Keywords
This publication has 3 references indexed in Scilit:
- Relationships between monadic recursion schemes and deterministic context-free languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Semantics and axiomatics of a simple recursive language.Published by Association for Computing Machinery (ACM) ,1974
- Tree-Manipulating Systems and Church-Rosser TheoremsJournal of the ACM, 1973