This file is indexed.

/usr/share/gap/doc/ref/chap52.html is in gap-doc 4r8p6-2.

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 52: 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="chap52"  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">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap51.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap53.html">[Next Chapter]</a>&nbsp;  </div>

<p id="mathjaxlink" class="pcenter"><a href="chap52_mj.html">[MathJax on]</a></p>
<p><a id="X7DE7C52A7C4BDADE" name="X7DE7C52A7C4BDADE"></a></p>
<div class="ChapSects"><a href="chap52.html#X7DE7C52A7C4BDADE">52 <span class="Heading">Finitely Presented Semigroups and Monoids</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X78C80F1A84C58E1E">52.1 <span class="Heading">IsSubsemigroupFpSemigroup (Filter)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X8496E23C80453C33">52.1-1 IsSubsemigroupFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X82128D4D83ACA683">52.1-2 IsSubmonoidFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X8239EF2B853411E9">52.1-3 IsFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7C2BA01D86087D11">52.1-4 IsFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X81ABBE997A4C19B7">52.1-5 IsElementOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7A570B89862C7399">52.1-6 IsElementOfFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7DC8A5D380AFE5DB">52.1-7 FpGrpMonSmgOfFpGrpMonSmgElement</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X84B8E3257E2E4134">52.2 <span class="Heading">Creating Finitely Presented Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7D3B9E317DD5AC8A">52.2-1 \/</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X822F04B2833BE254">52.2-2 FactorFreeSemigroupByRelations</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X869F966B8196F28C">52.2-3 IsomorphismFpSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X85E7C8407C9D5FBE">52.3 <span class="Heading">Comparison of Elements of Finitely Presented Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7DD9D81F863EBE31">52.3-1 \=</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X7D3EA628804E05D4">52.4 <span class="Heading">Preimages in the Free Semigroup</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X818E25C887512E89">52.4-1 UnderlyingElement</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X847012347856C55E">52.4-2 ElementOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X8726523779601873">52.4-3 FreeSemigroupOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X79A39402806B5EB7">52.4-4 FreeGeneratorsOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X862BE9FA7C987CAB">52.4-5 RelationsOfFpSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X7E79A80382563C26">52.5 <span class="Heading">Finitely presented monoids</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X82B5E4A27AAB6749">52.5-1 \/</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X87693BDC79DC6EBF">52.6 <span class="Heading">Rewriting Systems and the Knuth-Bendix Procedure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7D8F804E814D894D">52.6-1 ReducedConfluentRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7A3F8AE285C41D80">52.6-2 KB_REW</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X87A3823483E4FF86">52.6-3 <span class="Heading">KnuthBendixRewritingSystem</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7966343587A04AFF">52.6-4 SemigroupOfRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7EAB3E067D7557F6">52.6-5 MonoidOfRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X80B8115C8147F605">52.6-6 FreeSemigroupOfRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X84CE48BE7F870808">52.6-7 FreeMonoidOfRewritingSystem</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap52.html#X812C28217F3E6720">52.7 <span class="Heading">Todd-Coxeter Procedure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap52.html#X7C24508A7F677520">52.7-1 CosetTableOfFpSemigroup</a></span>
</div></div>
</div>

