Symbolic integration: the stormy decade

ABSTRACT

Three approaches to symbolic integration in the 1960's are described. The first, from artificial intelligence, led to Slagle's SAINT and to a large degree to Moses' SIN. The second, from algebraic manipulation, led to Manove's implementation and to Horowitz' and Tobey's reexamination of the Hermite algorithm for integrating rational functions. The third, from mathematics, led to Richardson's proof of the unsolvability of the problem for a class of functions and for Risch's decision procedure for the elementary functions. Generalizations of Risch's algorithm to a class of special functions and programs for solving differential equations and for finding the definite integral are also described.

REFERENCES

• 1: E. R. Berlekamp, Factoring polynomials over large finite fields*, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.223, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806290]
• 2: Hardy, G.H. The Integration of Functions of a Single Variable (2nd ed.). Cambridge U. Press, Cambridge, England, 1916.
• 3: Ellis Horowitz, Algorithms for partial fraction decomposition and rational function integration, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.441-457, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806314]
• 4: Manove, M., Bloom, S., and Engelman, C. Rational functions in MATHLAB, Proc, IFIP Conf. on Symbolic Manipulation Languages, Pisa, Italy, 1968.
• 5: Moses, J. Symbolic Integration. MAc-TR-47, Proj. MAC, MIT, Dec. 1967 (available from the Defense Document. Center, AD 662666).
• 6: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• 7: Moses, J. The integration of a class of special functions with the Risch algorithm. Memo MAc-M-421, Proj. MAC, MIT, Sept. 1969.
• 8: Ostrowski, A. Sur l'integrabilit~ elementaire de quelques classes d'expressions. Commentarii Mathematici Helvetici, Vol. 18, 1946, pp. 283-308.
• 9: Richardson, D. Some unsolvable problems involving elementary functions of a real variable. J. Symbolic Logic 33 (1968), 511-520.
• 10: Risch, R. The problem of integration in finite terms. Trans. AMS 139 (May 1969), 167-189.
• 11: Risch, R. On the integration of elementary functions which are built up using algebraic operations. Rep. SP-2801-002, Syst. Develop. Corp., Santa Monica, Calif, June 1968.
• 12: Risch, R. Further results on elementary functions. Rep. RC 2402, IBM Corp., Yorktown Heights, N.Y., Mar. 1969.
• 13: Risch, R. Solution of the problem of integration in finite terms. Bull AMS (to appear).
• 14: Slagle, J. A heuristic program that solves symbolic integration problems in freshman calculus. Ph.D. diss., MIT, May 1961 (also see Computers and Thought, E. Feigenbaum and J. Feldman, Eds.)
• 15: Tobey, R. Algorithms for antidifferentiation of rational functions. Ph.D. diss., Harvard U., Cambridge, Mass., May 1967.
• 16: Horst G. Zimmer, Computers and computations in algebraic number theory, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.172-179, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806284]

INDEX TERMS

Keywords:
definite integrals, integration, rational functions, symbolic integration