
7.9.2 Monomial orderings on free algebras
Monomial orderings are of critical importance when dealing with Groebner bases.
Especially in the noncommutative Groebner theory up to a degree (length) bound it might be vital
to have many choices for orderings since it is not guaranteed that there exists a finite Groebner
bases with respect to the given ordering.
Let
= {
,...,
} be a set of symbols. A total ordering < on the free monoid
with
as the neutral element is called a monomial ordering if
 it is a wellordering, i.e., every non empty subset has a least element with respect to <, and
 it respects multiplication, that is
implies
for all
,
,
and
in
.
Note that the latter implies
for all
in
.
The left lexicographical ordering on
with
...
is defined as follows:
For arbitrary
,
in
we say that
, if
Note: left lex is not a monomial ordering, though it is a natural choice to break ties in further definitions.
In a similar manner one can define the right lexicographical ordering.
On the monoid
define the weight homomorphism
, uniquely determined by
in
for
. As a special case, define the length
len:
by
for
. For any ordering << on
and any weight
define an ordering <, the
weight extension of << as follows: For arbitrary
,
in
we say that
if
An ordering < on
eliminates a certain subset
if for all
one has
.
In a ring declaration, LETTERPLACE supports the following monomial orderings.
We illustrate each of the available choices by an example on the free monoid
,
,
,
where we order the monomials
,
,
,
,
,
,
,
,
,
and
correspondingly.
 `
dp '
 The degree right lexicographical ordering is the lengthweight extension of the right lexicographical ordering.
With respect to the ordering `dp', the test monomials are ordered as follows:
 `
Dp '
 The degree left lexicographical ordering is the lengthweight extension of the left lexicographical ordering.
With respect to the ordering `Dp', the test monomials are ordered as follows:
 `
Wp(w) for intvec w'
 The weighted degree left lexicographical ordering is the
weight extension of the left lexicographical ordering with weight
uniquely determined by strict positive
.
With respect to the ordering `Wp(1, 2, 1)', the test monomials are ordered as follows:
 `
lp '
 Let be weights uniquely determined by
for
where denotes the Kronecker delta. Let be the weight extension of the left lexicographical ordering on
and inductively be the weight extension of for all .
The monomial ordering lp corresponds to and eliminates for all .
The monomial ordering `lp' corresponds to
and eliminates {
,...,
} for all
<=
<
.
With respect to the ordering `lp', the test monomials are ordered as follows:
 `
rp '
 Let be weights uniquely determined by
for
where denotes the Kronecker delta. Let be the weight extension of the left lexicographical ordering on
and inductively be the weight extension of for all .
The monomial ordering rp corresponds to and eliminates
for all .
The monomial ordering `rp' corresponds to
and eliminates {
,...,
} for all
.
With respect to the ordering `rp', the test monomials are ordered as follows:
 `
(a(v), ordering) for intvec v'
 For weight
determined by
with and monomial ordering on
, the weight extension of corresponds to (a(v), o). As a choice for there are currently two options implemented, which are dp and Dp. Notice that this ordering eliminates
.
With respect to the ordering `( a(1, 0, 0), Dp)', the test monomials are ordered as follows:
With ordering `( a(1, 1, 0), Dp)' one obtains:
The examples are generated by the following code but with customized orderings denoted above.
 LIB "freegb.lib";
ring r = 0, (x1,x2,x3),Dp; // variate ordering here
def R = freeAlgebra(r, 4);
setring R;
poly wr = x1*x1*x1+x3*x3*x3+x1*x2*x3+x3*x2*x1+x2*x2+x2*x3+x1*x3+x3*x1+x1+x2+x3;
wr;
==> x1*x1*x1+x1*x2*x3+x3*x2*x1+x3*x3*x3+x1*x3+x2*x2+x2*x3+x3*x1+x1+x2+x3

