### Characterizations of Reducible Flow GraphsCharacterizations of Reducible Flow Graphs

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

Source: ACM Digital Library