Difference between revisions of "ApCoCoA-1:NC.SetOrdering"
| Line 2: | Line 2: | ||
<title>NC.SetOrdering</title> | <title>NC.SetOrdering</title> | ||
<short_description> | <short_description> | ||
| − | Sets an | + | Sets an admissible ordering on <tt><X></tt>. |
</short_description> | </short_description> | ||
<syntax> | <syntax> | ||
| Line 8: | Line 8: | ||
</syntax> | </syntax> | ||
<description> | <description> | ||
| − | Note that default ordering is | + | Note that the default ordering is <quotes>LLEX</quotes> (length-lexicographic ordering). |
<itemize> | <itemize> | ||
| − | <item>@param <em>Ordering</em>: a string which indicates an (admissible) ordering. For the time being, the package supports length-lexicographic ordering (<quotes>LLEX</quotes>) and elimination ordering | + | <item>@param <em>Ordering</em>: a string which indicates an (admissible) ordering. For the time being, the package supports <quotes>LLEX</quotes> (length-lexicographic ordering), <quotes>ELIM</quotes> (elimination ordering) and <quotes>LRLEX</quotes> (length-reverse-lexicographic ordering).</item> |
| − | </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><X></tt> as follows. For two words <tt>W1, W2</tt> in <tt><X></tt>, we say <tt>W1>_{Lex}W2</tt> if we have <tt>W1=W2*W</tt> for some non-empty word <tt>W</tt> in <tt><X></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><X></tt> and some letters <tt>x_{i},x_{j}</tt> in <tt>X</tt> such that <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 an admissible ordering on <tt><X></tt>. We define admissible orderings <quotes>LLEX</quotes>, <quotes>ELIM</quotes> and <quotes>LRLEX</quotes> on <tt><X></tt> as follows. | ||
| + | <itemize> | ||
| + | <item><quotes>LLEX</quotes>: for two words <tt>W1, W2</tt> in <tt><X></tt>, we say <tt>W1>_{LLEX}W2</tt> if <tt>len(W1)>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>: for two words <tt>W1, W2</tt> in <tt><X></tt>, we say <tt>W1>_{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>_{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 in <tt>x_{1}</tt>, and then the letter <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><X></tt>, we say <tt>W1>_{LRLEX}W2</tt> if <tt>len(W1)>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> | </itemize> | ||
<example> | <example> | ||
| Line 35: | Line 40: | ||
<see>NC.GGB</see> | <see>NC.GGB</see> | ||
<see>NC.GHF</see> | <see>NC.GHF</see> | ||
| + | <see>NC.GInterreduction</see> | ||
<see>NC.GIsGB</see> | <see>NC.GIsGB</see> | ||
<see>NC.GLC</see> | <see>NC.GLC</see> | ||
| Line 43: | Line 49: | ||
<see>NC.GSubtract</see> | <see>NC.GSubtract</see> | ||
<see>NC.HF</see> | <see>NC.HF</see> | ||
| + | <see>NC.Interreduction</see> | ||
<see>NC.Intersection</see> | <see>NC.Intersection</see> | ||
<see>NC.IsGB</see> | <see>NC.IsGB</see> | ||
Revision as of 16:41, 7 June 2012
NC.SetOrdering
Sets an admissible ordering on <X>.
Syntax
NC.SetOrdering(Ordering:STRING)
Description
Note that the default ordering is "LLEX" (length-lexicographic ordering).
@param Ordering: a string which indicates an (admissible) ordering. For the time being, the package supports "LLEX" (length-lexicographic ordering), "ELIM" (elimination ordering) and "LRLEX" (length-reverse-lexicographic ordering).
Let X=x_{1}x_{2}...x_{n}. We define the (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 an admissible ordering on <X>. We define admissible 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": for two words W1, W2 in <X>, we say W1>_{ELIM}W2 if W1 is lexicographically larger than W2 by considering W1, W2 as two terms in the commutative case, or W1=W2 by considering W1, W2 as two terms in the commutative case and W1>_{Lex}W2 (W1 is left-to-right lexicographically larger than W2 by considering W1, W2 as two words in the non-commutative case). Thus, the elimination ordering "ELIM" first eliminates the letter in x_{1}, and then the letter x_{2}, and then x_{3}, and so on and so forth.
"LRLEX": for two words W1, W2 in <X>, we say W1>_{LRLEX}W2 if len(W1)>len(W2), or len(W1)=len(W2) and W1 is larger than W2 by right-to-left lexicographic ordering.
Example
NC.RingEnv(); Coefficient ring : Q Ordering : LLEX ------------------------------- NC.SetOrdering(<quotes>ELIM</quotes>); NC.RingEnv(); Coefficient ring : Q Ordering : ELIM -------------------------------
See also
