||abstract. This paper deals with the simplification problem of symbolic mathematics. The notion of canonical form is defined and presented as a well-defined alternative to the concept of simplified form. Following Richardson it is shown that canonical forms do not exist for sufficiently rich classes of mathematical expressions. However, with the aid of a number-theoretic conjecture, a large subclass of the negative classes is shown to possess a canonical form.
keywords and phrases: symbolic mathematics, nonnumerical mathematics, formula manipulation, simplification, canonical form, normal form, standard form, exponential expressions
cs categories: 5.10,5.20
Formula manipulation is the process of carrying out operations and transformations on mathematical expressions or formulas. In formula manipulation processes, expressions with unnecessarily complicated structures are invariably generated. For example, most differentiation algorithms, when applied to the expression x + x(e +2) + 1 will produce an expression similar to
2т1 + l(ee3+2) + x(0-e3 + 0)fee3+2) + 0 (l)
instead of the functionally equivalent and structurally simpler expression
2x + ee3+2. (2)
Such behavior seems to be intrinsic to most formula manipulation algorithms. The process of transforming expressions like (1) into a simpler equivalent form like (2) is called simplification. Simplification is also taken to embrace other kinds of transformations, such as reducing rational expressions by factoring out greatest common divisors, lexicographical ordering of subexpressions appearing in sums and products, etc.
There are at least three important reasons for keeping expressions in a simplified form. First of all, simplified expressions usually require less memory. Second, the processing of simplified formulas is faster and simpler. The processing is simpler in the sense that simplified formulas usually possess nice features which make possible cleaner and more precise algorithm design. Third, functionally equivalent expressions are easier to identify when they are in simplified form. Indeed, simplification is of such a nature that almost no formula manipulation program can do without simplification capabilities.
Given the central role of simplification, it is hardly surprising to find that many
* Present address: Department of Mathematics, Duke University, Durham, N.C. This work was supported in part by an NSF graduate fellowship and by the Advanced Research Projects Agency of the Office of the Secretary of Defense (SD-146).
Journal of the Association for Computing Machinery, Vol. 17, No. 2, April 1970, pp. 385-396.