2 Heuristic simplification of exponential CR expressions

The second pass of the heuristic simplification procedure is concerned with exponential CRs. Similar to the simplification of polynomial CRs, we first isolate all subexpressions of a CR expression which either already are, or could potentially be, transformed into an exponential CR and then deal with each of these expressions separately. Therefore, we may assume that the expressions which are to be simplified are CR expressions whose leaves are either already simplified polynomial CRs or are simple, one - dimensional exponential CRs.

Secondly, we once again treat the one - dimensional case differently from the
*n*-dimensional case.

The simplification of one - dimensional exponential CR expressions is very similar to the simplification of one - dimensional polynomial CR expressions, except that we can not use the degree of an expression to predetermine its CI. Instead, we symbolically determine the structure of the exponential CR expression which is obtained by unconditionally applying all simplification rules and can then easily read its CI. Hence, the algorithm for simplifying one - dimensional exponential CR expressions proceeds as follows:

**Algorithm** CREXPSIMP1D

**Input:**- CR expression with
**Output:**- Simplified CR expression with

**(A)**- If is a constant or a CR then return ;
**(B)**- Let
*c*_{a}be the CI of the expression which would be obtained from by unconditionally applying the simplification rules (6) - (15). **(C)**- If
then

Unconditionally apply the simplification rules (6) - (15) to and return the result. **(D)**- else
/* Now
*/

Return*f*CREXPSIMP1D CREXPSIMP1D .

For example, if we are given the expression
,
then to realize step
(B) we symbolically apply all simplification rules and obtain the
symbolic CR expression
which has a CI of
*c*_{s} = 8 *w*_{<tex2htmlverbmark>28<tex2htmlverbmark>} + 4
*w*_{<tex2htmlverbmark>29<tex2htmlverbmark>}. Consequently, if
then we actually apply all
simplification rules to
and return the results. Otherwise, we
call the algorithm recursively on
and
before returning the result.

We apply an even simpler strategy for *n*-dimensional exponential CR
expressions by basing the decision whether or not to apply a
simplification rule on local criteria, only. The reason for not taking
properties of the entire expression into account is that the
multi - dimensional polynomial CRs which are the leaves of the
expression already predetermine the variable orderings, and
furthermore greatly complicate the construction of symbolic
expressions:

**Algorithm** CREXPSIMPND

**Input:**- Multi - dimensional, exponential CR expression .
**Output:**- Simplified CR expression with

**(A)**- If is a constant or a CR then return ;
**(B)**- If is a one - dimensional CR expression return CREXPSIMP1D;
**(D)**- else
/* Now
*/
- 1.
- Set CREXPSIMPND for ;
- 2.
- If one of the simplification rules (6) - (15) applies to such that the CI is reduced then apply the rule (if a choice of a variable ordering is involved, choose the one which results in the smaller CI) and recursively apply the algorithm to the coefficients of the obtained CR;
- 3.
- else return ;