gap-online-help 4r7p9-1 / usr / share / gap / doc / ref / chap34.txt

  
  34 Orderings
  
  In  GAP  an  ordering is a relation defined on a family, which is reflexive,
  anti-symmetric and transitive.
  
  
  34.1 IsOrdering (Filter)
  
  34.1-1 IsOrdering
  
  IsOrdering( obj )  Category
  
  returns true if and only if the object ord is an ordering.
  
  34.1-2 OrderingsFamily
  
  OrderingsFamily( fam )  attribute
  
  for a family fam, returns the family of all orderings on elements of fam.
  
  
  34.2 Building new orderings
  
  34.2-1 OrderingByLessThanFunctionNC
  
  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.
  
  34.2-2 OrderingByLessThanOrEqualFunctionNC
  
  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.
  
    Example  
    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
  
  
  
  34.3 Properties and basic functionality
  
  34.3-1 IsWellFoundedOrdering
  
  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.
  
  34.3-2 IsTotalOrdering
  
  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.
  
  34.3-3 IsIncomparableUnder
  
  IsIncomparableUnder( ord, el1, el2 )  operation
  
  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.
  
  34.3-4 FamilyForOrdering
  
  FamilyForOrdering( ord )  attribute
  
  for  an  ordering  ord, returns the family of elements that the ordering ord
  compares.
  
  34.3-5 LessThanFunction
  
  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.
  
  34.3-6 LessThanOrEqualFunction
  
  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.
  
  34.3-7 IsLessThanUnder
  
  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.
  
  34.3-8 IsLessThanOrEqualUnder
  
  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.
  
    Example  
    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
  
  
  
  34.4 Orderings on families of associative words
  
  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].
  
  34.4-1 IsOrderingOnFamilyOfAssocWords
  
  IsOrderingOnFamilyOfAssocWords( ord )  property
  
  for  an  ordering  ord,  returns true if ord is an ordering over a family of
  associative words.
  
  34.4-2 IsTranslationInvariantOrdering
  
  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  ∈  X^*,
  IsLessThanUnder( ord, a*u*b, a*v*b ).
  
  34.4-3 IsReductionOrdering
  
  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.
  
  34.4-4 OrderingOnGenerators
  
  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).
  
  34.4-5 LexicographicOrdering
  
  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.
  
    Example  
    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
  
  
  34.4-6 ShortLexOrdering
  
  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.
  
  34.4-7 IsShortLexOrdering
  
  IsShortLexOrdering( ord )  property
  
  for  an  ordering  ord of a family of associative words, returns true if and
  only if ord is a shortlex ordering.
  
    Example  
    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
  
  
  34.4-8 WeightLexOrdering
  
  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.
  
  34.4-9 IsWeightLexOrdering
  
  IsWeightLexOrdering( ord )  property
  
  for  an  ordering  ord on a family of associative words, returns true if and
  only if ord is a weightlex ordering.
  
  34.4-10 WeightOfGenerators
  
  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).
  
    Example  
    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 ]
  
  
  34.4-11 BasicWreathProductOrdering
  
  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.
  
  34.4-12 IsBasicWreathProductOrdering
  
  IsBasicWreathProductOrdering( ord )  property
  
    Example  
    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
  
  
  34.4-13 WreathProductOrdering
  
  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.
  
  34.4-14 IsWreathProductOrdering
  
  IsWreathProductOrdering( ord )  property
  
  specifies   whether   an   ordering   is  a  wreath  product  ordering  (see
  WreathProductOrdering (34.4-13)).
  
  34.4-15 LevelsOfGenerators
  
  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)).
  
    Example  
    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 ]