34.3 Comparison of Associative Words

Two associative words are equal if they are words over the same alphabet and if they are sequences of the same letters. This is equivalent to saying that the external representations of the words are equal, see External Representation for Associative Words and Comparison of Words.

There is no ``universal'' empty word, every alphabet (that is, every family of words) has its own empty word.

gap> f:= FreeGroup( "a", "b", "b" );;
gap> gens:= GeneratorsOfGroup(f);
[ a, b, b ]
gap> gens[2] = gens[3];
false
gap> x:= gens[1]*gens[2];
a*b
gap> y:= gens[2]/gens[2]*gens[1]*gens[2];
a*b
gap> x = y;
true
gap> z:= gens[2]/gens[2]*gens[1]*gens[3];
a*b
gap> x = z;
false

The ordering of associative words is defined by length and lexicography (this ordering is called short-lex ordering), that is, shorter words are smaller than longer words, and words of the same length are compared w.r.t. the lexicographical ordering induced by the ordering of generators. Generators are sorted according to the order in which they were created. If the generators are invertible then each generator g is larger than its inverse g^-1, and g^-1 is larger than every generator that is smaller than g.

gap> f:= FreeGroup( 2 );;  gens:= GeneratorsOfGroup( f );;
gap> a:= gens[1];;  b:= gens[2];;
gap> One(f) < a^-1;  a^-1 < a;  a < b^-1;  b^-1 < b; b < a^2;  a^2 < a*b;
true
true
true
true
true
true

For two associative words u and v, IsShortLexLessThanOrEqual returns true if u is less than or equal to v, with respect to the short-lex ordering (which is the default ordering on associative words).

For two associative words u and v, IsBasicWreathLessThanOrEqual returns true if u is less than or equal to v, with respect to the basic wreath product ordering.

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