Article

Understanding expression simplification

Author:

Jacques CaretteAuthors Info & Claims

ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation

Pages 72 - 79

https://doi.org/10.1145/1005285.1005298

Published: 04 July 2004 Publication History

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]

J. Beaumont, R. Bradford, and J. H. Davenport. Better simplification of elementary functions through power series. In Proceedings of the 2003 international symposium on symbolic and algebraic computation, pages 30--36. ACM Press, 2003.]]

Digital Library

[2]

R. Boyer and J. Moore. A Computational Logic Handbook. Academic Press, 1988.]]

Digital Library

[3]

M. Bronstein. Simplification of real elementary functions. In Proceedings of ISSAC 1989, pages 207--211, 1989.]]

Digital Library

[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. Caviness. On canonical forms and simplification. J. ACM,17(2): 385--396, 1970.]]

Digital Library

[7]

E. Cheb-Terrab. personal communication.]]

[8]

F. Chyzak and B.Salvy. Non-commutative elimination in ore algebras proves ultivariate identities. Journal of Symbolic Computation, 26(2): 187--227, 1998.]]

Digital Library

[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]

R. M. Corless, J. H. Davenport, David J. Jeffrey, G. Litt, and S. M. Watt. Reasoning about the elementary functions of complex analysis. In Proceedings AISC Madrid, volume 1930 of Lecture Notes in AI. Springer, 2000.]]

Digital Library

[11]

J. Davenport, Y. Siret, and E. Tournier. Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic Press, 1988.]]

Digital Library

[12]

W. M. Farmer and M. v. Mohrenschildt. Transformers for symbolic computation and formal deduction. In S. Colton, U. Martin, and V. Sorge, editors, Proceedings of the Workshop on the Role of Automate Deduction in Mathematics, CADE-17, pages 36--45, 2000.]]

Digital Library

[13]

W. M. Farmer and M. v. Mohrenschildt. An overview of a formal framework for anaging athematics. Annals of Mathematics and Artificial Intelligence, 2003. In the forthcoming special issue: B. Buchberger, G. Gonnet, and M. Hazewinkel, eds., Mathematical Knowledge Management.]]

Digital Library

[14]

K. Geddes, S. Czapor, and G. Labahn. Algorithms for Computer Algebra. Kluwer, Boston/Dordrecht/London,1992.]]

Digital Library

[15]

J. Grabmeier, E. Kaltofen, and V. Weispfenning, editors. Computer Algebra Handbook: Foundations, Applications, Systems. Springer-Verlag, 2003.]]

Digital Library

[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.]]

Digital Library

[18]

M. Li and P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, Berlin, 1997.]]

Digital Library

[19]

J. Moses. Algebraic simplification: a guide for the perplexed. Communications of the ACM, 14(8):548--560, 1971.]]

Digital Library

[20]

J. Mulholland and M. Monagan. Algoriths for trigonometric polynomials. In Proceedings of the 2001 international symposium on Symbolic and algebraic computation, pages 245--252. ACM Press, 2001.]]

Digital Library

[21]

J. Rissanen. Modeling by shortest data description. Automatica, 14:465--471, 1978.]]

Digital Library

[22]

D. A. Schmidt. Denotational Semantics: A Methodology for Language Development. W. C. Brown, Dubuque, Iowa, 1986.]]

Digital Library

[23]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 2003.]]

Digital Library

[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]

D. Zeilberger. A holonomic systems approach to special function identities. J. Comput. Appl. Math., 32:321--368, 1990.]]

Digital Library

[26]

R. Zippel. Simplification of expressions involving radicals. J. of Symbolic Computation, 1(1):189--210, 1985.]]

Digital Library

Cited By

