3. Defining Reduction in ${\bf K}[{\cal M}]$

Throughout this paper let ${\cal M}$ be a monoid presented by a finite convergent semi-Thue system $(\Sigma, T)$ and $\succeq$ the well-founded ordering on ${\cal M}$ induced by the completion ordering of its presentation. Notice that although the completion ordering is compatible on $\Sigma^*$ with concatenation, this in general no longer holds for the ordering $\succeq$ on ${\cal M}$ with respect to the multiplication $\circ$ on ${\cal M}$. For example groups do not allow compatible well-founded orderings due to the existence of inverse elements. Given a non-zero polynomial p in ${\bf K}[{\cal M}]$, the head term ${\sf HT}(p)$ is the largest term in p with respect to $\succ$, ${\sf HC}(p)$ is the coefficient of this term and ${\sf HM}(p) = {\sf HC}(p) \cdot{\sf HT}(p)$ the head monomial. ${\sf T}(p)$ is the set of terms occurring in p. The ordering on ${\cal M}$ can be extended to a partial ordering on ${\bf K}[{\cal M}]$ by setting p > q if and only if ${\sf HT}(p) \succ {\sf HT}(q)$ or $( {\sf HM}(p) = {\sf HM}(q)$ and $p - {\sf HM}(p) > q - {\sf HM}(q))$, 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 $\Sigma = \{ a,b \}$ and $T = \{ab \longrightarrow\lambda, ba \longrightarrow \lambda \}$ be a presentation of a group ${\cal G}$ with a length-lexicographical ordering induced by $a \succ b$. Suppose we simply require divisibility¹⁰ of the head term to allow reduction. Then we could reduce the polynomial $b^2 + 1 \in {\bf Q}[{\cal G}]$ at the monomial b² by the polynomial a + b as $b^2 = a \circ b^3$. This would give us:

$$b^{2} + 1 \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{a + b}\,$} b^{2} + 1 - (a + b) \ast b^{3} = -b^{4} + 1$$

and the polynomial -b⁴ + 1 likewise would be reducible by a + b at the monomial -b⁴ 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 ${\cal M}$ 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 non-zero polynomials in ${\bf K}[{\cal M}]$. We say f strongly right reduces p to q at a monomial $\alpha \cdot t$ of p in one step, denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{f}\,$ } q$, if

(a)

${\sf HT}(f \ast w) = t$ for some $w \in {\cal M}$, and

(b)

$q = p - \alpha \cdot{\sf HC}(f \ast w)^{-1} \cdot f \ast w$.

We write $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{f}\,$ }$ 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 $F \subseteq {\bf K}[{\cal M}]$ is denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } q$ and abbreviates $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{f}\,$ } q$ for some $f \in F$.

Note that in order to strongly right reduce p, the polynomial f need not be smaller than p. The condition ${\sf HT}(f \ast w) = t$ prevents reduction with a polynomial in case $f \ast w = 0$, i.e., if the monomials of f eliminate each other by multiplying f with w. This might happen in case the monoid ring contains zero-divisors. Further, in case we have $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{f}\,$ } q$ at the monomial $\alpha \cdot t$, then $t \not\in {\sf T}(q)$. In order to decide, whether a polynomial f strongly right reduces a polynomial p at a monomial $\alpha \cdot t$ one has to decide whether there exist elements $s \in {\sf T}(p)$ and $w \in {\cal M}$ such that $s \circ w = {\sf HT}(f \ast w) = t$. Since this problem is connected to solving equations $s \circ{\rm x} = t$ in one variable ${\rm x}$ in the monoid ${\cal M}$ presented by $(\Sigma, T)$, this problem is undecidable in general, even if ${\cal M}$ is presented by a convergent semi-Thue system. Note that there can be no, one or even (infinitely) many solutions depending on ${\cal M}$. In case ${\cal M}$ is a group the equation only has one unique solution.

