This rather informal paper addresses an important problem in computer algebra systems (CAS): “Which of many possible representations of a result, typically a mathematical expression, should be delivered as the answer?” Not surprisingly, this depends on how the result will be used. The use of CAS systems is such that the user expects that a reasonable representation be presented automatically. A tricky point is where two representations are almost equivalent, such as 1 and x/x.
This paper suggests that an elaborated version of Kolmogorov complexity is the right tool. It presents examples of the decisions a CAS must be able to take, and reviews the concepts of Kolmogorov complexity, the minimum description length (MDL) principle, and biform theories [1] that make the necessary connection between the MDL principle and the expression manipulation context.
The paper concludes with application examples illustrating the author’s experience with CAS usage and development.
There is very little systematic work here on general rules for expression simplification. This work primarily focuses on the length of the presented result, and is apparently novel in that it makes use of the biform framework [1]. This framework could perhaps have been presented in a more digestible way. A perspective not addressed in the paper is the connection to computation cost in using a result, since going between two equivalent representations may well incur asymmetric conversion costs.