- 1 AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J D. The Design and Analysts of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974, pp 195-206. Google Scholar
- 2 AHO, A V, AND ULLMAN, J.D. Principles of Compiler Design Addison-Wesley, Reading, Mass, 1977, pp 408-517. Google Scholar
- 3 BACKHOUSE, R.C., AND CARRI~, B.A.Regular algebra apphed to path-f'mdmg problems. J. lnst. Math. Apphc. 15 (1975), 161-186.Google Scholar
- 4 Bul~cn, J.R., AND HOPCROFT, J E Triangular factonzation and inversion by fast matrix multtphcation. Math. Comput. 28 (1974), 231-236.Google Scholar
- 5 COUSOT, P., AND COUSOT, R. Abstract interpretation. A unified lattice model for static analysts of programs by construction or approximation of fixpoints Conf. Rec. 4th ACM Symp. on Principles of Programming Languages, Los Angeles, Calif., 1977, pp 238-252. Google Scholar
- 6 DIJKSTRA, E W A note on two problems in connexion with graphs Numer Math. I (1959), 269-271Google Scholar
- 7 FLOYD, R. Algonthm 97. Shortest path. Commun. ACM 5, 6 (June 1962), 345. Google Scholar
- 8 FONG, A C Generalized common subexpresstons in very high level languages Conf. Rec 4th ACM Symp on Principles of Programmmg Languages, Los Angeles, Calif, 1977, pp 48-57. Google Scholar
- 9 FONG, A.C., KAM, J B., AND ULLMAN, J.D. Apphcatlons of lattice algebra to loop optimization Conf. Rec. 2nd ACM Symp on Principles of Programming Languages, Palo Alto, Cahf, 1975, pp 1-9 Google Scholar
- 10 FORD, L.R. JR., AND FULKERSON, D R. Flows m Networks. Pnnceton University Press, Princeton, N J., 1962, pp 130-134Google Scholar
- 11 FORSYTHE, G.E, AND MOLER, C.B. Computer Solution of Linear Algebraic Equations. Prentice-Hall, Englewood Cliffs, N.J., 1967, pp 27-36.Google Scholar
- 12 FREDMAN, M.L New bounds on the complexity of the shortest path problem. SlAM ~ Comput. 5 (1976), 83-89Google Scholar
- 13 GRAHAM, S L., AI~D WEGMAN, M A fast and usually linear algorithm for global flow analysis. J. ACM 23, 1 (Jan 1976), 172-202 Google Scholar
- 14 HECHT, M.S. Flow Analysts of Computer Programs. Elsevier, New York, 1977 Google Scholar
- 15 HECHT, M.S, AND ULLMAN, J.n. Flow graph reducibility SlAM ~ Comput. 1 (1972), 188-202Google Scholar
- 16 JOHNSON, D.B Efficient algorithms for shortest paths m sparse networks ~ A CM 24, 1 (Jan. 1977), 1-13. Google Scholar
- 17 KAM, J B, AND ULLMAN, J D. Global data flow analysis and tterative algorithms. J A CM 23, 1 (Jan. 1976), 158-171 Google Scholar
- 18 KAM, J.B., AND ULLMAN, J D. Monotone data flow analysts frameworks Acta Inf 7 (1977), 305-317.Google Scholar
- 19 KENNEDY, K W Node hstmgs applied to data flow analysis. Conf. Rec 2nd ACM Symp. on Principles of Programming Languages, Palo Alto, Cahf, 1975, pp. 10-21 Google Scholar
- 20 KILDALL, G A A unified approach to program optimization Conf. Rec ACM Symp on Principles of Programmmg Languages, Boston, Mass., 1973, pp 10-21. Google Scholar
- 21 KLEENE, S C. Representation of events in nerve nets and finite automata. In Automata Studies, C. E Shannon and J. McCarthy, Eds., Princeton University Press, Princeton, N J, 1956, pp. 3-40.Google Scholar
- 22 LEHMANN, D J Algebraic structures for transitive closure. Theor. Comput Sc~ 4 (1977), 59-76.Google Scholar
- 23 PAN, V.Y Strassen's algorithm is not optimal. Tnlinear techmque of aggregating uniting and cancelmg for constructmg fast algonthms for matrix operatmns. Proc. 19th Ann IEEE Symp on Foundations of Computer Science, Ann Arbor, Mich, 1978, pp 166-176.Google Scholar
- 24 ROSEN, B K. Monoids for rapid data flow analysis. SlAM J Comput. 9 (1980), 159-196Google Scholar
- 25 SALOMAA, A.Two complete axiom systems for the algebra of regular events. J. A CM, 1 (Jan 1966), 158-169. Google Scholar
- 26 SCHAEFER, M A Mathemaucal Theory of Global Program Optimization. Prentice-Hall, Englewood Cliffs, N J, 1973 Google Scholar
- 27 STRASSEN, V.Gaussian ehmmatlon is not opttmal Numer. Math 13 (1969), 354-356.Google Scholar
- 28 SzAsz, G Introducuon to Lattice Theory, B. Balkay and G. T6th, Trans., Academic Press, New York, 1963, p 38--42, 59-60Google Scholar
- 29 TARJAN, R E.Testing flow graph reduclbihty J. Comput Syst Sct. 9 (1974), 355-365Google Scholar
- 30 TARJAN, R.Elteratwe algonthms for global flow analysis in Algorithms and Complexity, New Dtrecttons and Recent Results, J F Traub, Ed., Academic Press, New York, 1976, pp 91-102.Google Scholar
- 31 TARJAN, R E Fast algorithms for solving path problems, ~ ACM 28, 3 (July 1981), 594-614 Google Scholar
- 32 ULLMAN, J D Fast algorithms for the elimlnaUon of common subexpresslons Acta Inf. 2 (1973), 191-213Google Scholar
- 33 WAGNER, R.A A shortest path algonthm for edge-sparse graphs. J A CM 23, 1 (Jan 1976), 50-57. Google Scholar
- 34 WARSHALL, S A theorem on Boolean matrices. J ACM 9, 1 (Jan. 1962), 11-12. Google Scholar
- 35 WEGBREIT, B Property extraction m well-founded property sets. IEEE Trans. Soflw Eng. 1 (1975), 270-285.Google Scholar
Index Terms
- A Unified Approach to Path Problems
Comments