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
Rissanen's 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.
|