<h3>52 <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&gt;</span> <span class="GAPinput">f:=FreeSemigroup("a","b");;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x:=GeneratorsOfSemigroup(f);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s:=f/[ [x[1]*x[2],x[2]*x[1]] ];</span>
&lt;fp semigroup on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">GeneratorsOfSemigroup(s);</span>
[ a, b ]
<span class="GAPprompt">gap&gt;</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&gt;</span> <span class="GAPinput">f:=FreeMonoid("a","b");;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x:=GeneratorsOfMonoid(f);</span>
[ a, b ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">e:=Identity(f);</span>
&lt;identity ...&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">m:=f/[ [x[1]*x[2],e] ];</span>
&lt;fp monoid on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RelationsOfFpMonoid(m);</span>
[ [ a*b, &lt;identity ...&gt; ] ]
</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&gt;</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="chap52.html#X869F966B8196F28C"><span class="RefLink">52.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&gt;</span> <span class="GAPinput">Unbind(a);</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:=FreeSemigroup("a","b");;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x:=GeneratorsOfSemigroup(f);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s:=f/[ [x[1]*x[2],x[2]*x[1]] ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a;</span>
Error, Variable: 'a' must have a value
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a:=GeneratorsOfSemigroup(s)[1];</span>
a
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b:=GeneratorsOfSemigroup(s)[2];</span>
b
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a in f;</span>
false
<span class="GAPprompt">gap&gt;</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="chap52.html#X87693BDC79DC6EBF"><span class="RefLink">52.6</span></a>.)</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a*b=a^5;</span>
false
<span class="GAPprompt">gap&gt;</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&gt;</span> <span class="GAPinput">a^5*b^2*a;</span>
a^5*b^2*a
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a^6*b^2;</span>
a^6*b^2
</pre></div>

<p><a id="X78C80F1A84C58E1E" name="X78C80F1A84C58E1E"></a></p>

<h4>52.1 <span class="Heading">IsSubsemigroupFpSemigroup (Filter)</span></h4>

<p><a id="X8496E23C80453C33" name="X8496E23C80453C33"></a></p>

<h5>52.1-1 IsSubsemigroupFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsSubsemigroupFpSemigroup</code>( <var class="Arg">t</var> )</td><td class="tdright">( filter )</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>52.1-2 IsSubmonoidFpMonoid</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsSubmonoidFpMonoid</code>( <var class="Arg">t</var> )</td><td class="tdright">( filter )</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>52.1-3 IsFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsFpSemigroup</code>( <var class="Arg">s</var> )</td><td class="tdright">( filter )</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>52.1-4 IsFpMonoid</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsFpMonoid</code>( <var class="Arg">m</var> )</td><td class="tdright">( filter )</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>52.1-5 IsElementOfFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.1-6 IsElementOfFpMonoid</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.1-7 FpGrpMonSmgOfFpGrpMonSmgElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">f := FreeSemigroup("a","b");;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s := f / [ [ a^2 , a*b ] ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsFpSemigroup( s );</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">t := Semigroup( [ GeneratorsOfSemigroup( s )[ 1 ] ]);</span>
&lt;commutative semigroup with 1 generator&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsSubsemigroupFpSemigroup( t );</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsElementOfFpSemigroup( GeneratorsOfSemigroup( t )[ 1 ] );</span>
true
</pre></div>

<p><a id="X84B8E3257E2E4134" name="X84B8E3257E2E4134"></a></p>

<h4>52.2 <span class="Heading">Creating Finitely Presented Semigroups</span></h4>

<p><a id="X7D3B9E317DD5AC8A" name="X7D3B9E317DD5AC8A"></a></p>

<h5>52.2-1 \/</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; \/</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&gt;</span> <span class="GAPinput">f:=FreeSemigroup(3);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s:=GeneratorsOfSemigroup(f);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f/[ [s[1]*s[2]*s[1],s[1]] , [s[2]^4,s[1]] ];</span>
&lt;fp semigroup on the generators [ s1, s2, s3 ]&gt;
</pre></div>

<p><a id="X822F04B2833BE254" name="X822F04B2833BE254"></a></p>

<h5>52.2-2 FactorFreeSemigroupByRelations</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">FactorFreeSemigroupByRelations(f,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">                           [[s[1]*s[2]*s[1],s[1]],[s[2]^4,s[1]]]);</span>
&lt;fp semigroup on the generators [ s1, s2, s3 ]&gt;
</pre></div>

<p><a id="X869F966B8196F28C" name="X869F966B8196F28C"></a></p>

<h5>52.2-3 IsomorphismFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">f := FreeGroup(2);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g := f/[f.1^4,f.2^5];</span>
&lt;fp group on the generators [ f1, f2 ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">phi := IsomorphismFpSemigroup(g);</span>
MappingByFunction( &lt;fp group on the generators 
[ f1, f2 ]&gt;, &lt;fp semigroup on the generators 
[ &lt;identity ...&gt;, f1^-1, f1, f2^-1, f2 
 ]&gt;, function( x ) ... end, function( x ) ... end )
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s := Range(phi);</span>
&lt;fp semigroup on the generators [ &lt;identity ...&gt;, f1^-1, f1, f2^-1, 
  f2 ]&gt;
</pre></div>

<p><a id="X85E7C8407C9D5FBE" name="X85E7C8407C9D5FBE"></a></p>

<h4>52.3 <span class="Heading">Comparison of Elements of Finitely Presented Semigroups</span></h4>

<p><a id="X7DD9D81F863EBE31" name="X7DD9D81F863EBE31"></a></p>

<h5>52.3-1 \=</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; \=</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="chap52.html#X87693BDC79DC6EBF"><span class="RefLink">52.6</span></a>).</p>

