On Canonical Forms and Simplification B. F. CAVINESS* Carnegie-Mellon University, Pitlsburgh, Pennsylvania 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 nmnber- theoretic conjecture, a large subclass of the negative classes is shown to possess a canonical form. KEY WORDS AND PHRASES: symbolic mathematics, nonnumerical mathematics, formula manip- ulation, simplification, canonical form, normal form, standard form, exponential expressions CR CATEGORIES: 5.10, 5.20 1. Introduction 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 2 + x(e e~+~) + 1 will produce an expression similar to 2x I -~- l(e e3+2) + x(O'e 3 + 0)(e e~+2) -t- 0 (1) instead of the functionally equivalent and structurally simpler expression 2X + e e3+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 trans- formations, such as reducing rational expressions by factoring out greatest common divisors, lexieographieal 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 expres- sions 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 Ottiee of the Secretary of Defense (S1)-146). Journal of the Association for Computing Machinery, Vol. 17, No. 2, April 1970, pp. 385-396.386 B.F. CAVINESS algorithms for performing simplification have been reported in the literature. See Sammet's bibliographies [18, 19] for a listing of these. The usual form of attack of these algorithms has been to take a set of simplifying transformations that apply in obvious local cases and to try to weld these into a stable and coherent global scheme for simplifying a class of expressions. The need for simplification and the kind of simplification transforms needed seem obvious in simple cases. However, as expressions and algorithms increase in complexity, the answers are no longer so obvious. Fenichel [8], Moses [11], and Tobey, Bobrow, and Zilles [20] have discussed the problems of the simplification algorithms in some detail. One of the main conclu- sions to be drawn from their discussions is that simplification has meaning only in a local context. For instance, Fenichel points out that csc2(x) - cot (x) csc (x) is easier to integrate than its structurally simpler equivalent 1/[1 + cos (x)]. Thus in the context of integration the former expression is simpler, whereas in other cases the latter is considered simpler. Recently Richardson [15] provided some theoretical evidence of simplification problems. He proved that for sufficiently rich classes of expressions it is impossible to identify all expressions which are identically zero. Hence no set of local simplifi- cation transforms such as x -- x --~ 0 can be sufficient for Richardson's class of expressions. In this paper we study simplification through the concepts of canonical and normal forms. These global concepts, as developed in Section 3, are formalized alternatives to the ill-defined notion of a simplified form and hence are appropriate for a careful study. The structures of some common classes of expressions are studied and canonical (or normal) forms are shown to exist for these classes. Some of the results of Section 4 are similar to results obtained by others. Results of W. S. Brown [2] and Richardson [16] are discussed later. P. J. Brown [1] has written an interesting paper in which he studies the existence of canonical forms in a more general setting than we have. A paper by G. Rousseau [17] attacks some problems similar to ours in a somewhat different realm. He proves the existence of an effective procedure for deciding whether or not functions contained in a subclass of the primitive recursive functions are identically zero. (This problem is recursively undecidable for the class of all primitive recursive functions.) This paper is itself a revision of parts of [3]. 2. Undecidability Results From Richardson's theorem we know that canonical forms cannot exist for certain classes of expressions. In order to limit the search for canonical forms, it is desirable to have as much information as possible about negative results. Thus in this section Richardson's theorem and proof are studied in detail. From Richardson's proof and from studies on the unsoIvability of Hilbert's tenth problem, some conclusions about sharpenings of Richardson's theorem are drawn. To be given a class of expressions ~ means to be given an effective set of rules for determining the well-formed expressions in the class. The expressions must be formed from a finite set of atomic symbols of which a subset must be designated as variables. Any member of ~ not containing a variable is called an k-constant or Journal of the Association for Computing