Algebraic simplification: a guide for the perplexed

ABSTRACT

Algebraic simplification is examined first from the point of view of a user who needs 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 nonexistence of algorithms for certain classes of expressions are included.

REFERENCES

• 1: Abrahams, P.W. Application of LISP to sequence prediction. Comm. ACMg, 8 (Aug. 1966), 551.
• 2: Brown, W.S., et al. The ALPAK system for non-numerical algebra on a Digital Computer-II. Bell Sys. Tech. J. 43, 2 (Mar. 1964), 785-804.
• 3: Brown, W.S. Rational exponential expressions and a conjecture concerning rr and e. Amer. Math. Monthly 76 (Jan. 1969), 28-34.
• 4: Caviness, B.F. On canonical forms and simplification. Ph.D. diss., Carnegie-Mellon U., Pittsburgh, Pa., Aug. 1967.
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: Carl Engelman, The legacy of MATHLAB 68, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.29-41, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806265]
• 10: Engeli, M. User's manual for the formula manipulation language SYMBAL. Computer Center, U. of Texas at Austin, 1968.
• 11: 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]
• 12: Fateman, R. Essays in algebraic simplification. Ph.D. diss., Harvard U., Cambridge, Mass., 1971.
• 13: Fenichel, R. An on-line system for algebraic manipulation. Ph.D. diss., Harvard U., Cambridge, Mass., 1966.
• 14: 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]
• 15: Andrew D. Hall, Jr., The Altran system for rational function manipulation — a survey, Communications of the ACM, v.14 n.8, p.517-521, Aug. 1971 [doi>10.1145/362637.362644]
• 16: Hearn, A. REDUCE: A user-oriented interactive system for algebraic simplification. In b~teractive Systems for Experimental Applied Mathematics. Academic Press, New York, 1968, pp. 79-90.
• 17: Hearn, A. The Problem of Substitution. Proc. 1968 Summer Inst. on Symbolic Math. Comput. IBM, Cambridge, Mass., pp. 3-19.
• 18: 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]
• 19: Korsvold, K. An on-line algebraic simplification program. Artif. Intell. Proj. Memo. no. 37, Stanford U., Stanford, Cal., Nov. 1965.
• 20: 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]
• 21: Matijasevic, J.V. Enumerable sets are diophantine. Soviet Math. Dokl., 11, 1970.
• 22: Minsky, M., and Papert, S. Perceptrons. MIT Press, Cambridge, Mass., 1969.
• 23: Moses, J. Symbolic integration. Report MAc-TR-47, Project MAC, MIT, Cambridge, Mass., Dec. 1967. (Available as AD 662-666, Clearinghouse, Springheld, Va. 22151.)
• 24: Moses, J. A canonical form for first order exponential expressions. In preparation.
• 25: 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.
• 26: 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]
• 27: Perils, A., et al. A definition of Formula Algol. Comput. Center, Carnegie-Mellon U., Pittsburgh, Pa., Mar. 1966.
• 28: Richardson, D. Some unsolvable problems involving functions of a real variable. Ph.D. diss., U. of Bristol, England, 1966.
• 29: Richardson, D. Some unsolvable problems involving elementary functions of a real variable. J. Symb. Logic 33 (1968), 511-520.
• 30: Richardson, D. A solution of the identity problem for integral exponential functions. Z. Math Logik u. Grundlagen Math, to appear.
• 31: Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
• 32: 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]
• 33: Tobey, R., et al. Automatic simplification in FORMAC. Proc. A9IPS 1965 FJCC, Vol. 27, Pt. 1, Spartan Books, New York, pp. 37-57.

INDEX TERMS

Keywords:
algebraic manipulation, algebraic simplification, canonical simplification