Difference between revisions of "ApCoCoA-1:NCo.SetOrdering"

From ApCoCoAWiki
Line 2: Line 2:
 
<title>NCo.SetOrdering</title>
 
<title>NCo.SetOrdering</title>
 
<short_description>
 
<short_description>
Set an admissible ordering on <tt>&lt;X&gt;</tt>.
+
Set a word ordering on <tt>&lt;X&gt;</tt>.
 +
<par/>
 +
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).
 +
 
 +
Let <tt>X={x_{1}x_{2}...x_{n}}</tt>. We define the non-commutative (left-to-right) lexicographic ordering <quotes>LEX</quotes> on <tt>&lt;X&gt;</tt> as follows. For two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{Lex}W2</tt> if we have <tt>W1=W2*W</tt> for some non-empty word <tt>W</tt> in <tt>&lt;X&gt;</tt>, or if we have <tt>W1=W*x_{i}*W3, W2=W*x_{j}*W4</tt> for some words <tt>W,W3,W4</tt> in <tt>&lt;X&gt;</tt> and some letters <tt>x_{i},x_{j}</tt> in <tt>X</tt> such that <tt>i&lt;j</tt>. Thus, we have <tt>x_{1}&gt;_{LEX}x_{2}&gt;_{LEX}...&gt;_{LEX}x_{n}</tt>. Note that <quotes>LEX</quotes>  is not a word ordering on <tt>&lt;X&gt;</tt>. We define word orderings <quotes>LLEX</quotes>, <quotes>ELIM</quotes> and <quotes>LRLEX</quotes> on <tt>&lt;X&gt;</tt> as follows.
 +
<itemize>
 +
<item><quotes>LLEX</quotes>: for two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{LLEX}W2</tt> if <tt>len(W1)&gt;len(W2)</tt>, or <tt>len(W1)=len(W2)</tt> and <tt>W1</tt> is lexicographically larger than <tt>W2</tt>.</item>
 +
 
 +
<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}&gt;_{LEX}...&gt;_{LEX}x_{n}</tt>. That is, for two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{ELIM}W2</tt> if <tt>W1</tt> is lexicographically larger than <tt>W2</tt> by considering them as two terms in the commutative case, or <tt>W1=W2</tt> by considering them as two terms in the commutative case and <tt>W1&gt;_{Lex}W2</tt> where <quotes>LEX</quotes> is the non-commutative left-to-right lexicographic ordering. Thus, the elimination ordering <quotes>ELIM</quotes> first eliminates the letter <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&gt;_{LRLEX}W'</tt> if <tt>len(W)&gt;len(W')</tt>, or <tt>len(W)=len(W')</tt> and <tt>W</tt> is larger than <tt>W'</tt> by the non-commutative right-to-left lexicographic ordering.</item>
 +
</itemize>
 +
A word ordering on is said to be <em>length compatible</em> if <tt>len(W1)>len(W2)</tt> implies <tt>W1</tt> is larger than <tt>W2</tt> for all <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>. For instance, <quotes>LLEX</quotes> and <quotes>LRLEX</quotes> are length compatible while <quotes>ELIM</quotes> is not.
 
</short_description>
 
</short_description>
 
<syntax>
 
<syntax>
Line 8: Line 20:
 
</syntax>
 
</syntax>
 
<description>
 
<description>
Note that the default ordering is <quotes>LLEX</quotes> (length-lexicographic ordering).
+
Note that each word ordering is induced by the order of letters in X (see <ref>NCo.SetX</ref>). For instance, assume that X="abcdef". Then the word ordering is induced by a&gt;b&gt;b&gt;d&gt;e&gt;f.
<itemize>
 
<item>@param <em>Ordering</em>: a string which indicates an (admissible) ordering. For the time being, the package supports <quotes>LLEX</quotes> (the length-lexicographic ordering), <quotes>ELIM</quotes> (an elimination ordering) and <quotes>LRLEX</quotes> (the length-reverse-lexicographic ordering).</item>
 
</itemize>
 
Let <tt>X=x_{1}x_{2}...x_{n}</tt>. We define the (left-to-right) lexicographic ordering <quotes>LEX</quotes> on <tt>&lt;X&gt;</tt> as follows. For two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{Lex}W2</tt> if we have <tt>W1=W2*W</tt> for some non-empty word <tt>W</tt> in <tt>&lt;X&gt;</tt>, or if we have <tt>W1=W*x_{i}*W3, W2=W*x_{j}*W4</tt> for some words <tt>W,W3,W4</tt> in <tt>&lt;X&gt;</tt> and some letters <tt>x_{i},x_{j}</tt> in <tt>X</tt> such that <tt>i&lt;j</tt>. Thus, we have <tt>x_{1}&gt;_{LEX}x_{2}&gt;_{LEX}...&gt;_{LEX}x_{n}</tt>. Note that <quotes>LEX</quotes>  is not an admissible ordering on <tt>&lt;X&gt;</tt>. We define admissible orderings <quotes>LLEX</quotes>, <quotes>ELIM</quotes> and <quotes>LRLEX</quotes> on <tt>&lt;X&gt;</tt> as follows.
 
<itemize>
 
<item><quotes>LLEX</quotes>: for two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{LLEX}W2</tt> if <tt>len(W1)&gt;len(W2)</tt>, or <tt>len(W1)=len(W2)</tt> and <tt>W1</tt> is lexicographically larger than <tt>W2</tt>.</item>
 
<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}&gt;...&gt;x_{n}</tt>. That is, for two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{ELIM}W2</tt> if <tt>W1</tt> is lexicographically larger than <tt>W2</tt> by considering <tt>W1, W2</tt> as two terms in the commutative case, or <tt>W1=W2</tt> by considering <tt>W1, W2</tt> as two terms in the commutative case and <tt>W1&gt;_{Lex}W2</tt> (<tt>W1</tt> is left-to-right lexicographically larger than <tt>W2</tt> by considering <tt>W1, W2</tt> as two words in the non-commutative case). Thus, the elimination ordering <quotes>ELIM</quotes> first eliminates the letter <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>: for two words <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>, we say <tt>W1&gt;_{LRLEX}W2</tt> if <tt>len(W1)&gt;len(W2)</tt>, or <tt>len(W1)=len(W2)</tt> and <tt>W1</tt> is larger than <tt>W2</tt> by right-to-left lexicographic ordering.</item>
 
