Results

First we note that the relation between the two kinds of presentation is given by the following variation of a result of [8].

Proposition
Let

be a field and let

be a semigroup with presentation $sgp \langle X \vert R \rangle$ . Then the algebra

is isomorphic to the factor algebra $K[X^\dagger]/\! \langle F \rangle$ where

is the basis $\{l-r\vert (l,r) \in R\}$ .

Proof
Define $\phi:K[X^\dagger] \to K[S]$ by $\phi(k_1w_1 + \cdots + k_tw_t) := k_1[w_1]_R+\cdots+k_t[w_t]_R$ for $k_1, \ldots, k_t \in K$ , $w_1, \ldots, w_t \in X^\dagger$ . Define a homomorphism $\phi':K[X^\dagger]/\! \langle F \rangle \to K[S]$ by $\phi'([p]_F):=\phi(p)$ . It is injective since $\phi'[p]_F = \phi[q]_F$ if and only if

(using the definitions $\phi(p)=\phi(q) \Leftrightarrow p-q \in \langle F \rangle$ ). It is also surjective. Let $f\in K[S]$ . Then $f = k_1m_1 + \cdots + k_tm_t$ for some $k_1,\ldots,k_t\in K$ , $m_1,\ldots,m_t\in S$ . Since

is presented by $sgp\langle X \vert R \rangle$ there exist $w_1, \ldots, w_t \in X^\dagger$ such that

for $i=1,\ldots,t$ . Therefore let $p = k_1w_1 + \cdots + k_tw_t$ . Clearly $p \in K[X^\dagger]$ and also $\phi'[p]_F = f$ . Hence $\phi'$ is an isomorphism. $\Box$

Theorem
Let $sgp\langle X \vert R\rangle$ be a semigroup presentation, let

be a field and let $alg\langle X \vert F \rangle$ be the

-algebra presentation with $F:=\{ l-r: (l,r) \in R \}$ . Then the Knuth-Bendix completion algorithm for the rewrite system

corresponds step-by-step to the noncommutative Buchberger algorithm for finding a Gröbner basis for the ideal generated by

Proof Both the Knuth-Bendix algorithm for

and the Buchberger algorithm for

begin by specifying a monomial ordering on $X^\dagger$ which we denote

$\displaystyle (i)$	rewrite system	basis
$\displaystyle (ii)$	rule	two-term polynomial
$\displaystyle (iii)$	string	monomial
$\displaystyle (iv)$	reduction	reduction
$\displaystyle (v)$	left hand side	leading monomial
$\displaystyle (vi)$	substring	submonomial
$\displaystyle (vii)$	right hand side	remainder
$\displaystyle (viii)$	overlap	match
$\displaystyle (ix)$	critical pair	S-polynomial
This key part of the correspondence (viii) and (ix) is illustrated diagrammatically in the next section
$\displaystyle (x)$	resolve	reduce to zero
$\displaystyle (xi)$	reduced critical pair	reduced S-polynomial
$\displaystyle (xii)$	complete rewrite system	Gröbner basis

In terms of rewriting we consider the rewrite system

which consists of a set of rules of the form

orientated so that

. A string $w \in X^\dagger$ may be reduced with respect to

if it contains the left hand side

of a rule

as a substring i.e. if

for some $u,v \in X^*$ . To reduce

using the rule

we replace

by the right hand side

of the rule, and write $ulv \to_R urv$ . The Knuth-Bendix algorithm looks for overlaps between rules. Given a pair of rules

there are four possible ways in which an overlap can occur:

and

. The critical pair resulting from an overlap is the pair of strings resulting from applying each rule to the smallest string on which the overlap occurs. The critical pairs resulting from each of the four overlaps are:

and

respectively (see diagram). In one pass the completion procedure finds all the critical pairs resulting from overlaps of rules of

. Both sides of each of the critical pairs are reduced as far as possible with respect to

to obtain a reduced critical pair

. The original pair is said to resolve if

. The reduced pairs that have not resolved are orientated, so that

, and added to

forming

. The procedure is then repeated for the rewrite system

, to obtain

and so on. When all the critical pairs of a system

resolve (i.e. $R_{n+1}=R_n$ ) then

is a complete rewrite system.

In terms of Gröbner basis theory applied to this special case we consider the basis

which consists of a set of two-term polynomials of the form

multiplied by $\pm 1$ so that

. A monomial $m \in X^\dagger$ may be reduced with respect to

if it contains the leading monomial

of a polynomial

as a submonomial i.e. if

for some $u,v \in X^*$ . To reduce

using the polynomial

we replace

by the remainder

of the polynomial, and write $ulv \to_F urv$ . The Buchberger algorithm looks for matches between polynomials. Given a pair of polynomials

there are four possible ways in which an match can occur:

and

. The S- polynomial resulting from a match is the difference between the pair of monomials resulting from applying each two-term polynomial to the smallest monomial on which the match occurs. The S-polynomials resulting from each of the four matches are:

and

respectively (see diagram). In one pass the completion procedure finds all the S-polynomials resulting from matches of polynomials of

. The S-polynomials are reduced as far as possible with respect to

to obtain a reduced S-polynomial

. Note that reduction can only replace one term with another so the reduced S-ploynomial will have two terms unless the two terms reduce to the same thing

in which case the original S-polynomial is said to reduce to zero. The reduced S-polynomials that have not been reduced to zero are multiplied by $\pm 1$ , so that

, and added to

forming

. The procedure is then repeated for the basis

, to obtain

and so on. When all the S-polynomials of a basis

reduce to zero (i.e. $F_{n+1}=F_n$ ) then

is a Gröbner basis.

A critical pair in

will occur if and only if a corresponding S-polynomial occurs in

. Reduction of the pair by

is equivalent to reduction of the S-polynomial by

. Therefore at any stage any new rules correspond to the new two-term polynomials and $F_i:=\{l-r:(l,r) \in R_i\}$ . Therefore the completion procedures as applied to

and

correspond to each other at every step. $\Box$

	Department of Mathematics & Computer Science

Department of Mathematics & Computer Science

Results