Next: 5. Conclusions Up: String Rewriting and Gröbner Previous: 3. Defining Reduction in

# 4. Group Rings

In this section we show how structural information on certain classes of groups can be used to prove termination of procedure PREFIX GR¨OBNER BASES and to improve it. Let us start with the classes of finite, free respectively plain groups. These groups have in common that they can be presented using convergent 2-monadic group presentations, i.e., contains inverses of length one for all generators and for all rules , and hold. In fact finite or free groups are also plain groups, but sometimes it is useful to take advantage of the additional information we have concerning them. For example we can improve the process of saturation. Given a non-trivial group element w we let denote the last letter and the inverse of w.

Definition 4..1   For a polynomial which has more than one monomial, we define
 =

Then we can set and . For a non-zero polynomial we set and .

Notice that , but in case p has more than one monomial .

Example 4..2   Let and be a presentation of a group with a length-lexicographical ordering induced by . Then for the polynomial we get , , and .

These polynomials can be used to define prefix saturating sets.

Lemma 4..3   Let contain more than one monomial. Then the following statements hold:
(1)
In case is a free group presented by , then is a prefix saturating set for p.
(2)
In case is a plain group presented by a reduced convergent 2-monadic group system , and , then is a prefix saturating set for p.

Then we can compute finite prefix Gröbner bases of finitely generated right ideals for plain group rings using procedure PREFIX GR¨OBNER BASES and specifying saturating sets as described in lemma 4.3.

Theorem 4..4   Given a 2-monadic confluent group presentation for a group and a finite set of polynomials , procedure PREFIX GR¨OBNER BASES terminates.

We continue to show how we can gain a similar result for context-free group rings. A finitely generated context-free group is a group with a free normal subgroup of finite index. Hence, let the group be given by X a finite set of generators for a free subgroup and a finite group such that and . For all let be a function such that is the inclusion and for all , . For all let such that and for all with , . Let and let T contain the following rules:

xx-1

and
x-1x

for all ,
e1e2

e3ze1,e2 for all

such that

,
xe

and
x-1e

for all

.

then is convergent and is called a virtually free presentation (compare [CrOt94]). Presenting in this way we find that the elements of the group are of the form eu where and . We can specify a total well-founded ordering on the group by combining a total well-founded ordering on and a length-lexicographical ordering on : Let such that where , . Then we define if and only if |w1| > |w2| or (|w1| = |w2| and or (|w1| = |w2|, and . This ordering is compatible with right concatenation using elements in in the following sense: Given presented as described above, implies for all in case .

Example 4..5   Let be the finite group presented by and and the free group generated by . Further let and be a conjugation homomorphism. Then and is a virtually free presentation of , the direct product of and .

Let us take a closer look at prefix reduction in .

Example 4..6   Let be the group specified in example 4.5. Further let , q1 = a + x and be polynomials in .
Then the polynomial p is prefix reducible at its head term ax2 by q1 giving us

On the other hand, as x2 is no prefix of ax2, this is not true for q2.

Since prefix reduction using a non-constant13 polynomial involves right multiples of the polynomial with elements in only, we can restrict ourselves to special prefix-saturating sets.

Definition 4..7   A set is called a -prefix saturating set for a non-zero polynomial p in , if for all the polynomial is prefix reducible to zero using F in one step. A set of polynomials is called a -prefix saturated set, if for all and for all the polynomial is prefix reducible to zero using F in one step.

Reviewing the results on free groups, for a polynomial p in we can specify and and use them to define -prefix saturating sets.

Definition 4..8   For a non-zero polynomial containing more than one monomial we define

and set . In case for we define and else . For a polynomial we set .

Lemma 4..9   For a non-zero polynomial p in the set is a -prefix saturating set.

Example 4..10   Let be the group specified in example 4.5 and a polynomial in . Then the polynomials and give us a -prefix-saturating set for p.

The following lemma will be used as an analogon to lemma 3.30 when we characterize prefix Gröbner bases by using prefix reduction, prefix s-polynomials and now -prefix saturated sets.

Lemma 4..11   Let p be a non-zero polynomial and F a set of polynomials in .
Then gives us a representation of , with such that for all with , we get . In particular for all with , if for some , then holds.

For every let the mapping be defined by for . We now can give a characterization of prefix Gröbner bases by transforming a generating set for a right ideal using these finitely many mappings. This will enable us to restrict ourselves to -prefix saturated sets when characterizing prefix Gröbner bases.

Theorem 4..12   Let and such that
(a)
,
(b)
, and
(c)
G is -prefix saturated.
Then the following statements are equivalent:
(1)
For all we have .
(2)
For all we have .

On first sight the characterization given in theorem 4.12 above might seem artificial. The crucial point is that in losing the property admissible'' for our ordering, an essential lemma in Buchberger's context, namely that implies for any term w, no longer holds. Defining reduction by restricting ourselves to prefixes we gain enough structural information to weaken this lemma, but we have to do additional work to still describe the right ideal congruence. One step is to close the set of polynomials generating the right ideal with respect to the finite group : For a set of polynomials F using the -closure we can characterize the right ideal generated by F in terms of since . If we additionally incorporate the concept of saturation, prefix reduction can be used to express the right ideal congruence and then a prefix Gröbner basis can be characterized as usual by prefix s-polynomials. Now, using the characterization given in theorem 4.12 we can modify procedure PREFIX GR¨OBNER BASES as follows:

Procedure: PREFIX GR¨OBNER BASES IN CONTEXT-FREE GROUP RINGS
< tex2html_comment_mark>


Given: 		 A finite set of polynomials

,
and

a virtually free presentation of                   .
Find:

a prefix Gröbner basis of F.



G :=

;
% G fulfills (a), (b) and (c) of theorem 4.12
B :=

;
while

do
% Test if  statement (2) of theorem 4.12 is valid

(q1, q2) := remove(B);
% Remove an element using a fair strategy
if

exists
% The s-polynomial is not trivial
then		   h:= normal form

;
% Compute a normal form using        prefix reduction
if
then 		 G :=

;
% G fulfills (a), (b) and (c) of theorem 4.12
B :=

;
endif
endif
endwhile



Termination can be shown as in theorem 4.4.

Notice that the classes of groups studied in this section are known to have solvable subgroup problem. For free groups there is Nielsen's approach known as Nielsen reduction (compare [LySch77,AvMa84]). Kuhn and Madlener have developed prefix reduction methods and applied them successfully to the class of plain groups (see [KuMa89]). Cremanns and Otto successfully treated the class of context-free groups (see [CrOt94]).

Next: 5. Conclusions Up: String Rewriting and Gröbner Previous: 3. Defining Reduction in
| ZCA Home | Reports |