<html><head><title>[ref] 35 Associative Words</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP034.htm">Previous</a>] [<a href ="CHAP036.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>35 Associative Words</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP035.htm#SECT001">Categories of Associative Words</a>
<li> <A HREF="CHAP035.htm#SECT002">Free Groups, Monoids and Semigroups</a>
<li> <A HREF="CHAP035.htm#SECT003">Comparison of Associative Words</a>
<li> <A HREF="CHAP035.htm#SECT004">Operations for Associative Words</a>
<li> <A HREF="CHAP035.htm#SECT005">Operations for Associative Words by their Syllables</a>
<li> <A HREF="CHAP035.htm#SECT006">Representations for Associative Words</a>
<li> <A HREF="CHAP035.htm#SECT007">The External Representation for Associative Words</a>
<li> <A HREF="CHAP035.htm#SECT008">Straight Line Programs</a>
<li> <A HREF="CHAP035.htm#SECT009">Straight Line Program Elements</a>
</ol><p>
<p>
<p>
<h2><a name="SECT001">35.1 Categories of Associative Words</a></h2>
<p><p>
Associative words are used to represent elements in free groups,
semigroups and monoids in <font face="Gill Sans,Helvetica,Arial">GAP</font>
(see <a href="CHAP035.htm#SECT002">Free Groups, Monoids and Semigroups</a>).
An associative word is just a sequence of letters,
where each letter is an element of an alphabet (in the following called a
<strong>generator</strong>) or its inverse.
Associative words can be multiplied;
in free monoids also the computation of an identity is permitted,
in free groups also the computation of inverses
(see <a href="CHAP035.htm#SECT004">Operations for Associative Words</a>).
<p>
<a name = "SSEC001.1"></a>
<li><code>IsAssocWord( </code><var>obj</var><code> ) C</code>
<a name = "SSEC001.1"></a>
<li><code>IsAssocWordWithOne( </code><var>obj</var><code> ) C</code>
<a name = "SSEC001.1"></a>
<li><code>IsAssocWordWithInverse( </code><var>obj</var><code> ) C</code>
<p>
<code>IsAssocWord</code> is the category of associative words in free semigroups,
<code>IsAssocWordWithOne</code> is the category of associative words in free monoids
(which admit the operation <code>One</code> to compute an identity),
<code>IsAssocWordWithInverse</code> is the category of associative words in free
groups (which have an inverse).
See <a href="CHAP034.htm#SSEC001.1">IsWord</a> for more general categories of words.
<p>
Different alphabets correspond to different families of associative words.
There is no relation whatsoever between words in different families.
<p>
<pre>
gap> f:= FreeGroup( "a", "b", "c" );
<free group on the generators [ a, b, c ]>
gap> gens:= GeneratorsOfGroup(f);
[ a, b, c ]
gap> w:= gens[1]*gens[2]/gens[3]*gens[2]*gens[1]/gens[1]*gens[3]/gens[2];
a*b*c^-1*b*c*b^-1
gap> w^-1;
b*c^-1*b^-1*c*b^-1*a^-1
</pre>
<p>
Words are displayed as products of letters.
The letters are usually printed like <code>f1</code>, <code>f2</code>, …,
but it is possible to give user defined names to them,
which can be arbitrary strings.
These names do not necessarily identify a unique letter (generator),
it is possible to have several letters --even in the same family--
that are displayed in the same way.
Note also that
<strong>there is no relation between the names of letters and variable names</strong>.
In the example above, we might have typed
<p>
<pre>
gap> a:= f.1;; b:= f.2;; c:= f.3;;
</pre>
<p>
(<strong>Interactively</strong>, the function <code>AssignGeneratorVariables</code>
(see <a href="CHAP035.htm#SSEC002.5">AssignGeneratorVariables</a>) provides a shorthand for this.)
This allows us to define <code>w</code> more conveniently:
<p>
<pre>
gap> w := a*b/c*b*a/a*c/b;
a*b*c^-1*b*c*b^-1
</pre>
<p>
Using homomorphisms it is possible to express elements of a group as words
in terms of generators,
see <a href="CHAP037.htm#SECT005">Expressing group elements as words in generators</a>.
<p>
<p>
<h2><a name="SECT002">35.2 Free Groups, Monoids and Semigroups</a></h2>
<p><p>
Usually a family of associative words will be generated by constructing
the free object generated by them.
<p>
<a name = "SSEC002.1"></a>
<li><code>FreeGroup( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code> ) F</code>
<li><code>FreeGroup( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code>, </code><var>name</var><code> ) F</code>
<li><code>FreeGroup( [</code><var>wfilt</var><code>, ]</code><var>name1</var><code>, </code><var>name2</var><code>, ... ) F</code>
<li><code>FreeGroup( [</code><var>wfilt</var><code>, ]</code><var>names</var><code> ) F</code>
<li><code>FreeGroup( [</code><var>wfilt</var><code>, ]infinity, </code><var>name</var><code>, </code><var>init</var><code> ) F</code>
<p>
Called in the first form, <code>FreeGroup</code> returns a free group on
<var>rank</var> generators.
Called in the second form, <code>FreeGroup</code> returns a free group on
<var>rank</var> generators, printed as <code></code><var>name</var><code>1</code>, <code></code><var>name</var><code>2</code> etc.
Called in the third form, <code>FreeGroup</code> returns a free group on
as many generators as arguments, printed as <var>name1</var>, <var>name2</var> etc.
Called in the fourth form, <code>FreeGroup</code> returns a free group on
as many generators as the length of the list <var>names</var>, the <i>i</i>-th
generator being printed as <code></code><var>names</var><code>[<i>i</i>]</code>.
Called in the fifth form, <code>FreeGroup</code> returns a free group on
infinitely many generators, where the first generators are printed
by the names in the list <var>init</var>, and the other generators by <var>name</var>
and an appended number.
<p>
If the extra argument <var>wfilt</var> is given, it must be either
<code>IsSyllableWordsFamily</code> or <code>IsLetterWordsFamily</code> or
<code>IsWLetterWordsFamily</code> or <code>IsBLetterWordsFamily</code>. The filter then
specifies the representation used for the elements of the free group
(see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>). If no such filter is
given, a letter representation is used.
<p>
(For interfacing to old code that omits the representation flag, use of
the syllable representation is also triggered by setting the option
<code>FreeGroupFamilyType</code> to the string ``syllable''.)
<p>
<a name = "SSEC002.2"></a>
<li><code>IsFreeGroup( </code><var>obj</var><code> ) C</code>
<p>
Any group consisting of elements in <code>IsAssocWordWithInverse</code> lies in the
filter <code>IsFreeGroup</code>;
this holds in particular for any group created with <code>FreeGroup</code>
(see <a href="CHAP035.htm#SSEC002.1">FreeGroup</a>), or any subgroup of such a group.
<p>
Also see Chapter <a href="CHAP045.htm">Finitely Presented Groups</a>.
<p>
<a name = "SSEC002.3"></a>
<li><code>FreeMonoid( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code> ) F</code>
<li><code>FreeMonoid( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code>, </code><var>name</var><code> ) F</code>
<li><code>FreeMonoid( [</code><var>wfilt</var><code>, ]</code><var>name1</var><code>, </code><var>name2</var><code>, ... ) F</code>
<li><code>FreeMonoid( [</code><var>wfilt</var><code>, ]</code><var>names</var><code> ) F</code>
<li><code>FreeMonoid( [</code><var>wfilt</var><code>, ]infinity, </code><var>name</var><code>, </code><var>init</var><code> ) F</code>
<p>
Called in the first form, <code>FreeMonoid</code> returns a free monoid on
<var>rank</var> generators.
Called in the second form, <code>FreeMonoid</code> returns a free monoid on
<var>rank</var> generators, printed as <code></code><var>name</var><code>1</code>, <code></code><var>name</var><code>2</code> etc.,
that is, each name is the concatenation of the string <var>name</var> and an
integer from <code>1</code> to <var>range</var>.
Called in the third form, <code>FreeMonoid</code> returns a free monoid on
as many generators as arguments, printed as <var>name1</var>, <var>name2</var> etc.
Called in the fourth form, <code>FreeMonoid</code> returns a free monoid on
as many generators as the length of the list <var>names</var>, the <i>i</i>-th
generator being printed as <code></code><var>names</var><code>[<i>i</i>]</code>.
Called in the fifth form, <code>FreeMonoid</code> returns a free monoid on
infinitely many generators, where the first generators are printed
by the names in the list <var>init</var>, and the other generators by <var>name</var>
and an appended number.
<p>
If the extra argument <var>wfilt</var> is given, it must be either
<code>IsSyllableWordsFamily</code> or <code>IsLetterWordsFamily</code> or
<code>IsWLetterWordsFamily</code> or <code>IsBLetterWordsFamily</code>. The filter then
specifies the representation used for the elements of the free group
(see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>). If no such filter is
given, a letter representation is used.
<p>
Also see Chapter <a href="CHAP050.htm">Monoids</a>.
<p>
<a name = "SSEC002.4"></a>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code> ) F</code>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>rank</var><code>, </code><var>name</var><code> ) F</code>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>name1</var><code>, </code><var>name2</var><code>, ... ) F</code>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]</code><var>names</var><code> ) F</code>
<li><code>FreeSemigroup( [</code><var>wfilt</var><code>, ]infinity, </code><var>name</var><code>, </code><var>init</var><code> ) F</code>
<p>
Called in the first form, <code>FreeSemigroup</code> returns a free semigroup on
<var>rank</var> generators.
Called in the second form, <code>FreeSemigroup</code> returns a free semigroup on
<var>rank</var> generators, printed as <code></code><var>name</var><code>1</code>, <code></code><var>name</var><code>2</code> etc.,
that is, each name is the concatenation of the string <var>name</var> and an
integer from <code>1</code> to <var>range</var>.
Called in the third form, <code>FreeSemigroup</code> returns a free semigroup on
as many generators as arguments, printed as <var>name1</var>, <var>name2</var> etc.
Called in the fourth form, <code>FreeSemigroup</code> returns a free semigroup on
as many generators as the length of the list <var>names</var>, the <i>i</i>-th
generator being printed as <code></code><var>names</var><code>[<i>i</i>]</code>.
Called in the fifth form, <code>FreeSemigroup</code> returns a free semigroup on
infinitely many generators, where the first generators are printed
by the names in the list <var>init</var>, and the other generators by <var>name</var>
and an appended number.
<p>
If the extra argument <var>wfilt</var> is given, it must be either
<code>IsSyllableWordsFamily</code> or <code>IsLetterWordsFamily</code> or
<code>IsWLetterWordsFamily</code> or <code>IsBLetterWordsFamily</code>. The filter then
specifies the representation used for the elements of the free group
(see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>). If no such filter is
given, a letter representation is used.
<p>
Also see Chapter <a href="CHAP049.htm">Semigroups</a> and <a href="CHAP049.htm">FreeSemigroup!with examples</a>.
<p>
Each free object defines a unique alphabet (and a unique family of words).
Its generators are the letters of this alphabet,
thus words of length one.
<p>
<pre>
gap> FreeGroup( 5 );
<free group on the generators [ f1, f2, f3, f4, f5 ]>
gap> FreeGroup( "a", "b" );
<free group on the generators [ a, b ]>
gap> FreeGroup( infinity );
<free group with infinity generators>
gap> FreeSemigroup( "x", "y" );
<free semigroup on the generators [ x, y ]>
gap> FreeMonoid( 7 );
<free monoid on the generators [ m1, m2, m3, m4, m5, m6, m7 ]>
</pre>
<p>
Remember that names are just a help for printing and do not necessarily
distinguish letters.
It is possible to create arbitrarily weird situations by choosing strange
names for the letters.
<pre>
gap> f:= FreeGroup( "x", "x" ); gens:= GeneratorsOfGroup( f );;
<free group on the generators [ x, x ]>
gap> gens[1] = gens[2];
false
gap> f:= FreeGroup( "f1*f2", "f2^-1", "Group( [ f1, f2 ] )" );
<free group on the generators [ f1*f2, f2^-1, Group( [ f1, f2 ] ) ]>
gap> gens:= GeneratorsOfGroup( f );;
gap> gens[1]*gens[2];
f1*f2*f2^-1
gap> gens[1]/gens[3];
f1*f2*Group( [ f1, f2 ] )^-1
gap> gens[3]/gens[1]/gens[2];
Group( [ f1, f2 ] )*f1*f2^-1*f2^-1^-1
</pre>
<p>
<a name = "SSEC002.5"></a>
<li><code>AssignGeneratorVariables( </code><var>G</var><code> ) O</code>
<p>
If <var>G</var> is a group, whose generators are represented by symbols (for
example a free group, a finitely presented group or a pc group) this
function assigns these generators to global variables with the same
names.
<p>
The aim of this function is to make it easy in interactive use to work
with (for example) a free group. It is a shorthand for a sequence of
assignments of the form
<p>
<pre>
var1:=GeneratorsOfGroup(G)[1];
var2:=GeneratorsOfGroup(G)[2];
...
varn:=GeneratorsOfGroup(G)[n];
</pre>
<p>
However, since overwriting global variables can be very dangerous, <strong>it
is not permitted to use this function within a function</strong>. (If -- despite
this warning -- this is done, the result is undefined.)
<p>
If the assignment overwrites existing variables a warning is given, if
any of the variables if write protected, or any of the generator names
would not be a proper variable name, an error is raised.
<p>
<p>
<h2><a name="SECT003">35.3 Comparison of Associative Words</a></h2>
<p><p>
<a name = "SSEC003.1"></a>
<li><code></code><var>w1</var><code> = </code><var>w2</var><code></code>
<p>
Two associative words are equal if they are words over the same alphabet
and if they are sequences of the same letters.
This is equivalent to saying that the external representations of the
words are equal, see <a href="CHAP035.htm#SECT007">The External Representation for Associative Words</a> and
<a href="CHAP034.htm#SECT002">Comparison of Words</a>.
<p>
There is no ``universal'' empty word,
every alphabet (that is, every family of words) has its own empty word.
<pre>
gap> f:= FreeGroup( "a", "b", "b" );;
gap> gens:= GeneratorsOfGroup(f);
[ a, b, b ]
gap> gens[2] = gens[3];
false
gap> x:= gens[1]*gens[2];
a*b
gap> y:= gens[2]/gens[2]*gens[1]*gens[2];
a*b
gap> x = y;
true
gap> z:= gens[2]/gens[2]*gens[1]*gens[3];
a*b
gap> x = z;
false
</pre>
<p>
<a name = "SSEC003.2"></a>
<li><code></code><var>w1</var><code> < </code><var>w2</var><code></code>
<p>
The ordering of associative words is defined by length and lexicography
(this ordering is called <strong>short-lex</strong> ordering),
that is, shorter words are smaller than longer words,
and words of the same length are compared w.r.t. the lexicographical
ordering induced by the ordering of generators.
Generators are sorted according to the order in which they were created.
If the generators are invertible then each generator <var>g</var> is larger than
its inverse <code></code><var>g</var><code>^-1</code>,
and <code></code><var>g</var><code>^-1</code> is larger than every generator that is smaller than <var>g</var>.
<pre>
gap> f:= FreeGroup( 2 );; gens:= GeneratorsOfGroup( f );;
gap> a:= gens[1];; b:= gens[2];;
gap> One(f) < a^-1; a^-1 < a; a < b^-1; b^-1 < b; b < a^2; a^2 < a*b;
true
true
true
true
true
true
</pre>
<p>
<a name = "SSEC003.3"></a>
<li><code>IsShortLexLessThanOrEqual( </code><var>u</var><code>, </code><var>v</var><code> ) F</code>
<p>
returns <code>IsLessThanOrEqualUnder(</code><var>ord</var><code>, </code><var>u</var><code>, </code><var>v</var><code>)</code> where <var>ord</var> is the
short less ordering for the family of <var>u</var> and <var>v</var>.
(This is here for compatibility with <font face="Gill Sans,Helvetica,Arial">GAP</font> 4.2.)
<p>
<a name = "SSEC003.4"></a>
<li><code>IsBasicWreathLessThanOrEqual( </code><var>u</var><code>, </code><var>v</var><code> ) F</code>
<p>
returns <code>IsLessThanOrEqualUnder(</code><var>ord</var><code>, </code><var>u</var><code>, </code><var>v</var><code>)</code> where <var>ord</var> is the
basic wreath product ordering for the family of <var>u</var> and <var>v</var>.
(This is here for compatibility with <font face="Gill Sans,Helvetica,Arial">GAP</font> 4.2.)
<p>
<p>
<h2><a name="SECT004">35.4 Operations for Associative Words</a></h2>
<p><p>
<a name = "I0"></a>
<a name = "I1"></a>
<a name = "I2"></a>
<a name = "I3"></a>
<a name = "I4"></a>
<a name = "I5"></a>
The product of two given associative words is defined as the freely
reduced concatenation of the words;
so adjacent pairs of a generator and its inverse never occur in words.
Besides the multiplication <code>*</code>, the arithmetical operators
<code>One</code> (if the word lies in a family with identity)
and (if the generators are invertible) <code>Inverse</code>, <code>/</code>,<code>^</code>, <code>Comm</code>,
and <code>LeftQuotient</code> are applicable to associative words
(see <a href="CHAP030.htm#SECT012">Arithmetic Operations for Elements</a>).
<p>
For the operation <code>MappedWord</code>, which is applicable to arbitrary words,
see <a href="CHAP034.htm#SSEC003.1">MappedWord</a>.
<p>
There are two internal representations of associative words: By letters
and by syllables (see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>). Unless
something else is specified, words are stored in the letter
representation. Note, however, that operations to extract or act on
parts of words (letter or syllables) can carry substantially different
costs, depending on the representation the words are in.
<p>
<a name = "I6"></a>
<a name = "SSEC004.1"></a>
<li><code>Length( </code><var>w</var><code> ) A</code>
<p>
For an associative word <var>w</var>,
<code>Length</code> returns the number of letters in <var>w</var>.
<p>
<pre>
gap> f := FreeGroup("a","b");; gens := GeneratorsOfGroup(f);;
gap> a := gens[1];; b := gens[2];;w := a^5*b*a^2*b^-4*a;;
gap> w; Length( w ); Length( a^17 ); Length( w^0 );
a^5*b*a^2*b^-4*a
13
17
0
</pre>
<p>
<a name = "SSEC004.2"></a>
<li><code>ExponentSumWord( </code><var>w</var><code>, </code><var>gen</var><code> ) O</code>
<p>
For an associative word <var>w</var> and a generator <var>gen</var>,
<code>ExponentSumWord</code> returns the number of times <var>gen</var> appears in <var>w</var>
minus the number of times its inverse appears in <var>w</var>.
If both <var>gen</var> and its inverse do not occur in <var>w</var> then 0 is returned.
<var>gen</var> may also be the inverse of a generator.
<p>
<pre>
gap> w; ExponentSumWord( w, a ); ExponentSumWord( w, b );
a^5*b*a^2*b^-4*a
8
-3
gap> ExponentSumWord( (a*b*a^-1)^3, a ); ExponentSumWord( w, b^-1 );
0
3
</pre>
<p>
<a name = "SSEC004.3"></a>
<li><code>Subword( </code><var>w</var><code>, </code><var>from</var><code>, </code><var>to</var><code> ) O</code>
<p>
For an associative word <var>w</var> and two positive integers <var>from</var> and <var>to</var>,
<code>Subword</code> returns the subword of <var>w</var> that begins at position <var>from</var>
and ends at position <var>to</var>.
Indexing is done with origin 1.
<p>
<pre>
gap> w; Subword( w, 3, 7 );
a^5*b*a^2*b^-4*a
a^3*b*a
</pre>
<p>
<a name = "SSEC004.4"></a>
<li><code>PositionWord( </code><var>w</var><code>, </code><var>sub</var><code>, </code><var>from</var><code> ) O</code>
<p>
Let <var>w</var> and <var>sub</var> be associative words, and <var>from</var> a positive integer.
<code>PositionWord</code> returns the position of the first occurrence of <var>sub</var>
as a subword of <var>w</var>, starting at position <var>from</var>.
If there is no such occurrence, <code>fail</code> is returned.
Indexing is done with origin 1.
<p>
In other words, <code>PositionWord( </code><var>w</var><code>, </code><var>sub</var><code>, </code><var>from</var><code> )</code> is the smallest
integer <var>i</var> larger than or equal to <var>from</var> such that
<code>Subword( </code><var>w</var><code>, </code><var>i</var><code>, </code><var>i</var><code>+Length( </code><var>sub</var><code> )-1 ) = </code><var>sub</var><code></code>, see <a href="CHAP035.htm#SSEC004.3">Subword</a>.
<p>
<pre>
gap> w; PositionWord( w, a/b, 1 );
a^5*b*a^2*b^-4*a
8
gap> Subword( w, 8, 9 );
a*b^-1
gap> PositionWord( w, a^2, 1 );
1
gap> PositionWord( w, a^2, 2 );
2
gap> PositionWord( w, a^2, 6 );
7
gap> PositionWord( w, a^2, 8 );
fail
</pre>
<p>
<a name = "SSEC004.5"></a>
<li><code>SubstitutedWord( </code><var>w</var><code>, </code><var>from</var><code>, </code><var>to</var><code>, </code><var>by</var><code> ) O</code>
<li><code>SubstitutedWord( </code><var>w</var><code>, </code><var>sub</var><code>, </code><var>from</var><code>, </code><var>by</var><code> ) O</code>
<p>
Let <var>w</var> be an associative word.
<p>
In the first form, <code>SubstitutedWord</code> returns the associative word
obtained by replacing the subword of <var>w</var> that begins at position <var>from</var>
and ends at position <var>to</var> by the associative word <var>by</var>.
<var>from</var> and <var>to</var> must be positive integers,
indexing is done with origin 1.
In other words, <code>SubstitutedWord( </code><var>w</var><code>, </code><var>from</var><code>, </code><var>to</var><code>, </code><var>by</var><code> )</code> is the
product of the three words <code>Subword( </code><var>w</var><code>, 1, </code><var>from</var><code>-1 )</code>, <var>by</var>,
and <code>Subword( </code><var>w</var><code>, </code><var>to</var><code>+1, Length( </code><var>w</var><code> ) )</code>, see <a href="CHAP035.htm#SSEC004.3">Subword</a>.
<p>
In the second form, <code>SubstitutedWord</code> returns the associative word
obtained by replacing the first occurrence of the associative word <var>sub</var>
of <var>w</var>, starting at position <var>from</var>, by the associative word <var>by</var>;
if there is no such occurrence, <code>fail</code> is returned.
<p>
<pre>
gap> w; SubstitutedWord( w, 3, 7, a^19 );
a^5*b*a^2*b^-4*a
a^22*b^-4*a
gap> SubstitutedWord( w, a, 6, b^7 );
a^5*b^8*a*b^-4*a
gap> SubstitutedWord( w, a*b, 6, b^7 );
fail
</pre>
<p>
<a name = "SSEC004.6"></a>
<li><code>EliminatedWord( </code><var>w</var><code>, </code><var>gen</var><code>, </code><var>by</var><code> ) O</code>
<p>
For an associative word <var>w</var>, a generator <var>gen</var>, and an associative word
<var>by</var>, <code>EliminatedWord</code> returns the associative word obtained by
replacing each occurrence of <var>gen</var> in <var>w</var> by <var>by</var>.
<p>
<pre>
gap> w; EliminatedWord( w, a, a^2 ); EliminatedWord( w, a, b^-1 );
a^5*b*a^2*b^-4*a
a^10*b*a^4*b^-4*a^2
b^-11
</pre>
<p>
<p>
<h2><a name="SECT005">35.5 Operations for Associative Words by their Syllables</a></h2>
<p><p>
For an associative word <i>w</i> = <i>x</i><sub>1</sub><sup><i>n</i><sub>1</sub></sup> <i>x</i><sub>2</sub><sup><i>n</i><sub>2</sub></sup> …<i>x</i><sub><i>k</i></sub><sup><i>n</i><sub><i>k</i></sub></sup>
over an alphabet containing <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, …, <i>x</i><sub><i>k</i></sub>,
such that <i>x</i><sub><i>i</i></sub> ≠ <i>x</i><sub><i>i</i>+1</sub><sup>±1</sup> for 1 ≤ <i>i</i> ≤ <i>k</i>−1,
the subwords <i>x</i><sub><i>i</i></sub><sup><i>e</i><sub><i>i</i></sub></sup> are uniquely determined;
these powers of generators are called the <strong>syllables</strong> of <i>w</i>.
<p>
<a name = "SSEC005.1"></a>
<li><code>NumberSyllables( </code><var>w</var><code> ) A</code>
<p>
<code>NumberSyllables</code> returns the number of syllables of the associative
word <var>w</var>.
<p>
<a name = "SSEC005.2"></a>
<li><code>ExponentSyllable( </code><var>w</var><code>, </code><var>i</var><code> ) O</code>
<p>
<code>ExponentSyllable</code> returns the exponent of the <var>i</var>-th syllable of the
associative word <var>w</var>.
<p>
<a name = "SSEC005.3"></a>
<li><code>GeneratorSyllable( </code><var>w</var><code>, </code><var>i</var><code> ) O</code>
<p>
<code>GeneratorSyllable</code> returns the number of the generator that is involved
in the <var>i</var>-th syllable of the associative word <var>w</var>.
<p>
<a name = "SSEC005.4"></a>
<li><code>SubSyllables( </code><var>w</var><code>, </code><var>from</var><code>, </code><var>to</var><code> ) O</code>
<p>
<code>SubSyllables</code> returns the subword of the associative word <var>w</var>
that consists of the syllables from positions <var>from</var> to <var>to</var>,
where <var>from</var> and <var>to</var> must be positive integers,
and indexing is done with origin 1.
<p>
<pre>
gap> w; NumberSyllables( w );
a^5*b*a^2*b^-4*a
5
gap> ExponentSyllable( w, 3 );
2
gap> GeneratorSyllable( w, 3 );
1
gap> SubSyllables( w, 2, 3 );
b*a^2
</pre>
<p>
There are two internal representations of associative words: By letters
and by syllables (see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>). Unless
something else is specified, words are stored in the letter
representation. Note, however, that operations to extract or act on
parts of words (letter or syllables) can carry substantially different
costs, depending on the representation the words are in.
<p>
<p>
<h2><a name="SECT006">35.6 Representations for Associative Words</a></h2>
<p><p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> provides two different internal kinds of representations of
associative words. The first one are ``syllable representations'' in which
words are stored in syllable (i.e. generator,exponent) form. (Older versions
of <font face="Gill Sans,Helvetica,Arial">GAP</font> only used this representation.) The second kind are ``letter
representations'' in which each letter in a word is represented by its index
number. Negative numbers are used for inverses. Unless the syllable
representation is specified explicitly when creating the free group/monoid
or semigroup, a letter representation is used by default.
<p>
Depending on the task in mind, either of these two representations will
perform better in time or in memory use and algorithms that are syllable or
letter based (for example <code>GeneratorSyllable</code> and <code>Subword</code>) perform
substantially better in the corresponding representation.
For example when creating pc groups (see <a href="CHAP044.htm">Pc groups</a>), it is advantageous to
use a syllable representation while calculations in free groups usually
benefit from using a letter representation.
<p>
<a name = "SSEC006.1"></a>
<li><code>IsLetterAssocWordRep( </code><var>obj</var><code> ) R</code>
<p>
A word in letter representation stores a list of generator/inverses
numbers (as given by <code>LetterRepAssocWord</code>). Letter access is fast,
syllable access is slow for such words.
<p>
<a name = "SSEC006.2"></a>
<li><code>IsLetterWordsFamily( </code><var>obj</var><code> ) C</code>
<p>
A letter word family stores words by default in letter form.
<p>
Internally, there are letter representations that use integers (4 Byte) to
represent a generator and letter representations that use single bytes to
represent a character. The latter are more memory efficient, but can only be
used if there are less than 128 generators (in which case they are used by
default).
<p>
<a name = "SSEC006.3"></a>
<li><code>IsBLetterAssocWordRep( </code><var>obj</var><code> ) R</code>
<a name = "SSEC006.3"></a>
<li><code>IsWLetterAssocWordRep( </code><var>obj</var><code> ) R</code>
<p>
these two subrepresentations of <code>IsLetterAssocWordRep</code> indicate whether
the word is stored as a list of bytes (in a string) or as a list of
integers)
<p>
<a name = "SSEC006.4"></a>
<li><code>IsBLetterWordsFamily( </code><var>obj</var><code> ) C</code>
<a name = "SSEC006.4"></a>
<li><code>IsWLetterWordsFamily( </code><var>obj</var><code> ) C</code>
<p>
These two subcategories of <code>IsLetterWordsFamily</code> specify the type of
letter representation to be used.
<p>
<a name = "SSEC006.5"></a>
<li><code>IsSyllableAssocWordRep( </code><var>obj</var><code> ) R</code>
<p>
A word in syllable representation stores generator/exponents pairs (as
given by <code>ExtRepOfObj</code>. Syllable access is fast, letter access is slow
for such words.
<p>
<a name = "SSEC006.6"></a>
<li><code>IsSyllableWordsFamily( </code><var>obj</var><code> ) C</code>
<p>
A syllable word family stores words by default in syllable form.
<p>
There are also different versions of syllable representations, which
compress a generator exponent pair in 8,16 or 32 bits or use a pair of
integers. Internal mechanisms try to make this as memory efficient as
possible.
<a name = "SSEC006.7"></a>
<li><code>Is8BitsFamily( </code><var>obj</var><code> ) C</code>
<a name = "SSEC006.7"></a>
<li><code>Is16BitsFamily( </code><var>obj</var><code> ) C</code>
<a name = "SSEC006.7"></a>
<li><code>Is32BitsFamily( </code><var>obj</var><code> ) C</code>
<a name = "SSEC006.7"></a>
<li><code>IsInfBitsFamily( </code><var>obj</var><code> ) C</code>
<p>
Regardless of the internal representation used, it is possible to convert a
word in a list of numbers in letter or syllable representation and vice
versa:
<p>
<a name = "SSEC006.8"></a>
<li><code>LetterRepAssocWord( </code><var>w</var><code> ) O</code>
<li><code>LetterRepAssocWord( </code><var>w</var><code>, </code><var>gens</var><code> ) O</code>
<p>
The <strong>letter representation</strong> of an associated word is as a list of
integers, each entry corresponding to a group generator. Inverses of the
generators are represented by negative numbers. The generator numbers
are as associated to the family.
<p>
This operation returns the letter representation of the associative word
<var>w</var>.
<p>
In the second variant, the generator numbers correspond to the
generator order given in the list <var>gens</var>.
<p>
(For words stored in syllable form the letter representation has to be
comnputed.)
<p>
<a name = "SSEC006.9"></a>
<li><code>AssocWordByLetterRep( </code><var>Fam</var><code>, </code><var>lrep</var><code> [, </code><var>gens</var><code>] ) O</code>
<p>
takes a letter representation <var>lrep</var> (see <code>LetterRepAssocWord</code>,
section <a href="CHAP035.htm#SSEC006.8">LetterRepAssocWord</a>) and returns an associative word in
family <var>fam</var>. corresponding to this letter representation.
<p>
If <var>gens</var> is given, the numbers in the letter
rerpresentation correspond to <var>gens</var>.
<p>
<pre>
gap> w:=AssocWordByLetterRep( FamilyObj(a), [-1,2,1,-2,-2,-2,1,1,1,1]);
a^-1*b*a*b^-3*a^4
gap> LetterRepAssocWord( w^2 );
[ -1, 2, 1, -2, -2, -2, 1, 1, 1, 2, 1, -2, -2, -2, 1, 1, 1, 1 ]
</pre>
<p>
The external representation (see section <a href="CHAP035.htm#SECT007">The External Representation for Associative Words</a>) can be used if a syllable representation is needed.
<p>
<p>
<h2><a name="SECT007">35.7 The External Representation for Associative Words</a></h2>
<p><p>
The external representation of the associative word <i>w</i> is defined as
follows.
If <i>w</i> = <i>g</i><sub><i>i</i><sub>1</sub></sub><sup><i>e</i><sub>1</sub></sup> * <i>g</i><sub><i>i</i><sub>2</sub></sub><sup><i>e</i><sub>2</sub></sup> * …* <i>g</i><sub><i>i</i><sub><i>k</i></sub></sub><sup><i>e</i><sub><i>k</i></sub></sup>
is a word over the alphabet <i>g</i><sub>1</sub>, <i>g</i><sub>2</sub>, …,
i.e., <i>g</i><sub><i>i</i></sub> denotes the <i>i</i>-th generator of the family of <i>w</i>,
then <i>w</i> has external representation
[ <i>i</i><sub>1</sub>, <i>e</i><sub>1</sub>, <i>i</i><sub>2</sub>, <i>e</i><sub>2</sub>, …, <i>i</i><sub><i>k</i></sub>, <i>e</i><sub><i>k</i></sub> ].
The empty list describes the identity element (if exists) of the family.
Exponents may be negative if the family allows inverses.
The external representation of an associative word is guaranteed to be
freely reduced;
for example, <i>g</i><sub>1</sub> * <i>g</i><sub>2</sub> * <i>g</i><sub>2</sub><sup>−1</sup> * <i>g</i><sub>1</sub> has the external representation
<code>[ 1, 2 ]</code>.
<p>
Regardless of the family preference for letter or syllable
representations (see <a href="CHAP035.htm#SECT006">Representations for Associative Words</a>),
<code>ExtRepOfObj</code> and <code>ObjByExtRep</code> can be used and interface to this
``syllable''-like representation.
<p>
<pre>
gap> w:= ObjByExtRep( FamilyObj(a), [1,5,2,-7,1,3,2,4,1,-2] );
a^5*b^-7*a^3*b^4*a^-2
gap> ExtRepOfObj( w^2 );
[ 1, 5, 2, -7, 1, 3, 2, 4, 1, 3, 2, -7, 1, 3, 2, 4, 1, -2 ]
</pre>
<p>
<p>
<h2><a name="SECT008">35.8 Straight Line Programs</a></h2>
<p><p>
<strong>Straight line programs</strong> describe an efficient way for evaluating an
abstract word at concrete generators,
in a more efficient way than with <code>MappedWord</code> (see <a href="CHAP034.htm#SSEC003.1">MappedWord</a>).
For example, the associative word <i>ababbab</i> of length 7 can be computed
from the generators <i>a</i>, <i>b</i> with only four multiplications,
by first computing <i>c</i> = <i>ab</i>, then <i>d</i> = <i>cb</i>, and then <i>cdc</i>;
Alternatively, one can compute <i>c</i> = <i>ab</i>, <i>e</i> = <i>bc</i>, and <i>aee</i>.
In each step of these computations, one forms words in terms of the
words computed in the previous steps.
<p>
A straight line program in <font face="Gill Sans,Helvetica,Arial">GAP</font> is represented by an object in the
category <code>IsStraightLineProgram</code> (see <a href="CHAP035.htm#SSEC008.1">IsStraightLineProgram</a>)
that stores a list of ``lines''
each of which has one of the following three forms.
<ol>
<li>
a nonempty dense list <i>l</i> of integers,
<li>
a pair [ <i>l</i>, <i>i</i> ]
where <i>l</i> is a list of form 1. and <i>i</i> is a positive integer,
<li>
a list [ <i>l</i><sub>1</sub>, <i>l</i><sub>2</sub>, …, <i>l</i><sub><i>k</i></sub> ]
where each <i>l</i><sub><i>i</i></sub> is a list of form 1.;
this may occur only for the last line of the program.
</ol>
<p>
The lists of integers that occur are interpreted as external
representations of associative words
(see <a href="CHAP035.htm#SECT007">The External Representation for Associative Words</a>);
for example, the list [ 1, 3, 2, −1 ] represents the word
<i>g</i><sub>1</sub><sup>3</sup> <i>g</i><sub>2</sub><sup>−1</sup>, with <i>g</i><sub>1</sub> and <i>g</i><sub>2</sub> the first and second abstract
generator, respectively.
<p>
Straight line programs can be constructed using
<code>StraightLineProgram</code> (see <a href="CHAP035.htm#SSEC008.2">StraightLineProgram</a>).
<p>
Defining attributes for straight line programs are
<code>NrInputsOfStraightLineProgram</code> (see <a href="CHAP035.htm#SSEC008.4">NrInputsOfStraightLineProgram</a>)
and <code>LinesOfStraightLineProgram</code> (see <a href="CHAP035.htm#SSEC008.3">LinesOfStraightLineProgram</a>).
Another operation for straight line programs is
<code>ResultOfStraightLineProgram</code> (see <a href="CHAP035.htm#SSEC008.5">ResultOfStraightLineProgram</a>).
<p>
Special methods applicable to straight line programs are installed for
the operations <code>Display</code>, <code>IsInternallyConsistent</code>, <code>PrintObj</code>,
and <code>ViewObj</code>.
<p>
For a straight line program <var>prog</var>, the default <code>Display</code> method prints
the interpretation of <var>prog</var> as a sequence of assignments of associative
words;
a record with components <code>gensnames</code> (with value a list of strings)
and <code>listname</code> (a string) may be entered as second argument of <code>Display</code>,
in this case these names are used, the default for <code>gensnames</code> is
[ <tt>g</tt><tt>1</tt>, <tt>g</tt><tt>2</tt>, …], the default for <code>listname</code> is <i>r</i>.
<p>
<a name = "SSEC008.1"></a>
<li><code>IsStraightLineProgram( </code><var>obj</var><code> ) C</code>
<p>
Each straight line program in <font face="Gill Sans,Helvetica,Arial">GAP</font> lies in the category
<code>IsStraightLineProgram</code>.
<p>
<a name = "SSEC008.2"></a>
<li><code>StraightLineProgram( </code><var>lines</var><code>[, </code><var>nrgens</var><code>] ) F</code>
<li><code>StraightLineProgram( </code><var>string</var><code>, </code><var>gens</var><code> ) F</code>
<a name = "SSEC008.2"></a>
<li><code>StraightLineProgramNC( </code><var>lines</var><code>[, </code><var>nrgens</var><code>] ) F</code>
<li><code>StraightLineProgramNC( </code><var>string</var><code>, </code><var>gens</var><code> ) F</code>
<p>
In the first form, <var>lines</var> must be a list of lists that defines a unique
straight line program (see <a href="CHAP035.htm#SSEC008.1">IsStraightLineProgram</a>);
in this case <code>StraightLineProgram</code> returns this program,
otherwise an error is signalled.
The optional argument <var>nrgens</var> specifies the number of input generators
of the program;
if a line of form 1. (that is, a list of integers) occurs in <var>lines</var>
except in the last position, this number is not determined by <var>lines</var>
and therefore <strong>must</strong> be specified by the argument <var>nrgens</var>;
if not then <code>StraightLineProgram</code> returns <code>fail</code>.
<p>
In the second form, <var>string</var> must be a string describing an arithmetic
expression in terms of the strings in the list <var>gens</var>,
where multiplication is denoted by concatenation, powering is denoted by
<code>^</code>, and round brackets <code>(</code>, <code>)</code> may be used.
Each entry in <var>gens</var> must consist only of (uppercase or lowercase)
letters (i.e., letters in <code>IsAlphaChar</code>, see <a href="CHAP026.htm#SSEC003.4">IsAlphaChar</a>)
such that no entry is an initial part of another one.
Called with this input, <code>StraightLineProgramNC</code> returns a straight line
program that evaluates to the word corresponding to <var>string</var> when called
with generators corresponding to <var>gens</var>.
<p>
<code>StraightLineProgramNC</code> does the same as <code>StraightLineProgram</code>,
except that the internal consistency of the program is not checked.
<p>
<a name = "SSEC008.3"></a>
<li><code>LinesOfStraightLineProgram( </code><var>prog</var><code> ) A</code>
<p>
For a straight line program <var>prog</var>, <code>LinesOfStraightLineProgram</code> returns
the list of program lines.
There is no default method to compute these lines if they are not stored.
<p>
<a name = "SSEC008.4"></a>
<li><code>NrInputsOfStraightLineProgram( </code><var>prog</var><code> ) A</code>
<p>
For a straight line program <var>prog</var>, <code>NrInputsOfStraightLineProgram</code>
returns the number of generators that are needed as input.
<p>
If a line of form 1. (that is, a list of integers) occurs in the lines of
<var>prog</var> except the last line
then the number of generators is not determined by the lines,
and must be set in the construction of the straight line program
(see <a href="CHAP035.htm#SSEC008.2">StraightLineProgram</a>).
So if <var>prog</var> contains a line of form 1. other than the last line
and does <strong>not</strong> store the number of generators
then <code>NrInputsOfStraightLineProgram</code> signals an error.
<p>
<a name = "SSEC008.5"></a>
<li><code>ResultOfStraightLineProgram( </code><var>prog</var><code>, </code><var>gens</var><code> ) O</code>
<p>
<code>ResultOfStraightLineProgram</code> evaluates the straight line program
(see <a href="CHAP035.htm#SSEC008.1">IsStraightLineProgram</a>) <var>prog</var> at the group elements in the list
<var>gens</var>.
<p>
The <strong>result</strong> of a straight line program with lines
<i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, …, <i>p</i><sub><i>k</i></sub>
when applied to <var>gens</var> is defined as follows.
<ol type=a>
<li>
First a list <i>r</i> of intermediate results is initialized
with a shallow copy of <i>gens</i> .
<li>
For <i>i</i> < <i>k</i>, before the <i>i</i>-th step, let <i>r</i> be of length <i>n</i>.
If <i>p</i><sub><i>i</i></sub> is the external representation of an associative word
in the first <i>n</i> generators then the image of this word under the
homomorphism that is given by mapping <i>r</i> to these first <i>n</i>
generators is added to <i>r</i>;
if <i>p</i><sub><i>i</i></sub> is a pair [ <i>l</i>, <i>j</i> ], for a list <i>l</i>, then the same element
is computed, but instead of being added to <i>r</i>,
it replaces the <i>j</i>-th entry of <i>r</i>.
<li>
For <i>i</i> = <i>k</i>, if <i>p</i><sub><i>k</i></sub> is the external representation of an
associative word then the element described in (b) is the result
of the program,
if <i>p</i><sub><i>k</i></sub> is a pair [ <i>l</i>, <i>j</i> ], for a list <i>l</i>, then the result is
the element described by <i>l</i>,
and if <i>p</i><sub><i>k</i></sub> is a list [ <i>l</i><sub>1</sub>, <i>l</i><sub>2</sub>, …, <i>l</i><sub><i>k</i></sub> ] of lists
then the result is a list of group elements, where each <i>l</i><sub><i>i</i></sub> is
treated as in (b).
</ol>
<p>
Here are some examples.
<pre>
gap> f:= FreeGroup( "x", "y" );; gens:= GeneratorsOfGroup( f );;
gap> x:= gens[1];; y:= gens[2];;
gap> prg:= StraightLineProgram( [ [] ] );
<straight line program>
gap> ResultOfStraightLineProgram( prg, [] );
[ ]
</pre>
The above straight line program <code>prg</code> returns
--for <strong>any</strong> list of input generators-- an empty list.
<pre>
gap> StraightLineProgram( [ [1,2,2,3], [3,-1] ] );
fail
gap> prg:= StraightLineProgram( [ [1,2,2,3], [3,-1] ], 2 );
<straight line program>
gap> LinesOfStraightLineProgram( prg );
[ [ 1, 2, 2, 3 ], [ 3, -1 ] ]
gap> prg:= StraightLineProgram( "(a^2b^3)^-1", [ "a", "b" ] );
<straight line program>
gap> LinesOfStraightLineProgram( prg );
[ [ [ 1, 2, 2, 3 ], 3 ], [ [ 3, -1 ], 4 ] ]
gap> res:= ResultOfStraightLineProgram( prg, gens );
y^-3*x^-2
gap> res = (x^2 * y^3)^-1;
true
gap> NrInputsOfStraightLineProgram( prg );
2
gap> Print( prg, "\n" );
StraightLineProgram( [ [ [ 1, 2, 2, 3 ], 3 ], [ [ 3, -1 ], 4 ] ], 2 )
gap> Display( prg );
# input:
r:= [ g1, g2 ];
# program:
r[3]:= r[1]^2*r[2]^3;
r[4]:= r[3]^-1;
# return value:
r[4]
gap> IsInternallyConsistent( StraightLineProgramNC( [ [1,2] ] ) );
true
gap> IsInternallyConsistent( StraightLineProgramNC( [ [1,2,3] ] ) );
false
gap> prg1:= StraightLineProgram( [ [1,1,2,2], [3,3,1,1] ], 2 );;
gap> prg2:= StraightLineProgram( [ [ [1,1,2,2], 2 ], [2,3,1,1] ] );;
gap> res1:= ResultOfStraightLineProgram( prg1, gens );
x*y^2*x*y^2*x*y^2*x
gap> res1 = (x*y^2)^3*x;
true
gap> res2:= ResultOfStraightLineProgram( prg2, gens );
x*y^2*x*y^2*x*y^2*x
gap> res2 = (x*y^2)^3*x;
true
gap> prg:= StraightLineProgram( [ [2,3], [ [3,1,1,4], [1,2,3,1] ] ], 2 );;
gap> res:= ResultOfStraightLineProgram( prg, gens );
[ y^3*x^4, x^2*y^3 ]
</pre>
<p>
<a name = "SSEC008.6"></a>
<li><code>StringOfResultOfStraightLineProgram( </code><var>prog</var><code>, </code><var>gensnames</var><code>[, "LaTeX"] ) F</code>
<p>
<code>StringOfResultOfStraightLineProgram</code> returns a string that describes the
result of the straight line program (see <a href="CHAP035.htm#SSEC008.1">IsStraightLineProgram</a>) <var>prog</var>
as word(s) in terms of the strings in the list <var>gensnames</var>.
If the result of <var>prog</var> is a single element then the return value of
<code>StringOfResultOfStraightLineProgram</code> is a string consisting of the
entries of <var>gensnames</var>, opening and closing brackets <code>(</code> and <code>)</code>,
and powering by integers via <code>^</code>.
If the result of <var>prog</var> is a list of elements then the return value of
<code>StringOfResultOfStraightLineProgram</code> is a comma separated concatenation
of the strings of the single elements,
enclosed in square brackets <code>[</code>, <code>]</code>.
<p>
<pre>
gap> prg:= StraightLineProgram( [ [ 1, 2, 2, 3 ], [ 3, -1 ] ], 2 );;
gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ] );
"(a^2b^3)^-1"
gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ], "LaTeX" );
"(a^{2}b^{3})^{-1}"
</pre>
<p>
<a name = "SSEC008.7"></a>
<li><code>CompositionOfStraightLinePrograms( </code><var>prog2</var><code>, </code><var>prog1</var><code> ) F</code>
<p>
For two straight line programs <var>prog1</var> and <var>prog2</var>,
<code>CompositionOfStraightLinePrograms</code> returns a straight line program
<var>prog</var> with the properties that <var>prog1</var> and <var>prog</var> have the same number
of inputs, and the result of <var>prog</var> when applied to given generators
<var>gens</var> equals the result of <var>prog2</var> when this is applied to the output of
<var>prog1</var> applied to <var>gens</var>.
<p>
(Of course the number of outputs of <var>prog1</var> must be the same as the
number of inputs of <var>prog2</var>.)
<p>
<pre>
gap> prg1:= StraightLineProgram( "a^2b", [ "a","b" ] );;
gap> prg2:= StraightLineProgram( "c^5", [ "c" ] );;
gap> comp:= CompositionOfStraightLinePrograms( prg2, prg1 );
<straight line program>
gap> StringOfResultOfStraightLineProgram( comp, [ "a", "b" ] );
"(a^2b)^5"
gap> prg:= StraightLineProgram( [ [2,3], [ [3,1,1,4], [1,2,3,1] ] ], 2 );;
gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ] );
"[ b^3a^4, a^2b^3 ]"
gap> comp:= CompositionOfStraightLinePrograms( prg, prg );
<straight line program>
gap> StringOfResultOfStraightLineProgram( comp, [ "a", "b" ] );
"[ (a^2b^3)^3(b^3a^4)^4, (b^3a^4)^2(a^2b^3)^3 ]"
</pre>
<p>
<a name = "SSEC008.8"></a>
<li><code>IntegratedStraightLineProgram( </code><var>listofprogs</var><code> ) F</code>
<p>
For a nonempty dense list <var>listofprogs</var> of straight line programs
that have the same number <i>n</i>, say, of inputs
(see <a href="CHAP035.htm#SSEC008.4">NrInputsOfStraightLineProgram</a>)
and for which the results (see <a href="CHAP035.htm#SSEC008.5">ResultOfStraightLineProgram</a>) are single
elements (i.e., <strong>not</strong> lists of elements),
<code>IntegratedStraightLineProgram</code> returns a straight line program <var>prog</var>
with <i>n</i> inputs such that for each <i>n</i>-tuple <var>gens</var> of generators,
<code>ResultOfStraightLineProgram( </code><var>prog</var><code>, </code><var>gens</var><code> )</code> is equal to the list
<code>List( </code><var>listofprogs</var><code>, </code><var>p</var><code> -> ResultOfStraightLineProgram( </code><var>p</var><code>, </code><var>gens</var><code> )</code>.
<p>
<pre>
gap> f:= FreeGroup( "x", "y" );; gens:= GeneratorsOfGroup( f );;
gap> prg1:= StraightLineProgram( [ [ [ 1, 2 ], 1 ], [ 1, 2, 2, -1 ] ], 2 );;
gap> prg2:= StraightLineProgram( [ [ [ 2, 2 ], 3 ], [ 1, 3, 3, 2 ] ], 2 );;
gap> prg3:= StraightLineProgram( [ [ 2, 2 ], [ 1, 3, 3, 2 ] ], 2 );;
gap> prg:= IntegratedStraightLineProgram( [ prg1, prg2, prg3 ] );;
gap> ResultOfStraightLineProgram( prg, gens );
[ x^4*y^-1, x^3*y^4, x^3*y^4 ]
gap> prg:= IntegratedStraightLineProgram( [ prg2, prg3, prg1 ] );;
gap> ResultOfStraightLineProgram( prg, gens );
[ x^3*y^4, x^3*y^4, x^4*y^-1 ]
gap> prg:= IntegratedStraightLineProgram( [ prg3, prg1, prg2 ] );;
gap> ResultOfStraightLineProgram( prg, gens );
[ x^3*y^4, x^4*y^-1, x^3*y^4 ]
</pre>
<p>
<a name = "SSEC008.9"></a>
<li><code>RestrictOutputsOfSLP( </code><var>slp</var><code>, </code><var>k</var><code> ) F</code>
<p>
Returns a new slp that calculates only those outputs specified by
<var>k</var>. <var>k</var> may be an integer or a list of integers. If <var>k</var> is an integer,
the resulting slp calculates only the result with that number.
If <var>k</var> is a list of integers, the resulting slp calculates those
results with numbers in <var>k</var>. In both cases the resulting slp
does only what is necessary. The slp must have a line with at least
<var>k</var> expressions (lists) as its last line (if <var>k</var> is an integer).
<var>slp</var> is either an slp or a pair where the first entry are the lines
of the slp and the second is the number of inputs.
<p>
<a name = "SSEC008.10"></a>
<li><code>IntermediateResultOfSLP( </code><var>slp</var><code>, </code><var>k</var><code> ) F</code>
<p>
Returns a new slp that calculates only the value of slot <var>k</var>
at the end of <var>slp</var> doing only what is necessary.
slp is either an slp or a pair where the first entry are the lines
of the slp and the second is the number of inputs.
Note that this assumes a general SLP with possible overwriting.
If you know that your SLP does not overwrite slots, please use
<a href="CHAP035.htm#SSEC008.11">IntermediateResultOfSLPWithoutOverwrite</a>, which is much faster in this
case.
<p>
<a name = "SSEC008.11"></a>
<li><code>IntermediateResultOfSLPWithoutOverwrite( </code><var>slp</var><code>, </code><var>k</var><code> ) F</code>
<p>
Returns a new slp that calculates only the value of slot <var>k</var>, which
must be an integer.
Note that <var>slp</var> must not overwrite slots but only append!!!
Use <a href="CHAP035.htm#SSEC008.10">IntermediateResultOfSLP</a> in the other case!
<var>slp</var> is either an slp or a pair where the first entry is the lines
of the slp and the second is the number of inputs.
<p>
<a name = "SSEC008.12"></a>
<li><code>IntermediateResultsOfSLPWithoutOverwrite( </code><var>slp</var><code>, </code><var>k</var><code> ) F</code>
<p>
Returns a new slp that calculates only the value of slots contained
in the list k.
Note that <var>slp</var> must not overwrite slots but only append!!!
Use <a href="CHAP035.htm#SSEC008.10">IntermediateResultOfSLP</a> in the other case!
<var>slp</var> is either a slp or a pair where the first entry is the lines
of the slp and the second is the number of inputs.
<p>
<a name = "SSEC008.13"></a>
<li><code>ProductOfStraightLinePrograms( </code><var>s1</var><code>, </code><var>s2</var><code> ) F</code>
<p>
<var>s1</var> and <var>s2</var> must be two slps that return a single element with the same
number of inputs. This function contructs an slp that returns the product
of the two results the slps <var>s1</var> and <var>s2</var> would produce with the same
input.
<p>
<p>
<h2><a name="SECT009">35.9 Straight Line Program Elements</a></h2>
<p><p>
When computing with very large (in terms of memory) elements, for
example permutations of degree a few hundred thousands, it can be
helpful (in terms of memory usage) to represent them via straight line
programs in terms of an original generator set. (So every element takes
only small extra storage for the straight line program.)
<p>
A straight line program element has a <strong>seed</strong> (a list of group elements)
and a straight line program on the same number of generators as the
length of this seed, its value is the value of the evaluated straight
line program.
<p>
At the moment, the entries of the straight line program have to be
simple lists (i.e. of the first form).
<p>
Straight line program elements are in the same categories
and families as the elements of the seed, so they should work together
with existing algorithms.
<p>
Note however, that due to the different way of storage some normally
very cheap operations (such as testing for element equality) can become
more expensive when dealing with straight line program elements. This is
essentially the tradeoff for using less memory.
<p>
<a name = "SSEC009.1"></a>
<li><code>IsStraightLineProgElm( </code><var>obj</var><code> ) R</code>
<p>
A straight line program element is a group element given (for memory
reasons) as a straight line program. Straight line program elements are
positional objects, the first component is a record with a component
<code>seeds</code>, the second component the straight line program.
we need to rank higher than default methods
<p>
<a name = "SSEC009.2"></a>
<li><code>StraightLineProgElm( </code><var>seed</var><code>, </code><var>prog</var><code> ) F</code>
<p>
Creates a straight line program element for seed <var>seed</var> and program
<var>prog</var>.
<p>
<a name = "SSEC009.3"></a>
<li><code>StraightLineProgGens( </code><var>gens</var><code>[, </code><var>base</var><code>] ) F</code>
<p>
returns a set of straight line program elements corresponding to the
generators in <var>gens</var>.
If <var>gens</var> is a set of permutations then <var>base</var> can be given which must
be a base for the group generated by <var>gens</var>. (Such a base will be used to
speed up equality tests.)
<p>
<a name = "SSEC009.4"></a>
<li><code>EvalStraightLineProgElm( </code><var>slpel</var><code> ) F</code>
<p>
evaluates a straight line program element <var>slpel</var> from its seeds.
<p>
<a name = "SSEC009.5"></a>
<li><code>StretchImportantSLPElement( </code><var>elm</var><code> ) O</code>
<p>
If <var>elm</var> is a straight line program element whose straight line
representation is very long, this operation changes the
representation of <var>elm</var> to a straight line program element, equal to
<var>elm</var>, whose seed contains the evaluation of <var>elm</var> and whose straight
line program has length 1.
<p>
For other objects nothing happens.
<p>
This operation permits to designate ``important'' elements within an
algorithm (elements that wil be referred to often), which will be
represented by guaranteed short straight line program elements.
<p>
<pre>
gap> gens:=StraightLineProgGens([(1,2,3,4),(1,2)]);
[ <[ [ 2, 1 ] ]|(1,2,3,4)>, <[ [ 1, 1 ] ]|(1,2)> ]
gap> g:=Group(gens);;
gap> (gens[1]^3)^gens[2];
<[ [ 1, -1, 2, 3, 1, 1 ] ]|(1,2,4,3)>
gap> Size(g);
24
gap> Random(g);
<[ [ 1, -1, 2, -1, 1, 1, 2, -1, 1, -1, 2, 1, 1, 1, 2, 1, 1, -1, 2, 2, 1, 1 ],
[ 3, -2, 2, -2, 1, -1, 2, -2, 1, 1, 2, -1, 1, -1, 2, -2, 1, 1, 2, -1, 1,
-1, 2, -1, 1, 1, 2, 1, 1, -1, 2, 1, 1, 1 ] ]>
</pre>
<p>
See also Section <a href="CHAP041.htm#SECT012">Working with large degree permutation groups</a>.
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP034.htm">Previous</a>] [<a href ="CHAP036.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
177
