# Difference between revisions of "ApCoCoA-1:NC.SetOrdering"

Line 3: | Line 3: | ||

<short_description> | <short_description> | ||

Set a word ordering on the monoid of all words in a non-commutative polynomial ring. | Set a word ordering on the monoid of all words in a non-commutative polynomial ring. | ||

− | < | + | </short_description> |

+ | <syntax> | ||

+ | NC.SetOrdering(Ordering:STRING) | ||

+ | </syntax> | ||

+ | <description> | ||

Note that a <em>word ordering</em> is a well-ordering which is compatible with multiplication. The default ordering is LLEX (the length-lexicographic ordering). | Note that a <em>word ordering</em> is a well-ordering which is compatible with multiplication. The default ordering is LLEX (the length-lexicographic ordering). | ||

Line 15: | Line 19: | ||

</itemize> | </itemize> | ||

A word ordering on is said to be <em>length compatible</em> if <tt>len(W)>len(W')</tt> implies <tt>W</tt> is larger than <tt>W'</tt> for all <tt>W, W'</tt> in <tt>W^n</tt>. For instance, LLEX and LRLEX are length compatible while ELIM is not. | A word ordering on is said to be <em>length compatible</em> if <tt>len(W)>len(W')</tt> implies <tt>W</tt> is larger than <tt>W'</tt> for all <tt>W, W'</tt> in <tt>W^n</tt>. For instance, LLEX and LRLEX are length compatible while ELIM is not. | ||

− | </ | + | <par/> |

− | |||

− | |||

− | |||

− | |||

Note that each word ordering is induced by the order of indeterminates (see <ref>Use</ref>). For instance, assume that we are working in the ring QQ[x[1..2],y[1..2],z]. Then word ordering are induced by x[1]>x[2]>y[1]>y[1]>z. | Note that each word ordering is induced by the order of indeterminates (see <ref>Use</ref>). For instance, assume that we are working in the ring QQ[x[1..2],y[1..2],z]. Then word ordering are induced by x[1]>x[2]>y[1]>y[1]>z. | ||

<itemize> | <itemize> |

## Revision as of 19:40, 14 May 2013

## NC.SetOrdering

Set a word ordering on the monoid of all words in a non-commutative polynomial ring.

### Syntax

NC.SetOrdering(Ordering:STRING)

### Description

Note that a *word ordering* is a well-ordering which is compatible with multiplication. The default ordering is LLEX (the length-lexicographic ordering).

In the following, we let `W^n` be the monoid of all words generated by `{x[1],x[2],...,x[n]}`. We define the `non-commutative left-to-right lexicographic ordering` LEX on `W^n` as follows. For two words `W, W'` in `W^n`, we say `W>_{Lex}W'` if we have `W=W'W_{1}` for some non-empty word `W_{1}` in `W^n`, or if we have `W=W_{1}x[i]W_{2}, W'=W_{1}x[j]W_{3}` for some words `W_{1},W_{2},W_{3}` in `W^n` and `i<j`. Thus, we have `x[1]>_{LEX}x[2]>_{LEX}...>_{LEX}x[n]`. Note that LEX is not a word ordering on `W^n`. Given two words `W, W'` in `W^n`, we define word orderings LLEX, ELIM, LRLEX, and DEGREVLEX on `W^n` as follows.

LLEX: we say

`W>_{LLEX}W'`if`len(W)>len(W')`, or`len(W)=len(W')`and`W`is lexicographically larger than`W'`.ELIM: it first compares the associated commutative terms lexicographically and then breaks ties using the non-commutative lexicographic ordering with respect to

`x[1]>_{LEX}...>_{LEX}x[n]`. That is, we say`W>_{ELIM}W'`if`W`is lexicographically larger than`W'`by considering them as two terms in the commutative case, or`W=W'`as two commutative terms and`W>_{Lex}W'`(`W`is lexicographically larger than`W'`by considering them as two words in the non-commutative case). Thus, the elimination ordering ELIM first eliminates the indeterminate`x[1]`, and then`x[2]`, and then`x[3]`, and so on and so forth.LRLEX: we say

`W>_{LRLEX}W'`if`len(W)>len(W')`, or`len(W)=len(W')`and`W`is larger than`W'`by the non-commutative right-to-left lexicographic ordering.

A word ordering on is said to be *length compatible* if `len(W)>len(W')` implies `W` is larger than `W'` for all `W, W'` in `W^n`. For instance, LLEX and LRLEX are length compatible while ELIM is not.

Note that each word ordering is induced by the order of indeterminates (see Use). For instance, assume that we are working in the ring QQ[x[1..2],y[1..2],z]. Then word ordering are induced by x[1]>x[2]>y[1]>y[1]>z.

@param

*Ordering*: a STRING, which indicates a word ordering. For the time being, the package supports "LLEX" (the length-lexicographic ordering), "ELIM" (an elimination ordering),"LRLEX" (the length-reverse-lexicographic ordering), and "DEGREVLEX" (the degree-reverse-lexicographic ordering).

#### Example

NC.RingEnv(); Coefficient field : CoCoA::QQ Indeterminates : [<quotes>x[1]</quotes>, <quotes>y[1]</quotes>, <quotes>z[1]</quotes>] Word ordering : LLEX ------------------------------- NC.SetOrdering(<quotes>ELIM</quotes>); NC.RingEnv(); Coefficient field : CoCoA::QQ Indeterminates : [<quotes>x[1]</quotes>, <quotes>y[1]</quotes>, <quotes>z[1]</quotes>] Word ordering : ELIM -------------------------------

### See also