In GAP an ordering is a relation defined on a family, which is reflexive, anti-symmetric and transitive.
‣ IsOrdering( obj ) | ( category ) |
returns true if and only if the object ord is an ordering.
‣ OrderingsFamily( fam ) | ( attribute ) |
for a family fam, returns the family of all orderings on elements of fam.
‣ OrderingByLessThanFunctionNC( fam, lt[, l] ) | ( operation ) |
Called with two arguments, OrderingByLessThanFunctionNC returns the ordering on the elements of the elements of the family fam, according to the LessThanFunction (34.3-5) value given by lt, where lt is a function that takes two arguments in fam and returns true or false.
Called with three arguments, 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 (34.3-5) value given by lt and with the properties from l set to true.
‣ OrderingByLessThanOrEqualFunctionNC( fam, lteq[, l] ) | ( operation ) |
Called with two arguments, OrderingByLessThanOrEqualFunctionNC returns the ordering on the elements of the elements of the family fam according to the LessThanOrEqualFunction (34.3-6) value given by lteq, where lteq is a function that takes two arguments in fam and returns true or false.
Called with three arguments, 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 (34.3-6) value 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 satisfied.
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
‣ IsWellFoundedOrdering( ord ) | ( property ) |
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 ) | ( property ) |
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 ) | ( operation ) |
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 ) | ( attribute ) |
for an ordering ord, returns the family of elements that the ordering ord compares.
‣ LessThanFunction( ord ) | ( attribute ) |
for an ordering ord, returns a function \(f\) which takes two elements \(el1\), \(el2\) in FamilyForOrdering(ord) and returns true if \(el1\) is strictly less than \(el2\) (with respect to ord), and returns false otherwise.
‣ LessThanOrEqualFunction( ord ) | ( attribute ) |
for an ordering ord, returns a function that takes two elements \(el1\), \(el2\) in 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 ) | ( operation ) |
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 ) | ( operation ) |
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
We now consider orderings on families 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 [Sim94].
‣ IsOrderingOnFamilyOfAssocWords( ord ) | ( property ) |
for an ordering ord, returns true if ord is an ordering over a family of associative words.
‣ IsTranslationInvariantOrdering( ord ) | ( property ) |
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 \(F\), 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 ) | ( property ) |
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 well founded and translation invariant.
‣ OrderingOnGenerators( ord ) | ( attribute ) |
for an ordering ord on a family of associative words, returns a list 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 (34.4-8).
‣ LexicographicOrdering( D[, gens] ) | ( operation ) |
Let D be a free semigroup, a free monoid, or the elements family of such a domain. Called with only argument D, LexicographicOrdering returns the lexicographic ordering on the elements of D.
The optional argument gens can be either the list of free generators of D, in the desired order, or a list of the positions of these generators, in the desired order, and LexicographicOrdering returns the lexicographic ordering on the elements of D with the ordering on the generators as given.
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
‣ ShortLexOrdering( D[, gens] ) | ( operation ) |
Let D be a free semigroup, a free monoid, or the elements family of such a domain. Called with only argument D, ShortLexOrdering returns the shortlex ordering on the elements of D.
The optional argument gens can be either the list of free generators of D, in the desired order, or a list of the positions of these generators, in the desired order, and ShortLexOrdering returns the shortlex ordering on the elements of D with the ordering on the generators as given.
‣ IsShortLexOrdering( ord ) | ( property ) |
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
‣ WeightLexOrdering( D, gens, wt ) | ( operation ) |
Let D be a free semigroup, a free monoid, or the elements family of such a domain. gens can be either the list of free generators of D, in the desired order, or a list of the positions of these generators, in the desired order. Let wt be a list of weights. WeightLexOrdering returns the weightlex ordering on the elements of D with the ordering on the generators and weights of the generators as given.
‣ IsWeightLexOrdering( ord ) | ( property ) |
for an ordering ord on a family of associative words, returns true if and only if ord is a weightlex ordering.
‣ WeightOfGenerators( ord ) | ( attribute ) |
for a weightlex ordering ord, returns a list 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 (34.4-4).
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 ]
‣ BasicWreathProductOrdering( D[, gens] ) | ( operation ) |
Let D be a free semigroup, a free monoid, or the elements family of such a domain. Called with only argument D, BasicWreathProductOrdering returns the basic wreath product ordering on the elements of D.
The optional argument gens can be either the list of free generators of D, in the desired order, or a list of the positions of these generators, in the desired order, and BasicWreathProductOrdering returns the lexicographic ordering on the elements of D with the ordering on the generators as given.
‣ IsBasicWreathProductOrdering( ord ) | ( property ) |
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
‣ WreathProductOrdering( D[, gens], levels ) | ( operation ) |
Let D be a free semigroup, a free monoid, or the elements family of such a domain, let gens be either the list of free generators of D, in the desired order, or a list of the positions of these generators, in the desired order, and let levels be a list of levels for the generators. If gens is omitted then the default ordering is taken. WreathProductOrdering returns the wreath product ordering on the elements of D with the ordering on the generators as given.
‣ IsWreathProductOrdering( ord ) | ( property ) |
specifies whether an ordering is a wreath product ordering (see WreathProductOrdering (34.4-13)).
‣ LevelsOfGenerators( ord ) | ( attribute ) |
for a wreath product ordering ord, returns the levels of the generators as given at creation (with respect to OrderingOnGenerators (34.4-4)).
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 ]
generated by GAPDoc2HTML