Access Restriction

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

   Open content in new tab
Source: ACM Digital Library