5. Prefix Gröbner Bases in and

In order to use elements of
as rules for reduction we need an ordering
on and one on :
We will first specify a total well-founded ordering on
^{6}:

and iff or

As ordering on we take the one induced by the completion ordering on of the string rewriting system. This ordering has the advantage that it is admissible with respect to concatenation and we have where and the multiplication on is realized by normal form computation with respect to the string rewriting system presenting .

Then for any we can characterize its largest term as head term , the coefficient of this term as , and .

Let us briefly recall the reduction relation used for in [3].

We say

- (a)
- for some , i.e. is a prefix of as a word.
- (b)
- and with , , and .
- (c)
- .

- If ,
, where
,
, we get
the following superposition causing a critical pair:

- If ,
, where
, , we get
the following superposition causing a critical pair:

- .
- For all we have .
- For all , we have .

This follows as can be shown to be a ring with a reduction relation fulfilling the axioms (A1) - (A4) for reduction rings as presented in [4]. It is easy to see that the reduction relation is terminating (A1), preserves the right ideal congruence (A2) and for any non-zero polynomial holds (A3). The important axiom allowing to reduce prefix Gröbner bases without losing the prefix Gröbner basis property

Let at some monomial , i.e. for some , , , and . Moreover, let at some monomial , i.e. for some , , , and . We have to distinguish the following cases:

- If then we are done at once, since and hence .
- If we have to be more careful as
, i.e. the reduction step took place
at the head monomial of and
,
.
- If then . We get . Now either or there exist such that with . In either case then can be prefix reduced using .
- If then and hence and imply that is prefix reducible by .

1
Now a prefix Gröbner basis is called ** reduced** if no is prefix reducible
by
.

We show that the other cases are not possible.

- Assume that .

Then without loss of generality we can also assume and hence , , and . Therefore, contradicting the assumption that is supposed to be reduced. - Now let . We have to distinguish two cases:
- If again we have , , and . This situation now gives rise to an s-polynomial . Notice that this s-polynomial has head monomial and hence is neither reducible by nor by . On the other hand, as is a prefix Gröbner basis, the s-polynomial must be reducible to zero using elements of . Additionally we know that is reducible by this s-polynomial which implies that then must also be reducible by some element in contradicting our assumption of being reduced.
- If we get , , and . Then as before contradicting the assumption that is supposed to be reduced.

1

If we want to compute prefix Gröbner bases of submodules in a right -module this can be done by introducing a reduction relation and completing it. Provided a finite basis , ..., of its elements can be represented by polynomials . A reduction relation now can be defined as follows:

- (a)
- for ,
- (b)
- with , and
- (c)
- .

- initialize a counter ,
- compute a prefix Gröbner basis of the right ideal generated by the head terms of those vectors with which is in fact a prefix Gröbner basis computation in which also affects the components of the vectors involved ``below'' the i-th component,
- compute a set of solutions for the homogeneous equation related to those vectors with hence generating new generators for the submodule with non-zero component larger than ,
- continue for until all components have been handled.