/usr/share/gap/doc/ref/chap53.html is in gap-doc 4r6p5-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 | <?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 (ref) - Chapter 53: Finitely Presented Semigroups and Monoids</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" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap53" onload="jscontent()">
<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="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chap19.html">19</a> <a href="chap20.html">20</a> <a href="chap21.html">21</a> <a href="chap22.html">22</a> <a href="chap23.html">23</a> <a href="chap24.html">24</a> <a href="chap25.html">25</a> <a href="chap26.html">26</a> <a href="chap27.html">27</a> <a href="chap28.html">28</a> <a href="chap29.html">29</a> <a href="chap30.html">30</a> <a href="chap31.html">31</a> <a href="chap32.html">32</a> <a href="chap33.html">33</a> <a href="chap34.html">34</a> <a href="chap35.html">35</a> <a href="chap36.html">36</a> <a href="chap37.html">37</a> <a href="chap38.html">38</a> <a href="chap39.html">39</a> <a href="chap40.html">40</a> <a href="chap41.html">41</a> <a href="chap42.html">42</a> <a href="chap43.html">43</a> <a href="chap44.html">44</a> <a href="chap45.html">45</a> <a href="chap46.html">46</a> <a href="chap47.html">47</a> <a href="chap48.html">48</a> <a href="chap49.html">49</a> <a href="chap50.html">50</a> <a href="chap51.html">51</a> <a href="chap52.html">52</a> <a href="chap53.html">53</a> <a href="chap54.html">54</a> <a href="chap55.html">55</a> <a href="chap56.html">56</a> <a href="chap57.html">57</a> <a href="chap58.html">58</a> <a href="chap59.html">59</a> <a href="chap60.html">60</a> <a href="chap61.html">61</a> <a href="chap62.html">62</a> <a href="chap63.html">63</a> <a href="chap64.html">64</a> <a href="chap65.html">65</a> <a href="chap66.html">66</a> <a href="chap67.html">67</a> <a href="chap68.html">68</a> <a href="chap69.html">69</a> <a href="chap70.html">70</a> <a href="chap71.html">71</a> <a href="chap72.html">72</a> <a href="chap73.html">73</a> <a href="chap74.html">74</a> <a href="chap75.html">75</a> <a href="chap76.html">76</a> <a href="chap77.html">77</a> <a href="chap78.html">78</a> <a href="chap79.html">79</a> <a href="chap80.html">80</a> <a href="chap81.html">81</a> <a href="chap82.html">82</a> <a href="chap83.html">83</a> <a href="chap84.html">84</a> <a href="chap85.html">85</a> <a href="chap86.html">86</a> <a href="chap87.html">87</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="chap0.html#contents">[Contents]</a> <a href="chap52.html">[Previous Chapter]</a> <a href="chap54.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap53_mj.html">[MathJax on]</a></p>
<p><a id="X7DE7C52A7C4BDADE" name="X7DE7C52A7C4BDADE"></a></p>
<div class="ChapSects"><a href="chap53.html#X7DE7C52A7C4BDADE">53 <span class="Heading">Finitely Presented Semigroups and Monoids</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X78C80F1A84C58E1E">53.1 <span class="Heading">IsSubsemigroupFpSemigroup (Filter)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X8496E23C80453C33">53.1-1 IsSubsemigroupFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X82128D4D83ACA683">53.1-2 IsSubmonoidFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X8239EF2B853411E9">53.1-3 IsFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7C2BA01D86087D11">53.1-4 IsFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X81ABBE997A4C19B7">53.1-5 IsElementOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7A570B89862C7399">53.1-6 IsElementOfFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7DC8A5D380AFE5DB">53.1-7 FpGrpMonSmgOfFpGrpMonSmgElement</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X84B8E3257E2E4134">53.2 <span class="Heading">Creating Finitely Presented Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7D3B9E317DD5AC8A">53.2-1 \/</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X822F04B2833BE254">53.2-2 FactorFreeSemigroupByRelations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X869F966B8196F28C">53.2-3 IsomorphismFpSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X85E7C8407C9D5FBE">53.3 <span class="Heading">Comparison of Elements of Finitely Presented Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7DD9D81F863EBE31">53.3-1 \=</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X7D3EA628804E05D4">53.4 <span class="Heading">Preimages in the Free Semigroup</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X818E25C887512E89">53.4-1 UnderlyingElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X847012347856C55E">53.4-2 ElementOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X8726523779601873">53.4-3 FreeSemigroupOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X79A39402806B5EB7">53.4-4 FreeGeneratorsOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X862BE9FA7C987CAB">53.4-5 RelationsOfFpSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X7E79A80382563C26">53.5 <span class="Heading">Finitely presented monoids</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X82B5E4A27AAB6749">53.5-1 \/</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X87693BDC79DC6EBF">53.6 <span class="Heading">Rewriting Systems and the Knuth-Bendix Procedure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7D8F804E814D894D">53.6-1 ReducedConfluentRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7A3F8AE285C41D80">53.6-2 KB_REW</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X87A3823483E4FF86">53.6-3 <span class="Heading">KnuthBendixRewritingSystem</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7966343587A04AFF">53.6-4 SemigroupOfRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7EAB3E067D7557F6">53.6-5 MonoidOfRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X80B8115C8147F605">53.6-6 FreeSemigroupOfRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X84CE48BE7F870808">53.6-7 FreeMonoidOfRewritingSystem</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap53.html#X812C28217F3E6720">53.7 <span class="Heading">Todd-Coxeter Procedure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap53.html#X7C24508A7F677520">53.7-1 CosetTableOfFpSemigroup</a></span>
</div></div>
</div>
<h3>53 <span class="Heading">Finitely Presented Semigroups and Monoids</span></h3>
<p>A <em>finitely presented semigroup</em> (resp. <em>finitely presented monoid</em>) is a quotient of a free semigroup (resp. free monoid) on a finite number of generators over a finitely generated congruence on the free semigroup (resp. free monoid).</p>
<p>Finitely presented semigroups are obtained by factoring a free semigroup by a set of relations (a generating set for the congruence), i.e., a set of pairs of words in the free semigroup.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=FreeSemigroup("a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=GeneratorsOfSemigroup(f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=f/[ [x[1]*x[2],x[2]*x[1]] ];</span>
<fp semigroup on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup(s);</span>
[ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfFpSemigroup(s);</span>
[ [ a*b, b*a ] ]
</pre></div>
<p>Finitely presented monoids are obtained by factoring a free monoid by a set of relations, i.e. a set of pairs of words in the free monoid.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=FreeMonoid("a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=GeneratorsOfMonoid(f);</span>
[ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">e:=Identity(f);</span>
<identity ...>
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=f/[ [x[1]*x[2],e] ];</span>
<fp monoid on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfFpMonoid(m);</span>
[ [ a*b, <identity ...> ] ]
</pre></div>
<p>Notice that for <strong class="pkg">GAP</strong> a finitely presented monoid is not a finitely presented semigroup.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFpSemigroup(m);</span>
false
</pre></div>
<p>However, one can build a finitely presented semigroup isomorphic to that finitely presented monoid (see <code class="func">IsomorphismFpSemigroup</code> (<a href="chap53.html#X869F966B8196F28C"><span class="RefLink">53.2-3</span></a>)).</p>
<p>Also note that is not possible to refer to the generators by their names. These names are not variables, but just display figures. So, if one wants to access the generators by their names, one first has to introduce the respective variables and to assign the generators to them.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Unbind(a);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=FreeSemigroup("a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=GeneratorsOfSemigroup(f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=f/[ [x[1]*x[2],x[2]*x[1]] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a;</span>
Error, Variable: 'a' must have a value
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=GeneratorsOfSemigroup(s)[1];</span>
a
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=GeneratorsOfSemigroup(s)[2];</span>
b
<span class="GAPprompt">gap></span> <span class="GAPinput">a in f;</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">a in s;</span>
true
</pre></div>
<p>The generators of the free semigroup (resp. free monoid) are different from the generators of the finitely presented semigroup (resp. finitely presented monoid) (even though they are displayed by the same names). This means that words in the generators of the free semigroup (resp. free monoid) are not elements of the finitely presented semigroup (resp. finitely presented monoid). Conversely elements of the finitely presented semigroup (resp. finitely presented monoid) are not words of the free semigroup (resp. free monoid).</p>
<p>Calculations comparing elements of an finitely presented semigroup may run into problems: there are finitely presented semigroups for which no algorithm exists (it is known that no such algorithm can exist) that will tell for two arbitrary words in the generators whether the corresponding elements in the finitely presented semigroup are equal. Therefore the methods used by <strong class="pkg">GAP</strong> to compute in finitely presented semigroups may run into warning errors, run out of memory or run forever. If the finitely presented semigroup is (by theory) known to be finite the algorithms are guaranteed to terminate (if there is sufficient memory available), but the time needed for the calculation cannot be bounded a priori. The same can be said for monoids. (See <a href="chap53.html#X87693BDC79DC6EBF"><span class="RefLink">53.6</span></a>.)</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a*b=a^5;</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">a^5*b^2*a=a^6*b^2;</span>
true
</pre></div>
<p>Note that elements of a finitely presented semigroup (or monoid) are not printed in a unique way:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a^5*b^2*a;</span>
a^5*b^2*a
<span class="GAPprompt">gap></span> <span class="GAPinput">a^6*b^2;</span>
a^6*b^2
</pre></div>
<p><a id="X78C80F1A84C58E1E" name="X78C80F1A84C58E1E"></a></p>
<h4>53.1 <span class="Heading">IsSubsemigroupFpSemigroup (Filter)</span></h4>
<p><a id="X8496E23C80453C33" name="X8496E23C80453C33"></a></p>
<h5>53.1-1 IsSubsemigroupFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubsemigroupFpSemigroup</code>( <var class="Arg">t</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>true if <var class="Arg">t</var> is a finitely presented semigroup or a subsemigroup of a finitely presented semigroup (generally speaking, such a subsemigroup can be constructed with <code class="code">Semigroup(<var class="Arg">gens</var>)</code>, where <var class="Arg">gens</var> is a list of elements of a finitely presented semigroup).</p>
<p><a id="X82128D4D83ACA683" name="X82128D4D83ACA683"></a></p>
<h5>53.1-2 IsSubmonoidFpMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubmonoidFpMonoid</code>( <var class="Arg">t</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>true if <var class="Arg">t</var> is a finitely presented monoid or a submonoid of a finitely presented monoid (generally speaking, such a semigroup can be constructed with <code class="code">Monoid(<var class="Arg">gens</var>)</code>, where <var class="Arg">gens</var> is a list of elements of a finitely presented monoid).</p>
<p>A submonoid of a monoid has the same identity as the monoid.</p>
<p><a id="X8239EF2B853411E9" name="X8239EF2B853411E9"></a></p>
<h5>53.1-3 IsFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFpSemigroup</code>( <var class="Arg">s</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is a synonym for <code class="code">IsSubsemigroupFpSemigroup(<var class="Arg">s</var>)</code> and <code class="code">IsWholeFamily(<var class="Arg">s</var>)</code> (this is because a subsemigroup of a finitely presented semigroup is not necessarily finitely presented).</p>
<p><a id="X7C2BA01D86087D11" name="X7C2BA01D86087D11"></a></p>
<h5>53.1-4 IsFpMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFpMonoid</code>( <var class="Arg">m</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is a synonym for <code class="code">IsSubmonoidFpMonoid(<var class="Arg">m</var>)</code> and <code class="code">IsWholeFamily(<var class="Arg">m</var>)</code> (this is because a submonoid of a finitely presented monoid is not necessarily finitely presented).</p>
<p><a id="X81ABBE997A4C19B7" name="X81ABBE997A4C19B7"></a></p>
<h5>53.1-5 IsElementOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsElementOfFpSemigroup</code>( <var class="Arg">elm</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>returns true if <var class="Arg">elm</var> is an element of a finitely presented semigroup.</p>
<p><a id="X7A570B89862C7399" name="X7A570B89862C7399"></a></p>
<h5>53.1-6 IsElementOfFpMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsElementOfFpMonoid</code>( <var class="Arg">elm</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>returns true if <var class="Arg">elm</var> is an element of a finitely presented monoid.</p>
<p><a id="X7DC8A5D380AFE5DB" name="X7DC8A5D380AFE5DB"></a></p>
<h5>53.1-7 FpGrpMonSmgOfFpGrpMonSmgElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FpGrpMonSmgOfFpGrpMonSmgElement</code>( <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the finitely presented group, monoid or semigroup to which <var class="Arg">elm</var> belongs</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeSemigroup("a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := f / [ [ a^2 , a*b ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFpSemigroup( s );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">t := Semigroup( [ GeneratorsOfSemigroup( s )[ 1 ] ]);</span>
<semigroup with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubsemigroupFpSemigroup( t );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsElementOfFpSemigroup( GeneratorsOfSemigroup( t )[ 1 ] );</span>
true
</pre></div>
<p><a id="X84B8E3257E2E4134" name="X84B8E3257E2E4134"></a></p>
<h4>53.2 <span class="Heading">Creating Finitely Presented Semigroups</span></h4>
<p><a id="X7D3B9E317DD5AC8A" name="X7D3B9E317DD5AC8A"></a></p>
<h5>53.2-1 \/</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \/</code>( <var class="Arg">F</var>, <var class="Arg">rels</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>creates a finitely presented semigroup given by the presentation <span class="SimpleMath">⟨ gens ∣ <var class="Arg">rels</var> ⟩</span> where <span class="SimpleMath">gens</span> are the generators of the free semigroup <var class="Arg">F</var>, and the relations <var class="Arg">rels</var> are entered as pairs of words in the generators of the free semigroup.</p>
<p>The same result is obtained with the infix operator <code class="code">/</code>, i.e., as <var class="Arg">F</var> <code class="code">/</code> <var class="Arg">rels</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=FreeSemigroup(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=GeneratorsOfSemigroup(f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f/[ [s[1]*s[2]*s[1],s[1]] , [s[2]^4,s[1]] ];</span>
<fp semigroup on the generators [ s1, s2, s3 ]>
</pre></div>
<p><a id="X822F04B2833BE254" name="X822F04B2833BE254"></a></p>
<h5>53.2-2 FactorFreeSemigroupByRelations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FactorFreeSemigroupByRelations</code>( <var class="Arg">f</var>, <var class="Arg">rels</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>for a free semigroup <var class="Arg">f</var> and <var class="Arg">rels</var> is a list of pairs of elements of <var class="Arg">f</var>. Returns the finitely presented semigroup which is the quotient of <var class="Arg">f</var> by the least congruence on <var class="Arg">f</var> generated by the pairs in <var class="Arg">rels</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FactorFreeSemigroupByRelations(f,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [[s[1]*s[2]*s[1],s[1]],[s[2]^4,s[1]]]);</span>
<fp semigroup on the generators [ s1, s2, s3 ]>
</pre></div>
<p><a id="X869F966B8196F28C" name="X869F966B8196F28C"></a></p>
<h5>53.2-3 IsomorphismFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismFpSemigroup</code>( <var class="Arg">s</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>for a semigroup <var class="Arg">s</var> returns an isomorphism from <var class="Arg">s</var> to a finitely presented semigroup</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeGroup(2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := f/[f.1^4,f.2^5];</span>
<fp group on the generators [ f1, f2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := IsomorphismFpSemigroup(g);</span>
MappingByFunction( <fp group on the generators
[ f1, f2 ]>, <fp semigroup on the generators
[ <identity ...>, f1^-1, f1, f2^-1, f2
]>, function( x ) ... end, function( x ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">s := Range(phi);</span>
<fp semigroup on the generators [ <identity ...>, f1^-1, f1, f2^-1,
f2 ]>
</pre></div>
<p><a id="X85E7C8407C9D5FBE" name="X85E7C8407C9D5FBE"></a></p>
<h4>53.3 <span class="Heading">Comparison of Elements of Finitely Presented Semigroups</span></h4>
<p><a id="X7DD9D81F863EBE31" name="X7DD9D81F863EBE31"></a></p>
<h5>53.3-1 \=</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \=</code>( <var class="Arg">a</var>, <var class="Arg">b</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Two elements <var class="Arg">a</var>, <var class="Arg">b</var> of a finitely presented semigroup are equal if they are equal in the semigroup. Nevertheless they may be represented as different words in the generators. Because of the fundamental problems mentioned in the introduction to this chapter such a test may take a very long time and cannot be guaranteed to finish (see <a href="chap53.html#X87693BDC79DC6EBF"><span class="RefLink">53.6</span></a>).</p>
<p><a id="X7D3EA628804E05D4" name="X7D3EA628804E05D4"></a></p>
<h4>53.4 <span class="Heading">Preimages in the Free Semigroup</span></h4>
<p>Elements of a finitely presented semigroup are not words, but are represented using a word from the free semigroup as representative.</p>
<p><a id="X818E25C887512E89" name="X818E25C887512E89"></a></p>
<h5>53.4-1 UnderlyingElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UnderlyingElement</code>( <var class="Arg">elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>for an element <var class="Arg">elm</var> of a finitely presented semigroup, it returns the word from the free semigroup that is used as a representative for <var class="Arg">elm</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeSemigroup( "a" , "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ];</span>
<fp semigroup on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">w := GeneratorsOfSemigroup(s)[1] * GeneratorsOfSemigroup(s)[2];</span>
a*b
<span class="GAPprompt">gap></span> <span class="GAPinput">IsWord (w );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ue := UnderlyingElement( w );</span>
a*b
<span class="GAPprompt">gap></span> <span class="GAPinput">IsWord( ue );</span>
true
</pre></div>
<p><a id="X847012347856C55E" name="X847012347856C55E"></a></p>
<h5>53.4-2 ElementOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementOfFpSemigroup</code>( <var class="Arg">fam</var>, <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>for a family <var class="Arg">fam</var> of elements of a finitely presented semigroup and a word <var class="Arg">w</var> in the free generators underlying this finitely presented semigroup, this operation creates the element of the finitely presented semigroup with the representative <var class="Arg">w</var> in the free semigroup.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">fam := FamilyObj( GeneratorsOfSemigroup(s)[1] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ge := ElementOfFpSemigroup( fam, a*b );</span>
a*b
<span class="GAPprompt">gap></span> <span class="GAPinput">ge in f;</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ge in s;</span>
true
</pre></div>
<p><a id="X8726523779601873" name="X8726523779601873"></a></p>
<h5>53.4-3 FreeSemigroupOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeSemigroupOfFpSemigroup</code>( <var class="Arg">s</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the underlying free semigroup for the finitely presented semigroup <var class="Arg">s</var>, ie, the free semigroup over which <var class="Arg">s</var> is defined as a quotient (this is the free semigroup generated by the free generators provided by <code class="code">FreeGeneratorsOfFpSemigroup(<var class="Arg">s</var>)</code>).</p>
<p><a id="X79A39402806B5EB7" name="X79A39402806B5EB7"></a></p>
<h5>53.4-4 FreeGeneratorsOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeGeneratorsOfFpSemigroup</code>( <var class="Arg">s</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the underlying free generators corresponding to the generators of the finitely presented semigroup <var class="Arg">s</var>.</p>
<p><a id="X862BE9FA7C987CAB" name="X862BE9FA7C987CAB"></a></p>
<h5>53.4-5 RelationsOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RelationsOfFpSemigroup</code>( <var class="Arg">s</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the relations of the finitely presented semigroup <var class="Arg">s</var> as pairs of words in the free generators provided by <code class="code">FreeGeneratorsOfFpSemigroup(<var class="Arg">s</var>)</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeSemigroup( "a" , "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ];</span>
<fp semigroup on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( s );</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">fs := FreeSemigroupOfFpSemigroup( s );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f = fs;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeGeneratorsOfFpSemigroup( s );</span>
[ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfFpSemigroup( s );</span>
[ [ a^3, a ], [ b^3, b ], [ a*b, b*a ] ]
</pre></div>
<p><a id="X7E79A80382563C26" name="X7E79A80382563C26"></a></p>
<h4>53.5 <span class="Heading">Finitely presented monoids</span></h4>
<p>The functionality available for finitely presented monoids is essentially the same as that available for finitely presented semigroups, and thus the previous sections apply (with the obvious changes) to finitely presented monoids.</p>
<p><a id="X82B5E4A27AAB6749" name="X82B5E4A27AAB6749"></a></p>
<h5>53.5-1 \/</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \/</code>( <var class="Arg">F</var>, <var class="Arg">rels</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>creates a finitely presented monoid given by the monoid presentation <span class="SimpleMath">⟨ <var class="Arg">gens</var> ∣ <var class="Arg">rels</var> ⟩</span> where <var class="Arg">gens</var> are the generators of the free monoid <var class="Arg">F</var>, and the relations <var class="Arg">rels</var> are entered as pairs of words in both the identity and the generators of the free monoid.</p>
<p>The same result is obtained with the infix operator <code class="code">/</code>, i.e., as <code class="code"><var class="Arg">F</var>/<var class="Arg">rels</var></code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeMonoid( 3 );</span>
<free monoid on the generators [ m1, m2, m3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := GeneratorsOfMonoid( f );</span>
[ m1, m2, m3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">e:= Identity ( f );</span>
<identity ...>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := f/[ [x[1]^3,e] , [x[1]*x[2],x[2] ]];</span>
<fp monoid on the generators [ m1, m2, m3 ]>
</pre></div>
<p><a id="X87693BDC79DC6EBF" name="X87693BDC79DC6EBF"></a></p>
<h4>53.6 <span class="Heading">Rewriting Systems and the Knuth-Bendix Procedure</span></h4>
<p>If a finitely presented semigroup has a confluent rewriting system then it has a solvable word problem, that is, there is an algorithm to decide when two words in the free underlying semigroup represent the same element of the finitely presented semigroup. Indeed, once we have a confluent rewriting system, it is possible to successfully test that two words represent the same element in the semigroup, by reducing both words using the rewriting system rules. This is, at the moment, the method that <strong class="pkg">GAP</strong> uses to check equality in finitely presented semigroups and monoids.</p>
<p><a id="X7D8F804E814D894D" name="X7D8F804E814D894D"></a></p>
<h5>53.6-1 ReducedConfluentRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReducedConfluentRewritingSystem</code>( <var class="Arg">S</var>[, <var class="Arg">ordering</var>] )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns a reduced confluent rewriting system of the finitely presented semigroup or monoid <var class="Arg">S</var> with respect to the reduction ordering <var class="Arg">ordering</var> (see <a href="chap34.html#X7E4AAA7382D42361"><span class="RefLink">34</span></a>).</p>
<p>The default for <var class="Arg">ordering</var> is the length plus lexicographic ordering on words, also called the shortlex ordering; for the definition see for example <a href="chapBib.html#biBSims94">[Sim94]</a>.</p>
<p>Notice that this might not terminate. In particular, if the semigroup or monoid <var class="Arg">S</var> does not have a solvable word problem then it this will certainly never end. Also, in this case, the object returned is an immutable rewriting system, because once we have a confluent rewriting system for a finitely presented semigroup or monoid we do not want to allow it to change (as it was most probably very time consuming to get it in the first place). Furthermore, this is also an attribute storing object (see <a href="chap13.html#X8698205F8648EB33"><span class="RefLink">13.4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeSemigroup( "a" , "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := f / [ [ a^2 , a*b ] , [ a^4 , b] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rws := ReducedConfluentRewritingSystem(g);</span>
Rewriting System for Semigroup( [ a, b ] ) with rules
[ [ a*b, a^2 ], [ a^4, b ], [ b*a, a^2 ], [ b^2, a^2 ] ]
</pre></div>
<p>The creation of a reduced confluent rewriting system for a semigroup or for a monoid, in <strong class="pkg">GAP</strong>, uses the Knuth-Bendix procedure for strings, which manipulates a rewriting system of the semigroup or monoid and attempts to make it confluent (See <a href="chap38.html#X7CA8FCFD81AA1890"><span class="RefLink">38</span></a>. See also Sims <a href="chapBib.html#biBSims94">[Sim94]</a>). (Since the word problem for semigroups/monoids is not solvable in general, Knuth-Bendix procedure cannot always terminate).</p>
<p>In order to apply this procedure we will build a rewriting system for the semigroup or monoid, which we will call a <em>Knuth-Bendix Rewriting System</em> (we need to define this because we need the rewriting system to store some information needed for the implementation of the Knuth-Bendix procedure).</p>
<p>Actually, Knuth-Bendix Rewriting Systems do not only serve this purpose. Indeed these are objects which are mutable and which can be manipulated (see <a href="chap38.html#X7CA8FCFD81AA1890"><span class="RefLink">38</span></a>).</p>
<p>Note that the implemented version of the Knuth-Bendix procedure, in <strong class="pkg">GAP</strong> returns, if it terminates, a confluent rewriting system which is reduced. Also, a reduction ordering has to be specified when building a rewriting system. If none is specified, the shortlex ordering is assumed (note that the procedure may terminate with a certain ordering and not with another one).</p>
<p>On Unix systems it is possible to replace the built-in Knuth-Bendix by other routines, for example the package <strong class="pkg">kbmag</strong> offers such a possibility.</p>
<p><a id="X7A3F8AE285C41D80" name="X7A3F8AE285C41D80"></a></p>
<h5>53.6-2 KB_REW</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KB_REW</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GAPKB_REW</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p><code class="code">KB_REW</code> is a global record variable whose components contain functions used for Knuth-Bendix. By default <code class="code">KB_REW</code> is assigned to <code class="code">GAPKB_REW</code>, which contains the KB functions provided by the GAP library.</p>
<p><a id="X87A3823483E4FF86" name="X87A3823483E4FF86"></a></p>
<h5>53.6-3 <span class="Heading">KnuthBendixRewritingSystem</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KnuthBendixRewritingSystem</code>( <var class="Arg">s</var>, <var class="Arg">wordord</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KnuthBendixRewritingSystem</code>( <var class="Arg">m</var>, <var class="Arg">wordord</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>in the first form, for a semigroup <var class="Arg">s</var> and a reduction ordering for the underlying free semigroup, it returns the Knuth-Bendix rewriting system of the finitely presented semigroup <var class="Arg">s</var> using the reduction ordering <var class="Arg">wordord</var>. In the second form, for a monoid <var class="Arg">m</var> and a reduction ordering for the underlying free monoid, it returns the Knuth-Bendix rewriting system of the finitely presented monoid <var class="Arg">m</var> using the reduction ordering <var class="Arg">wordord</var>.</p>
<p><a id="X7966343587A04AFF" name="X7966343587A04AFF"></a></p>
<h5>53.6-4 SemigroupOfRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupOfRewritingSystem</code>( <var class="Arg">rws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the semigroup over which <var class="Arg">rws</var> is a rewriting system</p>
<p><a id="X7EAB3E067D7557F6" name="X7EAB3E067D7557F6"></a></p>
<h5>53.6-5 MonoidOfRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MonoidOfRewritingSystem</code>( <var class="Arg">rws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the monoid over which <var class="Arg">rws</var> is a rewriting system</p>
<p><a id="X80B8115C8147F605" name="X80B8115C8147F605"></a></p>
<h5>53.6-6 FreeSemigroupOfRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeSemigroupOfRewritingSystem</code>( <var class="Arg">rws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the free semigroup over which <var class="Arg">rws</var> is a rewriting system</p>
<p><a id="X84CE48BE7F870808" name="X84CE48BE7F870808"></a></p>
<h5>53.6-7 FreeMonoidOfRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeMonoidOfRewritingSystem</code>( <var class="Arg">rws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the free monoid over which <var class="Arg">rws</var> is a rewriting system</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := FreeSemigroupOfRewritingSystem(rws);</span>
<free semigroup on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1=f;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g1 := SemigroupOfRewritingSystem(rws);</span>
<fp semigroup on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">g1=g;</span>
true
</pre></div>
<p>As mentioned before, having a confluent rewriting system, one can decide whether two words represent the same element of a finitely presented semigroup (or finitely presented monoid).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfSemigroup( g )[ 1 ];</span>
a
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfSemigroup( g )[ 2 ];</span>
b
<span class="GAPprompt">gap></span> <span class="GAPinput">a*b*a=a^3;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedForm(rws,UnderlyingElement(a*b*a));</span>
a^3
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedForm(rws,UnderlyingElement(a^3));</span>
a^3
</pre></div>
<p><a id="X812C28217F3E6720" name="X812C28217F3E6720"></a></p>
<h4>53.7 <span class="Heading">Todd-Coxeter Procedure</span></h4>
<p>This procedure gives a standard way of finding a transformation representation of a finitely presented semigroup. Usually one does not explicitly call this procedure but uses <code class="func">IsomorphismTransformationSemigroup</code> (<a href="chap51.html#X78F29C817CF6827F"><span class="RefLink">51.3-3</span></a>) or <code class="func">HomomorphismTransformationSemigroup</code> (<a href="chap51.html#X78F29C817CF6827F"><span class="RefLink">51.3-3</span></a>).</p>
<p><a id="X7C24508A7F677520" name="X7C24508A7F677520"></a></p>
<h5>53.7-1 CosetTableOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CosetTableOfFpSemigroup</code>( <var class="Arg">r</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">r</var> is a right congruence of an fp-semigroup <var class="Arg">S</var>. This attribute is the coset table of FP semigroup <var class="Arg">S</var> on a right congruence <var class="Arg">r</var>. Given a right congruence <var class="Arg">r</var> we represent <var class="Arg">S</var> as a set of transformations of the congruence classes of <var class="Arg">r</var>.</p>
<p>The images of the cosets under the generators are compiled in a list <var class="Arg">table</var> such that <var class="Arg">table[i][s]</var> contains the image of coset <var class="Arg">s</var> under generator <var class="Arg">i</var>.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap52.html">[Previous Chapter]</a> <a href="chap54.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="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chap19.html">19</a> <a href="chap20.html">20</a> <a href="chap21.html">21</a> <a href="chap22.html">22</a> <a href="chap23.html">23</a> <a href="chap24.html">24</a> <a href="chap25.html">25</a> <a href="chap26.html">26</a> <a href="chap27.html">27</a> <a href="chap28.html">28</a> <a href="chap29.html">29</a> <a href="chap30.html">30</a> <a href="chap31.html">31</a> <a href="chap32.html">32</a> <a href="chap33.html">33</a> <a href="chap34.html">34</a> <a href="chap35.html">35</a> <a href="chap36.html">36</a> <a href="chap37.html">37</a> <a href="chap38.html">38</a> <a href="chap39.html">39</a> <a href="chap40.html">40</a> <a href="chap41.html">41</a> <a href="chap42.html">42</a> <a href="chap43.html">43</a> <a href="chap44.html">44</a> <a href="chap45.html">45</a> <a href="chap46.html">46</a> <a href="chap47.html">47</a> <a href="chap48.html">48</a> <a href="chap49.html">49</a> <a href="chap50.html">50</a> <a href="chap51.html">51</a> <a href="chap52.html">52</a> <a href="chap53.html">53</a> <a href="chap54.html">54</a> <a href="chap55.html">55</a> <a href="chap56.html">56</a> <a href="chap57.html">57</a> <a href="chap58.html">58</a> <a href="chap59.html">59</a> <a href="chap60.html">60</a> <a href="chap61.html">61</a> <a href="chap62.html">62</a> <a href="chap63.html">63</a> <a href="chap64.html">64</a> <a href="chap65.html">65</a> <a href="chap66.html">66</a> <a href="chap67.html">67</a> <a href="chap68.html">68</a> <a href="chap69.html">69</a> <a href="chap70.html">70</a> <a href="chap71.html">71</a> <a href="chap72.html">72</a> <a href="chap73.html">73</a> <a href="chap74.html">74</a> <a href="chap75.html">75</a> <a href="chap76.html">76</a> <a href="chap77.html">77</a> <a href="chap78.html">78</a> <a href="chap79.html">79</a> <a href="chap80.html">80</a> <a href="chap81.html">81</a> <a href="chap82.html">82</a> <a href="chap83.html">83</a> <a href="chap84.html">84</a> <a href="chap85.html">85</a> <a href="chap86.html">86</a> <a href="chap87.html">87</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>
|