Next: 4. Group Rings
Up: String Rewriting and Gröbner
Previous: 2. Fundamental Relations Between
3. Defining Reduction in
Throughout this paper let
be a monoid presented by a finite
convergent semiThue system
and
the
wellfounded ordering
on
induced by the completion ordering of its presentation.
Notice that although the completion ordering is compatible on
with concatenation, this in general no longer holds for the
ordering
on
with respect to the multiplication
on
.
For example groups do not allow compatible wellfounded orderings due
to the existence of inverse elements.
Given a nonzero polynomial p in
,
the head term
is the
largest term in p with respect to ,
is the
coefficient of this term and
the
head monomial.
is the set of terms occurring in
p.
The ordering on
can be extended to a partial ordering on
by setting p > q if and only if
or
and
,
and this ordering is Noetherian.
Frequently in polynomial rings reduction is defined by
using the head monomial of a polynomial as a left hand side of a
rule in case the head term of the
polynomial is a divisor of the term of the monomial to be reduced.
But defining reduction in this way for monoid rings need not be
Noetherian as the following example shows.
Example 3..1
Let
and
be a presentation of a group
with a
lengthlexicographical ordering induced by
.
Suppose we simply require divisibility
^{10} of the head term to allow reduction.
Then we could reduce the
polynomial
at the monomial
b^{2} by the polynomial
a +
b as
.
This would give us:
and the polynomial

b^{4} + 1 likewise would be reducible by
a +
b at the monomial 
b^{4} causing an
infinite reduction sequence.
Hence we will need additional restrictions in order to prevent
that a monomial is replaced by a larger polynomial.
Since our monoid
in general is not commutative, we will restrict ourselves
to right ideals  hence to right multiples  and inspect two variations of defining right reduction.
For further variants see e.g. [MaRe95,Re95].
Definition 3..2
Let
p,
f be two nonzero polynomials in
.
We say
f strongly right reduces p to
q at
a monomial
of
p in one step, denoted by
,
if
 (a)

for some
,
and
 (b)

.
We write
if there is a polynomial
q as defined
above and
p is then called strongly right reducible by
f.
Strong right reduction by a set
is denoted by
and abbreviates
for some
.
Note that in order to strongly right reduce p, the polynomial f
need not be smaller than p.
The condition
prevents reduction with a polynomial in case
,
i.e., if
the monomials of f eliminate each other by multiplying f with w.
This might happen in case the monoid ring contains zerodivisors.
Further, in case we have
at the monomial
,
then
.
In order to decide, whether a polynomial f strongly right reduces a
polynomial p at a monomial
one has to decide whether
there exist elements
and
such that
.
Since this problem is connected to solving equations
in one variable
in the monoid
presented by
,
this problem is undecidable in general, even if
is presented by a convergent semiThue system.
Note that there can be no, one or even (infinitely) many solutions
depending on .
In case
is a group the equation only has one unique solution.
Example 3..3
Let
and
be a
presentation of a monoid
with a lengthlexicographical ordering
induced by
.
Then the equation
has no solution in
,
the equation
has one solution in
,
namely
,
and
the equation
has infinitely many solutions in
,
namely the set
.
The following example illustrates how different monomials
can become equal when modifying a polynomial in order to use it for
strong right reduction.
Remark 3..4
Let
and
be a
presentation of a monoid
with a lengthlexicographical ordering
induced by
.
Furthermore, let
f_{1},
f_{2},
p be polynomials in
such that
f_{1} =
a^{2} +
a,
f_{2} =
a^{2}

