33.1 Categories of Words and Nonassociative Words

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, 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 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 is the collections category (see CategoryCollections) of IsWord.

gap> IsWordCollection( m );  IsWordCollection( s );
true
true
gap> IsWordCollection( [ "a", "b" ] );
false

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 is the collections category (see CategoryCollections) of IsNonassocWord, and IsNonassocWordWithOneCollection is the collections category of IsNonassocWordWithOne.

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