Space and Time Hierarchies for Classes of Control Structures and Data Structures

ABSTRACT

Control structures and data structures are modeled by directed graphs. In the control case nodes represent executable statements and arcs represent possible flow of control; in the data case nodes represent memory locations and arcs represent logical adjacencies in the data structure. Classes of graphs are compared by a relation ≤S.T where G ≤S.T H if G can be embedded in H with at most a T-fold increase in distance between embedded nodes by making at most S “copies” of any node in G. For both control structures and data structures, S and T are interpreted as space and time constants, respectively. Results are presented that establish hierarchies with respect to ≤S.T for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures.

REFERENCES

• 1: ASNCROFr, E., AND MANNA, Z The translatmn of GOTO programs to WHILE programs Proc IFIP Cong. 1971, North-Holland Pub Co., Amsterdam, 1972, pp. 250-255,
• 2: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 3: J. Bruno , K. Steiglitz, The Expression of Algorithms by Charts, Journal of the ACM (JACM), v.19 n.3, p.517-525, July 1972 [doi>10.1145/321707.321720]
• 4: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 5: Dv.MILLO, R A, EISENSTAT, S C., AND LleroN, R.J Space-time tradeoffs m structured programming (to appear)
• 6: ENt;ELrR, E. Structure and meamng of elementary programs Lecture Notes in Mathematics, No 188 Symp. on Semanucs of Algorithmic Languages. E. Engeler, Ed , Spnnger-Verlag, Berhn, 1971, pp. 89- 101
• 7: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 8: KNtrrrl, D E. The Art of Computer Programming, Vol. I: Fundamental Algorithms Addison-Wesley, Reading, Mass, 1968
• 9: KNOTH, D E Structured programming w~th GOTO statements Rep STAN-CS-74-416, Computer Scl Dep, Stanford U , Stanford, Cahf, 1974
• 10: NUTH, D E , AND FLOYD, R.W Notes on avoiding "go to" statements Infor Process Lett 1 (1971), 23-31.
• 11: KOSARA~U, S.R Analysis of structured programs. J. Computer and Syst. Scl. 9, 3 (June 1974), 232-255
• 12: L~.DGARD, H F A geneology of control structures Research Rep, Computer and Information Science Dep, U of Massachusetts,.Amherst, Mass , 1974
• 13: Cleve B. Moler, Matrix computations with Fortran and paging, Communications of the ACM, v.15 n.4, p.268-270, April 1972 [doi>10.1145/361284.361297]
• 14: A. J. Perlis , Charles Thornton, Symbol manipulation by threaded lists, Communications of the ACM, v.3 n.4, p.195-204, April 1960 [doi>10.1145/367177.367202]
• 15: W. W. Peterson , T. Kasami , N. Tokura, On the capabilities of while, repeat, and exit statements, Communications of the ACM, v.16 n.8, p.503-512, Aug. 1973 [doi>10.1145/355609.362337]
• 16: ROSENBERO, A.L Preserving prommJty m arrays. Rep. RC-4875, IBM Thomas J Watson Research Center, Yorktown Heights, N Y , 1974

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Languages, Performance, Reliability, Theory, Verification