a and
.
Then
p is strongly right reducible by
f_{1} at
b, as
and
.
On the other hand, although both equations
and
have
b as a solution, we get
that
p is not strongly right reducible by
f_{2}, as
.
In case
is a right cancellative monoid or a group, the phenomenon
described in this remark can no longer occur, since
then
implies u = v for all
.
Let us continue to state some of the properties strong right
reduction satisfies.
Unfortunately, for strong right reduction
,
in general does not imply
,
as the following example shows^{12}.
Therefore, our structure satisfies (A1), (A2) and (A3) but not (A4) of the axioms given in the introduction.
Example 3..6
Let
and
be a
monoid presentation of a group
with a lengthlexicographical ordering induced
by
.
Looking at
and
we get
and
,
but
.
Trying to reduce
ba by
w or
q_{1} we get
and
all violating condition (a) of definition
3.2.
Trying to reduce
b we get the same problem with
and
.
Nevertheless, strong right reduction has the essential properties
which allow us to characterize a right ideal by reduction with respect to
a set of generators, e.g. the translation lemma holds and the right
ideal congruence can be described by reduction.
In analogy to Buchberger we will call bases of right ideals which induce
a confluent strong right reduction describing the right ideal congruence strong Gröbner bases.
Definition 3..8
A set
is called a
Gröbner basis
with respect to
the reduction
or a
strong Gröbner
basis of
,
if
,
and
is confluent.
Notice that by lemma 3.7 we have
Lemma 3..9
For a set of polynomials
G in
,
G is a strong
Gröbner basis of
if and only if for all
we have
.
Unlike in Buchberger's case a polynomial itself need not be a Gröbner
basis of the right ideal it generates.
Example 3..10
Let
and
be a monoid presentation of a
group
with with a lengthlexicographical ordering
induced by
.
Further, let us consider the polynomial
.
Then
is not confluent on
,
as we can
strongly right reduce
using
and
,
but although
,
,
as for all
,
.
In accordance with the terminology used in Buchberger's approach
to give a confluence test for sets of polynomials,
we define critical pairs of polynomials
with respect to strong right reduction as situations were both polynomials
can be applied for strong reduction.
Definition 3..11
Given two nonzero polynomials
^{11}
,
every pair of elements
such that
,
defines a
strong spolynomial
Let
be the set containing
all such pairs
.
A strong spolynomial will be called nontrivial in case it is nonzero and
notice that we always have
.
Example 3..12
Reviewing example
3.10 we find that a polynomial
can have a nontrivial strong spolynomial with itself.
In fact since
we get
that
gives rise to a strong
spolynomial
This phenomenon, which differs from the one for free monoid rings,
is due to the fact that the definition of critical
situations no longer only involves the head terms of the respective
polynomials but the whole polynomials.
The set
U_{p1,p2} is contained in the set of all solutions in
to the
equations in two variables of the form
where
and
.
It can be empty, finite or even infinite.
We can now give a criterion that implies confluence
for strong right reduction in terms of strong spolynomials.
Notice that this theorem, although characterizing a strong Gröbner basis by
strong spolynomials, in general does not give a finite test to check
whether a set is a strong Gröbner basis, since in general infinitely
many strong spolynomials have to be considered.
Later on we will see that the right ideal generated by a+b+c in
example 3.10 has finite strong Gröbner bases and we
will show how to compute such a basis.
The following example shows how already
two polynomials can cause infinitely many critical situations.
Example 3..14
Let
and
be a presentation of a
monoid
with a lengthlexicographical ordering
induced by
.
Further consider two polynomials
.
Then we get infinitely many critical situations
where
,
giving rise to infinitely many strong spolynomials
and
.
Notice that in contrary to the definition of spolynomials in commutative
polynomial rings in this example there are infinitely many strong
spolynomials originating from p_{1} and p_{2} which cannot be expressed
by monomial multiples of one or even a finite set of these spolynomials.
Therefore, localization of critical situations in general is very hard.
As example 3.14 shows,
the set
U_{p1,p2} need not have a ``suitable finite basis'',
e.g. there need not exist a finite set
such that
for every pair
there exists a pair
and an element
with
and
.
The subset
is such a basis, but it is not finite and there is in fact no finite one.
It turns out that the following uniform problem is undecidable,
even in monoids where the solvability of
equations of the form
is decidable.
Given: Two polynomials
,
and
a convergent semiThue system presenting .
Question: Does there exist a strong spolynomial for p and q?
One way to reduce the set of critical situations that have to be
considered to ensure confluence is to weaken the reduction relation
while preserving the generated equivalence relation.
The key idea is that for two reduction relations
and
on a set
such that
and
,
the confluence of
on
implies the
confluence of
on .
One natural weakening strong right reduction we studied
is called right reduction.
Instead of using all right multiples of a polynomial by monomials as rules we
restrict ourselves to those right
multiples of a polynomial which allow the head
term of the polynomial to keep its head position.
Hence, reduction defined in this way can be called ``stable'' and
resembles Buchberger's definition of reduction.
The results can be found in [MaRe93b,Re95].
In the following we will introduce a further weakening of
strong reduction using prefixes in .
Notice that such prefixes are divisors with respect to word concatenation
and hence easy to determine.
Definition 3..15
Let
p,
f be two nonzero polynomials in
.
We say
f prefix reduces
p to
q at a monomial
of
p in one step, denoted by
,
if
 (a)

for some
,
i.e.,
is a prefix of t, and
 (b)

