---
abstract: |
    For an efficient implementation of Buchberger’s Algorithm, it is essential to avoid the treatment of as many unnecessary critical pairs or obstructions as possible. In the case of the commutative polynomial ring, this is achieved by the Gebauer-Möller criteria. Here we present an adaptation of the Gebauer-Möller criteria for non-commutative polynomial rings, i.e. for free associative algebras over fields. The essential idea is to detect unnecessary obstructions using other obstructions with or without overlap. Experiments show that the new criteria are able to detect almost all unnecessary obstructions during the execution of Buchberger’s procedure.

    [**Keywords:**]{} Gröbner basis, free associative algebra, obstruction, Buchberger procedure

    [**AMS classification:**]{} 16-08, 20-04, 13P10
author:
- |
    Martin Kreuzer[^1], Xingqiang Xiu[^2]\
    Fakultät für Informatik und Mathematik\
    Universität Passau, D-94030 Passau, Germany
title: 'Non-Commutative Gebauer-Möller Criteria'
---

Introduction {#sec1}
============

Ever since B. Buchberger’s thesis [@Bu65], Gröbner bases have become a fundamental tool for computations in commutative algebra and algebraic geometry. The most time-consuming part in Buchberger’s Algorithm is the computation of the normal remainder of an S-polynomial corresponding to a critical pair. Therefore a significant amount of energy has been spent on reducing the number of critical pairs which have to be treated. After the discovery of various criteria for discarding critical pairs ahead of time by B. Buchberger and H.M. Möller (see [@Bu79], [@Bu85] and [@Mo85]), this subject found an initial resolution via the *Gebauer-Möller installation* presented in [@GM88] which offers a good compromise between efficiency and the success rate for detecting unnecessary critical pairs.

A very different picture presents itself for Gröbner basis computations for two-sided ideals in non-commutative polynomial rings. The basic Gröbner basis theory in this case was described by G.H. Bergman (see [@Be78]), T. Mora (see [@Mo86] and [@Mo94]) and others, and obstructions, the non-commutative analogue of critical pairs, were studied in [@Mo94]. However, since only a few authors endeavoured to implement efficient versions of Buchberger’s Procedure for the non-commutative polynomial ring (i.e. the free associative algebra), the subject of minimizing the number of obstructions which have to be treated has received comparatively little attention, and merely a few rules were developed. For instance, the package [Plural]{} of the computer algebra system [Singular]{} implements a version of the product and the chain criterion, but not the multiply criterion or the leading word criterion. On the other hand, the system [Magma]{} appears to be based on a variant of the F4 Algorithm which does not use criteria for unnecessary obstructions. For an overview on rules which have been developed see for instance [@Co07].

In this paper, we present generalizations of the Gebauer-Möller criteria for non-commutative polynomials. They cover not only the known cases of useless obstructions discussed in [@Mo94], Lemma 5.11 and [@Co07], but form a complete analogue of the results in the commutative case. One of the key ingredients we use for this purpose is the consideration of obstructions without overlaps. We detect useless obstructions, i.e. obstructions that can be represented by other obstructions, using not only obstructions with overlaps but using also those without overlaps. We show that the consideration of obstructions without overlaps does not increase unnecessary computations, since a Gröbner representation is inherent in the S-polynomial of every obstruction without overlaps. Consequently, we reduce the number of obstructions efficiently and obtain a non-commutative version of the Gebauer-Möller criteria.

This paper is organised as follows. In Section \[sec2\] we recall the basic theory of Gröbner bases for two-sided ideals in non-commutative polynomial rings. In particular, we introduce and study obstructions (see Definitions \[sec2def4\] and \[sec2def9\], and Lemmas \[sec2lem6\] and \[sec2lem8\]), present the Buchberger Criterion (see Proposition \[sec2pro10\]), and formulate the Buchberger Procedure (see Theorem \[sec2the11\]). The non-commutative analogues of the Gebauer-Möller criteria are developed in Section \[sec3\]. They are based on a careful study of the set of newly constructed obstructions which are produced during the execution of Buchberger’s Procedure. As a result, we are able to formulate the Non-Commutative Multiply Criterion (see Proposition \[ncMCrit\]), the Non-Commutative Leading Word Criterion (see Proposition \[ncLWCrit\]) and the Non-Commutative Backward Criterion (see Proposition \[ncBKCrit\]). When we combine these criteria, the result is a new Improved Buchberger Procedure \[sec3the14\].

The second author has implemented a version of the Buchberger Procedure for non-commutative polynomial rings in a package for the computer algebra system [ApCoCoA]{} which includes the non-commutative Gebauer-Möller criteria developed here (see [@Ap10]). In the last section, we present experimental results about the efficiency of the criteria for some cases of moderately difficult Gröbner basis computations.

Unless mentioned otherwise, we adhere to the definitions and terminology given in [@KR00] and [@KR05].

Gröbner Bases in $K\langle X\rangle$ {#sec2}
====================================

In the following we let $X=\{x_1,\dots,x_n\}$ be a finite set of indeterminates (or a finite alphabet), and $\langle X\rangle$ the monoid of all *words* (or *terms*) $x_{i_1}\cdots x_{i_l}$ where the multiplication is concatenation of words. The empty word will be denoted by $\lambda$. Furthermore, let $K$ be a field, and let $$K\langle X\rangle=\{c_1w_1+\cdots+c_sw_s\ |\ s\in\mathbb{N},c_i\in K\setminus\{0\},w_i\in\langle X\rangle\}$$ be the non-commutative polynomial ring generated by $X$ over $K$ (or the free associative $K$-algebra generated by $X$). We introduce basic notions of Gröbner basis theory in this setting.

\[sec2def1\] A *word ordering* on $\langle X\rangle$ is a well-ordering ${\sigma}$ which is compatible with multiplication, i.e. $w_1\geq_{\sigma} w_2$ implies $w_3w_1w_4\geq_{\sigma} w_3w_2w_4$ for all words $w_1,w_2,w_3,w_4\in\langle X\rangle$.

In the commutative case, a word ordering is usually called a *term ordering* or *monomial ordering*. For instance, the *length-lexicographic ordering* $\LLex$ is a word ordering. It first compares the length of two words and then breaks ties using the non-commutative lexicographic ordering with respect to $x_1>_{\LLex}\cdots>_{\LLex}x_n$. Note that the non-commutative lexicographic ordering by itself is not a word ordering, since it is neither a well-ordering nor compatible with multiplication.

\[sec2def2\] Let ${\sigma}$ be a word ordering on $\langle X\rangle$.

-   Given a polynomial $f\in K\langle X\rangle\setminus\{0\}$, there exists a unique representation $f=c_1w_1+\cdots+c_sw_s$ with $c_1,\dots,c_s\in K\setminus\{0\}$ and $w_1,\dots,w_s\in\langle X\rangle$ such that $w_1>_{\sigma}\cdots>_{\sigma} w_s$. The word $\lw_{\sigma}(f)=w_1$ is called the *leading word* of $f$ with respect to ${\sigma}$. The element $\lc_{\sigma}(f)=c_1$ is called the *leading coefficient*. We let $\lm_{\sigma}(f)=c_1w_1$ and call it the *leading monomial* of $f$.

-   Let $I\subseteq K\langle X\rangle$ be a two-sided ideal. The set $\lw_{\sigma}\{I\}=\{\lw_{\sigma}(f)\ |\ f\in I\setminus\{0\}\}\subseteq\langle X\rangle$ is called the *leading word set* of $I$. The two-sided ideal $\lw_{\sigma}(I)=\langle\lw_{\sigma}(f)\ |\ f\in I\setminus\{0\}\rangle\subseteq K\langle X\rangle$ is called the *leading word ideal* of $I$.

-   A subset $G$ of a two-sided ideal $I\subseteq K\langle X\rangle$ is called a *${\sigma}$-Gröbner basis* of $I$ if the set of the leading words $\lw_{\sigma}\{G\}=\{\lw_{\sigma}(f)\ |\ f\in G\setminus\{0\}\}$ generates the leading word ideal $\lw_{\sigma}(I)$.

In the following we focus on computations of Gröbner bases for two-sided ideals in $K\langle X\rangle$. For readers who want to know further properties and applications of non-commutative Gröbner bases, we refer to [@Mo94] and [@Xiu12]. Throughout this paper we assume that ${\sigma}$ is a word ordering on $\langle X\rangle$. The next algorithm is a central part of all Gröbner basis computations.

\[sec2the3\] Let $f\in K\langle X\rangle$, $s\geq 1$, and $G=\{g_{1},\dots,g_{s}\}\subseteq K\langle X\rangle\setminus\{0\}$. Consider the following sequence of instructions.

-   Let $k_{1}=\cdots=k_{s}=0, p=0$, and $v=f$.

-   Find the smallest index $i\in\{1,\dots,s\}$ such that $\lw_{\sigma}(v)=w\lw_{\sigma}(g_{i})w'$ for some words $w,w'\in\langle X\rangle$. If such an $i$ exists, increase $k_{i}$ by $1$, set $c_{ik_{i}}=\frac{\lc_{\sigma}(v)}{\lc_{\sigma}(g_{i})}, w_{ik_{i}}=w, w'_{ik_{i}}=w'$, and replace $v$ by $v-c_{ik_{i}}w_{ik_{i}}g_{i}w'_{ik_{i}}$.

-   Repeat step [(D2)]{} until there is no more $i\in\{1,\dots,s\}$ such that $\lw_{\sigma}(v)$ is a multiple of $\lw_{\sigma}(g_{i})$. If now $v\neq 0$, then replace $p$ by $p+\lm_{\sigma}(v)$ and $v$ by $v-\lm_{\sigma}(v)$, continue with step [(D2)]{}.

-   Return the tuples $(c_{11},w_{11},w'_{11}),\dots,(c_{sk_{s}},w_{sk_{s}},w'_{sk_{s}})$ and $p$.

This is an algorithm which returns tuples $(c_{11},w_{11},w'_{11}),\dots,(c_{sk_{s}},w_{sk_{s}},w'_{sk_{s}})$ and a polynomial $p\in K\langle X\rangle$ such that the following conditions are satisfied.

-   We have $f=\sum^{s}_{i=1}\sum^{k_{i}}_{j=1}c_{ij}w_{ij}g_{i}w'_{ij}+p$.

-   No element of ${\rm Supp}(p)$ is contained in $\langle\lw_{\sigma}(g_{1}),\dots,\lw_{\sigma}(g_{s})\rangle$.

-   For all $i\in\{1,\dots,s\}$ and all $j\in\{1,\dots,k_{i}\}$, we have $\lw_{\sigma}(w_{ij}g_{i}w'_{ij})\leq_{\sigma}\lw_{\sigma}(f)$. If $p\neq 0$, we have $\lw_{\sigma}(p)\leq_{\sigma}\lw_{\sigma}(f)$.

-   For all $i\in\{1,\dots, s\}$ and all $j\in\{1,\dots,k_{i}\}$, we have $\lw_{\sigma}(w_{ij}g_{i}w'_{ij})\notin\langle\lw_{\sigma}(g_{1}),\dots,\lw_{\sigma}(g_{i-1})\rangle$.

Note that the resulting tuples $(c_{11},w_{11},w'_{11}),\dots,(c_{sk_{s}},w_{sk_{s}},w'_{sk_{s}})$ and polynomial $p$ satisfying conditions (a)-(d) are *not* unique. This is due to the fact that in step (D2) of the Division Algorithm there might exist more that one pair $(w,w')$ satisfying $\lw_{\sigma}(v)=w\lw_{\sigma}(g_{i})w'$ (see [@Xiu12], Example 3.2.2). A polynomial $p\in K\langle X\rangle$ obtained in Theorem \[sec2the3\] is called a *normal remainder* of $f$ with respect to $G$ and is denoted by ${\rm NR}_{\sigma,G}(f)$.

For $s\geq 1$, we let $F_s=(K\langle X\rangle\otimes_{K}K\langle X\rangle)^s$ be the free two-sided $K\langle X\rangle$-module of rank $s$ with the canonical basis $\{e_{1},\dots,e_{s}\}$, where $e_{i}=(0,\dots,0,1\otimes1,$ $0,\dots,0)$ with $1\otimes1$ occurring in the $i^{\rm th}$ position for $i=1,\dots,s$, and we let $\mathbb{T}(F_{s})$ be the set of terms in $F_{s}$, i.e. $\mathbb{T}(F_{s})=\{we_{i}w'\ |\ i\in\{1,\dots,s\}, w,w'\in\langle X\rangle\}$.

\[sec2def4\] Let $G=\{g_1,\dots,g_s\}\subseteq K\langle X\rangle\setminus\{0\}$ with $s\geq 1$, and let $i,j\in\{1,\dots,s\}$ such that $i\leq j$.

-   If there exist some words $w_{i},w'_{i},w_{j},w'_{j}\in\langle X\rangle$ such that $w_{i}\lw_{\sigma}(g_{i})w'_{i}=w_{j}\lw_{\sigma}(g_{j})w'_{j}$, then we call the element $${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})=\frac{1}{\lc_{\sigma}(g_{i})}w_{i}e_{i}w'_{i}-\frac{1}{\lc_{\sigma}(g_{j})}w_{j}e_{j}w'_{j}\in F_{s}\setminus\{0\}$$ an *obstruction* of $g_i$ and $g_j$. If $i=j$, it is called a *self obstruction* of $g_{i}$. We will denote the *set of all obstructions* of $g_{i}$ and $g_{j}$ by ${\rm Obs}(i,j)$.

-   Let ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in {\rm Obs}(i,j)$ be an obstruction of $g_{i}$ and $g_{j}$. The polynomial $$S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})=\frac{1}{\lc_{\sigma}(g_{i})}w_{i}g_{i}w'_{i}-\frac{1}{\lc_{\sigma}(g_{j})}w_{j}g_{j}w'_{j}\in K\langle X\rangle$$ is called the *S-polynomial* of ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$.

Using these definitions, we can characterize Gröbner bases in the following way.

\[sec2pro5\] Let $G=\{g_1,\dots,g_s\}\subseteq K\langle X\rangle\setminus\{0\}$ be a set of polynomials which generate a two-sided ideal $I=\langle G\rangle\subseteq K\langle X\rangle$. Then the following conditions are equivalent.

-   The set $G$ is a ${\sigma}$-Gröbner basis of $I$.

-   For every obstruction ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ in the set $\bigcup_{1\leq i\leq j\leq s}{\rm Obs}(i,j)$, its S-polynomial $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ has a representation $$S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})=\sum^{\mu}_{k=1}c_{k}w_{k}g_{i_{k}}w'_{k}$$ with $c_{k}\in K, w_{k},w'_{k}\in\langle X\rangle$, and $g_{i_{k}}\in G$ for all $k\in\{1,\dots,\mu\}$ such that $\lw_{\sigma}(w_{j}g_{j}w'_{j})>_{\sigma}\lw_{\sigma}(w_{k}g_{i_{k}}w'_{k})$ if $c_k\neq 0$ for some $k\in\{1,\dots,\mu\}$.

See [@Xiu12], Proposition 4.1.2.

A presentation of $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ as in Proposition \[sec2pro5\].b is called a *(weak) Gröbner representation* of $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ in terms of $G$.

Observe that there are infinitely many obstructions in each set ${\rm Obs}(i,j)$, due to the following two types of *trivial* obstructions.

-   If ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in {\rm Obs}(i,j)$, then, for all $w,w'\in\langle X\rangle$, we have ${\rm o}_{i,j}(ww_{i},w'_{i}w';ww_{j},w'_{j}w')\in{\rm Obs}(i,j)$.

-   For all $w\in\langle X\rangle$, we have ${\rm o}_{i,j}(\lw_{\sigma}(g_{j})w,1;1,w\lw_{\sigma}(g_{i})), {\rm o}_{i,j}(1, w\lw_{\sigma}(g_{j});$ $\lw_{\sigma}(g_{i})w,1)\in{\rm Obs}(i,j)$.

Before going on, let us get rid of these two types of trivial obstructions. The following lemma handles trivial obstructions of type (T1).

\[sec2lem6\] If the S-polynomial of ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in {\rm Obs}(i,j)$ has a Gröbner representation in terms of $G$, then, for all $w,w'\in\langle X\rangle$, the S-polynomial of ${\rm o}_{i,j}(ww_{i},w'_{i}w';ww_{j},w'_{j}w')$ also has a Gröbner representation in terms of $G$.

