Space and Time Hierarchies for Classes of Control Structures and Data Structures
- 1 October 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (4) , 720-732
- https://doi.org/10.1145/321978.321990
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.Keywords
This publication has 8 references indexed in Scilit:
- Characterizations of Reducible Flow GraphsJournal of the ACM, 1974
- On the capabilities of while, repeat, and exit statementsCommunications of the ACM, 1973
- The Expression of Algorithms by ChartsJournal of the ACM, 1972
- Matrix computations with Fortran and pagingCommunications of the ACM, 1972
- Notes on avoiding “go to” statementsInformation Processing Letters, 1971
- Structure and meaning of elementary programsPublished by Springer Nature ,1971
- Flow diagrams, turing machines and languages with only two formation rulesCommunications of the ACM, 1966
- Symbol manipulation by threaded listsCommunications of the ACM, 1960