Example 3..3   Let $\Sigma = \{ a,b \}$ and $T = \{ ab \longrightarrow a \}$ be a presentation of a monoid ${\cal M}$ with a length-lexicographical ordering induced by $a \succ b$. Then the equation $b \circ{\rm x} = a$ has no solution in ${\cal M}$, the equation $b \circ{\rm x} = b$ has one solution in ${\cal M}$, namely ${\rm x} = \lambda$, and the equation $a \circ{\rm x} = a$ has infinitely many solutions in ${\cal M}$, namely the set $\{ b^n \vert n \in {\bf N}\}$.

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 $\Sigma = \{ a,b \}$ and $T = \{ ab \longrightarrow b \}$ be a presentation of a monoid ${\cal M}$ with a length-lexicographical ordering induced by $a \succ b$. Furthermore, let f₁, f₂, p be polynomials in ${\bf Q}[{\cal M}]$ such that f₁ = a² + a, f₂ = a² - a and $p = b + \lambda$. Then p is strongly right reducible by f₁ at b, as ${\sf HT}(f_1 \ast b) = {\sf HT}(2 \cdot b) = b$ and $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{f_1}\,$ } p - \frac{1}{2} \cdot f_1 \ast b = b+\lambda - \frac{1}{2} \cdot2 \cdot b = \lambda$. On the other hand, although both equations $a^2 \circ {\rm x} = b$ and $a \circ{\rm x} =b$ have b as a solution, we get that p is not strongly right reducible by f₂, as $f_2 \ast b = b - b = 0$.

In case ${\cal M}$ is a right cancellative monoid or a group, the phenomenon described in this remark can no longer occur, since then $u \circ w = v \circ w$ implies u = v for all $u,w,w \in {\cal M}$. Let us continue to state some of the properties strong right reduction satisfies.

Lemma 3..5   Let F be a set of polynomials in ${\bf K}[{\cal M}]$ and $p,q, q_1, q_2 \in {\bf K}[{\cal M}]$ some polynomials. Then the following statements hold:

(1)

$p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } q$ implies p > q, in particular ${\sf HT}(p) \succeq {\sf HT}(q)$.

(2)

$\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ }$ is Noetherian.

(3)

If $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{q_1}\,$ } 0$ and $q_1 \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{q_2}\,$ } 0$ hold, so does $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{q_2}\,$ } 0$.

(4)

  $\alpha \cdot p \ast w \mbox{$\,\stackrel{{\leq 1}}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}\,$ } 0$ for all $\alpha \in {\bf K}$, $w \in {\cal M}$.

Unfortunately, for strong right reduction $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{q}\,$ }$, $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{w}\,$ } q_1$ in general does not imply $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{\{w,q_1\}}\,$ }$, as the following example shows¹². Therefore, our structure satisfies (A1), (A2) and (A3) but not (A4) of the axioms given in the introduction.

Example 3..6   Let $\Sigma = \{ a, b, c \}$ and $T = \{ a^2 \longrightarrow\lambda, b^2 \longrightarrow\lambda, c^2 \longrightarrow\lambda \}$ be a monoid presentation of a group ${\cal G}$ with a length-lexicographical ordering induced by $a \succ b \succ c$. Looking at $p = ba + b, q = bc + \lambda$ and $w = ac + b \in {\bf Q}[{\cal G}]$ we get $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{q}\,$ } p - q \ast ca = -ca + b$ and $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{w}\,$ } q - w \ast c = -a + \lambda = q_{1}$, but $p \mbox{$\,\,\,\,{\not\!\!\!\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{\{w,q_1\}}}\,$ }$. Trying to reduce ba by w or q₁ we get $w \ast a = \underline{aca} + ba, w \ast caba = ba + \underline{bcaba}$ and $q_{1} \ast aba = -ba + \underline{aba},q_{1} \ast ba = -\underline{aba} + ba$ all violating condition (a) of definition 3.2. Trying to reduce b we get the same problem with $w \ast cab = b + \underline{bcab}, q_1 \ast ab = -b+\underline{a}$ and $q_1 \ast b = -\underline{ab}+b$.

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.

Lemma 3..7    Let F be a set of polynomials in ${\bf K}[{\cal M}]$ and $p,q,h \in{\bf K}[{\cal M}]$ some polynomials. Then the following statements hold:

(1)

Let $p-q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } h$. Then there are polynomials $p',q' \in {\bf K}[{\cal M}]$ such that we have $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } p', q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } q'$ and h=p'-q'.

(2)

Let 0 be a normal form of p-q with respect to $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ }$. Then there exists a polynomial $g \in {\bf K}[{\cal M}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } g$ and $q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } g$.

(3)

