Next: Bibliography Up: Solving One-Sided Equations in Previous: 4. Conclusions

# 5. Prefix Gröbner Bases in and

In [3] it was shown how to characterize and compute prefix Gröbner bases in monoid rings where is presented by a finite convergent string rewriting system. Here we want to show that if a finite prefix Gröbner basis exists for a right ideal, then there is also a finite reduced prefix Gröbner basis and we want to list two important properties of such a basis needed to characterize the solutions of the homogeneous equations in the previous section. Further we outline how the technique of Gröbner bases extends to right -modules .

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

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

Definition 4   Let , be two non-zero polynomials in .
We say prefix reduces to at in one step, i.e. , if
(a)
for some , i.e.  is a prefix of as a word.
(b)
and with , , and .
(c)
.

Prefix Gröbner bases with respect to this reduction relation then can be characterized using the concept of prefix s-polynomials combined with some extra polynomials which are necessary to describe the whole right ideal congruence by prefix reduction.

Definition 5   Given two polynomials with for . If there is with we have to distinguish:
1. If , , where , , we get the following superposition causing a critical pair:

This gives us the prefix s-polynomial

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

This gives us the prefix s-polynomial

Prefix Gröbner bases then can be characterized by the following theorem from [6]:

Theorem 6   Equivalent are:
1. .
• For all we have .
• For all , we have .

The set then is called a prefix Gröbner basis of the right ideal it generates. Notice that without loss of generality we can always assume that all head coefficients of its polynomials are greater than zero.

Lemma 7   Let be a finite prefix Gröbner basis and such that . Then 8 is again a prefix Gröbner basis of the same right ideal.

Proof : 1.1
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 property9(A4) holds if for any , and imply .
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:
1. If then we are done at once, since and hence .
2. If we have to be more careful as , i.e. the reduction step took place at the head monomial of and , .
1. If then . We get . Now either or there exist such that with . In either case then can be prefix reduced using .
2. If then and hence and imply that is prefix reducible by .
Now it is easy to see that is again a prefix Gröbner basis of the same right ideal. If some polynomial is reducible by it will also be reducible by . q.e.d.

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

Lemma 8   Let be a reduced prefix Gröbner basis. Further let such that and for some . Then for some and .

Proof : 1.1
We show that the other cases are not possible.
1. Assume that .
Then without loss of generality we can also assume and hence , , and . Therefore, contradicting the assumption that is supposed to be reduced.
2. Now let . We have to distinguish two cases:
1. 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.
2. If we get , , and . Then as before contradicting the assumption that is supposed to be reduced.
Hence the only possible case remains to be for some and . As before this gives rise to an s-polynomial, but now we cannot conclude that one of the polynomials , is reducible by it hence since we get no contradiction to being reduced, this case is possible. q.e.d.

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:

Definition 9   Let , . We say that prefix reduces to at in one step, denoted by , if
(a)
for ,
(b)
with , and
(c)
.

Hence prefix reduction in reduces to prefix reduction in . One can show that together with this reduction relation fulfills (A1) - (A4) for reduction rings as specified in [4] and Gröbner bases can be characterized using g- and m-polynomials. The basic idea is to compute a prefix Gröbner basis of a right -module generated by a set of vectors by modifying the set according to the following steps:
1. initialize a counter ,
2. 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,
3. 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 ,
4. continue for until all components have been handled.

Next: Bibliography Up: Solving One-Sided Equations in Previous: 4. Conclusions
| ZCA Home | Reports |