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

Access Restriction
Subscribed

 Author Lipton, R. J. ♦ Eisenstat, S. C. ♦ Demillo, R. A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1976 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $≤\textit{S.T}$ where $\textit{G}$ $≤\textit{S.T}$ $\textit{H}$ if $\textit{G}$ can be embedded in $\textit{H}$ with at most a $\textit{T}-fold$ increase in distance between embedded nodes by making at most $\textit{S}$ “copies” of any node in $\textit{G}.$ For both control structures and data structures, $\textit{S}$ and $\textit{T}$ are interpreted as space and time constants, respectively. Results are presented that establish hierarchies with respect to $≤\textit{S.T}$ for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1976-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 23 Issue Number 4 Page Count 13 Starting Page 720 Ending Page 732

#### Open content in new tab

Source: ACM Digital Library