$p \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } q \mbox{ if and only if } p - q \in {\sf ideal}_{r}^{}(F)$.

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 $G \subseteq {\bf K}[{\cal M}]$ is called a   Gröbner basis with respect to the reduction $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{}\,$ }$ or a strong Gröbner basis of ${\sf ideal}_{r}^{}(G)$, if $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm s}}_{G}\,$ } = \;\;\equiv_{{\sf ideal}_{r}^{}(G)}$, and $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{G}\,$ }$ is confluent.

Notice that by lemma 3.7 we have

Lemma 3..9   For a set of polynomials G in ${\bf K}[{\cal M}]$, G is a strong Gröbner basis of ${\sf ideal}_{r}^{}(G)$ if and only if for all $g \in {\sf ideal}_{r}^{}(G)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{G}\,$ } 0$.

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 $\Sigma = \{ a, b, c \}$ and $T = \{ a^{2} \longrightarrow\lambda, b^{2} \longrightarrow\lambda, ab \longrightarrow c, ac \longrightarrow b, cb \longrightarrow a \}$ be a monoid presentation of a group ${\cal G}$ with with a length-lexicographical ordering induced by $a \succ b \succ c$. Further, let us consider the polynomial $p = a + b + c \in {\bf Q}[{\cal G}]$. Then $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}\,$ }$ is not confluent on ${\sf ideal}_{r}^{}(p)$, as we can strongly right reduce $a+b+c \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}\,$ } b- \lambda$ using $p \ast b = c+\lambda + \underline{a}$ and $a+b+c \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}\,$ } 0$, but although $b - \lambda \in {\sf ideal}_{r}^{}(p)$, $b- \lambda \mbox{$\,\,\,\,{\not\!\!\!\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}}\,$ } 0$, as for all $w \in {\cal G}$, ${\sf HT}(p \ast w) \neq b$.

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 non-zero polynomials¹¹ $p_{1}, p_{2} \in {\bf K}[{\cal M}]$, every pair of elements $w_{1}, w_{2} \in {\cal M}$ such that ${\sf HT}(p_1 \ast w_{1}) = {\sf HT}(p_2 \ast w_{2})$, defines a    strong s-polynomial

$${\sf spol}_{s}(p_{1}, p_{2}, w_{1}, w_{2}) = {\sf HC}(p_1 \as... ...p_1 \ast w_1 - {\sf HC}(p_2 \ast w_2)^{-1} \cdot p_2 \ast w_2.$$

Let $U_{p_1,p_2} \subseteq {\cal M}\times {\cal M}$ be the set containing all such pairs $w_{1}, w_{2} \in {\cal M}$.

A strong s-polynomial will be called non-trivial in case it is non-zero and notice that we always have ${\sf HT}({\sf spol}_{s}(p_{1}, p_{2}, w_{1}, w_{2})) \prec{\sf HT}(p_1 \ast w_{1}) = {\sf HT}(p_2 \ast w_{2})$.

Example 3..12   Reviewing example 3.10 we find that a polynomial can have a non-trivial strong s-polynomial with itself. In fact since ${\sf HT}(a+b+c) = a = {\sf HT}((a+b+c) \ast b)$ we get that $(\lambda,b) \in U_{a+b+c,a+b+c}$ gives rise to a strong s-polynomial

$${\sf spol}_{s}(a+b+c,a+b+c,\lambda,b) = (\underline{a} + b +c) - (c + \lambda + \underline{a}) = b - \lambda.$$

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 ${\cal M}$ to the equations in two variables of the form $u \circ{\rm x} = v \circ{\rm y}$ where $u \in {\sf T}(p_1)$ and $v \in{\sf T}(p_2)$. 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 s-polynomials.

Theorem 3..13   For a set F of polynomials in ${\bf K}[{\cal M}]$, the following statements are equivalent:

(1)

For all polynomials $g \in {\sf ideal}_{r}^{}(F)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } 0$.

(2)

For all not necessarily different polynomials $f_{k}, f_{l} \in F$ and every corresponding pair $(w_{k}, w_{l}) \in U_{f_k,f_l}$ we have ${\sf spol}_{s}(f_{k}, f_{l}, w_{k}, w_{l}) \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ } 0.$

