Top
Back: Free associative algebras
Forward: Groebner bases for two-sided ideals in free associative algebras
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

7.9.2 Monomial orderings on free algebras

We provide many types of orderings for non-commutative Groebner bases up to a degree (length) bound. In general it is not clear, whether a given generating set has a finite Groebner bases with respect to some 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 well-ordering, i.e., every non empty subset has a least element with respect to <, and
  • it is compatible with 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 after, say, comparing elements by the total degree.

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 by for .

For any ordering << on and any weight define an ordering , called the -weight extension of as follows: For arbitrary , in we say that if

  • or
  • and holds.
An ordering < on eliminates a certain subset

In a ring declaration, 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 length-weight 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 length-weight 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'

The monomial ordering `lp' corresponds to and eliminates { ,..., } for all <= < . We refer to it as to left elimination ordering.

With respect to the ordering `lp', the test monomials are ordered as follows:

`rp'

The monomial ordering `rp' corresponds to and eliminates { ,..., } for all . We refer to it as to right elimination ordering.

With respect to the ordering `rp', the test monomials are ordered as follows:

`(a(v), ordering) for intvec v'

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
ring R = freeAlgebra(r, 4);
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; // polynomial will be automatically ordered according to the ordering on R
==> x1*x1*x1+x1*x2*x3+x3*x2*x1+x3*x3*x3+x1*x3+x2*x2+x2*x3+x3*x1+x1+x2+x3


Top Back: Free associative algebras Forward: Groebner bases for two-sided ideals in free associative algebras FastBack: FastForward: Up: Singular Manual Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 4.3.1, 2022, generated by texi2html.