{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:51:35Z","timestamp":1654876295140},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1974,7]]},"abstract":"\n It is established that if\n G<\/jats:italic>\n is a reducible flow graph, then edge (\n n, m<\/jats:italic>\n ) is backward (a back latch) if and only if either\n n = m<\/jats:italic>\n or\n m<\/jats:italic>\n dominates\n n<\/jats:italic>\n in\n G<\/jats:italic>\n . Thus, the backward edges of a reducible flow graph are unique.\n <\/jats:p>\n \n Further characterizations of reducibility are presented. In particular, the following are equivalent: (a)\n G<\/jats:italic>\n = (\n \n N, E, n\n 0<\/jats:sub>\n <\/jats:italic>\n ) is reducible. (b) The \u201cdag\u201d of\n G<\/jats:italic>\n is unique. (A dag of a flow graph\n G<\/jats:italic>\n is a maximal acyclic flow graph which is a subgraph of\n G<\/jats:italic>\n .) (c)\n E<\/jats:italic>\n can be partitioned into two sets\n E<\/jats:italic>\n 1<\/jats:sub>\n and\n E<\/jats:italic>\n 2<\/jats:sub>\n such that\n E<\/jats:italic>\n 1<\/jats:sub>\n forms a dag\n D<\/jats:italic>\n of\n G<\/jats:italic>\n and each (\n n, m<\/jats:italic>\n ) in\n E<\/jats:italic>\n 2<\/jats:sub>\n has\n n = m<\/jats:italic>\n or\n m<\/jats:italic>\n dominates\n n<\/jats:italic>\n in\n G<\/jats:italic>\n . (d) Same as (c), except each (\n n, m<\/jats:italic>\n ) in\n E<\/jats:italic>\n 2<\/jats:sub>\n has\n n = m<\/jats:italic>\n or\n m<\/jats:italic>\n dominates\n n<\/jats:italic>\n in\n D<\/jats:italic>\n . (e) Same as (c), except\n E<\/jats:italic>\n 2<\/jats:sub>\n is the back edge set of a depth-first spanning tree for\n G<\/jats:italic>\n . (f) Every cycle of\n G<\/jats:italic>\n has a node which dominates the other nodes of the cycle.\n <\/jats:p>\n Finally, it is shown that there is a \u201cnatural\u201d single-entry loop associated with each backward edge of a reducible flow graph.<\/jats:p>","DOI":"10.1145\/321832.321835","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:10Z","timestamp":1027769170000},"page":"367-375","source":"Crossref","is-referenced-by-count":110,"title":["Characterizations of Reducible Flow Graphs"],"prefix":"10.1145","volume":"21","author":[{"given":"M. S.","family":"Hecht","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, Maryland"}]},{"given":"J. D.","family":"Ullman","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Princeton University, Princeton, New Jersey"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"2","volume":"1","author":"H~ CHT","year":"1972","journal-title":"SIAM J. Computing"},{"key":"e_1_2_1_2_2","first-page":"119","volume-title":"Proc. 6th Annual Princeton Conf. on Information Sciences and Systems","author":"An","year":"1972"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"ULLMAN J.D. Fast algorithms for the elimination of common subexpressions. Acta Infor. matica $ 3 (Dec. 1973) 191-213. ULLMAN J.D. Fast algorithms for the elimination of common subexpressions. Acta Infor. matica $ 3 (Dec. 1973) 191-213.","DOI":"10.1007\/BF00289078"},{"key":"e_1_2_1_4_2","volume-title":"Annual Rev. Automatic Prog.","volume":"5","year":"1969"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808479"},{"key":"e_1_2_1_6_2","first-page":"385","volume-title":"Proc. IFIP Conf. 71","volume":"1","author":"L~ N","year":"1971"},{"key":"e_1_2_1_7_2","unstructured":"ALLEN F. E. AND COCK~ J. Graph-theoretic constructs for program control flow analysis. IBM Res. Rep. RC 3923 T. J. Watson Research Center Yorktown Heights N.Y. July 1972. ALLEN F. E. AND COCK~ J. Graph-theoretic constructs for program control flow analysis. IBM Res. Rep. RC 3923 T. J. Watson Research Center Yorktown Heights N.Y. July 1972."},{"key":"e_1_2_1_8_2","volume-title":"Translation and Compiling","volume":"1973","author":"L~ AN"},{"key":"e_1_2_1_9_2","unstructured":"SCHAEFER M. A Mathematical Theory of Global Program Optimization. Prentice-Hall Englewood Cliffs N. J. 1973. SCHAEFER M. A Mathematical Theory of Global Program Optimization. Prentice-Hall Englewood Cliffs N. J. 1973."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/390013.808480"},{"key":"e_1_2_1_11_2","first-page":"5","volume":"3","year":"1971","journal-title":"Internat. J. Computer Math."},{"key":"e_1_2_1_12_2","first-page":"2","volume":"1","author":"Depth","year":"1972","journal-title":"SIAM J. Computing"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321832.321835","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T22:28:54Z","timestamp":1614724134000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321832.321835"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,7]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1974,7]]}},"alternative-id":["10.1145\/321832.321835"],"URL":"http:\/\/dx.doi.org\/10.1145\/321832.321835","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1974,7]]}}}