Notice that this theorem, although characterizing a strong Gröbner basis by strong s-polynomials, 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 s-polynomials 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 $\Sigma = \{ a,b,c,d,e,f \}$ and $T = \{ abc \longrightarrow ba, fbc \longrightarrow bf, bad \longrightarrow e \}$ be a presentation of a monoid ${\cal M}$ with a length-lexicographical ordering induced by $a \succ b \succ c \succ d \succ e \succ f$. Further consider two polynomials $p_1 = a + f, p_2 = bf + a \in {\bf Q}[{\cal M}]$. Then we get infinitely many critical situations

$${\sf HT}(p_1 \ast(bc)^idw) = f \circ(bc)^idw = bf \circ(bc)^{i-1} dw = {\sf HT}(p_2 \ast(bc)^{i-1}dw),$$

where $i \in {\bf N}^+, w \in {\cal M}$, giving rise to infinitely many strong s-polynomials

$${\sf spol}_{s}(p_1,p_2,(bc)^idw,(bc)^{i-1} dw) = (a+f) \ast(bc)^idw - (bf +a) \ast(bc)^{i-1} dw$$

and $U_{p_1,p_2} = \{ ( (bc)^idw, (bc)^{i-1} dw) \mid i \in{\bf N}^+, w \in{\cal M} \}$.

Notice that in contrary to the definition of s-polynomials in commutative polynomial rings in this example there are infinitely many strong s-polynomials originating from p₁ and p₂ which cannot be expressed by monomial multiples of one or even a finite set of these s-polynomials. 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 $B \subseteq U_{p_1,p_2}$ such that for every pair $(w_1,w_2) \in U_{p_1,p_2}$ there exists a pair $(u_1,u_2) \in B$ and an element $w \in {\cal M}$ with $u_1 \circ w = w_1$ and $u_2 \circ w = w_2$. The subset $\{ ( (bc)^id, (bc)^{i-1} d) \mid i \in{\bf N}^+ \} \subset U_{p_1,p_2}$ 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 $u \circ{\rm x} = v \circ{\rm y}$ is decidable.

Given: 		  Two polynomials 

$p,q \in {\bf K}[{\cal M}]$,
and
		 

$(\Sigma, T)$
a convergent semi-Thue system presenting ${\cal M}$.
Question: 		 Does there exist a strong s-polynomial 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 $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm 1}}_{}\,$ }$ and $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm 2}}_{}\,$ }$ on a set ${\cal E}$ such that $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm 1}}_{}\,$ } \subseteq \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm 2}}_{}\,$ }$ and $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm 1}}_{}\,$ } = \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm 2}}_{}\,$ }$, the confluence of $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm 1}}_{}\,$ }$ on ${\cal E}$ implies the confluence of $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm 2}}_{}\,$ }$ on ${\cal E}$.

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 $\Sigma^*$. Notice that such prefixes are divisors with respect to word concatenation and hence easy to determine.

Definition 3..15   Let p, f be two non-zero polynomials in ${\bf K}[{\cal M}]$. We say f   prefix reduces p to q at a monomial $\alpha \cdot t$ of p in one step, denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{f}\,$ } q$, if

(a)

${\sf HT}(f)w \equiv t$ for some $w \in {\cal M}$, i.e., ${\sf HT}(f)$ is a prefix of t, and

(b)

$q = p - \alpha \cdot{\sf HC}(f)^{-1} \cdot f \ast w$.

We write $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{f}\,$ }$ if there is a polynomial q as defined above and p is then called prefix reducible by f. Prefix reduction by a set $F \subseteq {\bf K}[{\cal M}]$ is denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } q$ and abbreviates $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{f}\,$ } q$ for some $f \in F$.

Notice that in the above definition the equation in (a) has at most one solution and we then always have ${\sf HC}(f \ast w) = {\sf HC}(f)$. This is due to the fact that $t \equiv{\sf HT}(f)w$ implies ${\sf HT}(f)w = {\sf HT}(f \ast w)$ and ${\sf HT}(f)w \succ s \circ w$ for all $s \in {\sf T}(f - {\sf HM}(f))$. Further, in case f prefix reduces p to q at the monomial $\alpha \cdot t$, we have $t \not\in {\sf T}(q)$ and p > q. In case ${\cal M}$ 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 $p \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{p}\,$ } 0$ in case $p \ast w \neq 0$.

Example 3..16   Let $\Sigma = \{ a,b \}$ and $T = \{ab \longrightarrow\lambda, ba \longrightarrow \lambda \}$ be a monoid presentation of a group ${\cal G}$ with a length-lexicographical ordering induced by $a \succ b$. Further let $p = a^2 + 1 \in {\bf Q}[{\cal G}]$. Then $p \ast b = a + b$ is not prefix reducible to zero by p.

As before, we can show that the translation lemma holds for prefix reduction.

Lemma 3..17   Let F be a set of polynomials in ${\bf K}[{\cal M}]$ and $p,q,h \in{\bf K}[{\cal M}]$ some polynomials. Then the following statements hold:

(1)

Let $p-q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } h$. Then there are $p',q' \in {\bf K}[{\cal M}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } p', q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } q'$ and h=p'-q'.

(2)

Let 0 be a normal form of p-q with respect to $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ }$. Then there exists a polynomial $g \in {\bf K}[{\cal M}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } g$ and $q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } g$.

Furthermore, $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{q}\,$ }$ and $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{w}\,$ } q$ imply $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{\{w,q\}}\,$ }$, i.e. the axioms (A1), (A2), (A3) and (A4) hold. Unfortunately, prefix reduction need not capture the right ideal congruence.

Lemma 3..18   Let $p,q \in {\bf K}[{\cal M}]$ and $F \subseteq {\bf K}[{\cal M}]$. Then $p \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } q$ implies $p - q \in {\sf ideal}_{r}^{}(F)$ but not vice versa.

Example 3..19   Let $\Sigma = \{ a, b, c \}$ and $T = \{ a^{2} \longrightarrow\lambda, b^{2} \longrightarrow\lambda, ab \longrightarrow c, ac \longrightarrow b, cb \longrightarrow a \}$ be a presentation of a group ${\cal G}$ with a length-lexicographical ordering induced by $a \succ b \succ c$. Inspecting the polynomials $p = a+b+c, q = b - \lambda\in{\bf Q}[{\cal G}]$ and the set $F = \{ a+b+c \}\subseteq {\bf Q}[{\cal G}]$ we get $p-q = a+c+ \lambda = (a+b+c) \ast b \in {\sf ideal}_{r}^{}(F)$, but $a+b+c \mbox{$\,\,\,\,{\not\!\!\!\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}}\,$ } b - \lambda$. To prove this claim, let us assume $a+b+c \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } b - \lambda$. Then, since $a+b+c \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$, we get $b - \lambda \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$. Let $n \in{\bf N}^+$ be minimal such that $b - \lambda \mbox{$\,\stackrel{n}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$. As $b - \lambda \mbox{$\,\,\,\,{\not\!\!\!\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}}\,$ } 0$ we know n>1. Thus, let us look at the sequence

$$b - \lambda =: p_0 \mbox{$\,\stackrel{}{\longleftrightarrow}\... ...stackrel{}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$} 0,$$

where for all $1 \leq i \leq n-1$, $p_i = p_{i-1} + \alpha_i \cdot(a+b+c) \ast w_i$, $\alpha_i \in {\bf K}^*, w_i \in{\cal G}$ and ${\sf HT}((a + b + c) \ast w_i) \equiv aw_i$. Further let $t = \max \{ {\sf HT}(p_i) \mid 1 \leq i \leq n-1 \}$. Then $t \succ b$, as $aw \succ b$ for all $w \in {\cal G}$ such that $a \circ w \equiv aw$. Let p_l be the first polynomial with ${\sf HT}(p_l)=t$, i.e., ${\sf HT}(p_j) \prec t$ for all j < l, and let p_l+k be the next polynomial, where the occurrence of t is changed. Since ${\sf HT}((a+b+c) \ast w_{l+k})\equiv aw_{l+k} \equiv t \equiv aw_l \equiv{\sf HT}((a+b+c) \ast w_l)$ we can conclude $w_{l+k} \equiv w_l$. 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 $p_l \mbox{$\,\stackrel{k-1}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } p_{l+k-1}$. But then, eliminating p_l and substituting p_l+j by $p'_{l+j}=p_{l+j} - \alpha_{l} \cdot(a+b+c) \ast w_l$ for all $1 \leq j<k$ gives us a shorter sequence $b - \lambda \mbox{$\,\stackrel{n-1}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$ contradicting our assumption.