Sawlat NQani YSadeqi N(2024)Numerical and Symbolic Analysis for Mathematical Problem-Solving with MapleJournal of Natural Science Review10.62810/jnsr.v2i3.752:3(29-46)Online publication date: 30-Sep-2024
https://doi.org/10.62810/jnsr.v2i3.75
Pickering Ldel Río Almajano TEngland MCohen K(2024)Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decompositionJournal of Symbolic Computation10.1016/j.jsc.2023.102276123(102276)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2023.102276
Florescu DEngland M(2024)Constrained Neural Networks for Interpretable Heuristic Creation to Optimise Computer Algebra SystemsMathematical Software – ICMS 202410.1007/978-3-031-64529-7_19(186-195)Online publication date: 22-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-64529-7_19
Show More Cited By

Index Terms

Understanding expression simplification
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Representation of mathematical objects

Recommendations

An Additivity Theorem for Plain Kolmogorov Complexity

We prove the formula C(a,b)=K(a|C(a,b))+C(b|a,C(a,b))+O(1) that expresses the plain complexity of a pair in terms of prefix-free and plain conditional complexities of its components.
Effective complexity and its relation to logical depth

Effective complexity measures the information content of the regularities of an object. It has been introduced by Gell-Mann and Lloyd to avoid some of the disadvantages of Kolmogorov complexity. In this paper, we derive a precise definition of effective ...
Kolmogorov Complexity for Possibly Infinite Computations

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation

July 2004

334 pages

ISBN:158113827X

DOI:10.1145/1005285

General Chair:
Josef Schicho
RICAM, Austrian Academy of Sciences, Linz, Austria

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC04

Sponsor:

ISSAC04: International Symposium on Symbolic and Algebraic Computation

July 4 - 7, 2004

Santander, Spain

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
667
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sawlat NQani YSadeqi N(2024)Numerical and Symbolic Analysis for Mathematical Problem-Solving with MapleJournal of Natural Science Review10.62810/jnsr.v2i3.752:3(29-46)Online publication date: 30-Sep-2024
https://doi.org/10.62810/jnsr.v2i3.75
Pickering Ldel Río Almajano TEngland MCohen K(2024)Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decompositionJournal of Symbolic Computation10.1016/j.jsc.2023.102276123(102276)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2023.102276
Florescu DEngland M(2024)Constrained Neural Networks for Interpretable Heuristic Creation to Optimise Computer Algebra SystemsMathematical Software – ICMS 202410.1007/978-3-031-64529-7_19(186-195)Online publication date: 22-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-64529-7_19
Henglein FKaarsgaard RMathiesen M(2022)The Programming of AlgebraElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.360.4360(71-92)Online publication date: 30-Jun-2022
https://doi.org/10.4204/EPTCS.360.4
Su WCai CWang PLi HHuang ZHuang Q(2021)Complexity of Mathematical Expressions and Its Application in Automatic Answer CheckingSymmetry10.3390/sym1302018813:2(188)Online publication date: 25-Jan-2021
https://doi.org/10.3390/sym13020188
Johansson FChyzak FLabahn G(2021)CalciumProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465513(225-232)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465513
Ayoub TBasu KJeffrey D(2021)Bernoulli’s Problem $$x^y=y^x$$ and MapleMaple in Mathematics Education and Research10.1007/978-3-030-81698-8_5(67-76)Online publication date: 20-Jul-2021
https://doi.org/10.1007/978-3-030-81698-8_5
Ayoub TBasu KJeffrey D(2020)Recent results on the Lambert W function2020 22nd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC51798.2020.00059(36-39)Online publication date: Sep-2020
https://doi.org/10.1109/SYNASC51798.2020.00059
Florescu DEngland M(2020)A Machine Learning Based Software Pipeline to Pick the Variable Ordering for Algorithms with Polynomial InputsMathematical Software – ICMS 202010.1007/978-3-030-52200-1_30(302-311)Online publication date: 8-Jul-2020
https://doi.org/10.1007/978-3-030-52200-1_30
Florescu DEngland M(2020)Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output CorrectnessMathematical Aspects of Computer and Information Sciences10.1007/978-3-030-43120-4_27(341-356)Online publication date: 18-Mar-2020
https://doi.org/10.1007/978-3-030-43120-4_27
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten