Degrees of translatability and canonical forms in program schemas: Part I

ABSTRACT

We define a measure of the generality of the control structure of a program schema. This imposes a partial ordering on program schemas, and leads to a concept of the “difficulty” of a programming problem. In this sense there exists a “hardest” flowchart program, recursive program etc. Some earlier proofs can also be simplified and/or clarified by this approach.

REFERENCES

• 1: Edward Ashcroft , Zohar Manna , Amir Pnueli, Decidable Properties of Monadic Functional Schemas, Journal of the ACM (JACM), v.20 n.3, p.489-499, July 1973 [doi>10.1145/321765.321780]
• 2: John Steven Brown, Program schemata and information flow: a study of some aspects of the schema-power of data structures., 1972
• 3: J. S. Brown, D. Gries and T. Szymanski, "Program schemes with pushdown stores", SIAM J. Comput., 1, 3, Sept. 1972, pp. 242-268.
• 4: Ashok K. Chandra, Efficient compilation of linear recursive programs., Stanford University, Stanford, CA, 1972
• 5: Ashok Kumar Chandra, On the properties and applications of program schemas, 1973
• 6: A. K. Chandra, "A note on the power of recursion and equality versus that of parallelism", IBM T. J. Watson Res. Center, Yorktown Heights, (to appear).
• 7: A. K. Chandra, "Degrees of translatability and canonical forms in program schemas: part II", IBM Thomas J. Watson Res. Center, Yorktown Heights (to appear).
• 8: Ashok K. Chandra , Z Manna, On the power of programming features., Stanford University, Stanford, CA, 1973
• 9: R. L. Constable and D. Gries, "On classes of program schemata", SIAM J. Comput., 1, 1, March 1972, pp. 66-118.
• 10: S. J. Garland and D. C. Luckham, "Program schemes, recursion schemes, and formal languages", JCCS 7, 1973, pp. 119-160.
• 11: C. Hewitt, "More comparative schematology", A.I. Memo 207, Project MAC, MIT, August 1970.
• 12: K. Hirose and M. Oya, "Some results in general theory of flow charts", Proc. of First USA-Japan Comp. Conf., October 1972, pp. 367-371.
• 13: I. Ianov, "The logical schemes of algorithms", Problems of Cybernetics, Vol. 1, Pergamon Press, 1970, pp. 82-140.
• 14: D. C. Luckham, D. M. R. Park and M. S. Paterson, "On formalized computer programs", JCSS, 4, 3, June 1970, pp. 220-249.
• 15: M. S. Paterson, "Equivalence problems in a model of computation", Ph.D. Thesis, Univ. of Cambridge, England, August, 1967. Also AI Memo, No. 1, MIT, 1970.
• 16: M. S. Paterson, "A simple monadic recursive schema which is not equivalent to any program schema", unpublished memo., December 1970.
• 17: M. S. Paterson and C. E. Hewitt, "Comparative schematology", in Rec. of Project MAC Conf. on Concurrent Syst. and Parallel Compt., Woods Hole, Mass. June 1970, pp. 119-127.
• 18: David A. Plaisted, Flowchart schemata with counters, Proceedings of the fourth annual ACM symposium on Theory of computing, p.44-51, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804895]
• 19: Lawrence Snyder, An analysis of parameter evaluation for recursive-procedures., 1973
• 20: H. R. Strong and S. A. Walker, "Characterizations of flowchartable recursions", JCSS 7,4, August 1973, pp. 404-447.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

General Terms:
Theory