Obviously for a set of polynomials $F \subseteq {\bf K}[{\cal M}]$ we have $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } \subseteq \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ }$, but as seen in example 3.19 in general we cannot expect $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } = \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ }$. This can be gained by enriching the set F to a set F' such that ${\sf ideal}_{r}^{}(F) = {\sf ideal}_{r}^{}(F')$ and $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F'}\,$ } = \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm s}}_{F}\,$ }$. This will be achieved by a process called prefix saturation.

Definition 3..20   A set of polynomials $F\subseteq \{\alpha \cdot p \ast w \mid \alpha \in {\bf K}^*, w \in{\cal M}\}$ is called a prefix saturating set for a non-zero polynomial $p\in {\bf K}[{\cal M}]$, if for all $w \in {\cal M}$, in case $p \ast w \neq 0$ then $p \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$ holds. ${\cal SAT}_p(p)$ denotes the family of all prefix saturating sets for p.

Definition 3..21   We call a set $F \subseteq {\bf K}[{\cal M}]$ prefix saturated, if for all $f \in F$ and all $w \in {\cal M}$, $f \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$ holds in case $f \ast w \neq 0$.

Note that in defining prefix saturating sets we demand prefix reducibility to 0 in one step. This is done to have some equivalent for $p \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{p}\,$ } 0$ in Buchberger's approach and the fact that for strong right reduction we have $p \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{p}\,$ } 0$ in case $p \ast w \neq 0$. 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 $\{p \ast w \mid w \in{\cal M}\}$ is recursively enumerable, and it is decidable whether $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$ for some $q \in {\bf K}[{\cal M}]$ and $F \subset {\bf K}[{\cal M}]$ finite. But in general the set $\{p \ast w \mid w \in{\cal M}\}$ 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 $F \subseteq {\bf K}[{\cal M}]$ be a prefix saturated set. Then every non-zero polynomial $g \in {\sf ideal}_{r}^{}(F)$ has a representation of the form $g = \sum_{i=1}^{k} \alpha_i \cdot f_i \ast w_i$ with $\alpha_i \in {\bf K}^*, f_i \in F, w_i \in {\cal M}$, and ${\sf HT}(f_i \ast w_i) \equiv{\sf HT}(f_i)w_i$.

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..23   For $f,g,p \in {\bf K}[{\cal M}]$ and $S \in{\cal SAT}_p(p)$, $f \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}\,$ } g$ if and only if $f \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{S}\,$ } g$.

Lemma 3..24   For a prefix saturated set F of polynomials in ${\bf K}[{\cal M}]$ and $p,q \in {\bf K}[{\cal M}]$ we have $p \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } q \mbox{ if and only if } p - q \in {\sf ideal}_{r}^{}(F)$.

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 semi-Thue system $(\Sigma, T)$. 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 

$p\in
{\bf K}[{\cal M}]$
and
		 

$(\Sigma, T)$
a convergent semi-Thue system presenting ${\cal M}$.
Find: 		 

$S \in{\cal SAT}_p(p)$.

S := $\{p \}$;
H := $\{p \}$;
while 

$H \neq \emptyset$
do
		 q := 

${\rm remove}(H)$;
		% Remove an element using a fair  strategy, i.e., no element is left in H for ever
		 t := 

${\sf HT}(q)$;
		 for all 

$w \in C(t) = \{ w \in \Sigma^* \mid tw \equiv t_{1}t_{2}w \equiv t_{1}l, t_2 \neq \lambda$
for some 

$(l, r) \in T \}$
do
		 		% C(t) contains special overlaps between  t and left hand sides of  rules in T
		 		 q' := $q \ast w$;
		 		 if 		 

$q' \mbox{$\,\,\,\,{\not\!\!\!\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{S}}\,$ } 0$
and $q' \neq 0$
		 		 		 then 		  S := 

$S \cup \{q' \}$;
		 		 		 		  H := 

$H \cup \{q' \}$;
		 		 endif
		 endfor 
endwhile 

Theorem 3..25   For a given polynomial $p\in {\bf K}[{\cal M}]$, let S be the set generated by procedure PREFIX SATURATION. Then for all $w \in {\cal M}$ every non-zero polynomial $p \ast w$ 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 PREFIX SATURATION 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 $G \subseteq {\bf K}[{\cal M}]$ is said to be a prefix Gröbner basis of ${\sf ideal}_{r}^{}(G)$, if $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ } = \;\;\equiv_{{\sf ideal}_{r}^{}(G)}$, and $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ }$ 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 ${\sf ideal}_{r}^{}(p)$, i.e., the elements of ${\sf ideal}_{r}^{}(p)$ do not necessarily prefix reduce to zero.

Example 3..28   Reviewing example 3.19, let p = a + b + c. Then $S = \{ a + b + c, a + c + \lambda, bc + c^2 + b, ba + ca + \lambda, ca + a + \lambda, c^{2} + b + c \} \in{\cal SAT}_p(p)$, but $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{S}\,$ }$ is not confluent on $\{p \ast w \mid w \in{\cal M}\}$. We have $a+b+c \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{ a + c + \lambda}\,$ } b- \lambda$ and $a+b+c \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{ a + b + c}\,$ } 0$ but $b- \lambda \mbox{$\,\,\,\,{\not\!\!\!\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{S}}\,$ } 0$.

This example also shows that Gröbner bases via $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{}\,$ }$ are Gröbner bases via $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{}\,$ }$ but not vice versa. The set $F = \{ a+b+c, b- \lambda \}$ is a strong Gröbner basis, but not a prefix Gröbner basis. Remember that prefix saturation enriches a polynomial p to a set $S \in{\cal SAT}_p(p)$ such that we can substitute $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm s}}_{p}\,$ }q'$ by $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{p' \in S}\,$ }q'$. We use this additional information to give a confluence criterion that will use a refined definition of s-polynomials.

Definition 3..29   Given two non-zero polynomials $p_{1}, p_{2} \in {\bf K}[{\cal M}]$, if there is $w \in {\cal M}$ such that ${\sf HT}(p_{1}) \equiv{\sf HT}(p_{2})w$ the prefix s-polynomial is defined as

$${\sf spol}_{p}(p_{1}, p_{2})={\sf HC}(p_1)^{-1} \cdot p_1 -{\sf HC}(p_2)^{-1} \cdot p_2 \ast w.$$

As before non-zero prefix s-polynomials are called non-trivial. In case an s-polynomial exists we always have ${\sf HT}({\sf spol}_{p}(p_{1}, p_{2})) \prec{\sf HT}(p_{1}) \equiv {\sf HT}(p_{2})w$. Notice that a finite set $F \subseteq {\bf K}[{\cal M}]$ defines finitely many prefix s-polynomials and the following lemma enables us to localize our confluence test to these s-polynomials.

Lemma 3..30   Let F be a set of polynomials in ${\bf K}[{\cal M}]$ and $p\in {\bf K}[{\cal M}]$. Further let $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$ and let us assume this reduction sequence results in a representation $p = \sum_{i=1}^{k} \alpha_i \cdot g_i \ast w_i$, where $\alpha_i \in {\bf K}^*$, $g_i \in F$, and $w_i \in {\cal M}$. Then for every term $t \in {\cal M}$ such that $t \succ {\sf HT}(p)$ and every term $w \in {\cal M}$ we get that if $s \in \bigcup_{i=1}^k {\sf T}(g_i \ast w_i \ast w)$ then $tw \succ s$ holds.

Prefix s-polynomials 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.

Theorem 3..31   For a prefix saturated set F of polynomials in ${\bf K}[{\cal M}]$, the following statements are equivalent:

(1)

For all polynomials $g \in {\sf ideal}_{r}^{}(F)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$.

(2)

For all polynomials $f_{k}, f_{l} \in F$ we have ${\sf spol}_{p}(f_{k}, f_{l}) \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$.

Corollary 3..32   A prefix saturated set $F \subseteq {\bf K}[{\cal M}]$ is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(F)$ if and only if for all $g \in {\sf ideal}_{r}^{}(F)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$.

Now theorem 3.31 gives rise to the following procedure, which can be modified to enumerate a Gröbner basis with respect to $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{}\,$ }$ 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 

$F \subseteq {\bf K}[{\cal M}]$,
and
		 

$(\Sigma, T)$
a convergent semi-Thue system presenting ${\cal M}$.
Find: 		 

$\mbox{\sc Gb}(F)$
a prefix Gröbner basis of F. 
Using: 		 