.
We write
if there is a polynomial
q as defined
above and
p is then called prefix reducible by
f.
Prefix reduction by a set
is denoted by
and abbreviates
for some
.
Notice that in the above definition the equation in
(a) has at most one solution and
we then always have
.
This is due to the fact that
implies
and
for all
.
Further, in case f prefix reduces p to q at the monomial
,
we have
and p > q.
In case
is the free monoid strong and prefix reduction coincide and are in fact Mora's reduction for treating right ideals in the free monoid ring.
The statements (1) to (3) of lemma 3.5 can
be carried over to prefix reduction.
But it is no longer true that
in case
.
Example 3..16
Let
and
be a monoid presentation of a group
with a lengthlexicographical ordering
induced by
.
Further let
.
Then
is not prefix reducible to
zero by
p.
As before, we can show that the translation lemma holds for prefix reduction.
Furthermore,
and
imply
,
i.e. the axioms (A1), (A2), (A3) and (A4) hold.
Unfortunately, prefix reduction need not capture the right ideal
congruence.
Lemma 3..18
Let
and
.
Then
implies
but not vice versa.
Example 3..19
Let
and
be a presentation of a group
with a lengthlexicographical ordering induced by
.
Inspecting the polynomials
and the set
we get
,
but
.
To prove this claim, let us assume
.
Then, since
,
we get
.
Let
be minimal such that
.
As
we know
n>1.
Thus, let us look at the sequence
where for all
,
,
and
.
Further let
.
Then
,
as
for all
such that
.
Let
p_{l} be the first polynomial with
,
i.e.,
for all
j <
l,
and let
p_{l+k} be the next polynomial,
where the occurrence of
t is changed.
Since
we can conclude
.
Further our transformation sequence is supposed to be of minimal length, i.e.,
t is not changed by the
reductions taking place in the sequence
.
But then, eliminating
p_{l} and substituting
p_{l+j} by
for all
gives us a shorter sequence
contradicting our assumption.
Obviously for a set of polynomials
we have
,
but as seen in
example 3.19 in general we cannot expect
.
This can be gained by enriching the set F to a set F' such that
and
.
This will be achieved by a process called prefix saturation.
Definition 3..20
A set of polynomials
is called a
prefix saturating set for a nonzero polynomial
,
if for all
,
in case
then
holds.
denotes the family of all prefix saturating sets for
p.
Definition 3..21
We call a set
prefix saturated, if for all
and all
,
holds in case
.
Note that in defining prefix saturating sets we demand prefix reducibility to 0 in one step.
This is done to have some equivalent for
in Buchberger's approach and the fact that for strong right reduction
we have
in case
.
Other definitions of similar properties are possible and can be found
in [Ap88,Kr93,Re95].
Of course there are procedures to enumerate prefix saturating sets of a polynomial p, since
the set
is recursively enumerable, and
it is decidable whether
for some
and
finite.
But in general the set
is infinite and,
hence, we have to look for
``suitable'' subsets and to find and compute finite ones in case they exist.
Note that prefix saturating sets for a polynomial p are prefix saturated.
A nice property of prefix saturated sets is that they
allow special representations of the elements belonging to
the right ideal they generate.
Lemma 3..22
Let
be a prefix saturated set.
Then every nonzero polynomial
has a
representation of the form
with
,
and
.
In fact using prefix reduction combined with prefix saturation we can
simulate strong right reduction and therefore we can then capture the
right ideal congruence.
Lemma 3..24
For a prefix saturated set
F of polynomials in
and
we have
.
To enumerate prefix saturating sets for a polynomial, we can make use
of the fact that the elements of the monoid are represented by
words which are irreducible with respect to a convergent semiThue
system
.
We do not have to compute all right monoid multiples of a polynomial
but we can restrict ourselves to those which are overlaps between the
respective head term of a polynomial multiple and the rules in T.
The following procedure uses this idea.
Procedure: PREFIX SATURATIONfont size=1>PROTECT
< tex2html_comment_mark>
Given: A polynomial
and
a convergent semiThue system presenting .
Find:
.
S := ;
H := ;
while
do
q :=
;
% Remove an element using a fair strategy, i.e., no element is left in H for ever
t :=
;
for all
for some
do
% C(t) contains special overlaps between t and left hand sides of rules in T
q' := ;
if
and
then S :=
;
H :=
;
endif
endfor
endwhile
Theorem 3..25
For a given polynomial
,
let
S be the
set generated by procedure P
REFIX S
ATURATION.
Then for all
every nonzero polynomial
is prefix reducible to zero in one step using
S.
Hence, procedure PREFIX SATURATION enumerates a prefix
saturating set for a polynomial and we find:
Lemma 3..26
In case a polynomial has a finite prefix saturating set, then
procedure P
REFIX S
ATURATION terminates.
This is the case e.g. for monoids with a finite convergent monadic presentation.
Similar to definition 3.8 we can define Gröbner bases with
respect to prefix reduction.
Definition 3..27
A set
is said to be a
prefix Gröbner basis of
,
if
,
and
is confluent.
Notice that prefix saturating sets for a polynomial p satisfy the
first statement of this definition,
but in general need not be prefix
Gröbner bases of
,
i.e., the elements of
do not necessarily prefix reduce to zero.
Example 3..28
Reviewing example
3.19, let
p =
a +
b +
c.
Then
,
but
is not confluent on
.
We have
and
but
.
This example also shows that Gröbner bases via
are Gröbner bases
via
but not vice versa.
The set
is a strong Gröbner basis, but
not a prefix Gröbner basis.
Remember that prefix saturation enriches a polynomial p to a set
such that we can
substitute
by
.
We use this additional information to give a confluence
criterion that will use a refined
definition of spolynomials.
Definition 3..29
Given two nonzero polynomials
,
if there is
such that
the
prefix
spolynomial is defined as
As before nonzero prefix spolynomials are called nontrivial.
In case an spolynomial exists
we always
have
.
Notice that a finite set
defines
finitely many prefix spolynomials and the following lemma enables us to localize our confluence test to these spolynomials.
Lemma 3..30
Let
F be a set of polynomials in
and
.
Further let
and let us assume this reduction sequence results
in a representation
,
where
,
,
and
.
Then for every term
such that
and
every term
we get that if
then
holds.
Prefix spolynomials alone are not sufficient to
characterize prefix Gröbner
bases, but
in case we demand our set of polynomials to be prefix saturated we
can give a characterization similar to theorem 3.13.
Corollary 3..32
A prefix saturated set
is a prefix
Gröbner basis of
if and only if
for all
we have
.
Now theorem 3.31 gives rise to the following procedure, which can be modified to enumerate a Gröbner
basis with respect to
for a finitely generated
right ideal.
Termination will be shown for some special cases where finite prefix
saturated Gröbner bases exist in the next section.
Procedure: PREFIX GR¨OBNER BASESfont size=1>PROTECT
< tex2html_comment_mark>
Given: A finite set of polynomials
,
and
a convergent semiThue system presenting .
Find:
a prefix Gröbner basis of F.
Using:
a prefix saturating procedure for polynomials.
G :=
;
% G is prefix saturated
B :=
;
while
do
% Test if statement 2 of theorem 3.31 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 is prefix saturated
B :=
;
endif
endif
endwhile
There are two crucial points, why procedure PREFIX GR¨OBNER BASES
might not terminate:
prefix saturation of a polynomial need not terminate
and the set B need not become empty.
In the next section certain groups with very simple finite
prefix saturating sets are presented.
Notice that in case prefix saturation does not terminate it is possible
to modify this procedure in order to enumerate a prefix Gröbner
basis by using fair enumerations of the prefix saturating sets
needed.
This results in a more technical procedure.
Termination of procedure PREFIX GR¨OBNER BASES
can be shown e.g. for finite convergent special monoid or
monadic group presentations.
More details on this subject are provided in the next section.
In the following example we want to illustrate how procedure PREFIX GR¨OBNER BASES works by computing a prefix Gröbner basis of the right ideal
specified in example 3.10.
Example 3..33
Let
and
with a lengthlexicographical ordering induced by
.
We want to compute a prefix Gröbner basis of
.
On initializing
G we get
(compare example
3.28).
Now inspecting this set we see that only one prefix spolynomial has to be considered, namely
Since
is a saturating set for the polynomial
we
get
.
Now there are two possible prefix spolynomials to consider and we find
respectively
and hence
is a prefix Gröbner basis of
.
Furthermore, theorem 3.31 characterizes prefix saturated prefix
Gröbner bases.
But prefix Gröbner bases need not be prefix saturated.
In [Re95] we have hence given other characterizations of
prefix Gröbner bases and introduced the concept of interreduction
to the theory.
Using those results we can even state that for
in example 3.33 the set
is a reduced
prefix Gröbner basis.
We close this section by showing how similar to the case of solvable polynomial rings ([Kr93,KaWe90]), Gröbner bases of twosided
ideals can be characterized by prefix reduction and prefix Gröbner bases which have
additional properties.
We will call a set of polynomials a Gröbner basis of the
twosided ideal it generates, if it fulfills one of the equivalent
statements in the next theorem.
Statement 4 enables a constructive approach to extend procedure PREFIX GR¨OBNER BASES in order to enumerate
prefix Gröbner bases of twosided ideals (and in fact in case
prefix saturation always terminates this procedure will compute finite
prefix saturated Gröbner bases in case they exist).
Item 2 states how prefix Gröbner bases are
related to the membership problem for twosided ideals.
In this case if
is a right reduction ring and G is a finite
prefix Gröbner basis of
,
then
is a right reduction ring.
Next: 4. Group Rings
Up: String Rewriting and Gröbner
Previous: 2. Fundamental Relations Between
 ZCA Home 
Reports 