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

摘要

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 < or = s.t where G < or = 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 < or = s.t for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures. (Author)