We now discuss some of the particulars of the GBA given
by **[FMora]**.
Critical to a GBA is the
construction of, from pairs of polynomials
(*f*,*g*), common multiples
for the leading terms of *f* and *g*.
Now we recall the appropriate notion of common multiple.

Let *S* be the free semigroup
generated
by a finite alphabet *A*
(i.e., the collection of words in the letters of *A*).
Let
be an ordered pair of elements of *S*. By a match of
we mean a 4-tuple of elements
of *S* which satisfy one of the following conditions:

(1) , . (2) , . (3) , , , there is a with , . (4) , , , there is a with , .

These conditions make . This is a common multiple of and which is minimal in some sense.

In the commutative case, the
Basis
Algorithm makes use of a kind of resolvent of two polynomials
called the
*S-Polynomial*. where
and
where is chosen so that
is the least common multiple of
and for *i*=1,2. In the noncommutative case, there are several
such
resolvents--one for each match. If
*M* is a 6-tuple
where is a match for
and , then we set

**Example**:

Consider the polynomials

There are four matches for :
1.
(*aba*,1,1,*aba*). In this case the S-Polynomial is

2.
(*ab*,1,1,*ba*) In this case the S-polynomial is

3.
(1,*baa*,*aab*,1) In this case the S-Polynomial is

4.
(1,*a*,*a*,1) In this case the S-Polynomial is

The algorithm is iterative and
starts with a finite set
of polynomials . The *k*-th step has available to it a set
such that the ideal generated by equals
the ideal generated by . The *k*-th step of the algorithm
creates a set by setting it equal to the union
of and the set of all
nonzero reductions of S-Polynomials for all
pairs in .
The process repeats as long as there are S-Polynomials with
nonzero reductions. In other works, the process repeats until
.

Wed Jul 3 10:27:42 PDT 1996