Space and Time Hierarchies for Classes of Control Structures and Data Structures
R.J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo · Journal of the ACM · 1976
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.