#############################################################################
##
#W  word.gd                     GAP library                     Thomas Breuer
#W                                                             & Frank Celler
##
#H  @(#)$Id: word.gd,v 4.33 2002/04/15 10:05:29 sal Exp $
##
#Y  Copyright (C)  1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file declares the categories and operations for words and
##  nonassociative words.
##
##  1. Categories of Words and Nonassociative Words
##  2. Comparison of Words
##  3. Operations for Words
##  4. Free Magmas
##  5. External Representation for Nonassociative Words
##
Revision.word_gd :=
    "@(#)$Id: word.gd,v 4.33 2002/04/15 10:05:29 sal Exp $";


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


#############################################################################
##
##  1. Categories of Words and Nonassociative Words
##


#############################################################################
##
#C  IsWord( <obj> )
#C  IsWordWithOne( <obj> )
#C  IsWordWithInverse( <obj> )
##
##  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").
##  
DeclareCategory( "IsWord", IsMultiplicativeElement );
DeclareSynonym( "IsWordWithOne", IsWord and IsMultiplicativeElementWithOne );
DeclareSynonym( "IsWordWithInverse",
    IsWord and IsMultiplicativeElementWithInverse );


#############################################################################
##
#C  IsWordCollection( <obj> )
##
##  `IsWordCollection' is the collections category
##  (see~"CategoryCollections") of `IsWord'.
##
DeclareCategoryCollections( "IsWord" );


#############################################################################
##
#C  IsNonassocWord( <obj> )
#C  IsNonassocWordWithOne( <obj> )
##
##  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").
##
DeclareCategory( "IsNonassocWord", IsWord );
DeclareSynonym( "IsNonassocWordWithOne", IsNonassocWord and IsWordWithOne );


#############################################################################
##
#C  IsNonassocWordCollection( <obj> )
#C  IsNonassocWordWithOneCollection( <obj> )
##
##  `IsNonassocWordCollection' is the collections category
##  (see~"CategoryCollections") of `IsNonassocWord',
##  and `IsNonassocWordWithOneCollection' is the collections category
##  of `IsNonassocWordWithOne'.
##
DeclareCategoryCollections( "IsNonassocWord" );
DeclareCategoryCollections( "IsNonassocWordWithOne" );


#############################################################################
##
#C  IsNonassocWordFamily( <obj> )
#C  IsNonassocWordWithOneFamily( <obj> )
##
DeclareCategoryFamily( "IsNonassocWord" );
DeclareCategoryFamily( "IsNonassocWordWithOne" );


#############################################################################
##
##  2. Comparison of Words
#2
##  \>`<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.
##


#############################################################################
##
##  3. Operations for Words
#3
##  Two words can be multiplied via `\*' only if they are words over the same
##  alphabet (see~"Comparison of Words").
##


#############################################################################
##
#O  MappedWord( <w>, <gens>, <imgs> )
##
##  `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").)
##
DeclareOperation( "MappedWord", [ IsWord, IsWordCollection, IsList ] );


#############################################################################
##
##  4. Free Magmas
#4
##  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.
##


#############################################################################
##
#C  IsFreeMagma( <obj> )
##
##  `IsFreeMagma' is just a synonym for
##  `IsNonassocWordCollection and IsMagma',
##  that is, any magma (see~"IsMagma") consisting of nonassociative words
##  (see~"IsNonassocWord") is in this category.
##
DeclareSynonym( "IsFreeMagma", IsNonassocWordCollection and IsMagma );


#############################################################################
##
##  5. External Representation for Nonassociative Words
#5
##  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'.
#T  (see~"ObjByExtRep").
##


#############################################################################
##
#O  NonassocWord( <Fam>, <extrep> )   . .  construct word from external repr.
##
DeclareSynonym( "NonassocWord", ObjByExtRep );


#############################################################################
##
#E