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

# 29 Orderings

### Sections

1. Building new orderings
2. Properties and basic functionality
3. Orderings on families of associative words

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.

  ## 29.1 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.

      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

- `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 ≠ 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.

      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.

- `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 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 ∈ 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.

      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(` 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.

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

      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(` 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`

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

      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
  August 2005