is used to determine in an algebra, if a set of monomials form a \(k\)-basis.
It is an extension of Grobner basis to non-commutative rings, with the possibility that it might not terminate.
Words
\(X\) be a set of variables, a word is a finite sequence of elements of \(X\).
Monomial Ordering
We want to have a total ordering on the set of words that is multiplicative, i.e.
\[ u < v \Rightarrow ouo' < ovo' \]
For example under the degree-lexicographic ordering, assuming \(x<y\) we have
\[ 1 < x < y < x^2 < xy < yx < y^2 < x^3 < x^2y < \cdots \]
The largest term of an element in \(k\langle X \rangle\) is called the leading term.
Reduced Word
Given a set of relations \(g_1, \ldots, g_n\), a word \(w\) is reduced if it is not a subword of the leading terms of any of the \(g_i\).
Reductions are performed for each relation \(g_i\), we can reduce any word that contains the leading term of \(g_i=w_i - f_i\) by replacing \(w_i\) with \(f_i\) (which is a linear combination of words strictly smaller than \(w_i\)).
Using this process, you can reduce any word to a reduced element.
An element \(h\in k\langle X\rangle\) is called reduction-unique if for any compositions of reductions, it always reduces to the same reduced element.
If \(w_i\) and \(w_j\) share a common part, so that \(w_i = ac\) and \(w_j = cb\), then we say \(w_i\) and \(w_j\) have an overlap ambiguity.
It is resolvable if the two ambiguous reductions of \(acb\) can be reduced to the same element under further reductions.
If \(w_i\) is contained in \(w_j\), \(w_j=aw_ib\), we say they have an inclusion ambiguity.
Again it is resolvable if \(aw_ib\) can be reduced to the same element under further reductions.
Let \(g_i\) be some relations generating an ideal \(I\subset k\langle X\rangle\), where \(g_i = w_i - f_i\). Then the following are equivalent:
The set of reduced words form a \(k\)-basis of \(k\langle X\rangle/I\).
Every element of \(k\langle X\rangle\) is reduction-unique.
All two types of ambiguous reductions are resolvable.
If \(w_i\) and \(w_j\) have ambiguity, they get reduced to elements \(c_i\) and \(c_j\), you can add a new relation \(c_i-c_j\) to the set of relations, and repeat the process.
Warning: This process might not terminate, and can be choice dependent.