Report Number: CS-TR-71-217
Institution: Stanford University, Department of Computer Science
Title: Decidable properties of monadic functional schemas
Author: Ashcroft, Edward A.
Author: Manna, Z ohar
Author: Pneuli, Amir
Date: July 1971
Abstract: We define a class of (monadic) functional schemas which properly includes 'Ianov' flowchart schemas. We show 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, we show that this cannot be done in general. We show also 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/71/217/CS-TR-71-217.pdf