29 Orderings

returns true if and only if the object ord is an ordering.

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

29.1 Building new orderings

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.

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.

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

29.2 Properties and basic functionality

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.

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.

for an ordering ord on the elements of the family of el1 and el2, returns true if el1 ≠ el2 and IsLessThanUnder(ord,el1,el2), IsLessThanUnder(ord,el2,el1) are both false; and returns false otherwise.

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

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.

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.

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.

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.

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

29.3 Orderings on families of associative words

We now consider orderings on families of associative words.

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 Sims94.

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 ∈ X^* IsLessThanUnder(ord, a*u*b, a*v*b).

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.

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

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.

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

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.

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

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

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.

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

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

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 ]

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.

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

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.

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

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 ]

[Top] [Up] [Previous] [Next] [Index]

GAP 4 manual
March 2006