Table 1 lists the major rules for simplifying multi - dimensional CR expressions. Most of these are generalizations of the rules given in [#!us:issac94!#,#!me:hisc!#,#!zima:issac95!#] from one- or two-dimensional CR expressions to multi - dimensional CR expressions. For a more detailed description and a proofs of these rules, see [#!me:thesis!#].
The left hand sides (LHS) of the simplification rules are given in column 2 and the respective right hand sides (RHS) are given in column 3. For reasons of clarity, the trivial simplification rules for general CR expressions based on the ring axioms are not shown.
In general, the difference CI(LHS) - CI(RHS) is dependent on the complexity of the regular grid, on the weights of the operations involved, and on a chosen variable ordering. Column 4 marks the cases where CI(LHS)-CI(RHS) > 0 independently of all of these factors (the symbol is used to mark the rules where CI(LHS)-CI(RHS) > 0 can not be decided a priori). Column 5 shows CI(LHS) - CI(RHS) of one - dimensional CR expressions for which this difference depends at most on the weights of the operations involved.
For one - dimensional CRs, the application of a simplification rule is
always unique in the sense that the same rule can not be applied to
the same CR expression and yield different simplification
results. However, this is, in general, not the case for
multi - dimensional CRs. Let us illustrate this by an example: Let
Then by (6),
More generally, the freedom of choosing a variable ordering implies an additional degree of freedom in applying certain simplification rules which consequently has an impact on the CI of the simplified CR expression. Column 6 of table 1 marks all simplification rules to which this applies with the symbol .