<p><a id="X7D3EA628804E05D4" name="X7D3EA628804E05D4"></a></p>

<h4>52.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>52.4-1 UnderlyingElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">f := FreeSemigroup( "a" , "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ];</span>
&lt;fp semigroup on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">w := GeneratorsOfSemigroup(s)[1] * GeneratorsOfSemigroup(s)[2];</span>
a*b
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsWord (w );</span>
false
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ue := UnderlyingElement( w );</span>
a*b
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsWord( ue );</span>
true
</pre></div>

<p><a id="X847012347856C55E" name="X847012347856C55E"></a></p>

<h5>52.4-2 ElementOfFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">fam := FamilyObj( GeneratorsOfSemigroup(s)[1] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ge := ElementOfFpSemigroup( fam, a*b );</span>
a*b
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ge in f;</span>
false
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ge in s;</span>
true
</pre></div>

<p><a id="X8726523779601873" name="X8726523779601873"></a></p>

<h5>52.4-3 FreeSemigroupOfFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.4-4 FreeGeneratorsOfFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.4-5 RelationsOfFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">f := FreeSemigroup( "a" , "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ];</span>
&lt;fp semigroup on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( s );</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">fs := FreeSemigroupOfFpSemigroup( s );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f = fs;</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">FreeGeneratorsOfFpSemigroup( s );</span>
[ a, b ]
<span class="GAPprompt">gap&gt;</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>52.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>52.5-1 \/</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; \/</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&gt;</span> <span class="GAPinput">f := FreeMonoid( 3 );</span>
&lt;free monoid on the generators [ m1, m2, m3 ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x := GeneratorsOfMonoid( f );</span>
[ m1, m2, m3 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">e:= Identity ( f );</span>
&lt;identity ...&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">m := f/[ [x[1]^3,e] , [x[1]*x[2],x[2] ]];</span>
&lt;fp monoid on the generators [ m1, m2, m3 ]&gt;
</pre></div>

<p><a id="X87693BDC79DC6EBF" name="X87693BDC79DC6EBF"></a></p>

<h4>52.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>52.6-1 ReducedConfluentRewritingSystem</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">f := FreeSemigroup( "a" , "b" );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a := GeneratorsOfSemigroup( f )[ 1 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := GeneratorsOfSemigroup( f )[ 2 ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g := f /  [ [ a^2 , a*b ] , [ a^4 , b] ];;</span>
<span class="GAPprompt">gap&gt;</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>52.6-2 KB_REW</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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">&#8227; 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>52.6-3 <span class="Heading">KnuthBendixRewritingSystem</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; KnuthBendixRewritingSystem</code>( <var class="Arg">s</var>, <var class="Arg">wordord</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">&#8227; KnuthBendixRewritingSystem</code>( <var class="Arg">m</var>, <var class="Arg">wordord</var> )</td><td class="tdright">( operation )</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>52.6-4 SemigroupOfRewritingSystem</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.6-5 MonoidOfRewritingSystem</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.6-6 FreeSemigroupOfRewritingSystem</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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>52.6-7 FreeMonoidOfRewritingSystem</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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&gt;</span> <span class="GAPinput">f1 := FreeSemigroupOfRewritingSystem(rws);</span>
&lt;free semigroup on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f1=f;</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g1 := SemigroupOfRewritingSystem(rws);</span>
&lt;fp semigroup on the generators [ a, b ]&gt;
<span class="GAPprompt">gap&gt;</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&gt;</span> <span class="GAPinput">a := GeneratorsOfSemigroup( g )[ 1 ];</span>
a
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">b := GeneratorsOfSemigroup( g )[ 2 ];</span>
b
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a*b*a=a^3;</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ReducedForm(rws,UnderlyingElement(a*b*a));</span>
a^3
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ReducedForm(rws,UnderlyingElement(a^3));</span>
a^3
</pre></div>

<p><a id="X812C28217F3E6720" name="X812C28217F3E6720"></a></p>

<h4>52.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="chap53.html#X78F29C817CF6827F"><span class="RefLink">53.7-5</span></a>).</p>

<p><a id="X7C24508A7F677520" name="X7C24508A7F677520"></a></p>

<h5>52.7-1 CosetTableOfFpSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; 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">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap51.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap53.html">[Next Chapter]</a>&nbsp;  </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>