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

Line 8: | Line 8: | ||

</syntax> | </syntax> | ||

<description> | <description> | ||

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

<itemize> | <itemize> | ||

− | <item>@param <em>Ordering</em>: a string which indicates | + | <item>@param <em>Ordering</em>: a string which indicates a word ordering. For the time being, the package supports <quotes>LLEX</quotes> (the length-lexicographic ordering), <quotes>ELIM</quotes> (an elimination ordering),<quotes>LRLEX</quotes> (the length-reverse-lexicographic ordering), and <quotes>DEGREVLEX</quotes> (the degree-reverse-lexicographic ordering).</item> |

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

− | + | <par/> | |

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

<itemize> | <itemize> | ||

− | <item><quotes>LLEX</quotes>: | + | <item><quotes>LLEX</quotes>: we say <tt>W>_{LLEX}W'</tt> if <tt>len(W)>len(W')</tt>, or <tt>len(W)=len(W')</tt> and <tt>W</tt> is lexicographically larger than <tt>W'</tt>.</item> |

− | <item><quotes>ELIM</quotes>: it first compares the associated commutative terms lexicographically and then breaks ties using the non-commutative lexicographic | + | |

− | <item><quotes>LRLEX</quotes>: | + | <item><quotes>ELIM</quotes>: it first compares the associated commutative terms lexicographically and then breaks ties using the non-commutative lexicographic ordering with respect to <tt>x[1]>_{LEX}...>_{LEX}x[n]</tt>. That is, we say <tt>W>_{ELIM}W'</tt> if <tt>W</tt> is lexicographically larger than <tt>W'</tt> by considering them as two terms in the commutative case, or <tt>W=W'</tt> as two commutative terms and <tt>W>_{Lex}W'</tt> (<tt>W</tt> is lexicographically larger than <tt>W'</tt> by considering them as two words in the non-commutative case). Thus, the elimination ordering <quotes>ELIM</quotes> first eliminates the indeterminate <tt>x[1]</tt>, and then <tt>x[2]</tt>, and then <tt>x[3]</tt>, and so on and so forth.</item> |

+ | |||

+ | <item><quotes>LRLEX</quotes>: we say <tt>W>_{LRLEX}W'</tt> if <tt>len(W)>len(W')</tt>, or <tt>len(W)=len(W')</tt> and <tt>W</tt> is larger than <tt>W'</tt> by the right-to-left lexicographic ordering.</item> | ||

</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>Wn</tt>. For instance, <quotes>LLEX</quotes> and <quotes>LRLEX</quotes> are length compatible while <quotes>ELIM</quotes> is not. | |

<example> | <example> | ||

NC.RingEnv(); | NC.RingEnv(); |

## Revision as of 19:02, 25 April 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).

@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).

In the following, we let `Wn` be the monoid of all words generated by `{x[1],x[2],...,x[n]}`. We define the (left-to-right) lexicographic ordering "LEX" on `Wn` as follows. For two words `W, W'` in `Wn`, we say `W>_{Lex}W'` if we have `W=W'W_{1}` for some non-empty word `W_{1}` in `Wn`, 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 `Wn` and `i<j`. Thus, we have `x[1]>_{LEX}x[2]>_{LEX}...>_{LEX}x[n]`. Note that "LEX" is not a word ordering on `Wn`. Given two words `W, W'` in `Wn`, we define word orderings "LLEX", "ELIM", "LRLEX", and "DEGREVLEX" on `Wn` 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 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 `Wn`. For instance, "LLEX" and "LRLEX" are length compatible while "ELIM" is not.

#### Example

NC.RingEnv(); Coefficient ring : Q Ordering : LLEX ------------------------------- NC.SetOrdering(<quotes>ELIM</quotes>); NC.RingEnv(); Coefficient ring : Q Ordering : ELIM -------------------------------