$\mbox{\sc Sat}_p$
a prefix saturating procedure for polynomials.

G := 

$\bigcup_{f \in F} \mbox{\sc Sat}_p(f)$;
% G is prefix saturated
B := 

$\{ (q_{1}, q_{2}) \mid q_{1}, q_{2} \in G, q_{1} \neq q_{2} \}$;
while 

$B \neq \emptyset$
do
		% Test if  statement 2 of theorem 3.31 is valid
		  

(q1, q2) := remove(B);
		  % Remove an element using a fair strategy
		      if 		  

${\sf spol}_{p}(q_{1}, q_{2})$
exists
		 		 % The s-polynomial is not trivial
		 		then		   h:= normal form

$({\sf spol}_{p}(q_{1}, q_{2}),\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ })$;
		 		 		 % Compute a normal form using        prefix reduction
		 		 		      if 		 $h \neq 0$
		 		 				      then 		 G := 

$G \cup \mbox{\sc Sat}_p(h)$;
		 		 				 		 % G is prefix  saturated
		 		 				 		 B := 

$B \cup \{ (f, {\tilde h}), ( {\tilde h},f) \mid f \in G, {\tilde h} \in \mbox{\sc Sat}_p(h) \}$;
		 		 		 endif
		 endif 
endwhile  


$\mbox{\sc Gb}(F):= G$

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 $\Sigma = \{ a, b, c \}$ and $T = \{ a^{2} \longrightarrow\lambda, b^{2} \longrightarrow\lambda, ab \longrightarrow c, ac \longrightarrow b, cb \longrightarrow a \}$ with a length-lexicographical ordering induced by $a \succ b \succ c$. We want to compute a prefix Gröbner basis of ${\sf ideal}_{r}^{}(a+b+c)$.
On initializing G we get $G = \{ a+b+c, a+c+\lambda, bc + c^2 + b, ba + ca+\lambda, ca + a + \lambda, c^2 + b +c \}$ (compare example 3.28).
Now inspecting this set we see that only one prefix s-polynomial has to be considered, namely

$${\sf spol}_{p}(a+b+c,a+c+\lambda) = b- \lambda.$$

Since $\{b-\lambda\}$ is a saturating set for the polynomial $b-\lambda$ we get $G= G \cup \{ b- \lambda \}$.
Now there are two possible prefix s-polynomials to consider and we find

$${\sf spol}_{p}(bc+c^2+b,b-\lambda) = c^2 + b + c \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$$

respectively

$${\sf spol}_{p}(ba+ca+\lambda, b-\lambda) = ca+a+\lambda \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$$

and hence $\{a+b+c,a+c+\lambda,bc+c^2+b,ba+ca+\lambda,ca+a+\lambda,c^2+b+c,b-\lambda\}$ is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(a+b+c)$.

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 ${\sf ideal}_{r}^{}(a+b+c)$ in example 3.33 the set $\{ a+c+\lambda, ca-c, c^2+c+\lambda,b-\lambda \}$ 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 two-sided 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 two-sided ideal it generates, if it fulfills one of the equivalent statements in the next theorem.

Theorem 3..34   For a set of polynomials $G \subseteq {\bf K}[{\cal M}]$, assuming that ${\cal M}$ is presented by $(\Sigma, T)$ as described above, the following properties are equivalent:

(1)

G is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(G)$ and ${\sf ideal}_{r}^{}(G) = {\sf ideal}_{}^{}(G)$.

(2)

For all $g \in {\sf ideal}_{}^{}(G)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ } 0$.

(3)

G is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(G)$ and for all $w \in {\cal M}$, $g \in G$ we have $w \ast g \in {\sf ideal}_{r}^{}(G)$.

(4)

G is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(G)$ and for all $a \in \Sigma$, $g \in G$ we have $a \ast g \in {\sf ideal}_{r}^{}(G)$.

Statement 4 enables a constructive approach to extend procedure PREFIX GR¨OBNER BASES in order to enumerate prefix Gröbner bases of two-sided 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 two-sided ideals. In this case if ${\bf K}[{\cal M}]$ is a right reduction ring and G is a finite prefix Gröbner basis of ${\sf ideal}_{}^{}(G)$, then ${\bf K}[{\cal M}]/{\sf ideal}_{}^{}(G)$ is a right reduction ring.