Algebraic simplification a guide for the perplexed

ABSTRACT

Algebraic simplification is examined first from the point of view of a user needing to comprehend a large expression, and second from the point of view of a designer who wants to construct a useful and efficient system. First we describe various techniques akin to substitution. These techniques can be used to decrease the size of an expression and make it more intelligible to a user. Then we delineate the spectrum of approaches to the design of automatic simplification capabilities in an algebraic manipulation system. Systems are divided into five types. Each type provides different facilities for the manipulation and simplification of expressions. Finally we discuss some of the theoretical results related to algebraic simplification. We describe several positive results about the existence of powerful simplification algorithms and the number-theoretic conjectures on which they rely. Results about the non-existence of algorithms for certain classes of expressions are included.

REFERENCES

• 1: Abrahams, P.W., "Applications of LISP to Sequence Prediction," CACM, vol.9, no.8, p.551, Aug. 1966.
• 2: J. H. Griesmer , R. D. Jenks, SCRATCHPAD/1: An interactive facility for symbolic mathematics, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.42-58, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806266]
• 3: Brown, W.S., et al., "The ALPAK System for Non-Numerical Algebra on a Digital Computer-II," Bell System Technical Journal, vol. XLIII, no.2, pp.785-804, March, 1964.
• 4: Brown, W.S., "Rational Exponential Expressions and a Conjecture Concerning and e," Amer. Math. Monthly, vol.76, pp.28-34, Jan. 1969.
• 5: W. S. Brown, On Euclid's algorithm and the computation of polynomial greatest common divisors, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.195-211, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806288]
• 6: Caviness, B.F., "On Canonical Forms and Simplification," PhD disser., Carnegie-Mellon U., Pitts. Pa., Aug. 1967.
• 7: B. F. Caviness, On Canonical Forms and Simplification, Journal of the ACM (JACM), v.17 n.2, p.385-396, April 1970 [doi>10.1145/321574.321591]
• 8: Carlos Christensen , Michael Karr, IAM, a system for interactive algebraic manipulation, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.115-127, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806276]
• 9: G. E. Collins, PM, a system for polynomial manipulation, Communications of the ACM, v.9 n.8, p.578-589, Aug. 1966 [doi>10.1145/365758.365770]
• 10: George E. Collins, The SAC-1 system: An introduction and survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.144-152, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806279]
• 11: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 12: Engeli, M., "User's Manual for the Formula Manipulation Language SYMBAL," University of Texas at Austin, Computer Center, 1968.
• 13: Richard J. Fateman, The user-level semantic matching capability in MACSYMA, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.311-323, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806300]
• 14: Fenichel, R., "An On-Line System for Algebraic Manipulation," PhD. dissert., Harvard U., Cambridge, Mass., 1966.
• 15: Goldberg, S.H., "Solution of an Electrical Network Using a Digital Computer," M.S. Thesis, *MIT, Cambridge, Mass.,| 1959.
• 16: Andrew D. Hall, Jr., The ALTRAN system for rational function manipulation - a survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.153-157, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806280]
• 17: Hart, T., "Simplify," Memo.27, Artificial Intelligence Group, Project MAC, MIT, Cambridge, Mass., 1961.
• 18: Hearn, A., "REDUCE: A User-Oriented Interactive System for Algebraic Simplification," In Interactive Systems for Experimental Applied Mathematics, Academic Press, New York, pp.79-90.
• 19: Hearn, A., "The Problem of Substitution," in Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM, Cambridge, Mass., pp.3-19.
• 20: Anthony C. Hearn, REDUCE 2: A system and language for algebraic manipulation, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.128-133, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806277]
• 21: S. C. Johnson, On the problem of recognizing zero, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.324-327, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806301]
• 22: Korsvold, K., "An On-Line Algebraic Simplification Program," Artificial Intelligence Project Memo. no.37, Stanford University, Stanford, California, Nov. 1965.
• 23: Manove, M. et al., "Rational Functions in MATHLAB," in Symbol Manipulation Languages and Techniques, North-Holland, Amsterdam, pp.86-102.
• 24: Martin, W., "Symbolic Mathematical Laboratory," Report MAC-TR-36. Project MAC, MIT, Cambridge, Mass., Jan. 1967.
• 25: William A. Martin, Determining the equivalence of algebraic expressions by hash coding, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.305-310, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806299]
• 26: W. A. Martin , R. J. Fateman, The MACSYMA system, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.59-75, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806267]
• 27: Minsky, M., and Papert, S., Perceptrons, MIT Press, Cambridge, Mass., 1969.
• 28: Joel Moses, Solutions of systems of polynomial equations by elimination, Communications of the ACM, v.9 n.8, p.634-637, Aug. 1966 [doi>10.1145/365758.365802]
• 29: Moses, J., "Symbolic Integration," Report MAC-TR-47, Project MAC, MIT, Cambridge, Mass., Dec. 1967.
• 30: Moses, J., "A Canonical Form for First Order Exponential Expressions," in preparation.
• 31: Moses, J., "Sarge - A Program for Drilling Students in Freshman Calculus Integration Problems," Project MAC memo., March 1968.
• 32: Moses, J., Rothschild, L.P., and Schroeppel, R., "A Zero Equivalence Algorithm for Expressions Formed by Functions Definable by First Order Differential Equations," in preparation.
• 33: Arthur E. Oldehoeft, Analysis of constructed mathematical responses by numeric tests for equivalence, Proceedings of the 1969 24th national conference, p.117-124, August 26-28, 1969 [doi>10.1145/800195.805923]
• 34: Perlis, A., et al., "A Definition of Formula Algol," Computation Center, Carnegie-Mellon Univ., Pitts., Pa., March 1966.
• 35: Richardson, D., "Some Unsolvable Problems Involving Functions of a Real Variable," PhD dissert., Univ. of Bristol, Bristol, England, 1966.
• 36: Richardson, R., "Some Unsolvable Problems Involving Elementary Functions of a Real Variable," Journal of Symbolic Logic, vol.33, 1968, pp.511-520.
• 37: Richardson, R., "A Solution of the Identity Problem for Integral Exponential Functions," Z. Math Logik u. Grundlagen Math, to appear.
• 38: Risch, R., "The Problem of Integration in Finite Terms," Trans. of the AMS, vol.139, May 1969, pp.167-189.
• 39: Risch, R., "On the Integration of Elementary Functions Which are Built up Using Algebraic Operations," Report SP-2801-002, Systems Develop. Corp., Santa Monica, Calif., June 1968.
• 40: Risch, R., "Further Results on Elementary Functions," Report RC 2402, IBM Corp., Yorktown Heights, NY, March 1969.
• 41: Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
• 42: Slagle, J., "A Heuristic Program that Solves Symbolic Integration Problems in Freshman Calculus," PhD dissert., MIT, May 1961.
• 43: R. G. Tobey, Experience with FORMAC algorithm design, Communications of the ACM, v.9 n.8, p.589-597, Aug. 1966 [doi>10.1145/365758.365773]
• 44: Tobey, R., et al. "PL/I-FORMAC Symbolic Mathematics Interpreter," IBM, Cambridge, Mass., 1969.
• 45: Tobey, R., et al., "Automatic Simplification in FORMAC," in Proc of Fall Joint Computer Conference, vol.27, 1965, pp.37-52.
• 46: van der Waerden, B., Modern Algebra, vol. I, F. Ungar, New York, pp.77-78.
• 47: Wooldridge, D., "An Algebraic Simplify Program in LISP," Art. Intell. Project Memo. no.ll, Stanford Univ., Stanford,Calif., Dec. 1963.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory