Next: 6. Examples and Notations Up: Coset Enumeration using Prefix Previous: 4. Strategies

# 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.

Definition 1 (Length-Lexicographical Ordering)
Let be a finite alphabet. Let be a total precedence on . Let . The length-lexicographical ordering is defined as:

 iff or and

Definition 2 (Knuth-Bendix Ordering)
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

Definition 3 (Syllable Ordering)
Let be a finite alphabet. Let be a total precedence on . Let be a total function named status function. Let be the largest letter of with respect to the precedence on .

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.

Next: 6. Examples and Notations Up: Coset Enumeration using Prefix Previous: 4. Strategies
| ZCA Home | Reports |