5. Orderings

As will be seen later, orderings play an important rôle for the enumeration process. The strategies presented will behave differently when they are combined with different orderings. Three different orderings are defined which are well-founded, total, and admissible. They are implemented in MRC 1.2 and are used for the coset enumerations.

Let be a finite alphabet. Let be a total precedence on . Let . The

iff | or | |

and |

Let be a finite alphabet. Let be a total precedence on . Let . Let be a total function attaching a weight to each letter of the alphabet. Then is defined on words as:

The ** Knuth-Bendix ordering (kbo)** is defined as:

iff | or | |

and |

Let be a finite alphabet. Let be a total precedence on . Let be a total function named

The ** syllable ordering**
is defined as:

iff or

and and

and and

and

or

and

Notice, that the syllable ordering has a recursive definition. In MRC 1.2 the orderings are implemented according to the definitions given with the restriction that for the syllable ordering or . That is, for all letters of the alphabet syllables are either compared from left to right or from right to left.

The comparison of terms is frequently needed for example for the determination of the head term after each reduction step. Therefore, the time needed to compare two terms with respect to the chosen ordering directly influences the time needed to compute the prefix Gröbner basis. As can be seen from the definitions, the length-lexicographical ordering has at least to compare the length of the two terms and at most compare the length and compare each character of the terms. The Knuth-Bendix ordering has at least to compute the sum of both terms and at most compute the sum and compare each character of the term. The syllable ordering has at least to count the number of syllables of each term and at most in addition compare the syllables recursively. Thus, we have that the expense needed for the comparison of two terms grows from length-lexicographical over Knuth-Bendix to syllable orderings.