Thumbnail
Access Restriction
Subscribed

Author Hecht, M. S. ♦ Ullman, J. D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1974
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract It is established that if $\textit{G}$ is a reducible flow graph, then edge (n, m) is backward (a back latch) if and only if either n = m or $\textit{m}$ dominates $\textit{n}$ in $\textit{G}.$ Thus, the backward edges of a reducible flow graph are unique.Further characterizations of reducibility are presented. In particular, the following are equivalent: (a) $\textit{G}$ = (N, E, n0) is reducible. (b) The “dag” of $\textit{G}$ is unique. (A dag of a flow graph $\textit{G}$ is a maximal acyclic flow graph which is a subgraph of $\textit{G}.)$ (c) $\textit{E}$ can be partitioned into two sets $\textit{E}1$ and $\textit{E}2$ such that $\textit{E}1$ forms a dag $\textit{D}$ of $\textit{G}$ and each (n, m) in $\textit{E}2$ has n = m or $\textit{m}$ dominates $\textit{n}$ in $\textit{G}.$ (d) Same as (c), except each (n, m) in $\textit{E}2$ has n = m or $\textit{m}$ dominates $\textit{n}$ in $\textit{D}.$ (e) Same as (c), except $\textit{E}2$ is the back edge set of a depth-first spanning tree for $\textit{G}.$ (f) Every cycle of $\textit{G}$ has a node which dominates the other nodes of the cycle.Finally, it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducible flow graph.
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 1974-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 21
Issue Number 3
Page Count 9
Starting Page 367
Ending Page 375


Open content in new tab

   Open content in new tab
Source: ACM Digital Library