</itemize>
 
An admissible ordering on is called <em>length compatible</em> if <tt>len(W1)>len(W2)</tt> implies <tt>W1</tt> is larger than <tt>W2</tt> for all <tt>W1, W2</tt> in <tt>&lt;X&gt;</tt>. For instance, <quotes>LLEX</quotes> and <quotes>LRLEX</quotes> are length compatible while <quotes>ELIM</quotes> is not.
 
 
<example>
 
<example>
 
NCo.RingEnv();
 
NCo.RingEnv();
Line 32: Line 34:
 
</description>
 
</description>
 
<seealso>
 
<seealso>
<see>NCo.UnsetOrdering</see>
+
<see>NCo.SetFp</see>
<see>Introduction to CoCoAServer</see>
+
<see>NCo.SetX</see>
 
</seealso>
 
</seealso>
 
<types>
 
<types>

Revision as of 14:54, 30 April 2013

NCo.SetOrdering

Set a word ordering on <X>.

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

Let X={x_{1}x_{2}...x_{n}}. We define the non-commutative (left-to-right) lexicographic ordering "LEX" on <X> as follows. For two words W1, W2 in <X>, we say W1>_{Lex}W2 if we have W1=W2*W for some non-empty word W in <X>, or if we have W1=W*x_{i}*W3, W2=W*x_{j}*W4 for some words W,W3,W4 in <X> and some letters x_{i},x_{j} in X such that i<j. Thus, we have x_{1}>_{LEX}x_{2}>_{LEX}...>_{LEX}x_{n}. Note that "LEX" is not a word ordering on <X>. We define word orderings "LLEX", "ELIM" and "LRLEX" on <X> as follows.

  • "LLEX": for two words W1, W2 in <X>, we say W1>_{LLEX}W2 if len(W1)>len(W2), or len(W1)=len(W2) and W1 is lexicographically larger than W2.

  • "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, for two words W1, W2 in <X>, we say W1>_{ELIM}W2 if W1 is lexicographically larger than W2 by considering them as two terms in the commutative case, or W1=W2 by considering them as two terms in the commutative case and W1>_{Lex}W2 where "LEX" is the non-commutative left-to-right lexicographic ordering. Thus, the elimination ordering "ELIM" first eliminates the letter 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(W1)>len(W2) implies W1 is larger than W2 for all W1, W2 in <X>. For instance, "LLEX" and "LRLEX" are length compatible while "ELIM" is not.

Syntax

NCo.SetOrdering(Ordering:STRING)

Description

Note that each word ordering is induced by the order of letters in X (see NCo.SetX). For instance, assume that X="abcdef". Then the word ordering is induced by a>b>b>d>e>f.

Example

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

See also

NCo.SetFp

NCo.SetX