This chapter describes categories of words and nonassociative words, and operations for them. For information about associative words, which occur for example as elements in free groups, see Chapter Associative Words.
IsWord( obj ) C
IsWordWithOne( obj ) C
IsWordWithInverse( obj ) C
Given a free multiplicative structure M that is freely generated by a subset X, any expression of an element in M as an iterated product of elements in X is called a word over X.
Interesting cases of free multiplicative structures are those of free semigroups, free monoids, and free groups, where the multiplication is associative (see IsAssociative), which are described in Chapter Associative Words, and also the case of free magmas, where the multiplication is nonassociative (see IsNonassocWord).
Elements in free magmas (see FreeMagma) lie in the category IsWord;
similarly, elements in free magmas-with-one (see FreeMagmaWithOne)
lie in the category IsWordWithOne, and so on.
IsWord is mainly a ``common roof'' for the two disjoint categories
IsAssocWord (see IsAssocWord) and IsNonassocWord
(see IsNonassocWord) of associative and nonassociative words.
This means that associative words are not regarded as special cases
of nonassociative words.
The main reason for this setup is that we are interested in different
external representations for associative and nonassociative words
(see External Representation for Nonassociative Words and
The External Representation for Associative Words).
Note that elements in finitely presented groups and also elements in
polycyclic groups in GAP are not in IsWord although they are
usually called words,
see Chapters Finitely Presented Groups and Pc Groups.
Words are constants (see Mutability and Copyability), that is, they are not copyable and not mutable.
The usual way to create words is to form them as products of known words, starting from generators of a free structure such as a free magma or a free group (see FreeMagma, FreeGroup).
Words are also used to implement free algebras, in the same way as group elements are used to implement group algebras (see Constructing Algebras as Free Algebras and Chapter Magma Rings).
gap> m:= FreeMagmaWithOne( 2 );; gens:= GeneratorsOfMagmaWithOne( m ); [ x1, x2 ] gap> w1:= gens[1] * gens[2] * gens[1]; ((x1*x2)*x1) gap> w2:= gens[1] * ( gens[2] * gens[1] ); (x1*(x2*x1)) gap> w1 = w2; IsAssociative( m ); false false gap> IsWord( w1 ); IsAssocWord( w1 ); IsNonassocWord( w1 ); true false true gap> s:= FreeMonoid( 2 );; gens:= GeneratorsOfMagmaWithOne( s ); [ m1, m2 ] gap> u1:= ( gens[1] * gens[2] ) * gens[1]; m1*m2*m1 gap> u2:= gens[1] * ( gens[2] * gens[1] ); m1*m2*m1 gap> u1 = u2; IsAssociative( s ); true true gap> IsWord( u1 ); IsAssocWord( u1 ); IsNonassocWord( u1 ); true true false gap> a:= (1,2,3);; b:= (1,2);; gap> w:= a*b*a;; IsWord( w ); false
IsWordCollection( obj ) C
IsWordCollection is the collections category
(see CategoryCollections) of IsWord.
gap> IsWordCollection( m ); IsWordCollection( s ); true true gap> IsWordCollection( [ "a", "b" ] ); false
IsNonassocWord( obj ) C
IsNonassocWordWithOne( obj ) C
A nonassociative word in GAP is an element in a free magma or a free magma-with-one (see Free Magmas).
The default methods for ViewObj and PrintObj (see View and Print)
show nonassociative words as products of letters,
where the succession of multiplications is determined by round brackets.
In this sense each nonassociative word describes a ``program'' to
form a product of generators.
(Also associative words can be interpreted as such programs,
except that the exact succession of multiplications is not prescribed
due to the associativity.)
The function MappedWord (see MappedWord) implements a way to
apply such a program.
A more general way is provided by straight line programs
(see Straight Line Programs).
Note that associative words (see Chapter Associative Words) are not regarded as special cases of nonassociative words (see IsWord).
IsNonassocWordCollection( obj ) C
IsNonassocWordWithOneCollection( obj ) C
IsNonassocWordCollection is the collections category
(see CategoryCollections) of IsNonassocWord,
and IsNonassocWordWithOneCollection is the collections category
of IsNonassocWordWithOne.
= w2Two words are equal if and only if they are words over the same alphabet and with equal external representations (see External Representation for Nonassociative Words and The External Representation for Associative Words). For nonassociative words, the latter means that the words arise from the letters of the alphabet by the same sequence of multiplications.
< w2
Words are ordered according to their external representation.
More precisely, two words can be compared if they are words over the same
alphabet, and the word with smaller external representation is smaller.
For nonassociative words, the ordering is defined
in External Representation for Nonassociative Words;
associative words are ordered by the shortlex ordering via <
(see The External Representation for Associative Words).
Note that the alphabet of a word is determined by its family
(see Families),
and that the result of each call to FreeMagma, FreeGroup etc.
consists of words over a new alphabet.
In particular, there is no ``universal'' empty word,
every families of words in IsWordWithOne has its own empty word.
gap> m:= FreeMagma( "a", "b" );; gap> x:= FreeMagma( "a", "b" );; gap> mgens:= GeneratorsOfMagma( m ); [ a, b ] gap> xgens:= GeneratorsOfMagma( x ); [ a, b ] gap> a:= mgens[1];; b:= mgens[2];; gap> a = xgens[1]; false gap> a*(a*a) = (a*a)*a; a*b = b*a; a*a = a*a; false false true gap> a < b; b < a; a < a*b; true false true
Two words can be multiplied via * only if they are words over the same
alphabet (see Comparison of Words).
MappedWord( w, gens, imgs ) O
MappedWord returns the object that is obtained by replacing each
occurrence in the word w of a generator in the list gens
by the corresponding object in the list imgs.
The lists gens and imgs must of course have the same length.
MappedWord needs to do some preprocessing to get internal generator
numbers etc. When mapping many (several thousand) words, an
explicit loop over the words syllables might be faster.
(For example, If the elements in imgs are all associative words
(see Chapter Associative Words)
in the same family as the elements in gens,
and some of them are equal to the corresponding generators in gens,
then those may be omitted from gens and imgs.
In this situation, the special case that the lists gens
and imgs have only length 1 is handled more efficiently by
EliminatedWord (see EliminatedWord).)
gap> m:= FreeMagma( "a", "b" );; gens:= GeneratorsOfMagma( m );; gap> a:= gens[1]; b:= gens[2]; a b gap> w:= (a*b)*((b*a)*a)*b; (((a*b)*((b*a)*a))*b) gap> MappedWord( w, gens, [ (1,2), (1,2,3,4) ] ); (2,4,3) gap> a:= (1,2);; b:= (1,2,3,4);; (a*b)*((b*a)*a)*b; (2,4,3)
gap> f:= FreeGroup( "a", "b" );; gap> a:= GeneratorsOfGroup(f)[1];; b:= GeneratorsOfGroup(f)[2];; gap> w:= a^5*b*a^2/b^4*a; a^5*b*a^2*b^-4*a gap> MappedWord( w, [ a, b ], [ (1,2), (1,2,3,4) ] ); (1,3,4,2) gap> (1,2)^5*(1,2,3,4)*(1,2)^2/(1,2,3,4)^4*(1,2); (1,3,4,2) gap> MappedWord( w, [ a ], [ a^2 ] ); a^10*b*a^4*b^-4*a^2
The easiest way to create a family of words is to construct the free
object generated by these words.
Each such free object defines a unique alphabet,
and its generators are simply the words of length one over this alphabet;
These generators can be accessed via GeneratorsOfMagma in the case of
a free magma, and via GeneratorsOfMagmaWithOne in the case of a free
magma-with-one.
FreeMagma( rank ) F
FreeMagma( rank, name ) F
FreeMagma( name1, name2, ... ) F
FreeMagma( names ) F
FreeMagma( infinity, name, init ) F
Called in the first form, FreeMagma returns a free magma on
rank generators.
Called in the second form, FreeMagma returns a free magma on
rank generators, printed as name1, name2 etc.,
that is, each name is the concatenation of the string name and an
integer from 1 to range.
Called in the third form, FreeMagma returns a free magma on
as many generators as arguments, printed as name1, name2 etc.
Called in the fourth form, FreeMagma returns a free magma 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, FreeMagma returns a free magma 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.
FreeMagmaWithOne( rank ) F
FreeMagmaWithOne( rank, name ) F
FreeMagmaWithOne( name1, name2, ... ) F
FreeMagmaWithOne( names ) F
FreeMagmaWithOne( infinity, name, init ) F
Called in the first form, FreeMagmaWithOne returns
a free magma-with-one on rank generators.
Called in the second form, FreeMagmaWithOne returns
a free magma-with-one on rank generators,
printed as name1, name2 etc.
Called in the third form, FreeMagmaWithOne returns
a free magma-with-one on as many generators as arguments,
printed as name1, name2 etc.
Called in the fourth form, FreeMagmaWithOne returns
a free magma-with-one 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, FreeMagmaWithOne returns
a free magma 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.
gap> FreeMagma( 3 ); <free magma on the generators [ x1, x2, x3 ]> gap> FreeMagma( "a", "b" ); <free magma on the generators [ a, b ]> gap> FreeMagma( infinity ); <free magma with infinity generators> gap> FreeMagmaWithOne( 3 ); <free magma-with-one on the generators [ x1, x2, x3 ]> gap> FreeMagmaWithOne( "a", "b" ); <free magma-with-one on the generators [ a, b ]> gap> FreeMagmaWithOne( infinity ); <free magma-with-one with infinity generators>
Remember that the names of generators used for printing do not necessarily distinguish letters of the alphabet; so it is possible to create arbitrarily weird situations by choosing strange letter names.
gap> m:= FreeMagma( "x", "x" ); gens:= GeneratorsOfMagma( m );; <free magma on the generators [ x, x ]> gap> gens[1] = gens[2]; false
The external representation of nonassociative words is defined as follows. The i-th generator of the family of elements in question has external representation i, the identity (if exists) has external representation 0, the inverse of the i-th generator (if exists) has external representation −i. If v and w are nonassociative words with external representations ev and ew, respectively then the product v * w has external representation [ ev, ew ]. So the external representation of any nonassociative word is either an integer or a nested list of integers and lists, where each list has length two.
One can create a nonassociative word from a family of words and the
external representation of a nonassociative word using ObjByExtRep.
gap> m:= FreeMagma( 2 );; gens:= GeneratorsOfMagma( m ); [ x1, x2 ] gap> w:= ( gens[1] * gens[2] ) * gens[1]; ((x1*x2)*x1) gap> ExtRepOfObj( w ); ExtRepOfObj( gens[1] ); [ [ 1, 2 ], 1 ] 1 gap> ExtRepOfObj( w*w ); [ [ [ 1, 2 ], 1 ], [ [ 1, 2 ], 1 ] ] gap> ObjByExtRep( FamilyObj( w ), 2 ); x2 gap> ObjByExtRep( FamilyObj( w ), [ 1, [ 2, 1 ] ] ); (x1*(x2*x1))
[Top] [Up] [Previous] [Next] [Index]
GAP 4 manual
March 2006