% This file was created automatically from orders.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  orders.msk                GAP documentation                Isabel Araujo
%%
%A  @(#)$Id: orders.msk,v 1.6 2002/04/15 10:02:31 sal Exp $
%%
%Y  (C) 2000 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Orderings}

In {\GAP} an ordering is a relation defined on a family, which is 
reflexive, anti-symmetric and transitive.


\>IsOrdering( <ord> ) C

returns `true' if and only if the object <ord> is an ordering.


\>OrderingsFamily( <fam> ) A

for a family <fam>, returns the family of all
orderings on elements of <fam>.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Building new orderings}

\>OrderingByLessThanFunctionNC( <fam>, <lt> ) O
\>OrderingByLessThanFunctionNC( <fam>, <lt>, <l> ) O

In the first form, `OrderingByLessThanFunctionNC' returns the ordering on
the elements of the  elements  of  the  family  <fam>  according  to  the
`LessThanFunction' given by <lt>, where <lt> is a function that takes two
arguments in <fam> and returns `true' or `false'.

In the second form, for a family <fam>, a function <lt> that takes 
two arguments in <fam> and returns `true' or `false', and a list <l>
of properties of orderings, `OrderingByLessThanFunctionNC'
returns the ordering on the elements of <fam> with
`LessThanFunction' given by <lt> and with the properties
from <l> set to `true'.


\>OrderingByLessThanOrEqualFunctionNC( <fam>, <lteq> ) O
\>OrderingByLessThanOrEqualFunctionNC( <fam>, <lteq>, <l> ) O

In the  first  form,  `OrderingByLessThanOrEqualFunctionNC'  returns  the
ordering on the elements of the elements of the family <fam> according to
the `LessThanOrEqualFunction' given by <lteq>, where <lteq> is a function
that takes two arguments in <fam> and returns `true' or `false'.

In the second form, for a family <fam>, a function <lteq> that takes 
two arguments in <fam> and returns `true' or `false', and a list <l>
of properties of orderings, `OrderingByLessThanOrEqualFunctionNC'
returns the ordering on the elements of <fam> with
`LessThanOrEqualFunction' given by <lteq> and with the properties
from <l> set to `true'.

Notice that these functions do not check whether <fam> and <lt> or <lteq>
are compatible, and whether the properties listed in <l> are indeed
true.




\beginexample
gap> f := FreeSemigroup("a","b");;
gap> a := GeneratorsOfSemigroup(f)[1];;
gap> b := GeneratorsOfSemigroup(f)[2];;
gap> lt := function(x,y) return Length(x)<Length(y); end;
function( x, y ) ... end
gap> fam := FamilyObj(a);;
gap> ord := OrderingByLessThanFunctionNC(fam,lt);
Ordering
\endexample
			 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Properties and basic functionality}

\>IsWellFoundedOrdering( <ord> ) P

for an ordering <ord>,
returns `true' if and only if the ordering is well founded.
An ordering <ord> is well founded if it admits no infinite descending
chains.
Normally this property is set at the time of creation of the ordering
and there is no general method to check whether a certain ordering
is well founded.


\>IsTotalOrdering( <ord> ) P

for an ordering <ord>,
returns true if and only if the ordering is total.
An ordering <ord> is total if any two elements of the family 
are comparable under <ord>. 
Normally this property is set at the time of creation of the ordering
and there is no general method to check whether a certain ordering
is total.


\>IsIncomparableUnder( <ord>, <el1>, <el2> ) O

for an ordering <ord> on the elements of the family of <el1> and <el2>,
returns `true' if $el1\neq el2$ and  `IsLessThanUnder'(<ord>,<el1>,<el2>), 
`IsLessThanUnder'(<ord>,<el2>,<el1>) are both false; and
returns `false' otherwise.


\>FamilyForOrdering( <ord> ) A

for an ordering <ord>,
returns the family of elements that the ordering <ord> compares.


\>LessThanFunction( <ord> ) A

for an ordering <ord>, 
returns a function <f> which takes two elements <el1>, <el2> in the 
`FamilyForOrdering'(<ord>) and returns `true' if <el1> is 
strictly less than <el2> (with respect to <ord>) and returns `false' 
otherwise.


\>LessThanOrEqualFunction( <ord> ) A

for an ordering <ord>,
returns a function that takes two elements <el1>, <el2> in the 
`FamilyForOrdering'(<ord>) and returns `true' if <el1> is 
less than *or equal to* <el2> (with respect to <ord>) and returns `false' 
otherwise.


\>IsLessThanUnder( <ord>, <el1>, <el2> ) O

for an ordering <ord> on the elements of the family of <el1> and <el2>,
returns `true' if <el1> is (strictly) less than <el2> with
respect to <ord>, and `false' otherwise.


\>IsLessThanOrEqualUnder( <ord>, <el1>, <el2> ) O

for an ordering <ord> on the elements of the family of <el1> and <el2>,
returns `true' if <el1> is less than or equal to <el2> with
respect to <ord>, and `false' otherwise.



\beginexample
gap> IsLessThanUnder(ord,a,a*b);
true
gap> IsLessThanOrEqualUnder(ord,a*b,a*b);
true
gap> IsIncomparableUnder(ord,a,b);
true
gap> FamilyForOrdering(ord) = FamilyObj(a);
true
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Orderings on families of associative words}

We now consider orderings on families of associative words.

\>IsOrderingOnFamilyOfAssocWords( <ord> ) P

for an ordering <ord>,
returns true if <ord> is an ordering over a family of associative
words.


Examples of families of associative words are the families of elements
of a free semigroup or a free monoid;
these are the two cases that we consider mostly.
Associated with those families is
an alphabet, which is the semigroup (resp. monoid) generating set
of the correspondent free semigroup (resp. free monoid).
For definitions of the orderings considered see Sims \cite{Sims94}.


\>IsTranslationInvariantOrdering( <ord> ) P

for an ordering <ord> on a family of associative words,
returns `true' if and only if the ordering is translation invariant.
This is a property of orderings on families of associative words.
An ordering <ord> over a family <fam>, with alphabet <X> is
translation invariant if
`IsLessThanUnder(<ord>, <u>, <v>)' implies that for any $a,b\in X^\*$
`IsLessThanUnder(<ord>, $a*u*b, a*v*b$)'.


\>IsReductionOrdering( <ord> ) P

for an ordering <ord> on a family of associative words,
returns `true' if and only if the ordering is a reduction ordering.
An ordering <ord> is a reduction ordering 
if it is founded and translation invariant.


\>OrderingOnGenerators( <ord> ) A

for an ordering <ord> on a family of associative words,
returns a list <alphabet> in which the generators are considered.
This could be indeed the ordering of the generators in the ordering,
but, for example, if a weight is associated to each generator
then this is not true anymore. See the example for `WeightLexOrdering'
("WeightLexOrdering").



\>LexicographicOrdering( <fam> ) O
\>LexicographicOrdering( <fam>, <gensord> ) O
\>LexicographicOrdering( <fam>, <alphabet> ) O
\>LexicographicOrdering( <f> ) O
\>LexicographicOrdering( <f>, <alphabet> ) O
\>LexicographicOrdering( <f>, <gensord> ) O

In the first form, for a family <fam> of associative words,
`LexicographicOrdering'
returns the lexicographic ordering on the elements of <fam>.

In the second form, for a family <fam> of associate words and
a list <alphabet> which is the actual list of generators in the
desired order, `LexicographicOrdering' 
returns the lexicographic ordering on the elements of
<fam> with the ordering on the alphabet as given.

In the third form, for a family <fam> of associative words and
a list <gensorder> of the length of the alphabet,
`LexicographicOrdering' returns the lexicographic 
ordering on the elements of <fam> with the order on the alphabet
given by <gensord>.

In the fourth form, for a free semigroup of a free monoid <f>,
`LexicographicOrdering'
returns the lexicographic ordering on the family of the elements of <f>
with the order in the alphabet being the default one.

In the fifth form, for a free semigroup or a free monoid <f> and
a list <alphabet> which is the actual list of generators in the
desired order, `LexicographicOrdering'
returns the lexicographic ordering on the elements of
<f> with the ordering on the alphabet as given.

In the sixth form, for a free semigroup of a free monoid <f>,
and a list <gensorder>, `LexicographicOrdering'
returns the lexicographic ordering on the elements of <f> with the order
on the alphabet given by <gensord>.



\beginexample
gap> f := FreeSemigroup(3);
<free semigroup on the generators [ s1, s2, s3 ]>
gap> lex := LexicographicOrdering(f,[2,3,1]);
Ordering
gap> IsLessThanUnder(lex,f.2*f.3,f.3);
true
gap> IsLessThanUnder(lex,f.3,f.2);
false
\endexample

\>ShortLexOrdering( <fam> ) O
\>ShortLexOrdering( <fam>, <alphabet> ) O
\>ShortLexOrdering( <fam>, <gensord> ) O
\>ShortLexOrdering( <f> ) O
\>ShortLexOrdering( <f>, <alphabet> ) O
\>ShortLexOrdering( <f>, <gensord> ) O

In the first form, for a family <fam> of associative words,
`ShortLexOrdering'
returns the ShortLex ordering on the elements of <fam>
with the order in the alphabet being the default one.

In the second form, for a family <fam> of associate words and
a list <alphabet> which is the actual list of generators in the 
desired order, `ShortLexOrdering'
returns the ShortLex ordering on the elements of
<fam> with the ordering on the alphabet as given.

In the third form, for a family <fam> of associative words and
a list <gensorder> of the length of the alphabet,
`ShortLexOrdering' returns the ShortLex
ordering on the elements of <fam> with the order on the alphabet
given by <gensord>. 

In the fourth form, for a free semigroup of a free monoid <f>,
`ShortLexOrdering'
returns the ShortLex ordering on the family of the elements of <f> 
with the order in the alphabet being the default one.

In the fifth form, for a free semigroup or a free monoid <f> and
a list <alphabet> which is the actual list of generators in the 
desired order, `ShortLexOrdering'
returns the ShortLex ordering on the elements of
<f> with the ordering on the alphabet as given.

In the sixth form, for a free semigroup of a free monoid <f>,
and a list <gensorder>, `ShortLexOrdering' 
returns the ShortLex ordering on the elements of <f> with the order 
on the alphabet given by <gensord>.


\>IsShortLexOrdering( <ord> ) P

for an ordering <ord> of a family of associative words,
returns `true' if and only if <ord> is a ShortLex ordering.



\beginexample
gap> f := FreeSemigroup(3);
<free semigroup on the generators [ s1, s2, s3 ]>
gap> sl := ShortLexOrdering(f,[2,3,1]);
Ordering
gap> IsLessThanUnder(sl,f.1,f.2);
false
gap> IsLessThanUnder(sl,f.3,f.2);
false
gap> IsLessThanUnder(sl,f.3,f.1);
true
\endexample

\>WeightLexOrdering( <fam>, <alphabet>, <wt> ) O
\>WeightLexOrdering( <fam>, <gensord>, <wt> ) O
\>WeightLexOrdering( <f>, <alphabet>, <wt> ) O
\>WeightLexOrdering( <f>, <gensord>, <wt> ) O

In the first form, for a family <fam> of associative words
and a list <wt>, `WeightLexOrdering'
returns the WeightLex ordering on the elements of <fam>
with the order in the alphabet being the default one
and the weights of the letters in the alphabet being given
by <wt>.

In the second form, for a family <fam> of associative words,
a list <wt> and a list <gensorder> of the length of the alphabet, 
`WeightLexOrdering' returns the WeightLex  
ordering on the elements of <fam> with the order on the alphabet
given by <gensord> and the weights of the letters in the alphabet 
being given by <wt>. 

In the third form, for a free semigroup of a free monoid <f>
and a list <wt>, `WeightLexOrdering'
returns the WeightLex ordering on the family of the elements of <f>
with the order in the alphabet being the default one
and  the weights of the letters in the alphabet being given
by <wt>.

In the fourth form, for a free semigroup of a free monoid <f>,
a list <wt> and a list <gensorder> of the length of the alphabet,
`WeightLexOrdering' returns the WeightLex  
ordering on the elements of <f> with the order on the alphabet
given by <gensord> and the weights of the letters in the alphabet 
being given by <wt>. 


\>IsWeightLexOrdering( <ord> ) P

for an ordering <ord> on a family of associative words,
returns `true' if and only if <ord> is a WeightLex ordering.


\>WeightOfGenerators( <ord> ) A

for a WeightLex ordering <ord>,
returns a list <l> with length the size of the alphabet of the family.
This list gives the weight of each of the letters of the alphabet
which are used for WeightLex orderings with respect to the
ordering given by `OrderingOnGenerators' (see~"OrderingOnGenerators").



\beginexample
gap> f := FreeSemigroup(3);
<free semigroup on the generators [ s1, s2, s3 ]>
gap> wtlex := WeightLexOrdering(f,[f.2,f.3,f.1],[3,2,1]);
Ordering
gap> IsLessThanUnder(wtlex,f.1,f.2);
true
gap> IsLessThanUnder(wtlex,f.3,f.2);
true
gap> IsLessThanUnder(wtlex,f.3,f.1);
false
gap> OrderingOnGenerators(wtlex);
[ s2, s3, s1 ]
gap> WeightOfGenerators(wtlex);
[ 3, 2, 1 ]
\endexample

\>BasicWreathProductOrdering( <fam> ) O
\>BasicWreathProductOrdering( <fam>, <alphabet> ) O
\>BasicWreathProductOrdering( <fam>, <gensord> ) O
\>BasicWreathProductOrdering( <f> ) O
\>BasicWreathProductOrdering( <f>, <alphabet> ) O
\>BasicWreathProductOrdering( <f>, <gensord> ) O

In the first form, for a family of associative words,
`BasicWreathProductOrdering'
returns the basic wreath product ordering on the elements of <fam>
with the order in the alphabet being the default one.

In the second form, for a family of associative words and
a list <alphabet>, `BasicWreathProductOrdering' returns the
basic wreath product ordering on the elements of <fam> with the order 
on the alphabet given by <alphabet>. 

In the third form, for a family of associative words and
a list <gensorder> of the length of the alphabet,
`BasicWreathProductOrdering' returns the 
basic wreath product ordering on the elements of <fam> with the order 
on the alphabet given by <gensord>. 

In the fourth form, for a free semigroup of a free monoid <f>,
`BasicWreathProductOrdering'
returns the basic wreath product ordering on the family of the 
elements of <f> with the order in the alphabet being the default one.

In the fifth form, for a free semigroup or a free monoid <f>,
and a list <alphabet> of generators, `BasicWreathProductOrdering' 
returns the basic wreath product ordering on the family of the elements 
of <f> with the order on the alphabet given by <alphabet>. 

In the sixth form, for a free semigroup or a free monoid <f>,
and a list <gensorder>, `BasicWreathProductOrdering' 
returns the basic wreath product ordering on the family of the elements 
of <f> with the order on the alphabet given by <gensord>. 


\>IsBasicWreathProductOrdering( <ord> ) P



\beginexample
gap> f := FreeSemigroup(3);
<free semigroup on the generators [ s1, s2, s3 ]>
gap> basic := BasicWreathProductOrdering(f,[2,3,1]);
Ordering
gap> IsLessThanUnder(basic,f.3,f.1);
true
gap> IsLessThanUnder(basic,f.3*f.2,f.1);
true
gap> IsLessThanUnder(basic,f.3*f.2*f.1,f.1*f.3);
false
\endexample

\>WreathProductOrdering( <fam>, <levels> ) O
\>WreathProductOrdering( <fam>, <alphabet>, <levels> ) O
\>WreathProductOrdering( <fam>, <gensord>, <levels> ) O
\>WreathProductOrdering( <f>, <levels> ) O
\>WreathProductOrdering( <f>, <alphabet>, <levels> ) O
\>WreathProductOrdering( <f>, <gensord>, <levels> ) O

returns the wreath product ordering of the
family <fam> of associative words or a free semigroup/monoid <f>.
The ordering on the generators may be omitted (in which case the default
one is considered), or may be given either by a list
<alphabet> consisting of the alphabet of the family in the appropriate
ordering, or by a list <gensord>  giving the permutation of the alphabet. 
It also needs a list <levels> giving the levels of each generator.
Notice that this list gives the levels of the generators in the new 
ordering (not necessarily the default one),
i.e. `<levels>[<i>]' is the level of the generator that comes <i>-th
in the ordering of generators given by <alphabet> or <gensord>.


\>IsWreathProductOrdering( <ord> ) P


\>LevelsOfGenerators( <ord> ) A

for a wreath product ordering <ord>, returns the levels 
of the generators as given at creation (with
respect to `OrderingOnGenerators'; see~"OrderingOnGenerators").



\beginexample
gap> f := FreeSemigroup(3);
<free semigroup on the generators [ s1, s2, s3 ]>
gap> wrp := WreathProductOrdering(f,[1,2,3],[1,1,2,]);
Ordering
gap> IsLessThanUnder(wrp,f.3,f.1);
false
gap> IsLessThanUnder(wrp,f.3,f.2);
false
gap> IsLessThanUnder(wrp,f.1,f.2);
true
gap> LevelsOfGenerators(wrp);
[ 1, 1, 2 ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E