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 re-examination 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., Camb. Univ. 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 Symbol Manip. Languages, Pisa, Italy, 1968.
• 5: Moses, J., "Symbolic Integration", MAC-TR-47, Project MAC, MIT, Dec. 1967, (available from the Defense Documentation Center AD# 662666).
• 6: Joel Moses, Algebraic simplification a guide for the perplexed, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.282-304, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806298]
• 7: Moses, J., "The Integration of a Class of Special Functions with the Risch Algorithm", Memo MAC-M-421, Project MAC, MIT, Sept. 1969.
• 8: Ostrowski, A., "Sur l'integrabilite elementaire de quelques classes d'expressions", Commentarii Mathematici Helvetici, vol.XVIII, 1946, pp.283-308.
• 9: Richardson, D., "Some Unsolvable Problems Involving Elementary Functions of a Real Variable", J. Symbolic Logic, vol.33, 1968, pp.511-520.
• 10: Risch, R., "The Problem of Integration in Finite Terms", Trans. AMS, vol.139, May 1969, pp.167-189.
• 11: Risch, R., "On the Integration of Elementary Functions which are Built Up Using Algebraic Operations", Report SP-2801-002, System Develop Corp, Santa Monica, Calif., June 1968.
• 12: Risch, R., "Further Results on Elementary Functions", Report RC 2402, IBM Corp, Yorktown Heights, N.Y., March 1969.
• 13: Risch, R., "Solution of the Problem of Integration in Finite Terms", Submitted to Bull. of AMS.
• 14: James R. Slagle, A heuristic program that solves symbolic integration problems in freshman calculus, Computers & thought, MIT Press, Cambridge, MA, 1995
• 15: 15)Tobey, R., "Algorithms for Antidifferentiation of Rational Functions", PhD dissert, Harvard U., Camb. 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

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.9 Integral Equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory