Research and Advances

Algebraic simplification: a guide for the perplexed


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.

View this article in the ACM Digital Library.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More