The simplification strategies developed in this paper, considered, for the first time, CR simplifications not independently of the computational context and firstly addressed the problem of variable orderings for multi - dimensional CR expressions. Our simplification strategies were based on the Cost Index (CI) of a CR expression, which we introduced in Section 2 as a system-independent measure for the evaluation cost, and on the analysis of the influence of CR simplifications on the CI of the transformed CR expressions (Section 3).
Our first CR simplification algorithm, given in Section 4, employs an exhaustive search technique to find the CR expression with a minimal CI. While this strategy has the advantage of resulting in a CR expression whose evaluation cost is minimal, the algorithm itself has a (worst case) exponential time and space complexity and is therefore of limited applicability. As an alternative, we furthermore developed a heuristic simplification algorithm, which balances the time spent during simplifications with the time saved in the following evaluations. The suggested heuristics are based on observations about the structure of CR simplification rules and on the ratio of the dimensions of the evaluation domain (for determining the variable ordering of multi - dimensional CRs). The simplifications are accomplish in a reasonable time (i.e., in at most polynomial time) such that the CI of the resulting CR expression is close to the minimum.
The MPCR server - our implementation of the CR method described in [#!me:sigsam!#,#!me:thesis!#] - successfully implements the simplification algorithms described here, and the reported timings are a further illustration that our proposed strategies work.
Numerous, often tediously to describe, but more or less obvious refinements of these simplification strategies are possible, especially for the multi - dimensional heuristic simplification algorithms. Furthermore, the simplification strategies should be extended to include rational and factorial simplifications of CR expressions based on the principles given in [#!zima:issac95!#].