Accession Number : AD0731730

Title :   Decidable Properties of Monadic Functional Schemas,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Ashcroft,Edward ; Manna,Zohar ; Pneuli,Amir

Report Date : JUL 1971

Pagination or Media Count : 11

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)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, AUTOMATA), ARTIFICIAL INTELLIGENCE, MATHEMATICAL LOGIC, THEOREMS

Subject Categories : Linguistics
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE