Noncommutative Gröbner basis

Summary

A noncommutative Gröbner basis, or Gröbner–Shirshov basis, generates a two-sided ideal of a free algebra $k\langle X \rangle$. Its leading words control the leading words of all elements of the ideal. It extends the commutative Gröbner basis from polynomial rings to free algebras, with words in place of monomials. The words that avoid all leading words give a linear basis of the quotient algebra. So a Gröbner basis solves the normal form problem for an algebra given by generators and relations. Unlike the commutative case, a finitely generated ideal may have no finite Gröbner basis, and the completion procedure need not terminate.