I guess you'll find much of what you would like to know in this 2004 <A HREF="http://www.cas.mcmaster.ca/~carette/publications/simplification.pdf">paper</A> by Jacques Carette (published <A HREF="http://dx.doi.org/10.1145/1005285.1005298">here</A>):

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