INTRODUCTION

Rewriting for semigroups is a special case of Gröbner basis theory for noncommutative polynomial algebras. The fact is a kind of folklore but is not fully recognised. So our aim in this paper is to elucidate this relationship. A good introduction to string rewriting is, and a recent introduction to non-commutative Gröbner basis theory is. Similarities between the two critical pair completion methods (Knuth-Bendix and Buchberger's algorithm) have often been pointed out in the commutative case. The connection was first observed in and more closely analysed in and more recently in and. In particular it is well known that the commutative Buchberger algorithm may be applied to presentations of abelian groups to obtain complete rewrite systems.

Rewriting involves a presentation sgp〈X|R〉 of a semigroup S and presents S as a factor semigroup X† / =R where X† is the free semigroup on X and =R is the congruence generated by the subset R of X† × X†. Non-commutative Gröbner basis theory involves a presentation alg〈X|F〉 of a non-commutative algebra A over a field K and presents A as a factor algebra K[X†]/〈F〉 where K[X†] is the free K-algebra on the semigroup X† and 〈F〉 is the ideal generated by F, a subset of K[X†].