Characterizations of flowchartable recursions short version

ABSTRACT

In this paper we give new characterizations for the flowchartability of recursive functionals. The general question of flowchartability is recursively undecidable. We present here an effective map from recursions to representatives for which the question is decidable. The decision provides a good approximation to a characterization for general flowchartability in the following senses: (1) if a representative is flowchartable then the recursions it represents are, and (2) there is a straightforward method of flowcharting, depending only on recursion structure, such that a recursion is flowchartable by this method if and only if its representative is flowchartable. The main results of the paper are (1) that such a representative is flowchartable if, and only if, it is simple or linear, and (2) that, when the context is restricted so that only invertible operations are considered, such a representative is flowchartable if, and only if, it is nested. The terms “simple” and “linear” have been defined in previous papers in the area, although they are extended slightly in this one. The term nested is introduced here. Simple, linear, and nested recursions are very easy to identify by inspection.

REFERENCES

• 1: J.W. deBakker and D. Scott. A Theory of Programs, unpublished report (August 1969).
• 2: S.J. Garland and D.C. Luckham. Program Schemes, Recursion Schemes and Formal Languages, Technical Report, UCLA-ENG-7154, (June 1971).
• 3: M.S. Paterson. Equivalence Problems in a Model of Computation, Ph.D. Dissertation, Univ. of Cambridge, Cambridge, England, 1967.
• 4: M.S. Paterson and C.E. Hewitt. Comparative Schemotology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation (June 1970), 119-;128, ACM, New Jersey (December 1970).
• 5: D.A. Plaisted. Flowchart Schemas With Counters, Stanford University, to appear.
• 6: H.R. Strong. Translating Recursion Equations Into Flow Charts, Journal of Computer and System Sciences 5, 3 (June 1971), 254-;285.
• 7: H.R. Strong and S.A. Walker. Properties Preserved Under Recursion Removal, to appear as an IBM Research Report.
• 8: S.A. Walker. Some Graph Games Related to the Efficient Calculation of Expressions, IBM Research Report RC-3628, 1971.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

General Terms:
Theory