From ApCoCoAWiki
Revision as of 16:31, 2 October 2020 by AndraschkoBot (talk | contribs) (Bot: Category moved)


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.

Note that each word ordering is induced by the order of letters in X (see NCo.SetX). For instance,


defines an elimination ordering induced by a>b>b>d>e>f.

  • @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), and "LRLEX" (the length-reverse-lexicographic ordering).


Coefficient ring : Q
Ordering : LLEX
Coefficient ring : Q
Ordering : ELIM

See also