gap-online-help 4r7p9-1 / usr / share / gap / doc / ref / chap36.txt

  
  36 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 37.
  
  
  36.1 Categories of Words and Nonassociative Words
  
  36.1-1 IsWord
  
  IsWord( obj )  Category
  IsWordWithOne( obj )  Category
  IsWordWithInverse( obj )  Category
  
  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 (35.4-7)), which are described in Chapter 37,
  and also the case of free magmas, where the multiplication is nonassociative
  (see IsNonassocWord (36.1-3)).
  
  Elements in free magmas (see FreeMagma (36.4-1)) lie in the category IsWord;
  similarly,  elements in free magmas-with-one (see FreeMagmaWithOne (36.4-2))
  lie in the category IsWordWithOne, and so on.
  
  IsWord  is  mainly a common roof for the two disjoint categories IsAssocWord
  (37.1-1)  and  IsNonassocWord  (36.1-3)  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 36.5 and 37.7).
  
  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 47 and 46.
  
  Words  are  constants  (see 12.6),  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 (36.4-1), FreeGroup (37.2-1)).
  
  Words  are  also  used  to implement free algebras, in the same way as group
  elements are used to implement group algebras (see 62.3 and Chapter 65).
  
    Example  
    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
  
  
  36.1-2 IsWordCollection
  
  IsWordCollection( obj )  Category
  
  IsWordCollection   is   the  collections  category  (see CategoryCollections
  (30.2-4)) of IsWord (36.1-1).
  
    Example  
    gap> IsWordCollection( m );  IsWordCollection( s );
    true
    true
    gap> IsWordCollection( [ "a", "b" ] );
    false
  
  
  36.1-3 IsNonassocWord
  
  IsNonassocWord( obj )  Category
  IsNonassocWordWithOne( obj )  Category
  
  A  nonassociative  word  in  GAP  is  an  element  in a free magma or a free
  magma-with-one (see 36.4).
  
  The   default   methods  for  ViewObj  (6.3-5)  and  PrintObj  (6.3-5)  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 (36.3-1) implements a way to
  apply  such  a  program.  A  more  general  way is provided by straight line
  programs (see 37.8).
  
  Note  that  associative  words  (see Chapter 37) are not regarded as special
  cases of nonassociative words (see IsWord (36.1-1)).
  
  36.1-4 IsNonassocWordCollection
  
  IsNonassocWordCollection( obj )  Category
  IsNonassocWordWithOneCollection( obj )  Category
  
  IsNonassocWordCollection       is       the       collections       category
  (see CategoryCollections   (30.2-4))   of   IsNonassocWord   (36.1-3),   and
  IsNonassocWordWithOneCollection    is    the    collections    category   of
  IsNonassocWordWithOne (36.1-3).
  
  
  36.2 Comparison of Words
  
  36.2-1 \=
  
  \=( w1, w2 )  function
  
  Two words are equal if and only if they are words over the same alphabet and
  with  equal external representations (see 36.5 and 37.7). For nonassociative
  words,  the  latter  means  that  the  words  arise  from the letters of the
  alphabet by the same sequence of multiplications.
  
  36.2-2 \<
  
  \<( w1, w2 )  function
  
  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 36.5; associative words are
  ordered by the shortlex ordering via < (see 37.7).
  
  Note that the alphabet of a word is determined by its family (see 13.1), and
  that  the result of each call to FreeMagma (36.4-1), FreeGroup (37.2-1) etc.
  consists  of words over a new alphabet. In particular, there is no universal
  empty  word,  every  families of words in IsWordWithOne (36.1-1) has its own
  empty word.
  
    Example  
    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
  
  
  
  36.3 Operations for Words
  
  Two  words  can  be  multiplied  via  * only if they are words over the same
  alphabet (see 36.2).
  
  36.3-1 MappedWord
  
  MappedWord( w, gens, imgs )  operation
  
  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 37) 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
  (37.4-6).
  
    Example  
    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
  
  
  
  36.4 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 (35.4-1) in the case
  of  a free magma, and via GeneratorsOfMagmaWithOne (35.4-2) in the case of a
  free magma-with-one.
  
  
  36.4-1 FreeMagma
  
  FreeMagma( rank[, name] )  function
  FreeMagma( name1, name2, ... )  function
  FreeMagma( names )  function
  FreeMagma( infinity, name, init )  function
  
  Called  with a positive integer rank, FreeMagma returns a free magma on rank
  generators.  If  the optional argument name is given then the generators are
  printed as name1, name2 etc., that is, each name is the concatenation of the
  string  name  and  an  integer  from 1 to range. The default for name is the
  string "m".
  
  Called  in  the  second  form,  FreeMagma  returns  a  free magma on as many
  generators as arguments, printed as name1, name2 etc.
  
  Called  in  the  third  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 fourth 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.
  
  
  36.4-2 FreeMagmaWithOne
  
  FreeMagmaWithOne( rank[, name] )  function
  FreeMagmaWithOne( name1, name2, ... )  function
  FreeMagmaWithOne( names )  function
  FreeMagmaWithOne( infinity, name, init )  function
  
  Called  with  a  positive  integer  rank,  FreeMagmaWithOne  returns  a free
  magma-with-one  on  rank  generators. If the optional argument name is given
  then  the generators are printed as name1, name2 etc., that is, each name is
  the  concatenation  of  the  string name and an integer from 1 to range. The
  default for name is the string "m".
  
  Called in the second form, FreeMagmaWithOne returns a free magma-with-one on
  as many generators as arguments, printed as name1, name2 etc.
  
  Called  in the third 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 fourth form, FreeMagmaWithOne returns a free magma-with-one 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.
  
    Example  
    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.
  
    Example  
    gap> m:= FreeMagma( "x", "x" );  gens:= GeneratorsOfMagma( m );;
    <free magma on the generators [ x, x ]>
    gap> gens[1] = gens[2];
    false
  
  
  
  36.5 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 (79.16-1).
  
    Example  
    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))