34.1 Categories of Associative Words
Associative words are used to represent elements in free groups, semigroups and monoids in GAP (see Free Groups, Monoids and Semigroups). An associative word is just a sequence of letters, where each letter is an element of an alphabet (in the following called a generator) or its inverse. Associative words can be multiplied; in free monoids also the computation of an identity is permitted, in free groups also the computation of inverses (see Operations for Associative Words).
IsAssocWord(
obj ) C
IsAssocWordWithOne(
obj ) C
IsAssocWordWithInverse(
obj ) C
IsAssocWord
is the category of associative words in free semigroups,
IsAssocWordWithOne
is the category of associative words in free monoids
(which admit the operation One
to compute an identity),
IsAssocWordWithInverse
is the category of associative words in free
groups (which have an inverse).
See IsWord for more general categories of words.
Different alphabets correspond to different families of associative words. There is no relation whatsoever between words in different families.
gap> f:= FreeGroup( "a", "b", "c" ); <free group on the generators [a,b,c]> gap> gens:= GeneratorsOfGroup(f); [ a, b, c ] gap> w:= gens[1]*gens[2]/gens[3]*gens[2]*gens[1]/gens[1]*gens[3]/gens[2]; a*b*c^-1*b*c*b^-1 gap> w^-1; b*c^-1*b^-1*c*b^-1*a^-1
Words are displayed as products of letters.
The letters are usually printed like f1
, f2
, ¼,
but it is possible to give user defined names to them,
which can be arbitrary strings.
These names do not necessarily identify a unique letter (generator),
it is possible to have several letters --even in the same family--
that are displayed in the same way.
Note also that
there is no relation between the names of letters and variable names.
Using homomorphisms it is possible to express elements of a group as words in terms of generators, see Expressing group elements as words in generators.
34.2 Free Groups, Monoids and Semigroups
Usually a family of associative words will be generated by constructing the free object generated by them.
FreeGroup(
rank ) F
FreeGroup(
rank,
name ) F
FreeGroup(
name1,
name2, ... ) F
FreeGroup(
names ) F
FreeGroup( infinity,
name,
init ) F
Called in the first form, FreeGroup
returns a free group on
rank generators.
Called in the second form, FreeGroup
returns a free group on
rank generators, printed as name
1
, name
2
etc.
Called in the third form, FreeGroup
returns a free group on
as many generators as arguments, printed as name1, name2 etc.
Called in the fourth form, FreeGroup
returns a free group on
as many generators as the length of the list names, the i-th
generator being printed as names
[ i]
.
Called in the fifth form, FreeGroup
returns a free group on
infinitely many generators, where the first generators are printed
by the names in the list init, and the other generators by name
and an appended number.
IsFreeGroup(
obj ) C
Any group consisting of elements in IsAssocWordWithInverse
lies in the
filter IsFreeGroup
;
this holds in particular for any group created with FreeGroup
(see FreeGroup), or any subgroup of such a group.
FreeMonoid(
rank ) F
FreeMonoid(
rank,
name ) F
FreeMonoid(
name1,
name2, ... ) F
FreeMonoid(
names ) F
FreeMonoid( infinity,
name,
init ) F
Called in the first form, FreeMonoid
returns a free monoid on
rank generators.
Called in the second form, FreeMonoid
returns a free monoid on
rank generators, printed as name
1
, name
2
etc.,
that is, each name is the concatenation of the string name and an
integer from 1
to range.
Called in the third form, FreeMonoid
returns a free monoid on
as many generators as arguments, printed as name1, name2 etc.
Called in the fourth form, FreeMonoid
returns a free monoid on
as many generators as the length of the list names, the i-th
generator being printed as names
[ i]
.
Called in the fifth form, FreeMonoid
returns a free monoid on
infinitely many generators, where the first generators are printed
by the names in the list init, and the other generators by name
and an appended number.
FreeSemigroup(
rank ) F
FreeSemigroup(
rank,
name ) F
FreeSemigroup(
name1,
name2, ... ) F
FreeSemigroup(
names ) F
FreeSemigroup( infinity,
name,
init ) F
Called in the first form, FreeSemigroup
returns a free semigroup on
rank generators.
Called in the second form, FreeSemigroup
returns a free semigroup on
rank generators, printed as name
1
, name
2
etc.,
that is, each name is the concatenation of the string name and an
integer from 1
to range.
Called in the third form, FreeSemigroup
returns a free semigroup on
as many generators as arguments, printed as name1, name2 etc.
Called in the fourth form, FreeSemigroup
returns a free semigroup on
as many generators as the length of the list names, the i-th
generator being printed as names
[ i]
.
Called in the fifth form, FreeSemigroup
returns a free semigroup on
infinitely many generators, where the first generators are printed
by the names in the list init, and the other generators by name
and an appended number.
Each free object defines a unique alphabet (and a unique family of words). Its generators are the letters of this alphabet, thus words of length one.
gap> FreeGroup( 5 ); <free group on the generators [ f1, f2, f3, f4, f5 ] > gap> FreeGroup( "a", "b" ); <free group on the generators [a,b]> gap> FreeGroup( infinity ); <free group with infinity generators> gap> FreeSemigroup( "x", "y" ); <free semigroup on the generators [ x, y ]> gap> FreeMonoid( 7 ); <free monoid on the generators [ m1, m2, m3, m4, m5, m6, m7 ]>
Remember that names are just a help for printing and do not necessarily distinguish letters. It is possible to create arbitrarily weird situations by choosing strange names for the letters.
gap> f:= FreeGroup( "x", "x" ); gens:= GeneratorsOfGroup( f );; <free group on the generators [x,x]> gap> gens[1] = gens[2]; false gap> f:= FreeGroup( "f1*f2", "f2^-1", "Group( [ f1, f2 ] )" ); <free group on the generators [ f1*f2, f2^-1, Group( [ f1, f2 ] ) ]> gap> gens:= GeneratorsOfGroup( f );; gap> gens[1]*gens[2]; f1*f2*f2^-1 gap> gens[1]/gens[3]; f1*f2*Group( [ f1, f2 ] )^-1 gap> gens[3]/gens[1]/gens[2]; Group( [ f1, f2 ] )*f1*f2^-1*f2^-1^-1
w1 =
w2
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
w1 <
w2
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
IsShortLexLessThanOrEqual(
u,
v ) F
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).
IsBasicWreathLessThanOrEqual(
u,
v ) F
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.
34.4 Operations for Associative Words
The product of two given associative words is defined as the freely
reduced concatenation of the words;
so adjacent pairs of a generator and its inverse never occur in words.
Besides the multiplication *
, the arithmetical operators
One
(if the word lies in a family with identity)
and (if the generators are invertible) Inverse
, /
,^
, Comm
,
and LeftQuotient
are applicable to associative words
(see Arithmetic Operations for Elements).
For the operation MappedWord
, which is applicable to arbitrary words,
see MappedWord.
Length(
w ) A
For an associative word w,
Length
returns the number of letters in w.
gap> f := FreeGroup("a","b");; gens := GeneratorsOfGroup(f);; gap> a := gens[1];; b := gens[2];;w := a^5*b*a^2*b^-4*a;; gap> w; Length( w ); Length( a^17 ); Length( w^0 ); a^5*b*a^2*b^-4*a 13 17 0
ExponentSumWord(
w,
gen ) O
For an associative word w and a generator gen,
ExponentSumWord
returns the number of times gen appears in w
minus the number of times its inverse appears in w.
If both gen and its inverse do not occur in w then 0 is returned.
gen may also be the inverse of a generator.
gap> w; ExponentSumWord( w, a ); ExponentSumWord( w, b ); a^5*b*a^2*b^-4*a 8 -3 gap> ExponentSumWord( (a*b*a^-1)^3, a ); ExponentSumWord( w, b^-1 ); 0 3
Subword(
w,
from,
to ) O
For an associative word w and two positive integers from and to,
Subword
returns the subword of w that begins at position from
and ends at position to.
Indexing is done with origin 1.
gap> w; Subword( w, 3, 7 ); a^5*b*a^2*b^-4*a a^3*b*a
PositionWord(
w,
sub,
from ) O
Let w and sub be associative words, and from a positive integer.
PositionWord
returns the position of the first occurrence of sub
as a subword of w, starting at position from.
If there is no such occurrence, fail
is returned.
Indexing is done with origin 1.
In other words, PositionWord(
w,
sub,
from )
is the smallest
integer i larger than or equal to from such that
Subword(
w,
i,
i+Length(
sub )-1 ) =
sub, see Subword.
gap> w; PositionWord( w, a/b, 1 ); a^5*b*a^2*b^-4*a 8 gap> Subword( w, 8, 9 ); a*b^-1 gap> PositionWord( w, a^2, 1 ); 1 gap> PositionWord( w, a^2, 2 ); 2 gap> PositionWord( w, a^2, 6 ); 7 gap> PositionWord( w, a^2, 8 ); fail
SubstitutedWord(
w,
from,
to,
by ) O
SubstitutedWord(
w,
sub,
from,
by ) O
Let w be an associative word.
In the first form, SubstitutedWord
returns the associative word
obtained by replacing the subword of w that begins at position from
and ends at position to by the associative word by.
from and to must be positive integers,
indexing is done with origin 1.
In other words, SubstitutedWord(
w,
from,
to,
by )
is the
product of the three words Subword(
w, 1,
from-1 )
, by,
and Subword(
w,
to+1, Length(
w ) )
, see Subword.
In the second form, SubstitutedWord
returns the associative word
obtained by replacing the first occurrence of the associative word sub
of w, starting at position from, by the associative word by;
if there is no such occurrence, fail
is returned.
gap> w; SubstitutedWord( w, 3, 7, a^19 ); a^5*b*a^2*b^-4*a a^22*b^-4*a gap> SubstitutedWord( w, a, 6, b^7 ); a^5*b^8*a*b^-4*a gap> SubstitutedWord( w, a*b, 6, b^7 ); fail
EliminatedWord(
w,
gen,
by ) O
For an associative word w, a generator gen, and an associative word
by,
EliminatedWord
returns the associative word obtained by replacing
each occurrence of gen in w by by.
gap> w; EliminatedWord( w, a, a^2 ); EliminatedWord( w, a, b^-1 ); a^5*b*a^2*b^-4*a a^10*b*a^4*b^-4*a^2 b^-11
34.5 Operations for Associative Words by their Syllables
For an associative word w = x1n1 x2n2 ¼xknk over an alphabet containing x1, x2, ¼, xk, such that xi ¹ xi+1±1 for 1 £ i £ k-1, the subwords xiei are uniquely determined; these powers of generators are called the syllables of w.
NumberSyllables(
w ) A
NumberSyllables
returns the number of syllables of the associative
word w.
ExponentSyllable(
w,
i ) O
ExponentSyllable
returns the exponent of the i-th syllable of the
associative word w.
GeneratorSyllable(
w,
i ) O
GeneratorSyllable
returns the number of the generator that is involved
in the i-th syllable of the associative word w.
SubSyllables(
w,
from,
to ) O
SubSyllables
returns the subword of the associative word w
that consists of the syllables from positions from to to,
where from and to must be positive integers,
and indexing is done with origin 1.
gap> w; NumberSyllables( w ); a^5*b*a^2*b^-4*a 5 gap> ExponentSyllable( w, 3 ); 2 gap> GeneratorSyllable( w, 3 ); 1 gap> SubSyllables( w, 2, 3 ); b*a^2
34.6 External Representation for Associative Words
The external representation of the associative word w is defined as
follows.
If w = gi1e1 * gi2e2 * ¼* gikek
is a word over the alphabet g1, g2, ¼,
i.e., gi denotes the i-th generator of the family of w,
then w has external representation
[ i1, e1, i2, e2, ¼, ik, ek ].
The empty list describes the identity element (if exists) of the family.
Exponents may be negative if the family allows inverses.
The external representation of an associative word is guaranteed to be
freely reduced;
for example, g1 * g2 * g2-1 * g1 has the external representation
[ 1, 2 ]
.
gap> w:= ObjByExtRep( FamilyObj(a), [1,5,2,-7,1,3,2,4,1,-2] ); a^5*b^-7*a^3*b^4*a^-2 gap> ExtRepOfObj( w^2 ); [ 1, 5, 2, -7, 1, 3, 2, 4, 1, 3, 2, -7, 1, 3, 2, 4, 1, -2 ]
Straight line programs describe an efficient way for evaluating an
abstract word at concrete generators,
in a more efficient way than with MappedWord
(see MappedWord).
For example, the associative word ababbab of length 7 can be computed
from the generators a, b with only four multiplications,
by first computing c = ab, then d = cb, and then cdc;
Alternatively, one can compute c = ab, e = bc, and aee.
In each step of these computations, one forms words in terms of the
words computed in the previous steps.
A straight line program in GAP is represented by an object in the
category IsStraightLineProgram
(see IsStraightLineProgram)
that stores a list of ``lines''
each of which has one of the following three forms.
The lists of integers that occur are interpreted as external representations of associative words (see External Representation for Associative Words); for example, the list [ 1, 3, 2, -1 ] represents the word g13 g2-1, with g1 and g2 the first and second abstract generator, respectively.
Straight line programs can be constructed using
StraightLineProgram
(see StraightLineProgram).
Defining attributes for straight line programs are
NrInputsOfStraightLineProgram
(see NrInputsOfStraightLineProgram)
and LinesOfStraightLineProgram
(see LinesOfStraightLineProgram).
Another operation for straight line programs is
ResultOfStraightLineProgram
(see ResultOfStraightLineProgram).
Special methods applicable to straight line programs are installed for
the operations Display
, IsInternallyConsistent
, PrintObj
,
and ViewObj
.
For a straight line program prog, the default Display
method prints
the interpretation of prog as a sequence of assignments of associative
words;
a record with components gensnames
(with value a list of strings)
and listname
(a string) may be entered as second argument of Display
,
in this case these names are used, the default for gensnames
is
[ g1, g2, ¼], the default for listname
is r.
IsStraightLineProgram(
obj ) C
Each straight line program in GAP lies in the category
IsStraightLineProgram
.
StraightLineProgram(
lines[,
nrgens] ) F
StraightLineProgram(
string,
gens ) F
StraightLineProgramNC(
lines[,
nrgens] ) F
StraightLineProgramNC(
string,
gens ) F
In the first form, lines must be a list of lists that defines a unique
straight line program (see IsStraightLineProgram);
in this case StraightLineProgram
returns this program,
otherwise an error is signalled.
The optional argument nrgens specifies the number of input generators
of the program;
if a line of form 1. (that is, a list of integers) occurs in lines
except in the last position, this number is not determined by lines
and therefore must be specified by the argument nrgens;
if not then StraightLineProgram
returns fail
.
In the second form, string must be a string describing an arithmetic
expression in terms of the strings in the list gens,
where multiplication is denoted by concatenation, powering is denoted by
^
, and round brackets (
, )
may be used.
Each entry in gens must consist only of (uppercase or lowercase)
letters (i.e., letters in IsAlphaChar
, see IsAlphaChar)
such that no entry is an initial part of another one.
Called with this input, StraightLineProgramNC
returns a straight line
program that evaluates to the word corresponding to string when called
with generators corresponding to gens.
StraightLineProgramNC
does the same as StraightLineProgram
,
except that the internal consistency of the program is not checked.
LinesOfStraightLineProgram(
prog ) A
For a straight line program prog, LinesOfStraightLineProgram
returns
the list of program lines.
There is no default method to compute these lines if they are not stored.
NrInputsOfStraightLineProgram(
prog ) A
For a straight line program prog, NrInputsOfStraightLineProgram
returns the number of generators that are needed as input.
If a line of form 1. (that is, a list of integers) occurs in the lines of
prog except the last line
then the number of generators is not determined by the lines,
and must be set in the construction of the straight line program
(see StraightLineProgram).
So if prog contains a line of form 1. other than the last line
and does not store the number of generators
then NrInputsOfStraightLineProgram
signals an error.
ResultOfStraightLineProgram(
prog,
gens ) O
ResultOfStraightLineProgram
evaluates the straight line program
(see IsStraightLineProgram) prog at the group elements in the list
gens.
The result of a straight line program with lines p1, p2, ¼, pk when applied to gens is defined as follows.
Here are some examples.
gap> f:= FreeGroup( "x", "y" );; gens:= GeneratorsOfGroup( f );; gap> x:= gens[1];; y:= gens[2];; gap> prg:= StraightLineProgram( [ [] ] ); <straight line program> gap> ResultOfStraightLineProgram( prg, [] ); [ ]The above straight line program
prg
returns
--for any list of input generators-- an empty list.
gap> StraightLineProgram( [ [1,2,2,3], [3,-1] ] ); fail gap> prg:= StraightLineProgram( [ [1,2,2,3], [3,-1] ], 2 ); <straight line program> gap> LinesOfStraightLineProgram( prg ); [ [ 1, 2, 2, 3 ], [ 3, -1 ] ] gap> prg:= StraightLineProgram( "(a^2b^3)^-1", [ "a", "b" ] ); <straight line program> gap> LinesOfStraightLineProgram( prg ); [ [ [ 1, 2, 2, 3 ], 3 ], [ [ 3, -1 ], 4 ] ] gap> res:= ResultOfStraightLineProgram( prg, gens ); y^-3*x^-2 gap> res = (x^2 * y^3)^-1; true gap> NrInputsOfStraightLineProgram( prg ); 2 gap> Print( prg, "\n" ); StraightLineProgram( [ [ [ 1, 2, 2, 3 ], 3 ], [ [ 3, -1 ], 4 ] ], 2 ) gap> Display( prg ); # input: r:= [ g1, g2 ]; # program: r[3]:= r[1]^2*r[2]^3; r[4]:= r[3]^-1; # return value: r[4] gap> IsInternallyConsistent( StraightLineProgramNC( [ [1,2] ] ) ); true gap> IsInternallyConsistent( StraightLineProgramNC( [ [1,2,3] ] ) ); false gap> prg1:= StraightLineProgram( [ [1,1,2,2], [3,3,1,1] ], 2 );; gap> prg2:= StraightLineProgram( [ [ [1,1,2,2], 2 ], [2,3,1,1] ] );; gap> res1:= ResultOfStraightLineProgram( prg1, gens ); x*y^2*x*y^2*x*y^2*x gap> res1 = (x*y^2)^3*x; true gap> res2:= ResultOfStraightLineProgram( prg2, gens ); x*y^2*x*y^2*x*y^2*x gap> res2 = (x*y^2)^3*x; true gap> prg:= StraightLineProgram( [ [2,3], [ [3,1,1,4], [1,2,3,1] ] ], 2 );; gap> res:= ResultOfStraightLineProgram( prg, gens ); [ y^3*x^4, x^2*y^3 ]
StringOfResultOfStraightLineProgram(
prog,
gensnames[, "LaTeX"] ) F
StringOfResultOfStraightLineProgram
returns a string that describes the
result of the straight line program (see IsStraightLineProgram) prog
as word(s) in terms of the strings in the list gensnames.
If the result of prog is a single element then the return value of
StringOfResultOfStraightLineProgram
is a string consisting of the
entries of gensnames, opening and closing brackets (
and )
,
and powering by integers via ^
.
If the result of prog is a list of elements then the return value of
StringOfResultOfStraightLineProgram
is a comma separated concatenation
of the strings of the single elements,
enclosed in square brackets [
, ]
.
gap> prg:= StraightLineProgram( [ [ 1, 2, 2, 3 ], [ 3, -1 ] ], 2 );; gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ] ); "(a^2b^3)^-1" gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ], "LaTeX" ); "(a^{2}b^{3})^{-1}"
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual