% This file was created automatically from word.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  word.msk                    GAP documentation               Thomas Breuer
%%
%A  @(#)$Id: word.msk,v 1.5 2002/04/15 10:02:34 sal Exp $
%%
%Y  (C) 1999 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Words}

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".




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Categories of Words and Nonassociative Words}

\index{abstract word}

\>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").


\beginexample
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
\endexample

\>IsWordCollection( <obj> ) C

`IsWordCollection' is the collections category
(see~"CategoryCollections") of `IsWord'.


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

\>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'.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparison of Words}

\>`<w1> = <w2>'{equality!nonassociative words}

Two 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.

\>`<w1> \< <w2>'{smaller!nonassociative words}

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.



\beginexample
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
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations for Words}

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").)


\beginexample
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)
\endexample

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Free Magmas}

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 `<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, `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 `<name>1', `<name>2' 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.



\beginexample
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>
\endexample

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.

\beginexample
gap> m:= FreeMagma( "x", "x" );  gens:= GeneratorsOfMagma( m );;
<free magma on the generators [ x, x ]>
gap> gens[1] = gens[2];
false
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{External Representation for Nonassociative Words}

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
$e_v$ and $e_w$, respectively then the product $v \* w$ has external
representation $[ e_v, e_w ]$.
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'.



\beginexample
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))
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E