Decidable Properties of Monadic Functional Schemas,
Abstract
A class of (monadic) functional schemas are defined which properly includes 'Ianov' flowchart schemas. It is shown that the termination, divergence and freedom problems for functional schemas are decidable. Although it is possible to translate a large class of non-free functional schemas into equivalent free functional schemas, it is shown that this cannot be done in general. It is also indicated that the equivalence problem for free functional schemas is decidable. Most of the results are obtained from well-known results in Formal Languages and Automata Theory. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1971
- Accession Number
- AD0731730
Entities
People
- Amir Pneuli
- Edward Ashcroft
- Zohar Manna
Organizations
- Stanford University