<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (IdRel) - Chapter 2: Rewriting Systems</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X7CA8FCFD81AA1890" name="X7CA8FCFD81AA1890"></a></p>
<div class="ChapSects"><a href="chap2.html#X7CA8FCFD81AA1890">2 <span class="Heading">Rewriting Systems</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7C9AE9BC78CCBFAA">2.1 <span class="Heading">Identity Y-sequences</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7875619E84157FC1">2.2 <span class="Heading">Monoid Presentations of FpGroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X868422B878B0C380">2.2-1 FreeRelatorGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7CBE13927DFF4446">2.2-2 MonoidPresentationFpGroup</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7A1F10597D8FC9A9">2.3 <span class="Heading">Rewriting systems for FpGroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X858ECE3E807C7363">2.3-1 RewritingSystemFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X83BD6C0A80D88C2C">2.3-2 OnePassReduceWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7F0CD1EB7C220D40">2.3-3 OnePassKB</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X83CBF2BE8478A728">2.4 <span class="Heading">Enumerating elements</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7EDA50068207339D">2.4-1 ElementsOfMonoidPresentation</a></span>
</div>
</div>
<h3>2 <span class="Heading">Rewriting Systems</span></h3>
<p>This chapter describes functions to construct rewriting systems for finitely presented groups which store rewriting information. The main example used is a presentation of the quaternion group <code class="code">q8</code> with generators a,b and relators [a^4, b^4, abab^-1, a^2b^2].</p>
<p><a id="X7C9AE9BC78CCBFAA" name="X7C9AE9BC78CCBFAA"></a></p>
<h4>2.1 <span class="Heading">Identity Y-sequences</span></h4>
<p>A typical input for <strong class="pkg">IdRel</strong> is an fp-group presentation. This requires a free group <code class="code">F</code> on a set of generators and a set of relators <code class="code">R</code> (words in the free group). The module of identities among relators for this presentation has as its elements the Peiffer equivalence classes of all products of conjugates of relators which represent the identity in the free group.</p>
<p>In this package the identities among relators are represented by Y-sequences, which are lists [[r_1, u_1],...,[r_k,u_k]] where r_1,...,r_k are the group relators or their inverses, and u_1,...,u_k are words in the free group <code class="code">F</code>. A Y-sequence is evaluated in <code class="code">F</code> as the product (u_1^-1r_1u_1)...(u_k^-1r_ku_k) and is an identity Y-sequence if it evaluates to the identity in <code class="code">F</code>. An identity Y-sequence represents an identity among the relators of the group presentation. The main function of the package is to produce a set of Y-sequences which generate the module of identites among relators, and further, that this set be minimal in the sense that every element in it is needed to generate the module.</p>
<p>Before starting on the main example, we consider a simpler example illustrating the use of <strong class="pkg">IdRel</strong>. All the functions used are described in detail in this manual. We compute a reduced set of identities among relators for the presentation of the symmetric group <code class="code">s3</code> with generators a,b and relators [a^3 , b^2, (ab)^2]. In the listing below, <code class="code">s3_M1</code> is the first monoid generator for <code class="code">s3</code>, <code class="code">s3_R2</code> is the second relator, while <code class="code">s3_Y4</code> is the fourth Y-sequence for <code class="code">s3</code>.</p>
<table class="example">
<tr><td><pre>
gap> F := FreeGroup( 2 );;
gap> a := F.l;; b:= F.2;;
gap> rels3 := [ a^3 , b^2, a*b*a*b];
[ fl^3 , f2^2, fl*f2*fl*f2]
gap> s3 := F/rels3;
<fp group on the generators [ fl, f2 ]>
gap> SetName( s3, "s3" );
gap> idy3 := IdentityYSequences( s3 );;
gap> Length( idy3 );
18
gap> Y4 := idy3[4];
[ [ s3_R1^-1, f1^-1 ], [ s3_R1, <identity ...> ] ]
gap> Y6 := idy3[6];
[ [ s3_R3^-1, f1^-1 ], [ s3_R1, <identity ...> ], [ s3_R3^-1, f1 ],
[ s3_R2, f1^-1*f2^-1 ], [ s3_R1, f2^-1 ], [ s3_R3^-1, f1*f2^-1 ],
[ s3_R2, <identity ...> ], [ s3_R2, f1^-1 ] ]
gap> Y7 := idy3[7];
[ [ s3_R3^-1, f1*f2^-1 ], [ s3_R2, <identity ...> ], [ s3_R3, <identity ...> ],
[ s3_R2^-1, <identity ...> ] ]
gap> Y8 := idy3[8];
[ [ s3_R2^-1, f2^-1 ], [ s3_R2, <identity ...> ] ]
</pre></td></tr></table>
<p>Of the 18 Y-sequences formed, 6 are empty, and <code class="code">Y4</code> is the <em>root identity</em> <code class="code">((a^3)^-1)^(a^-1).(a^3)</code>. If we write r=a^3, s=b^2, t=(ab)^2 then <code class="code">Y4</code> is <code class="code">(r^-1)^(a^-1).r</code>. Similarly, <code class="code">Y8</code> is the second root identity <code class="code">(s^-1)^(b^-1).s</code>, while <code class="code">Y7</code> is the third root identity <code class="code">(t^-1)^(ab^-1).t</code>. The identity <code class="code">Y6</code>, which is not a root identity, is obtained by walking around the Schreier diagram of the presentation, which is a somewhat truncated triangular prism, taking the appropriate conjugate of each face in turn: <code class="code"> Y6=(t^-1)^(a^-1).r.(t^-1)^a.s^(a^-1b^-1).r^(b^-1).(t^-1)^(ab^-1).s.s^(a^-1) </code>. These four identities generate the module of identities for <code class="code">s3</code>.</p>
<table class="example">
<tr><td><pre>
gap> idrels3 := IdentitiesAmongRelators( s3 );;
gap> Display( idrels3[1] );
[ ( s3_Y4*( s3_M2*s3_M1), s3_R1*( s3_M1 - <identity ...>) ),
( s3_Y8*( s3_M2*s3_M1), s3_R2*( s3_M2 - <identity ...>) ),
( s3_Y7*( s3_M2*s3_M1), s3_R3*( s3_M2 - s3_M1) ),
( s3_Y6*( -s3_M2*s3_M1), s3_R1*( -s3_M2*s3_M1 - s3_M1) + s3_R2*( -s3_M1*s3_M\
2 - s3_M1 - <identity ...>) + s3_R3*( s3_M3 + s3_M2 + <identity ...>) )
]
</pre></td></tr></table>
<p><a id="X7875619E84157FC1" name="X7875619E84157FC1"></a></p>
<h4>2.2 <span class="Heading">Monoid Presentations of FpGroups</span></h4>
<p><a id="X868422B878B0C380" name="X868422B878B0C380"></a></p>
<h5>2.2-1 FreeRelatorGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FreeRelatorGroup</code>( <var class="Arg">grp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FreeRelatorHomomorphism</code>( <var class="Arg">grp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The function <code class="code">FreeRelatorGroup</code> returns a free group on the set of relators of the given fp-group <code class="code">G</code>. If <code class="code">HasName(G)</code> is <code class="code">true</code> then a name is automatically assigned to the free group.</p>
<p>The function <code class="code">FreeRelatorHomomorphism</code> returns the group homomorphism from the free group on the relators to the free group on the generators of <code class="code">G</code>, mapping each generator to the corresponding word.</p>
<table class="example">
<tr><td><pre>
gap> F := FreeGroup( 2 );;
gap> a := F.1;; b:= F.2;;
gap> rels := [ a^4, b^4, a*b*a*b^-1, a^2*b^2];;
gap> q8 := F/rels;;
gap> SetName( q8, "q8" );
gap> frq8 := FreeRelatorGroup( q8 );
q8_R
gap> GeneratorsOfGroup( frq8 );
[ q8_R1, q8_R2, q8_R3, q8_R4]
gap> frhomq8 := FreeRelatorHomomorphism( q8 );
[ q8_R1, q8_R2, q8_R3, q8_R4] -> [ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2]
</pre></td></tr></table>
<p><a id="X7CBE13927DFF4446" name="X7CBE13927DFF4446"></a></p>
<h5>2.2-2 MonoidPresentationFpGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MonoidPresentationFpGroup</code>( <var class="Arg">grp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FreeGroupOfPresentation</code>( <var class="Arg">mon</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GroupRelatorsOfPresentation</code>( <var class="Arg">mon</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> InverseRelatorsOfPresentation</code>( <var class="Arg">mon</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HomomorphismOfPresentation</code>( <var class="Arg">mon</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>A monoid presentation for a finitely presented group <code class="code">G</code> has two monoid generators g^+,g^- for each group generator g. The relators of the monoid presentation comprise the group relators, and relators g^+g^- specifying the inverses. The function <code class="code">MonoidPresentationFpGroup</code> returns the monoid presentation derived in this way from an fp-presentation. (Note: this function should always be followed by a double semicolon -- <code class="code">MonoidPresentationFpGroup(G);;</code> -- because an error occurs in attempting to display the results on the screen: the <code class="code">ElementsFamily</code> needs to be fixed.)</p>
<p>The function <code class="code">FreeGroupOfPresentation</code> returns the free group on the monoid generators.</p>
<p>The function <code class="code">GroupRelatorsOfPresentation</code> returns those relators of the monoid which correspond to the relators of the group. All negative powers in the group relators are converted to positive powers of the g^-.</p>
<p>The function <code class="code">InverseRelatorsOfPresentation</code> returns relators which specify the inverse pairs of the monoid generators.</p>
<p>The function <code class="code">HomomorphismOfPresentation</code> returns the homomorphism from the free group of the monoid presentation to the free group of the group presentation.</p>
<p>In the example below, the four monoid generators a^+, b^+, a^-, b^- are named <code class="code">q8\_M1, q8\_M2, q8\_M3, q8\_M4</code>.</p>
<table class="example">
<tr><td><pre>
gap> mon := MonoidPresentationFpgroup( q8 );;
gap> fgmon := FreeGroupOfPresentation( mon);
<free group on the generators [ q8_Ml, q8_M2, q8_M3, q8_M4]>
gap> genfgmon := GeneratorsOfGroup( fgmon);
[ q8_Ml, q8_M2, q8_M3, q8_M4]
gap> gprels := GroupRelatorsOfPresentation( mon );
[ q8_Ml^4, q8_M2^4, q8_Ml*q8_M2*q8_Ml*q8_M4, q8_Ml^2*q8_M2^2]
gap> invrels := InverseRelatorsOfPresentation( mon);
[ q8_Ml*q8_M3, q8_M2*q8_M4, q8_M3*q8_Ml, q8_M4*q8_M2]
gap> hompres := HomomorphismOfPresentation( mon );
[ q8_Ml, q8_M2, q8_M3, q8_M4] -> [ fl, f2, fl^-l, f2^-1 ]
</pre></td></tr></table>
<p><a id="X7A1F10597D8FC9A9" name="X7A1F10597D8FC9A9"></a></p>
<h4>2.3 <span class="Heading">Rewriting systems for FpGroups</span></h4>
<p>These functions duplicate the standard Knuth Bendix functions which are available in the <strong class="pkg">GAP</strong> library. There are two reasons for this: (1) these functions were first written before the standard functions were available; (2) we require logged versions of the functions, and these are most conveniently extended versions of the non-logged code.</p>
<p><a id="X858ECE3E807C7363" name="X858ECE3E807C7363"></a></p>
<h5>2.3-1 RewritingSystemFpGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RewritingSystemFpGroup</code>( <var class="Arg">grp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>This function attempts to return a complete rewrite system for the group <code class="code">G</code> obtained from the monoid presentation <code class="code">mon</code>, with a length-lexicographical ordering on the words in <code class="code">fgmon</code>, by applying Knuth-Bendix completion. Such a rewrite system can be obtained for all finite groups. The rewrite rules are (partially) ordered, starting with the inverse relators, followed by the rules which reduce the word length the most.</p>
<p>In our <code class="code">q8</code> example there are 16 rewrite rules.</p>
<table class="example">
<tr><td><pre>
gap> rws := RewritingSystemFpGroup( q8 );
[ [q8_Ml*q8_M3, <identity ...>], [ q8_M2*q8_M4, <identity ...> ],
[q8_M3*q8_Ml, <identity ...>], [ q8_M4*q8_M2, <identity ...> ],
[q8_M1^2*q8_M4, q8_M2], [q8_Ml^2*q8_M2, q8_M4], [ q8_Ml^3, q8_M3 ],
[ q8_M4^2, q8_Ml^2], [ q8_M4*q8_M3, q8_Ml*q8_M4],
[ q8_M4*q8_Ml, q8_Ml*q8_M2], [q8_M3*q8_M4, q8_Ml*q8_M2],
[ q8_M3^2, q8_Ml^2], [q8_M3*q8_M2, q8_Ml*q8_M4],
[ q8_M2*q8_M3, q8_Ml*q8_M2], [q8_M2^2, q8_Ml^2],
[ q8_M2*q8_Ml, q8_Ml*q8_M4] ]
</pre></td></tr></table>
<p>The functions called by <code class="code">RewritingSystemFpGroup</code> are as follows.</p>
<p><a id="X83BD6C0A80D88C2C" name="X83BD6C0A80D88C2C"></a></p>
<h5>2.3-2 OnePassReduceWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> OnePassReduceWord</code>( <var class="Arg">word, rules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ReduceWordKB</code>( <var class="Arg">word, rules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Assuming that <code class="code">word</code> is an element of a free monoid and <code class="code">rules</code> is a list of ordered pairs of such words, the function <code class="code">OnePassReduceWord</code> searches the list of rules until it finds that the left-hand side of a <code class="code">rule</code> is a <code class="code">subword</code> of <code class="code">word</code>, whereupon it replaces that <code class="code">subword</code> with the right-hand side of the matching rule. The search is continued from the next <code class="code">rule</code> in <code class="code">rules</code>, but using the new <code class="code">word</code>. When the end of <code class="code">rules</code> is reached, one pass is considered to have been made and the reduced <code class="code">word</code> is returned. If no matches are found then the original <code class="code">word</code> is returned.</p>
<p>The function <code class="code">ReduceWordKB</code> repeatedly applies the function <code class="code">OnePassReduceWord</code> until the <code class="code">word</code> remaining contains no left-hand side of a <code class="code">rule</code> as a <code class="code">subword</code>. If <code class="code">rules</code> is a complete rewrite system, then the irreducible <code class="code">word</code> that is returned is unique, otherwise the order of the rules in <code class="code">rules</code> will determine which irreducible word is returned. In the example we see that b^9a^9 reduces to ba, and we shall see later that this is not a normal form.</p>
<table class="example">
<tr><td><pre>
gap> monrels := Concatenation( gprels, invrels );
[ q8_Ml^4, q8_M2^4, q8_Ml*q8_M2*q8_Ml*q8_M4, q8_Ml^2*q8_M2^2, q8_Ml*q8_M3,
q8_M2*q8_M4, q8_M3*q8_Ml, q8_M4*q8_M2]
gap> id := One( monrels[l] );;
gap> r0 := List( monrels, r -> [ r, id ] );
[ [ q8_Ml^4, <identity ...> ], [ q8_M2^4, <identity. ..> ],
[ q8_Ml*q8_M2*q8_Ml*q8_M4, <identity ...> ],
[ q8_Ml^2*q8_M2^2, <identity. ..>], [ q8_Ml*q8_M3, <identity ...> ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity. ..>],
[ q8_M4*q8_M2, <identity ...> ] ]
gap> ap := genfgmon[l];; bp := genfgmon[2];; ## p for plus
gap> am := genfgmon[3];; bm := genfgmon[4];; ## m for minus
gap> w0 := bp^9 * ap^9;
q8_M2^9*q8_M1^9
gap> w1 := OnePassReduceWord( w0, r0 );
q8_M2^5*q8_M1^5
gap> w2 := ReduceWordKB( w0, r0 );
q8_M2*q8_M1
</pre></td></tr></table>
<p><a id="X7F0CD1EB7C220D40" name="X7F0CD1EB7C220D40"></a></p>
<h5>2.3-3 OnePassKB</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> OnePassKB</code>( <var class="Arg">rules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RewriteReduce</code>( <var class="Arg">rules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KnuthBendix</code>( <var class="Arg">rules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ShorterRule</code>( <var class="Arg">rule1, rule2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The function <code class="code">OnePassKB</code> implements the main loop of the Knuth-Bendix completion algorithm. Rules are compared with each other; all critical pairs are calculated; and the irreducible critical pairs are orientated with respect to the length-lexicographical ordering and added to the rewrite system.</p>
<p>The function <code class="code">RewriteReduce</code> will remove unnecessary rules from a rewrite system. A rule is deemed to be unnecessary if it is implied by the other rules, i.e. if both sides can be reduced to the same thing by the remaining rules.</p>
<p>The function <code class="code">KnuthBendix</code> implements the Knuth-Bendix algorithm, attempting to complete a rewrite system with respect to a length-lexicographic ordering. It calls first <code class="code">OnePassKB</code>, which adds rules, and then (for efficiency) <code class="code">RewriteReduce</code> which removes any unnecessary ones. This procedure is repeated until <code class="code">OnePassKB</code> adds no more rules. It will not always terminate, but for many examples (all finite groups) it will be successful. The rewrite system returned is complete, that is: it will rewrite any given word in the free monoid to a unique irreducible; there is one irreducible for each element of the quotient monoid; and any two elements of the free monoid which are in the same class will rewrite to the same irreducible.</p>
<p>The function <code class="code">ShorterRule</code> gives an ordering on rules. Rules (g_lg_2,id) that identify two generators (or one generator with the inverse of another) come first in the ordering. Otherwise one precedes another if it reduces the length of a word by a greater amount.</p>
<p>One pass of this procedure for our <code class="code">q8</code> example adds 13 relators to the original 8, and these 21 are then reduced to 9. A second pass and reduction gives a list of 16 rules which forms a complete rewrite system for the group.</p>
<table class="example">
<tr><td><pre>
gap> r1 := OnePassKB( r0 );
[ [ q8_Ml^4, <identity ...> ], [ q8_M2^4, <identity ...> ],
[ q8_Ml*q8_M2*q8_Ml*q8_M4, <identity ...> ],
[ q8_Ml^2*q8_M2^2, <identity. ..> ], [ q8_Ml*q8_M3, <identity ...> ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ],
[ q8_M4*q8_M2, <identity ...> ], [ q8_M2*q8_Ml*q8_M4, q8_Ml^3],
[ q8_Ml*q8_M2^2, q8_Ml^3 ], [ q8_M2^2, q8_Ml^2 ], [q8_Ml^3, q8_M3 ],
[ q8_M2^3, q8_M4 ], [ q8_Ml*q8_M2*q8_Ml, q8_M2],
[ q8_M2^3, q8_Ml^2*q8_M2], [ q8_M2^2, q8_Ml^2 ], [q8_Ml^2*q8_M2, q8_M4 ],
[ q8_Ml^3, q8_M3 ], [ q8_M2*q8_Ml*q8_M4, q8_M3 ], [q8_Ml*q8_M2^2, q8_M3 ],
[ q8_M2^3, q8_M4 ] ]
gap> r1 := RewriteReduce( r1 );
[ [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2^2, q8_Ml^2 ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ],
[ q8_M4*q8_M2, <identity ...> ], [ q8_Ml^3, q8_M3 ],
[ q8_Ml^2*q8_M2, q8_M4 ], [ q8_Ml*q8_M2*q8_Ml, q8_M2 ],
[ q8_M2*q8_Ml*q8_M4, q8_M3 ] ]
gap> r2 := KnuthBendix( r1 );
[ [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2*q8_Ml, q8_Ml*q8_M4 ],
[ q8_M2^2, q8_Ml^2], [ q8_M2*q8_M3, q8_Ml*q8_M2 ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ],
[ q8_M3*q8_M2, q8_Ml*q8_M4 ], [ q8_M3^2, q8_Ml^2 ],
[ q8_M3*q8_M4, q8_Ml*q8_M2 ], [ q8_M4*q8_Ml, q8_Ml*q8_M2 ],
[ q8_M4*q8_M2, <identity ...> ], [ q8_M4*q8_M3, q8_Ml*q8_M4 ],
[ q8_M4^2, q8_Ml^2], [ q8_Ml^3, q8_M3 ], [q8_Ml^2*q8_M2, q8_M4 ],
[ q8_Ml^2*q8_M4, q8_M2 ] ]
gap> w2 := ReduceWordKB( w0, r2 );
q8_M1*q8_M4
</pre></td></tr></table>
<p><a id="X83CBF2BE8478A728" name="X83CBF2BE8478A728"></a></p>
<h4>2.4 <span class="Heading">Enumerating elements</span></h4>
<p><a id="X7EDA50068207339D" name="X7EDA50068207339D"></a></p>
<h5>2.4-1 ElementsOfMonoidPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ElementsOfMonoidPresentation</code>( <var class="Arg">mon</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The function <code class="code">ElementsOfMonoidPresentation</code> returns a list of normal forms for the elements of the group given by the monoid presentation <code class="code">mon</code>. The normal forms are the least elements in each equivalence class (with respect to length-lex order). When <code class="code">rules</code> is a complete rewrite system for <code class="code">G</code> the list returned is a set of normal forms for the group elements.</p>
<table class="example">
<tr><td><pre>
gap> elq8 := Elements( q8 );
[ <identity .. .>, fl, f2, fl^2, fl*f2, fl^3*f2, fl^3, fl^2*f2 ]
gap> elmonq8 := ElementsOfMonoidPresentation( monq8 );
[ <identity. ..>, q8_Ml, q8_M2, q8_M3, q8_M4, q8_Ml^2, q8_Ml*q8_M2,
q8_Ml*q8_M4 ]
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1537