Without loss of generality, we assume that $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ is non-zero. We write $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})=\sum^{\mu}_{k=1}c_{k}w_{k}g_{i_{k}}w'_{k}$, where $c_{k}\in K\setminus\{0\}$, $w_{k},w'_{k}\in\langle X\rangle$, and $g_{i_{k}}\in G$ such that $\lw_{\sigma}(w_{j}g_{j}w'_{j})>_{\sigma}\lw_{\sigma}(w_{k}g_{i_{k}}w'_{k})$ for all $k\in\{1,\dots,\mu\}$. For all $w,w'\in\langle X\rangle$, it is clear that $S_{i,j}(ww_{i},w'_{i}w';ww_{j},w'_{j}w')$ $=\sum^{\mu}_{k=1}c_{k}ww_{k}g_{i_{k}}w'_{k}w'$. Since the word ordering $\sigma$ is compatible with multiplication, we have $w\lw_{\sigma}(w_{j}g_{j}w'_{j})w'>_{\sigma}w\lw_{\sigma}(w_{k}g_{i_{k}}w'_{k})w'$ for all $k\in\{1,\dots,\mu\}$. Hence we have $\lw_{\sigma}(ww_{j}g_{j}w'_{j}w')>_{\sigma}\lw_{\sigma}(ww_{k}g_{i_{k}}w'_{k}w')$ for all $k\in\{1,\dots,\mu\}$ and $S_{i,j}(ww_{i},w'_{i}w';ww_{j},w'_{j}w')=\sum^{\mu}_{k=1}c_{k}ww_{k}g_{i_{k}}w'_{k}w'$ is a Gröbner representation in terms of $G$.

To deal with trivial obstructions of type (T2), we introduce some terminology as follows.

\[sec2def7\] Let $G=\{g_1,\dots,g_s\}\subseteq K\langle X\rangle\setminus\{0\}$ with $s\geq 1$.

-   Let $w_{1},w_{2}\in\langle X\rangle$ be two words. If there exist some words $w,w',w''\in\langle X\rangle$ and $w\neq 1$ such that $w_{1}=w'w$ and $w_{2}=ww''$, or $w_{1}=ww'$ and $w_{2}=w''w$, or $w_{1}=w$ and $w_{2}=w'ww''$, or $w_{1}=w'ww''$ and $w_{2}=w$, then we say $w_{1}$ and $w_{2}$ have an *overlap* at $w$. Otherwise, we say that $w_{1}$ and $w_{2}$ have *no overlap*.

-   Let ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in {\rm Obs}(i,j)$ be an obstruction. If $\lw_{\sigma}(g_{i})$ and $\lw_{\sigma}(g_{j})$ have an overlap at $w\in\langle X\rangle\setminus\{1\}$ and if $w$ is a subword of $w_{i}\lw_{\sigma}(g_{i})w'_{i}$, then we say that ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ has an *overlap* at $w$. Otherwise, we say that ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ has *no overlap*.

Thus, as shown in (T2), there are infinitely many obstructions without overlaps in each ${\rm Obs}(i,j)$. The following lemma gets rid of these trivial obstructions.

\[sec2lem8\] If ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in {\rm Obs}(i,j)$ has no overlap, then $S_{i,j}(w_{i},w'_{i};$ $w_{j},w'_{j})$ has a Gröbner representation in terms of $G$.

See [@Mo94], Lemma 5.4.

Observe that Lemma \[sec2lem8\] is indeed a non-commutative version of the *product criterion* (or *criterion 2*) of Buchberger (cf. [@Bu85]).

\[sec2def9\] Let $G=\{g_1,\dots,g_s\}\subseteq K\langle X\rangle\setminus\{0\}$ with $s\geq 1$.

-   Let $i,j\in\{1,\dots,s\}$ and $i<j$. An obstruction in ${\rm Obs}(i,j)$ is called *non-trivial* if it has an overlap and is of the form ${\rm o}_{i,j}(w_{i},1;1,w'_{j})$, or ${\rm o}_{i,j}(1,w'_{i};$ $w_{j},1)$, or ${\rm o}_{i,j}(w_{i},w'_{i};1,1)$, or ${\rm o}_{i,j}(1,1;w_{j},w'_{j})$ with $w_{i},w'_{i},w_{j},w'_{j}\in\langle X\rangle$.

-   Let $i\in\{1,\dots,s\}$. A self obstruction in ${\rm Obs}(i,i)$ is called *non-trivial* if it has an overlap and is of the form ${\rm o}_{i,i}(1,w'_{i};w_{i},1)$ with $w_{i},w'_{i}\in\langle X\rangle\setminus\{1\}$.

-   Let $i,j\in\{1,\dots,s\}$ and $i\leq j$. The *set of all non-trivial obstructions* of $g_{i}$ and $g_{j}$ will be denoted by ${\rm NTObs}(i,j)$.

In the literature, a non-trivial obstruction of the form ${\rm o}_{i,j}(w_{i},1;1,w'_{j})$ is called a *left obstruction*, a non-trivial obstruction of the form ${\rm o}_{i,j}(1,w'_{i};w_{j},1)$ is called a *right obstruction*, and a non-trivial obstruction of the form ${\rm o}_{i,j}(w_{i},w'_{i};$ $1,1)$ or ${\rm o}_{i,j}(1,1;w_{j},w'_{j})$ is called a *center obstruction*. We picture four types of obstructions as follows.

[\*[3]{}[C]{}]{} &\
&\
&&\
& &\
\
&&

[\*[3]{}[C]{}]{} &\
&\
&&\
\
& &\
&&

At this point we can refine the characterization of Gröbner bases given in Proposition \[sec2pro5\] in the following way.

\[sec2pro10\] Let $G=\{g_1,\dots,g_s\}\subseteq K\langle X\rangle$ be a set of non-zero polynomials which generate a two-sided ideal $I=\langle G\rangle\subseteq K\langle X\rangle$. Then the set $G$ is a ${\sigma}$-Gröbner basis of $I$ if and only if, for each non-trivial obstruction ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in\bigcup_{1\leq i\leq j\leq s}{\rm NTObs}(i,j)$, its S-polynomial $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ has a Gröbner representation in terms of $G$.

This follows directly from Proposition \[sec2pro5\] and Lemmas \[sec2lem6\] and \[sec2lem8\]. In view of Lemma \[sec2lem8\], it suffices to consider each obstruction with overlap, which is either a non-trivial obstruction or a multiple of a non-trivial obstruction. Further, Lemma \[sec2lem6\] treats a multiple of a non-trivial obstruction via the corresponding non-trivial obstruction. Therefore, it is sufficient to consider only non-trivial obstructions.

The Buchberger Criterion enables us to formulate the following procedure for computing Gröbner bases of two-sided ideals. Note that, in the procedure, by a *fair strategy* we mean a selection strategy which ensures that every obstruction is selected eventually. Since these Gröbner bases need not be finite, we have to content ourselves with an enumerating procedure.

\[sec2the11\] Let $s\geq 1$, and let $G=\{g_1,\dots,g_s\}\subseteq K\langle X\rangle$ be a set of non-zero polynomials which generate a two-sided ideal $I=\langle G\rangle\subseteq K\langle X\rangle$. Consider the following sequence of instructions.

-   Let $B=\bigcup_{1\leq i\leq j\leq s}{\rm NTObs}(i,j)$.

-   If $B=\emptyset$, return the result ${G}$. Otherwise, select an obstruction ${\rm o}_{i,j}(w_{i},w'_{i};$ $w_{j},w'_{j})\in B$ using a fair strategy and delete it from $B$.

-   Compute the S-polynomial $S=S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ and its normal remainder $S'={\rm NR}_{\sigma,G}(S)$. If $S'=0$, continue with step [(B2)]{}.

-   Increase $s$ by one, append $g_{s}=S'$ to the set ${G}$, and append the set of obstructions $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ to the set $B$. Then continue with step [(B2)]{}.

This is a procedure that enumerates a ${\sigma}$-Gröbner basis ${G}$ of $I$. If $I$ has a finite ${\sigma}$-Gröbner basis, the procedure stops after finitely many steps and the resulting set ${G}$ is a finite ${\sigma}$-Gröbner basis of $I$.

Note that this is a straightforward generalization of the commutative version of Buchberger’s algorithm to the non-commutative case. We refer to [@Mo94] for the original form of this procedure and to [@Xiu12], Theorem 4.1.14 for a detailed proof.

Non-Commutative Gebauer-Möller Criteria {#sec3}
=======================================

In this section we present non-commutative Gebauer-Möller criteria. They check whether an obstruction can be represented by “smaller” obstructions. If so, we declare such obstructions to be *unnecessary*. Before going into details, we define a certain well-ordering $\tau$ on $\mathbb{T}(F_{s})=\{we_{i}w'\ |\ i\in\{1,\dots,s\}, w,w'\in\langle X\rangle\}$ and use it to order obstructions. In the following, let $s\geq1$, and let $G=\{g_1,\dots,g_{s}\}\subseteq K\langle X\rangle\setminus\{0\}$ be a set of non-commutative polynomials.

\[sec3def1\] Let us define a relation $\tau$ on $\mathbb{T}(F_{s})$ as follows. For two terms $w_{1}e_{i}w'_{1},w_{2}e_{j}w'_{2}\in\mathbb{T}(F_{s})$, we let $w_{1}e_{i}w'_{1}\geq_{\tau}w_{2}e_{j}w'_{2}$ if

-   $w_{1}\lw_{\sigma}(g_{i})w'_{1}>_{\sigma}w_{2}\lw_{\sigma}(g_{j})w'_{2}$, or

-   $w_{1}\lw_{\sigma}(g_{i})w'_{1}=w_{2}\lw_{\sigma}(g_{j})w'_{2}$ and $i>j$, or

-   $w_{1}\lw_{\sigma}(g_{i})w'_{1}=w_{2}\lw_{\sigma}(g_{j})w'_{2}$ and $i=j$ and $w_{1}\geq_{\sigma}w_{2}$.

One can check that $\tau$ is a well-ordering and is compatible with scalar multiplication. The relation $\tau$ is called the *module term ordering induced by* $({\sigma},{G})$ on $\mathbb{T}(F_{s})$.

By definition, for every obstruction ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in\bigcup_{1\leq i\leq j\leq s}{\rm Obs}(i,j)$, we have $w_{i}e_{i}w'_{i}<_{\tau}w_{j}e_{j}w'_{j}$. We extend the ordering $\tau$ to the set of obstructions $\bigcup_{1\leq i\leq j\leq s}{\rm Obs}(i,j)$ by committing the following slight abuse of notation.

\[sec3def2\] Let $\tau$ be the module term ordering induced by $({\sigma},{G})$ on $\mathbb{T}(F_{s})$. Let ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j}), {\rm o}_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$ be two obstructions in the set $\bigcup_{1\leq i\leq j\leq s}{\rm Obs}(i,j)$. If we have $w_{j}e_{j}w'_{j}>_{\tau}w_{l}e_{l}w'_{l}$, or if we have $w_{j}e_{j}w'_{j}=w_{l}e_{l}w'_{l}$ and $w_{i}e_{i}w'_{i}\geq_{\tau}w_{k}e_{k}w'_{k}$, then we let ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\geq_{\tau}{\rm o}_{k,l}(w_{k},w'_{k};$ $w_{l},w'_{l})$. The ordering $\tau$ is called the ordering *induced by* $({\sigma},{G})$ on the set of obstructions.

One can verify that $\tau$ is also a well-ordering on $\bigcup_{1\leq i\leq j\leq s}{\rm Obs}(i,j)$ and compatible with scalar multiplication.

Now we are ready to generalize the commutative Gebauer-Möller criteria (see [@CKR04] and [@GM88]) to the non-commutative case. Recall that, in step (B4) of the Buchberger Procedure, when a new generator $g_{s}$ is added, we immediately construct new obstructions $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$. We want to detect unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ of newly constructed obstructions as well as in the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$ of previously constructed obstructions. We achieve this goal via the following three steps. Firstly, we detect unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ with the aid of other obstructions also in this set. This step is called a *head reduction step* in [@CKR04]. Secondly, we detect unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ with the aid of obstructions in the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$. This step is called a *tail reduction step* in [@CKR04]. Thirdly, we detect unnecessary obstructions in the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$ with the aid of the new generator $g_{s}$. Indeed, the first step corresponds to the commutative Gebauer-Möller criteria $M$ and $F$, and the last step corresponds to criterion $B_k$ (c.f. [@GM88], Subsection 3.4).

The following lemma helps us to implement the first step, that is, to detect unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ of newly constructed obstructions via other obstructions in this set.

\[sec3lem3\] Let ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ and ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ be two distinct non-trivial obstructions in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ with two words $w,w'\in\langle X\rangle$ satisfying $u_{s}=$ $wv_{s}$ and $u'_{s}=v'_{s}w'$.

-   If $i<j$ and $ww'\neq1$, then we have $${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=w{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})w'+{\rm o}_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$$ with ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$. Further, if the S-polynomials $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$ have Gröbner representations in terms of $G$, then so does $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$.

-   If $i>j$, then we have $${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=w{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})w'-{\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$$ with ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$. Further, if the S-polynomials $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$ have Gröbner representations in terms of $G$, then so does $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$.

-   If $i=j$ and $ww'\neq 1$ or if $i=j$ and $ww'=1$ and $w_i>_{\sigma}w_j$, then we have $${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=w{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})w'+{\rm o}_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$$ with ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$. Further, if the S-polynomials $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$ have Gröbner representations in terms of $G$, then so does $_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$.

We prove case (a). Cases (b) and (c) can be proved similarly. The equation in case (a) follows from Definition \[sec2def4\].a and from the conditions $u_{s}=wv_{s}, u'_{s}=v'_{s}w'$ and $i<j$. Because of $ww'>1$, we have $u_{s}\lw(g_{s})u'_{s}=wv_{s}\lw(g_{s})v'_{s}w'>_{\sigma}v_{s}\lw(g_{s})v'_{s}$. Consequently, we get $u_{s}e_{s}u'_{s}>_{\tau}v_{s}e_{s}v'_{s}$ and ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$. From $u_{s}\lw(g_{s})u'_{s}$ $=w_{i}\lw(g_{i})w'_{i}=ww_{j}\lw(g_{j})w'_{j}w'$ and $s>j$, we get the inequalities $u_{s}e_{s}u'_{s}>_{\tau}ww_{j}e_{j}w'_{j}w'$ and ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})>_{\tau}{\rm o}_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$.

Next we show that, if $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$ have Gröbner representations in terms of $G$, then so does $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$. Clearly we have $$S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=wS_{j,s}(w_{j},w'_{j};v_{s},v'_{s})w'+S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w').$$ Without loss of generality, we assume that $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s}), S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$ are non-zero. Since there is a Gröbner representation for $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$, we have $$S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})=\sum^\mu_{k=1}a_kw_kg_{i_k}w'_k$$ with $a_k\in K\setminus\{0\},\ w_k,w'_k\in\langle X\rangle,\ g_{i_k}\in G$ for all $k\in\{1,\dots,\mu\}$, such that $\lw_{\sigma}(v_{s}g_{s}v'_{s})>_{\sigma}\lw_{\sigma}(a_kw_kg_{i_k}w'_k)$. Similarly, for $S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$ we have $$S_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')=\sum^\nu_{l=1}b_lw_lg_{i_l}w'_l$$ with $b_l\in K\setminus\{0\},\ w_l,w'_l\in\langle X\rangle,\ g_{i_l}\in G$ for all $l\in\{1,\dots,\nu\}$, such that $\lw_{\sigma}(ww_{j}g_{j}w'_{j}w')>_{\sigma}\lw_{\sigma}(b_lw_lg_{i_l}w'_l)$. Therefore we have $$\begin{aligned}
S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})&=&w(\sum^\mu_{k=1}a_kw_kg_{i_k}w'_k)w'+\sum^\nu_{l=1}b_lw_lg_{i_l}w'_l\\
&=&\sum^\mu_{k=1}a_kww_kg_{i_k}w'_kw'+\sum^\nu_{l=1}b_lw_lg_{i_l}w'_l.\end{aligned}$$ As $u_{s}\lw_{\sigma}(g_{s})u'_{s}=wv_{s}\lw_{\sigma}(g_{s})v'_{s}w'$, we have $\lw_{\sigma}(u_{s}g_{s}u'_{s})=\lw_{\sigma}(wv_{s}g_{s}v'_{s}w')$ $>_{\sigma}\lw_{\sigma}(ww_kg_{i_k}w'_kw')$ for all $k\in\{1,\dots,\mu\}$. By Definition \[sec2def4\], we have $\lw_{\sigma}(u_{s}g_{s}u'_{s})=\lw_{\sigma}(w_{i}g_iw'_{i})=\lw_{\sigma}(ww_{j}g_jw'_{j}w')>_{\sigma}\lw_{\sigma}(b_lw_lg_{i_l}w'_l)$ for all $l\in\{1,\dots,\nu\}$. Therefore $$S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=\sum^\mu_{k=1}a_kww_kg_{i_k}w'_kw'+\sum^\nu_{l=1}b_lw_lg_{i_l}w'_l$$ is a Gröbner representation of $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$.

The following example shows that the obstruction ${\rm o}_{i,j}(w_{i},w'_{i};ww_{j},w'_{j}w')$ in case (a) of Lemma \[sec3lem3\] can be a non-trivial obstruction, i.e. a multiple of a non-trivial obstruction or an obstruction without overlap. Similar phenomena occur in cases (b) and (c) of Lemma \[sec3lem3\], as well as in Lemmas \[sec3lem7\] and \[sec3lem10\].

\[sec3exa4\] Consider polynomials $G=\{g_{1},g_{2},g_{3}\}$ in the non-commutative polynomial ring $K\langle x,y\rangle$.

-   Assume that $\lm_{\sigma}(g_{1})=y^3, \lm_{\sigma}(g_{2})=x^2y^{2}$ and $\lm_{\sigma}(g_{3})=xyx^{2}y$. Then we have ${\rm o}_{1,3}(xyx^{2},1;1,y^{2}), {\rm o}_{2,3}(xy,1;1,y)\in\bigcup_{1\leq i\leq 3}{\rm NTObs}(i,3)$, and $${\rm o}_{1,3}(xyx^{2},1;1,y^{2})={\rm o}_{2,3}(xy,1;1,y)y+{\rm o}_{1,2}(xyx^2,1;xy,y).$$ Observe that ${\rm o}_{1,2}(xyx^2,xy;y)=xy{\rm o}_{1,2}(x^2,1;1,y)$ is a multiple of the non-trivial obstruction ${\rm o}_{1,2}(x^2,1;1,y)$.

-   Now assume that $\lm_{\sigma}(g_{1})=(xy)^{2}, \lm_{\sigma}(g_{2})=y$ and $\lm_{\sigma}(g_{3})=xyx^{2}y$. Then we have ${\rm o}_{1,3}(xyx,1;1,xy), {\rm o}_{2,3}(x,x^{2}y;1,1)\in\bigcup_{1\leq i\leq 3}{\rm NTObs}(i,3)$, and $${\rm o}_{1,3}(xyx,1;1,xy)={\rm o}_{2,3}(x,x^{2}y;1,1)xy+{\rm o}_{1,2}(xyx,1;x,x^{2}yxy).$$ One can check that ${\rm o}_{1,2}(xyx,1;x,x^{2}yxy)$ is an obstruction without overlap.

In the following, we present the non-commutative multiply criterion and the leading word criterion. They are non-commutative analogues of the Gebauer-Möller criteria M and F, respectively.

\[ncMCrit\] Suppose that ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ and ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ are two distinct non-trivial obstructions in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ such that there exist two words $w,w'$ in $\langle X\rangle$ satisfying $u_{s}=wv_{s}$ and $u'_{s}=v'_{s}w'$. Then we can remove the obstruction ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ from $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ in the execution of the Buchberger Procedure if $ww'\neq 1$.

By the previous lemma, the obstruction ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ can be represented as $${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=w{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})w'+a{\rm o}_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$$ with $a\in\{1,-1\}$ and $k=\min\{i,j\},l=\max\{i,j\}$. To prove that ${\rm o}_{i,s}(w_{i},w'_{i};$ $u_{s},u'_{s})$ is strictly larger than ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and ${\rm o}_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$, we consider two cases. If $i>j$, then the result follows from Lemma \[sec3lem3\].b; if $i\leq j$, then the result follows from Lemma \[sec3lem3\].a and \[sec3lem3\].c and the condition $ww'\neq 1$. Moreover, the S-polynomial $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ has a Gröbner representation in terms of $G$ if $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$ have Gröbner representations in terms of $G$. Theorem \[sec2the11\] ensures that $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ has a Gröbner representation in terms of $G$. Note that the obstruction ${\rm o}_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$ can be either a multiple of a non-trivial obstruction or an obstruction without overlap (for instance, see Example \[sec3exa4\]). If ${\rm o}_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$ is a multiple of a non-trivial obstruction, then Lemma \[sec2lem6\] and Theorem \[sec2the11\] guarantee that $S_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$ has a Gröbner representation in terms of $G$. If ${\rm o}_{k,l}(w_{k},w'_{k};w_{l},w'_{l})$ is an obstruction without overlap, then, by Lemma \[sec2lem8\], its S-polynomial has a Gröbner representation in terms of $G$. Now the conclusion follows from Proposition \[sec2pro10\] and Theorem \[sec2the11\].

\[ncLWCrit\] Suppose that ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ and ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ are two distinct non-trivial obstructions in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ such that there exist two words $w,w'$ in $\langle X\rangle$ satisfying $u_{s}=wv_{s}$ and $u'_{s}=v'_{s}w'$. Then ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ can be removed from $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ in the execution of the Buchberger Procedure if one of the following conditions is satisfied.

-   $i>j$.

-   $i=j$ and $ww'=1$ and $w_{i}>_{\sigma}w_{j}$.

Observe that condition (a) corresponds to Lemma \[sec3lem3\].b, while condition (b) corresponds to Lemma \[sec3lem3\].c. We represent ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ as $${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})=w{\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})w'-{\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i}).$$ By Lemma \[sec3lem3\].b and \[sec3lem3\].c, we have ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ is strictly larger than ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and ${\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$. Moreover, if the S-polynomials $S_{j,s}(w_{j},w'_{j};v_{s},v'_{s})$ and $S_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$ have Gröbner representations in terms of $G$, then so does $S_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$. Theorem \[sec2the11\] ensures $S_{j,s}(w_{j},w'_{j};$ $v_{s},v'_{s})$ has a Gröbner representation in terms of $G$. Note that the obstruction ${\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$ can be either a multiple of a non-trivial obstruction or an obstruction without overlap (for instance, see Example \[sec3exa4\]). If ${\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$ is a multiple of a non-trivial obstruction, then Lemma \[sec2lem6\] and Theorem \[sec2the11\] guarantee that $S_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$ has a Gröbner representation in terms of $G$. If ${\rm o}_{j,i}(ww_{j},w'_{j}w';w_{i},w'_{i})$ is an obstruction without overlap, then, by Lemma \[sec2lem8\], its S-polynomial has a Gröbner representation in terms of $G$. Now the conclusion follows from Proposition \[sec2pro10\] and Theorem \[sec2the11\].

Next we work on detecting unnecessary obstructions in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ via obstructions in the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$ of previously constructed obstructions.

\[sec3lem7\] Let ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$ and ${\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})$ be non-trivial obstructions in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ and $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$, respectively. If there exist two words $w,w'\in\langle X\rangle$ such that $u_{j}=wv_{j}$ and $u'_{j}=v'_{j}w'$, then we have $${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})=-w{\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})w'+
{\rm o}_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$$ where the inequalities ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})
>_{\tau}{\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})$ and ${\rm o}_{j,s}(u_{j},u'_{j};$ $w_{s},w'_{s})
>_{\tau}{\rm o}_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ hold. Further, if the S-polynomials $S_{i,j}(w_{i},w'_{i};$ $v_{j},v'_{j})$ and $S_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ have Gröbner representations in terms of $G$, then so does $S_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$.

The claimed equality follows from Definition \[sec2def4\].a and from the conditions $u_{j}=wv_{j}$ and $u'_{j}=v'_{j}w'$. We have ${\rm o}_{j,s}(u_{j},u'_{j}; w_{s},w'_{s})>_{\tau}{\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})$ for $w_{s}e_{s}w'_{s}>_{\tau}u_{j}e_{j}u'_{j}=
wv_{j}e_{j}v'_{j}w\geq_{\tau}v_{j}e_{j}v'_{j}$. From the inequality $u_{j}e_{j}u'_{j}=
wv_{j}e_{j}v'_{j}w>_{\tau}ww_{i}e_{i}w'_{i}w'$, it follows that ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})
>_{\tau}{\rm o}_{i,s}(ww_{i},w'_{i}w';$ $w_{s},w'_{s})$. Again, we can prove the second part by following the same argument as in the proof of Lemma \[sec3lem3\].a.

Note that the obstruction ${\rm o}_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ in Lemma \[sec3lem7\] can be either a multiple of a non-trivial obstruction or an obstruction without overlap. However, it suffices for us to consider only the latter case, since the former case has been considered in Proposition \[ncMCrit\], and, more precisely, in Lemma \[sec3lem3\].b.

\[ncTailRed\] Suppose that ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$ and ${\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})$ are non-trivial obstructions in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ and $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$, respectively, such that there exist two words $w,w'\in\langle X\rangle$ satisfying $u_{j}=wv_{j}$ and $u'_{j}=v'_{j}w'$. If the word $ww_{i}$ is a multiple of $w_{s}\lw_{\sigma}(g_{s})$, or if the word $w'_{i}w'$ is a multiple of $\lw_{\sigma}(g_{s})w'_{s}$, then ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$ can be removed from $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ in the execution of the Buchberger Procedure.

By Lemma \[sec3lem7\], the obstruction ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$ can be represented as $${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})=
-w{\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})w'+{\rm o}_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$$ where the inequalitites ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})>_\tau{\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})$ and ${\rm o}_{j,s}(u_{j},u'_{j};$ $w_{s},w'_{s})>_\tau{\rm o}_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ hold. Further, if the S-polynomials $S_{i,j}(w_{i},w'_{i};$ $v_{j},v'_{j})$ and $S_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ have Gröbner representations in terms of $G$, then so does $S_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$. Theorem \[sec2the11\] ensures that $S_{i,j}(w_{i},w'_{i};v_{j},v'_{j})$ has a Gröbner representation in terms of $G$. Note that $ww_{i}$ is a multiple of $w_{s}\lw_{\sigma}(g_{s})$ or $w'_{i}w'$ is a multiple of $\lw_{\sigma}(g_{s})w'_{s}$. This implies that ${\rm o}_{i,s}(ww_{i},$ $w'_{i}w';w_{s},w'_{s})$ has no overlap. By Lemma \[sec2lem8\], $S_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ has a Gröbner representation in terms of $G$. Now the conclusion follows from Proposition \[sec2pro10\] and Theorem \[sec2the11\].

\[sec3rem9\] Our experiments in the final section show that, after applying the previous two criteria, the Non-Commutative Tail Reduction is unlikely to apply in the Buchberger Procedure. This may be due to the fact that frequently the Non-Commutative Multiply Criterion and the Non-Commutative Leading Word Criterion have already detected all unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ of newly constructed obstructions.

So far we have detected unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm O}(i,s)$ of newly constructed obstructions. Intuitively, we are also able to detect unnecessary obstructions in the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm Obs}(i,j)$ of previously constructed obstructions. Thus, in the last step, we detect unnecessary obstructions in this set by using the new generator $g_{s}$.

\[sec3lem10\] Let ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$ be a non-trivial obstruction. If there are two words $w,w'\in\langle X\rangle$ satisfying $w_{j}\lw_{\sigma}(g_{j})w'_{j}=w\lw_{\sigma}(g_{s})w'$, then we can represent ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ as $${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})={\rm o}_{i,s}(w_{i},w'_{i};w,w')-{\rm o}_{j,s}(w_{j},w'_{j};w,w').$$ Moreover, if $S_{i,s}(w_{i},w'_{i};w,w')$ and $S_{j,s}(w_{j},w'_{j};w,w')$ have Gröbner representations in terms of $G$, then so does $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$.

The claimed equality follows from Definition \[sec2def4\].a and the condition $w_{j}\lw_{\sigma}(g_{j})w'_{j}$ $=w\lw_{\sigma}(g_{s})w'$. The proof of the second part is analogous to the proof of the second part of Lemma \[sec3lem3\].a.

The following example shows that the obstruction ${\rm o}_{i,s}(w_{i},w'_{i};w,w')$ in the equation of Lemma \[sec3lem10\] can be either an obstruction without overlap or a multiple of a non-trivial obstruction. In the case that ${\rm o}_{i,s}(w_{i},w'_{i};w,w')$ is a multiple of a non-trivial obstruction, say ${\rm o}_{i,s}(\tilde{w}_{i},\tilde{w}'_{i};\tilde{w},\tilde{w}')$, the example shows that it is not necessary to have ${\rm o}_{i,s}(w_{i},w'_{i};w,w')>_{\tau}{\rm o}_{i,s}(\tilde{w}_{i},\tilde{w}'_{i};\tilde{w},\tilde{w}')$ (compared to Lemmas \[sec3lem3\] and \[sec3lem7\]). The same also holds for the obstruction ${\rm o}_{j,s}(w_{j},w'_{j};w,w')$ in the equation of Lemma \[sec3lem10\].

\[sec3exa11\] Consider polynomials $G=\{g_{1},g_{2},g_{3}\}$ in the non-commutative polynomial ring $K\langle x,y\rangle$ with $\lm_{\sigma}(g_{1})=x^3yx, \lm_{\sigma}(g_{2})=x^2$ and $\lm_{\sigma}(g_{3})=x$. We have ${\rm o}_{1,2}(1,1;x,yx)\in\bigcup_{1\leq i\leq j\leq 2}{\rm NTObs}(i,j)$ and $x\lw_{\sigma}(g_{2})yx=x^3yx=x^3y\lw_{\sigma}(g_{3})$ and $${\rm o}_{1,2}(1,1;x,yx)={\rm o}_{1,3}(1,1;x^3y,1)-{\rm o}_{2,3}(x,yx;x^3y,1).$$ One can check that ${\rm o}_{1,3}(1,1;x^3y,1)$ is a non-trivial obstruction in ${\rm NTObs}(1,3)$ and ${\rm o}_{1,2}(1,1;x,yx)<_{\tau}{\rm o}_{1,3}(1,1;x^3y,1)$. Moreover, ${\rm o}_{2,3}(x,yx;x^3y,1)$ is an obstruction without overlap.

The following is a non-commutative analogue of the Gebauer-Möller criterian $B_k$, which is also known as the *chain criterion* (or *criterion 1*) of Buchberger (cf. [@Bu85]).

\[ncBKCrit\] Suppose that ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})\in\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$ is a non-trivial obstruction. Then in the execution of the Buchberger Procedure ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ can be removed from $\bigcup_{1\leq i\leq j\leq s-1}{\rm NTObs}(i,j)$ if the following three conditions are satisfied.

-   There are two words $w,w'\in\langle X\rangle$ such that $w_{j}\lw_{\sigma}(g_{j})w'_{j}=w\lw_{\sigma}(g_{s})w'$.

-   The obstruction ${\rm o}_{i,s}(w_{i},w'_{i};w,w')$ is either an obstruction without overlap or a multiple of a non-trivial obstruction in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$.

-   The obstruction ${\rm o}_{j,s}(w_{j},w'_{j};w,w')$ is either an obstruction without overlap or a multiple of a non-trivial obstruction in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$.

By Lemma \[sec3lem10\], we can represent ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ as $${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})={\rm o}_{i,s}(w_{i},w'_{i};w,w')-{\rm o}_{j,s}(w_{j},w'_{j};w,w').$$ Moreover, $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ has a Gröbner representations in terms of $G$ if $S_{i,s}(w_{i},w'_{i};w,w')$ and $S_{j,s}(w_{j},w'_{j};w,w')$ have Gröbner representations in terms of $G$. If ${\rm o}_{i,s}(w_{i},w'_{i};w,w')$ is an obstruction without overlap, then, by Lemma \[sec2lem8\], its S-polynomial has a Gröbner representations in terms of $G$. If it is a multiple of a non-trivial obstruction in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$, then Lemma \[sec2lem8\] and Theorem \[sec2the11\] ensure that $S_{i,s}(w_{i},w'_{i};w,w')$ has a Gröbner representations in terms of $G$. By the same argument, one can show that $S_{j,s}(w_{j},w'_{j};w,w')$ has a Gröbner representations in terms of $G$. Now the conclusion follows from Proposition \[sec2pro10\] and Theorem \[sec2the11\].

We would like to mention that the Non-Commutative Backward Criterion given in Proposition \[ncBKCrit\] covers in particular all useless obstructions presented by T. Mora in [@Mo94], Lemma 5.11.

\[sec3rem13\] In order to apply Propositions \[ncMCrit\], \[ncLWCrit\], \[ncTailRed\] and \[ncBKCrit\] to remove unnecessary obstructions during the execution of the Buchberger Procedure, it is crucial to make sure that the S-polynomials of those removed obstructions have Gröbner representations.

-   Propositions \[ncMCrit\], \[ncLWCrit\] and \[ncTailRed\] remove unnecessary non-trivial obstructions, say ${\rm o}_{i,s}(w_{i},w'_{i};w_{s},w'_{s})$, from the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ of newly constructed obstructions. The Gröbner representation of the S-polynomial $S_{i,s}(w_{i},w'_{i};w_{s},w'_{s})$ depends on the Gröbner representations of the S-polynomials of two smaller obstructions in the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm Obs}(i,j)$ and the set $\bigcup_{1\leq i\leq s}{\rm Obs}(i,s)$.

-   Proposition \[ncBKCrit\] removes unnecessary obstructions, say ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$, from the set $\bigcup_{1\leq i\leq j\leq s-1}{\rm Obs}(i,j)$ of previously constructed obstructions. The Gröbner representation of $S_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ depends on the Gröbner representations of the S-polynomials of two obstructions, say ${\rm o}_{k,s}(w_{k},w'_{k};$ $u_{s},u'_{s})$ and ${\rm o}_{l,s}(w_{l},w'_{l};v_{s},v'_{s})$, in $\bigcup_{1\leq i\leq s}{\rm Obs}(i,s)$, which are not necessarily smaller than ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$. If ${\rm o}_{k,s}(w_{k},w'_{k};u_{s},u'_{s})$ is a multiple of a non-trivial obstruction, say ${\rm o}_{k,s}(\tilde{w}_{k},\tilde{w}'_{k};\tilde{u}_{s},\tilde{u}'_{s})$, in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$, then, before removing ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$, it is important to ensure that ${\rm o}_{k,s}(\tilde{w}_{k},\tilde{w}'_{k};\tilde{u}_{s},\tilde{u}'_{s})$ is in $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$. The same check should be applied to ${\rm o}_{l,s}(w_{l},w'_{l};v_{s},v'_{s})$.

Observe that Propositions \[ncMCrit\], \[ncLWCrit\] and \[ncBKCrit\] are actually generalizations of the well-known Gebauer-Möller criteria (see [@CKR04] and [@GM88]) in commutative polynomial rings. More precisely, Propositions \[ncMCrit\], \[ncLWCrit\] and \[ncBKCrit\] correspond to criterion $M$, criterion $F$ and criterion $B_k$, respectively (c.f. [@GM88], Subsection 3.4).

Using the Gebauer-Möller criteria, we can improve the Buchberger Procedure as follows.

\[sec3the14\] In the setting of Theorem \[sec2the11\], we replace step [(B4)]{} by the following sequence of instructions.

-   Increase $s$ by one. Append $g_{s}=S'$ to the set ${G}$, and form the set of non-trivial obstructions ${\rm NTObs}(s)=\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$.

-   Remove from ${\rm NTObs}(s)$ all obstructions ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ such that there exists an obstruction ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})\in{\rm NTObs}(s)$ with the properties that there exist two words $w,w'\in\langle X\rangle$ satisfying $u_{s}=wv_{s}$, $u'_{s}=v'_{s}w'$ and $ww'\neq1$.

-   Remove from ${\rm NTObs}(s)$ all obstructions ${\rm o}_{i,s}(w_{i},w'_{i};u_{s},u'_{s})$ such that there exists an obstruction ${\rm o}_{j,s}(w_{j},w'_{j};v_{s},v'_{s})\in{\rm NTObs}(s)$ with the properties that there exist two words $w,w'\in\langle X\rangle$ satisfying $u_{s}=wv_{s}$, $u'_{s}=v'_{s}w'$, and such that $i>j$, or $i=j$ and $ww'=1$ and $w_{i}>_{\sigma}w_{j}$.

-   Remove from ${\rm NTObs}(s)$ all obstructions ${\rm o}_{j,s}(u_{j},u'_{j};w_{s},w'_{s})$ such that there exists an obstruction ${\rm o}_{i,j}(w_{i},w'_{i};v_{j},v'_{j})\in B$ with the properties that there exist two words $w,w'\in\langle X\rangle$ satisfying $u_{j}=wv_{j}, u'_{j}=v'_{j}w'$, and such that ${\rm o}_{i,s}(ww_{i},w'_{i}w';w_{s},w'_{s})$ has no overlap.

-   Remove from $B$ all obstructions ${\rm o}_{i,j}(w_{i},w'_{i};w_{j},w'_{j})$ such that there exist two words $w,w'\in\langle X\rangle$ satisfying $w\lw_{\sigma}(g_{s})w'=w_{j}\lw_{\sigma}(g_{j})w'_{j}$, and such that the following conditions are satisfied.

    -   ${\rm o}_{i,s}(w_{i},w'_{i};w,w')$ is either an obstruction without overlap or a multiple of a non-trivial obstruction in ${\rm NTObs}(s)$.

    -   ${\rm o}_{j,s}(w_{j},w'_{j};w,w')$ is either an obstruction without overlap or a multiple of a non-trivial obstruction in ${\rm NTObs}(s)$.

-   Replace $B$ by $B\cup {\rm NTObs}(s)$ and continue with step [(B2)]{}.

Then the resulting set of instructions is a procedure that enumerates a ${\sigma}$-Gröbner basis ${G}$ of $I$. If $I$ has a finite ${\sigma}$-Gröber basis, it stops after finitely many steps and the resulting set ${G}$ is a finite ${\sigma}$-Gröbner basis of $I$.

This follows from Theorem \[sec2the11\] and Propositions \[ncMCrit\], \[ncLWCrit\], \[ncTailRed\] and \[ncBKCrit\].

Experiments and Conclusions {#sec4}
===========================

In this section we want to present some experimental data which illustrate the performance of the Gebauer-Möller criteria presented in Propositions \[ncMCrit\], \[ncTailRed\] and \[ncBKCrit\]. The computations are based on an implementation (using C++) in an experimental version of the ApCoCoA library (see [@Ap10]) by the second author.

\[sec4exa1\] Consider the non-commutative polynomial ring $\mathbb{Q}\langle a,b\rangle$ equipped with the word ordering $\LLex$ on $\langle a,b\rangle$ such that $a>_{\LLex}b$. We take the list of *finite generalized triangle groups* from [@RS02], Theorem 2.12 and construct a list of ideals in $\mathbb{Q}\langle a,b\rangle$. For $k=1,\dots,13$ let $I_{k}=\langle G_{k}\rangle\subseteq\mathbb{Q}\langle a,b\rangle$ be the ideal generated by the following set of polynomials $G_{k}\subseteq\mathbb{Q}\langle a,b\rangle$. $$\begin{aligned}
G_{1}&=&\{a^2-1,b^3-1,(ababab^2ab^2)^2-1\},\\
G_{2}&=&\{a^2-1,b^3-1,(ababab^2)^3-1\},\\
G_{3}&=&\{a^3-1,b^3-1,(abab^2)^2-1\},\\ 
G_{4}&=&\{a^3-1,b^3-1,(aba^2b^2)^2-1\},\\
G_{5}&=&\{a^2-1,b^5-1,(abab^2)^2-1\},\\
G_{6}&=&\{a^2-1,b^5-1,(ababab^4)^2-1\}, \\
G_{7}&=&\{a^2-1,b^5-1,(abab^2ab^4)^2-1\},\\
G_{8}&=&\{a^2-1,b^4-1,(ababab^3)^2-1\},\\
G_{9}&=&\{a^2-1,b^3-1,(abab^2)^2-1\}, \\
G_{10}&=&\{a^2-1,b^3-1,(ababab^2)^2-1\},\\
G_{11}&=&\{a^2-1,b^3-1,(abababab^2)^2-1\},\\
G_{12}&=&\{a^2-1,b^3-1,(ababab^2abab^2)^2-1\},\\
G_{13}&=&\{a^2-1,b^3-1,(ababababab^2ab^2)^2-1\}.\end{aligned}$$ The following table lists some numbers of polynomials and obstructions treated by the Improved Buchberger Procedure given in Theorem \[sec3the14\].

    $k$  $\#(Gb)$   $\!\!\#(RGb)\!\!$   $\#(Tot)$   $\#(Sel)$   $\#(M)$   $\#(F)$   $\#(B_k)$   $\rho$  
  ----- ---------- ------------------- ----------- ----------- --------- --------- ----------- -------- --
      1     62             35             7032         248       6512       48         224      0.0353  
      2    133             96             31700        533       30571      70         526      0.0168  
      3     50             40             2828         197       2489       11         131      0.0697  
      4     64             28             4702         253       4185       46         218      0.0538  
      5     35             21             1580         115       1348       24         93       0.0728  
      6    199             164            51175        882       49126      26        1141      0.0172  
      7    200             164            51864        886       49818      17        1143      0.0170  
      8     53             37             3756         192       3357       19         188      0.0511  
      9     11              5              150         31         98         8         13       0.2067  
     10     22             15              741         74         605       18         44       0.0999  
     11     30             21             1573         116       1324       50         83       0.0737  
     12     97             70             16841        365       15989      97         390      0.0217  
     13    220             194            87673       1021       85136      153       1363      0.0116  

Here we used the following abbreviations.

-   $\#(Gb)$ is the number of elements of the Gröbner basis returned by the procedure.

-   $\#(RGb)$ is the cardinality of the reduced Gröbner basis of the corresponding ideal.

-   $\#(Tot)$ is the total number of non-trivial obstructions constructed during the Buchberger Procedure.

-   $\#(Sel)$ is the number of actually selected and analysed non-trivial obstructions.

-   $\#(M)$ is the number of unnecessary non-trivial obstructions detected by the Non-Commutative Multiply Criterion given in Proposition \[ncMCrit\].

-   $\#(F)$ is the number of unnecessary non-trivial obstructions detected by the Non-Commutative Leading Word Criterion given in Proposition \[ncLWCrit\].

-   $\#(B_k)$ is the number of unnecessary non-trivial obstructions detected by the Non-Commutative Backward Criterion given in Proposition \[ncBKCrit\].

-   $\rho=\#(Sel)/\#(Tot)$.

Note that $\#(RGb)$ is an invariant of the ideal which only depends on chosen word ordering. Other numbers in the table rely also on the selection strategy. In our experiments we used the *normal strategy* which first chooses the obstruction whose S-polynomial has the lowest degree and then breaks ties by choosing the obstruction whose S-polynomial has the smallest leading word with respect to the word ordering. In these experiments, the Non-Commutative Tail Reduction given in Proposition \[ncTailRed\] detected no of unnecessary non-trivial obstruction (see Remark \[sec3rem9\]). Apparently, the Non-Commutative Multiply Criterion and the Non-Commutative Leading Word Criterion had already detected all unnecessary obstructions in the set $\bigcup_{1\leq i\leq s}{\rm NTObs}(i,s)$ of newly constructed obstructions. The low ratios $\rho$ in the table indicate that the non-commutative Gebauer-Möller criteria we obtained can detect most unnecessary obstructions during the procedure.

\[sec4exa2\] The following ideals [braid3]{} and [braid4]{} in the non-commutative polynomial ring $\mathbb{Q}\langle x_{1},x_{2},x_{3}\rangle$ are taken from [@SL09], Section 5. More precisely, [braid3]{} is the ideal generated by the set $\{-x_{2}x_{3}x_{1}+x_{3}x_{1}x_{3},$ $x_{2}x_{1}x_{2}-x_{3}x_{2}x_{3}$, $x_{1}x_{2}x_{1}-x_{3}x_{1}x_{2}, x_{1}^3+x_{1}x_{2}x_{3}+x_{2}^3+x_{3}^3\}$, and [braid4]{} is the ideal generated by the set $\{-x_{2}x_{3}x_{1}+x_{3}x_{1}x_{3}, x_{2}x_{1}x_{2}-x_{3}x_{2}x_{3}, x_{1}x_{2}x_{3}-x_{3}x_{1}x_{2}, x_{1}^3+x_{1}x_{2}x_{3}+x_{2}^3+x_{3}^3\}$. These ideals are generated by sets of homogeneous generators. The following table lists the results of the computations of Gröbner bases truncated at degree $11$ with respect to $\LLex$ on $\langle x_{1},x_{2},x_{3}\rangle$ such that $x_{1}>_{\LLex} x_{2}>_{\LLex}x_{3}$, via the Improved Buchberger Procedure.

               $\#(Gb)$   $\#(Tot)$   $\#(Sel)$   $\rho$
  ----------- ---------- ----------- ----------- --------
  braid3-11      726       289642       1663      0.0057
  braid4-11      416        93252       1150      0.0123

The meaning of the symbols is the same as in Example \[sec4exa1\]. In this experiment we also used the normal strategy. Moreover, since we compute truncated Gröbner bases, we discard those obstructions whose S-polynomial have degrees larger than the degree of truncation. Thus the ratios $\rho$ in the table are lower than the ratios in the table of Example \[sec4exa1\]. Again, the non-commutative Gebauer-Möller criteria detect most unnecessary obstructions during the procedure.

The experimental data in Examples \[sec4exa1\] and \[sec4exa2\] show that the generalizations of the Gebauer-Möller criteria presented in Propositions \[ncMCrit\], \[ncLWCrit\] and \[ncBKCrit\] can successfully detect a large number of unnecessary obstructions. In fact, they apparently detect almost all unnecessary obstructions during the Buchberger Procedure.

Acknowledgements {#acknowledgements .unnumbered}
----------------

The second author is grateful to the Chinese Scholarship Council (CSC) for providing partial financial support. Both authors thank G. Studzinski for valuable discussions about non-commutative Gröbner bases. And both authors appreciate anonymous referees for careful reading and useful suggestions.

[00]{}

ApCoCoA team, ApCoCoA: Applied Computations in Commutative Algebra, available at http://www.apcocoa.org.

G.H. Bergman, The diamond lemma for ring theory, Adv. Math. 29 (1978), 178-218.

B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal, Dissertation, Universität Inssbruck, Austria, 1965.

B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, in: Proceedings of the International Symposiumon on Symbolic and Algebraic Computation (EUROSAM ’79), Edward W. Ng (Ed.), Springer-Verlag, London, UK, 3-21, 1979.

B. Buchberger, Gröbner bases: an algorithmic method in polynomial ideal theory, in: Multidimensional Systems Theory-Progress, Directions and Open Problems in Multidimensional Systems, N.K. Bose (Ed.), Reidel Publishing Company, Dodrecht-Boston-Lancaster, 184-232, 1985.

M. Caboara, M. Kreuzer and L. Robbiano, Efficiently computing minimal sets of critical pairs, Journal of Symbolic Computation 38 (2004), 1169-1190.

A.M. Cohen, Non-commutative polynomial computations, 2007, available at www.win.tue.nl/$\sim$amc/pub/gbnpaangepast.pdf.

R. Gebauer and H.M. Möller, On an installation of Buchberger’s algorithm, Journal Symbolic Computation 6 (1988), 275-286.

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer, Heidelberg, 2000.

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer, Heidelberg, 2005.

H.M. Möller, A reduction strategy for the Taylor resolution, Proc. EUROCAL 85, Springer L.N. in Comp. Sci. 162, 526-534.

T. Mora, Gröbner bases for non-commutative polynomial rings, in: Proceedings of the 3rd International Conference on Algebraic Algorithms and Error-Correcting Codes (AAECC-3), Jacques Calmet (Ed.), Springer-Verlag, London, UK, 1986, 353-362.

T. Mora, An introduction to commutative and non-commutative Gröbner Bases, Journal of Theoretical Computer Science 134 (1994), 131-173.

G. Rosenberger and M. Scheer, Classification of the finite generalized tetrahedron groups, Contemporary Mathematics 296 (2002), 207- 229.

R. Scala and V. Levandovskyy, Letterplace ideals and non-commutative Gröbner bases, Journal of Symbolic Computation 44 (2004), 1374-1393.

X. Xiu, Non-Commutative Gröbner Bases and Applications, Dissertation, Universität Passau, Germany, 2012.

[^1]: [martin.kreuzer@uni-passau.de]{} (Corresponding author)

[^2]: [xingqiang.xiu@uni-passau.de]{}
