[The University of Leicester]

Department of Mathematics & Computer Science



Next: Results Up: paper3 Previous: paper3

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 [2], and a recent introduction to noncommutative Gröbner basis theory is [12]. 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 [7,5] and more closely analysed in [3,4] and more recently in [11] and [10]. 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 \langle X \vert R \rangle$ of a semigroup $ S$ and presents $ S$ as a factor semigroup $ X^\dagger / =_R$ where $ X^\dagger$ is the free semigroup on $ X$ and $ =_R$ is the congruence generated by the subset $ R$ of $ X^\dagger \times X^\dagger$. Noncommutative Gröbner basis theory involves a presentation $ alg \langle X \vert F \rangle$ of a noncommutative algebra $ A$ over a field $ K$ and presents $ A$ as a factor algebra $ K[X^\dagger]/ \langle F \rangle$ where $ K[X^\dagger]$ is the free $ K$-algebra on the semigroup $ X^\dagger$ and $ \langle F \rangle$ is the ideal generated by $ F$, a subset of $ K[X^\dagger]$. Given a semigroup presentation $ sgp\langle X \vert R \rangle$ we consider the algebra presentation $ alg \langle X \vert F \rangle$ where $ F:=\{l-r : (l,r) \in R \}$. It is well known that the word problem for $ sgp \langle X \vert R \rangle$ is solvable if and only if the (monomial) equality problem for $ alg \langle X \vert F \rangle$ is solvable. Teo Mora [8] recorded that a complete rewrite system for a semigroup $ S$ presented by $ sgp\langle X\vert Rel\rangle$ is equivalent to a noncommutative Gröbner basis for the ideal specified by the congruence $ =_R$ on $ X^\dagger$ in the algebra $ \mathbb{F}_3[X^\dagger]$ where $ \mathbb{F}_3$ is the field with elements $ \{-1,0,1\}$.

In this paper we show that the noncommutative Buchberger algorithm applied to $ F$ corresponds step-by-step to the Knuth-Bendix completion procedure for $ R$. This is the meaning intended for the first sentence of this paper.

Next: Results Up: paper3 Previous: paper3

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

Author: A. Heyworth, tel: +44 (0)116 252 3884
Last updated: 2001-05-08
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.