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 2monadic 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 nontrivial 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 nonzero 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
lengthlexicographical ordering induced by
.
Then for the polynomial
we get
,
,
and
.
These polynomials can be used to define prefix saturating sets.
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 2monadic confluent group presentation for a group
and a finite set of polynomials
,
procedure P
REFIX G
R¨
OBNER B
ASES
terminates.
We continue to show how we can gain a similar result for contextfree
group rings.
A finitely generated contextfree 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^{1}x
for all ,
e_{1}e_{2}
e_{3}z_{e1,e2} for all
such that
,
xe
and
x^{1}e
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 wellfounded ordering on the group by combining a
total wellfounded ordering
on
and a
lengthlexicographical
ordering
on :
Let
such that
where
,
.
Then we define
if and only if
w_{1} > w_{2}
or
(w_{1} = w_{2} and
or
(w_{1} = w_{2},
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
,
q_{1} =
a +
x and
be polynomials in
.
Then the polynomial
p is prefix reducible at its head term
ax^{2} by
q_{1} giving us
On the other hand, as
x^{2} is no prefix of
ax^{2}, this is not true
for
q_{2}.
Since prefix reduction using a nonconstant^{13} polynomial involves
right multiples of the polynomial with elements in
only, we
can restrict ourselves to special prefixsaturating sets.
Definition 4..7
A set
is called a
prefix saturating set
for a nonzero 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 nonzero 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 nonzero 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
prefixsaturating 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 spolynomials and now prefix saturated
sets.
Lemma 4..11
Let
p be a nonzero 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.
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 spolynomials.
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 CONTEXTFREE 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
(q_{1}, q_{2}) := remove(B);
% Remove an element using a fair strategy
if
exists
% The spolynomial 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 contextfree groups (see
[CrOt94]).
Next: 5. Conclusions
Up: String Rewriting and Gröbner
Previous: 3. Defining Reduction in
 ZCA Home 
Reports 