Understanding expression simplification

ABSTRACT

We give the first formal definition of the concept of simplification for general expressions in the context of Computer Algebra Systems. The main mathematical tool is an adaptation of the theory of Minimum Description Length, which is closely related to various theories of complexity, such as Kolmogorov Complexity and Algorithmic Information Theory. In particular, we show how this theory can justify the use of various "magic constants" for deciding between some equivalent representations of an expression, as found in implementations of simplification routines.

REFERENCES

• 1: James Beaumont , Russell Bradford , James H. Davenport, Better simplification of elementary functions through power series, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.30-36, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860867]
• 2: Robert S. Boyer , J. Strother Moore, A computational logic handbook, Academic Press Professional, Inc., San Diego, CA, 1988
• 3: M. Bronstein, Simplification of real elementary functions, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.207-211, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74566]
• 4: B. Buchberger and R. Loos. Algebraic simplification In B. Buchberger, G. E. Collins, and R. Loos, editors, Computer Algebra-Symbolic and Algebraic Computation, pages 11--44. Springer-Verlag, New York, 1982.
• 5: J. Carette, W. Farmer, and J. Wajs. Trustable communication between mathematical systems. In T. Hardin and R. Rioboo, editors, Proceedings of Calculemus 2003,pages 58--68, Rome, 2003. Aracne.
• 6: 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]
• 7: E. Cheb-Terrab. personal communication.
• 8: Frédéric Chyzak , Bruno Salvy, Non-commmutative elimination in ore algebras proves multivariate identities, Journal of Symbolic Computation, v.26 n.2, p.187-227, Aug. 1998 [doi>10.1006/jsco.1998.0207]
• 9: R. Corless, G. Gonnet, D. Hare, D. Jeffrey, and D. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5:329--359, 1996.
• 10: Robert M. Corless , James H. Davenport , David J. Jeffrey , Gurjeet Litt , Stephen M. Watt, Reasoning about the Elementary Functions of Complex Analysis, Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation, p.115-126, July 17-19, 2000
• 11: J. H. Davenport , Y. Siret , E. Tournier, Computer algebra: systems and algorithms for algebraic computation, Academic Press Ltd., London, UK, 1988
• 12: Simon Colton , Volker Sorge , Ursula Martin, Workshop: The Role of Automated Deduction in Mathematics, Proceedings of the 17th International Conference on Automated Deduction, p.517, June 17-20, 2000
• 13: William M. Farmer , Martin V. Mohrenschildt, An Overview of a Formal Framework for Managing Mathematics, Annals of Mathematics and Artificial Intelligence, v.38 n.1-3, p.165-191, May 2003 [doi>10.1023/A:1022971915900]
• 14: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 15: Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
• 16: P. Grünwald. The Minimum Description Length Principle and Reasoning under Uncertainty. PhD thesis, CWI, 1998.
• 17: S. Landau. Simplification of nested radicals. SIAM Journal on Computing, 14(1):184--195, 1985.
• 18: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 19: 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]
• 20: Jamie Mulholland , Michael Monagan, Algorithms for trigonometric polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.245-252, July 2001, London, Ontario, Canada [doi>10.1145/384101.384135]
• 21: J. Rissanen. Modeling by shortest data description. Automatica, 14:465--471, 1978.
• 22: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• 23: Joachim Von Zur Gathen , Jurgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, NY, 2003
• 24: C. S. Wallace and D. Dowe. Minimum message length and kolmogorov complexity. Computer Journal (special issue on Kolmogorov complexity), 42(4):270--283, 1999.
• 25: Doron Zeilberger, A holonomic systems approach to special functions identities, Journal of Computational and Applied Mathematics, v.32 n.3, p.321-368, Nov. 27, 1990 [doi>10.1016/0377-0427(90)90042-X]
• 26: R Zippel, Simplification of expressions involving radicals, Journal of Symbolic Computation, v.1 n.2, p.189-210, June 1985 [doi>10.1006/jsco.1993.1041]

INDEX TERMS

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

Keywords:
Kolmogorov complexity, computer algebra, model description length, simplification of expressions