Impressum chap51.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/doc/ref/chap51.html |
 |
<?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 51: 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="chap51" 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="chap50.html">[Previous Chapter]</a> <a href="chap52.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap51_mj.html">[MathJax on]</a></p>
<p><a id="X8665D8737FDD5B10" name="X8665D8737FDD5B10"></a></p>
<div class="ChapSects"><a href="chap51.html#X8665D8737FDD5B10">51 <span class="Heading">Semigroups and Monoids</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X80AF5F307DBDC2B4">51.1 <span class="Heading">Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7B412E5B8543E9B7">51.1-1 IsSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7F55D28F819B2817">51.1-2 <span class="Heading">Semigroup</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X8678D40878CC09A1">51.1-3 Subsemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X782B7BDD8252581C">51.1-4 IsSubsemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X79FBBEC9841544F3">51.1-5 SemigroupByGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X80ED104F85AE5134">51.1-6 AsSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7B1EEA3E82BFE09F">51.1-7 AsSubsemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X78147A247963F23B">51.1-8 GeneratorsOfSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X79776D7C8399F2CF">51.1-9 IsGeneratorsOfSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7C72E4747BF642BB">51.1-10 <span class="Heading">FreeSemigroup</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7E67E13F7A01F8D3">51.1-11 SemigroupByMultiplicationTable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X872FE34A7814C0DC">51.2 <span class="Heading">Monoids</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X861C523483C6248C">51.2-1 IsMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7F95328B7C7E49EA">51.2-2 <span class="Heading">Monoid</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X8322D01E84912FD7">51.2-3 Submonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X85129EE387CC4D28">51.2-4 MonoidByGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7B22038F832B9C0F">51.2-5 AsMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7C9A12DE8287B2D3">51.2-6 AsSubmonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X83CA2E7279C44718">51.2-7 GeneratorsOfMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7EC77C0184587181">51.2-8 TrivialSubmonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X79FA3FA978CA2E43">51.2-9 <span class="Heading">FreeMonoid</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7BFE938E857CA27D">51.2-10 MonoidByMultiplicationTable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X840847B6810BD0E1">51.3 <span class="Heading">Inverse semigroups and monoids</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X78B13FED7AFB4326">51.3-1 InverseSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X80D9B9A98736051B">51.3-2 InverseMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X87C373597F787250">51.3-3 GeneratorsOfInverseSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7A3B262C85B6D475">51.3-4 GeneratorsOfInverseMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7C4C6EE681E7A57E">51.3-5 IsInverseSubsemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X78274024827F306D">51.4 <span class="Heading">Properties of Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7C4663827C5ACEF1">51.4-1 IsRegularSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X87532A76854347E0">51.4-2 IsRegularSemigroupElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7AFDE0F17AE516C5">51.4-3 InversesOfSemigroupElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X836F4692839F4874">51.4-4 IsSimpleSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X8193A60F839C064E">51.4-5 IsZeroSimpleSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X85F7E5CD86F0643B">51.4-6 IsZeroGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7FFEC81F7F2C4EAA">51.4-7 IsReesCongruenceSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X83F1529479D56665">51.4-8 IsInverseSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X7BB32D508183C0F1">51.5 <span class="Heading">Ideals of semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7D5CEE4D7D4318ED">51.5-1 SemigroupIdealByGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7F01FFB18125DED5">51.5-2 ReesCongruenceOfSemigroupIdeal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7A3FF85984345540">51.5-3 IsLeftSemigroupIdeal</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X7914691E7DFFE27A">51.6 <span class="Heading">Congruences on semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X78E34B737F0E009F">51.6-1 IsSemigroupCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X822DB78579BCB7B5">51.6-2 IsReesCongruence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X87CE9EAB7EE3A128">51.7 <span class="Heading">Quotients</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X80EF3E6F842BE64E">51.7-1 IsQuotientSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7CAD3D1687956F7F">51.7-2 HomomorphismQuotientSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X87120C46808F7289">51.7-3 QuotientSemigroupPreimage</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X80C6C718801855E9">51.8 <span class="Heading">Green's Relations
</ span>
< div class= "ContSSBlock">
< span class= "ContSS">< br />< span class= "nocss"> </ span><a href= "chap51.html#X786CEDD4814A9079"> 51.8-1 GreensRRelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X8364D69987D49DE1">51.8-2 IsGreensRelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X82A11A087AFB3EB0">51.8-3 IsGreensClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7AA204C8850F9070">51.8-4 IsGreensLessThanOrEqual</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X86FE5F5585EBCF13">51.8-5 RClassOfHClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X78C56F4A78E0088A">51.8-6 EggBoxOfDClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X803237F17ACD44E3">51.8-7 DisplayEggBoxOfDClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X87C75A9D86122D93">51.8-8 GreensRClassOfElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X844D20467A644811">51.8-9 GreensRClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7CB4A18685B850E2">51.8-10 GroupHClassOfGreensDClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X79D740EF7F0E53BD">51.8-11 IsGroupHClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7F5860927CAD920F">51.8-12 IsRegularDClass</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X81AF2EAB7CEF8C19">51.8-13 DisplaySemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap51.html#X8225A9EC87A255E6">51.9 <span class="Heading">Rees Matrix Semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X8526AA557CDF6C49">51.9-1 ReesMatrixSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X78D2A48C87FC8E38">51.9-2 ReesMatrixSubsemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7964B5C97FB9C07D">51.9-3 IsomorphismReesMatrixSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7F6B852B81488C86">51.9-4 IsReesMatrixSemigroupElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7A0DE1F28470295E">51.9-5 ReesMatrixSemigroupElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7F03BE707AC7F8A0">51.9-6 IsReesMatrixSubsemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X780BB78A79275244">51.9-7 IsReesMatrixSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7CACF4D686AF1D19">51.9-8 Matrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X82FC5D6980C66AC4">51.9-9 <span class="Heading">Rows and columns</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7D9719F887AFCF8F">51.9-10 UnderlyingSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap51.html#X7D1D9A0382064B8F">51.9-11 AssociatedReesMatrixSemigroupOfDClass</a></span>
</div></div>
</div>
<h3>51 <span class="Heading">Semigroups and Monoids</span></h3>
<p>This chapter describes functions for creating semigroups and monoids and determining information about them.</p>
<p><a id="X80AF5F307DBDC2B4" name="X80AF5F307DBDC2B4"></a></p>
<h4>51.1 <span class="Heading">Semigroups</span></h4>
<p><a id="X7B412E5B8543E9B7" name="X7B412E5B8543E9B7"></a></p>
<h5>51.1-1 IsSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSemigroup</code>( <var class="Arg">D</var> )</td><td class="tdright">( synonym )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if the object <var class="Arg">D</var> is a semigroup. A <em>semigroup</em> is a magma (see <a href="chap35.html#X873E502F7D21C39C"><span class="RefLink">35</span></a>) with associative multiplication.</p>
<p><a id="X7F55D28F819B2817" name="X7F55D28F819B2817"></a></p>
<h5>51.1-2 <span class="Heading">Semigroup</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Semigroup</code>( <var class="Arg">gen1</var>, <var class="Arg">gen2</var>, <var class="Arg">...</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">‣ Semigroup</code>( <var class="Arg">gens</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form, <code class="func">Semigroup</code> returns the semigroup generated by the arguments <var class="Arg">gen1</var>, <var class="Arg">gen2</var>, <span class="SimpleMath">...</span>, that is, the closure of these elements under multiplication. In the second form, <code class="func">Semigroup</code> returns the semigroup generated by the elements in the homogeneous list <var class="Arg">gens</var>; a square matrix as only argument is treated as one generator, not as a list of generators.</p>
<p>It is <em>not</em> checked whether the underlying multiplication is associative, use <code class="func">Magma</code> (<a href="chap35.html#X839147CF813312D6"><span class="RefLink">35.2-1</span></a>) and <code class="func">IsAssociative</code> (<a href="chap35.html#X7C83B5A47FD18FB7"><span class="RefLink">35.4-7</span></a>) if you want to check whether a magma is in fact a semigroup.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:= Transformation( [ 2, 3, 4, 1 ] );</span>
Transformation( [ 2, 3, 4, 1 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">b:= Transformation( [ 2, 2, 3, 4 ] );</span>
Transformation( [ 2, 2 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">s:= Semigroup(a, b);</span>
<transformation semigroup of degree 4 with 2 generators>
</pre></div>
<p><a id="X8678D40878CC09A1" name="X8678D40878CC09A1"></a></p>
<h5>51.1-3 Subsemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Subsemigroup</code>( <var class="Arg">S</var>, <var class="Arg">gens</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">‣ SubsemigroupNC</code>( <var class="Arg">S</var>, <var class="Arg">gens</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>are just synonyms of <code class="func">Submagma</code> (<a href="chap35.html#X8268EAA47E4A3A64"><span class="RefLink">35.2-7</span></a>) and <code class="func">SubmagmaNC</code> (<a href="chap35.html#X8268EAA47E4A3A64"><span class="RefLink">35.2-7</span></a>), respectively.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=GeneratorsOfSemigroup(s)[1];</span>
Transformation( [ 2, 3, 4, 1 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">t:=Subsemigroup(s,[a]);</span>
<commutative transformation semigroup of degree 4 with 1 generator>
</pre></div>
<p><a id="X782B7BDD8252581C" name="X782B7BDD8252581C"></a></p>
<h5>51.1-4 IsSubsemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubsemigroup</code>( <var class="Arg">S</var>, <var class="Arg">T</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This operation returns <code class="keyw">true</code> if the semigroup <var class="Arg">T</var> is a subsemigroup of the semigroup <var class="Arg">S</var> and <code class="keyw">false</code> if it is not.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := Transformation([5, 6, 7, 1, 4, 3, 2, 7]);</span>
Transformation( [ 5, 6, 7, 1, 4, 3, 2, 7 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">T := Semigroup(f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubsemigroup(FullTransformationSemigroup(4), T);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(f);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := Semigroup(f ^ 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubsemigroup(S, T);</span>
true</pre></div>
<p><a id="X79FBBEC9841544F3" name="X79FBBEC9841544F3"></a></p>
<h5>51.1-5 SemigroupByGenerators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupByGenerators</code>( <var class="Arg">gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>is the underlying operation of <code class="func">Semigroup</code> (<a href="chap51.html#X7F55D28F819B2817"><span class="RefLink">51.1-2</span></a>).</p>
<p><a id="X80ED104F85AE5134" name="X80ED104F85AE5134"></a></p>
<h5>51.1-6 AsSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSemigroup</code>( <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">C</var> is a collection whose elements form a semigroup under <code class="func">\*</code> (<a href="chap31.html#X8481C9B97B214C23"><span class="RefLink">31.12-1</span></a>) (see <code class="func">IsSemigroup</code> (<a href="chap51.html#X7B412E5B8543E9B7"><span class="RefLink">51.1-1</span></a>)) then <code class="func">AsSemigroup</code> returns this semigroup. Otherwise <code class="keyw">fail</code> is returned.</p>
<p><a id="X7B1EEA3E82BFE09F" name="X7B1EEA3E82BFE09F"></a></p>
<h5>51.1-7 AsSubsemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSubsemigroup</code>( <var class="Arg">D</var>, <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Let <var class="Arg">D</var> be a domain and <var class="Arg">C</var> a collection. If <var class="Arg">C</var> is a subset of <var class="Arg">D</var> that forms a semigroup then <code class="func">AsSubsemigroup</code> returns this semigroup, with parent <var class="Arg">D</var>. Otherwise <code class="keyw">fail</code> is returned.</p>
<p><a id="X78147A247963F23B" name="X78147A247963F23B"></a></p>
<h5>51.1-8 GeneratorsOfSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Semigroup generators of a semigroup <var class="Arg">D</var> are the same as magma generators, see <code class="func">GeneratorsOfMagma</code> (<a href="chap35.html#X872E05B478EC20CA"><span class="RefLink">35.4-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup(s);</span>
[ Transformation( [ 2, 3, 4, 1 ] ), Transformation( [ 2, 2 ] ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup(t);</span>
[ Transformation( [ 2, 3, 4, 1 ] ) ]
</pre></div>
<p><a id="X79776D7C8399F2CF" name="X79776D7C8399F2CF"></a></p>
<h5>51.1-9 IsGeneratorsOfSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGeneratorsOfSemigroup</code>( <var class="Arg">C</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>This property reflects whether the list or collection <var class="Arg">C</var> generates a semigroup. <code class="func">IsAssociativeElementCollection</code> (<a href="chap31.html#X7979AFAA80FF795A"><span class="RefLink">31.15-1</span></a>) implies <code class="func">IsGeneratorsOfSemigroup</code>, but is not used directly in semigroup code, because of conflicts with matrices.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGeneratorsOfSemigroup([Transformation([2,3,1])]);</span>
true
</pre></div>
<p><a id="X7C72E4747BF642BB" name="X7C72E4747BF642BB"></a></p>
<h5>51.1-10 <span class="Heading">FreeSemigroup</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeSemigroup</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">rank</var>[, <var class="Arg">name</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">‣ FreeSemigroup</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">name1</var>[, <var class="Arg">name2</var>[, <var class="Arg">...</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">‣ FreeSemigroup</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">names</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">‣ FreeSemigroup</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">infinity</var>[, <var class="Arg">name</var>][, <var class="Arg">init</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">FreeSemigroup</code> returns a free semigroup. The number of generators, and the labels given to the generators, can be specified in several different ways. Warning: the labels of generators are only an aid for printing, and do not necessarily distinguish generators; see the examples at the end for more information.</p>
<dl>
<dt><strong class="Mark">
1: For a given rank, and an optional generator name prefix
</strong></dt>
<dd><p>Called with a positive integer <var class="Arg">rank</var>, <code class="func">FreeSemigroup</code> returns a free semigroup on <var class="Arg">rank</var> generators. The optional argument <var class="Arg">name</var> must be a string; its default value is <code class="code">"s"</code>.</p>
<p>If <var class="Arg">name</var> is not given but the <code class="code">generatorNames</code> option is, then this option is respected as described in Section <a href="chap50.html#X7D0FFDA4793995FC"><span class="RefLink">50.1-16</span></a>.</p>
<p>Otherwise, the generators of the returned free semigroup are labelled <var class="Arg">name</var><code class="code">1</code>, ..., <var class="Arg">name</var><code class="code">k</code>, where <code class="code">k</code> is the value of <var class="Arg">rank</var>.</p>
</dd>
<dt><strong class="Mark">2: For given generator names</strong></dt>
<dd><p>Called with various (at least one) nonempty strings, <code class="func">FreeSemigroup</code> returns a free semigroup on as many generators as arguments, which are labelled <var class="Arg">name1</var>, <var class="Arg">name2</var>, etc.</p>
</dd>
<dt><strong class="Mark">3: For a given list of generator names</strong></dt>
<dd><p>Called with a nonempty finite list <var class="Arg">names</var> of nonempty strings, <code class="func">FreeSemigroup</code> returns a free semigroup on <code class="code">Length(<var class="Arg">names</var>)</code> generators, whose <code class="code">i</code>-th generator is labelled <var class="Arg">names</var><code class="code">[i]</code>.</p>
</dd>
<dt><strong class="Mark">
4: For the rank <code class="keyw">infinity</code>,
an optional default generator name prefix,
and an optional finite list of generator names
</strong></dt>
<dd><p>Called in the fourth form, <code class="func">FreeSemigroup</code> returns a free semigroup on infinitely many generators. The optional argument <var class="Arg">name</var> must be a string; its default value is <code class="code">"s"</code>, and the optional argument <var class="Arg">init</var> must be a finite list of nonempty strings; its default value is an empty list. The generators are initially labelled according to the list <var class="Arg">init</var>, followed by <var class="Arg">name</var><code class="code">i</code> for each <code class="code">i</code> in the range from <code class="code">Length(<var class="Arg">init</var>)+1</code> to <code class="keyw">infinity</code>; such a label is not allowed to appear in <var class="Arg">init</var>.</p>
</dd>
</dl>
<p>If the optional first argument <var class="Arg">wfilt</var> is given, then it must be either <code class="code">IsSyllableWordsFamily</code>, <code class="code">IsLetterWordsFamily</code>, <code class="code">IsWLetterWordsFamily</code>, or <code class="code">IsBLetterWordsFamily</code>. This filter specifies the representation used for the elements of the free semigroup (see <a href="chap37.html#X80A9F39582ED296E"><span class="RefLink">37.6</span></a>). If no such filter is given, a letter representation is used.</p>
<p>For more on associative words see Chapter <a href="chap37.html#X78C56A0A87CE380E"><span class="RefLink">37</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := FreeSemigroup( 3 );</span>
<free semigroup on the generators [ s1, s2, s3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := FreeSemigroup( 3 , "generator" );</span>
<free semigroup on the generators
[ generator1, generator2, generator3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f3 := FreeSemigroup( "gen1" , "gen2" );</span>
<free semigroup on the generators [ gen1, gen2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f4 := FreeSemigroup( ["gen1" , "gen2"] );</span>
<free semigroup on the generators [ gen1, gen2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeSemigroup( 3 : generatorNames := "boom" );</span>
<free semigroup on the generators [ boom1, boom2, boom3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeSemigroup( 2 : generatorNames := [ "u", "v", "w" ] );</span>
<free semigroup on the generators [ u, v ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeSemigroup( infinity ) ;</span>
<free semigroup on the generators [ s1, s2, ... ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup( infinity, "g", [ "a", "b" ]);</span>
<free semigroup on the generators [ a, b, ... ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup( F ){[1..4]};</span>
[ a, b, g3, g4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup( FreeSemigroup( infinity, "gen" ) ){[1..3]};</span>
[ gen1, gen2, gen3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup( FreeSemigroup( infinity, [ "f" ] ) ){[1..3]};</span>
[ f, s2, s3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeSemigroup(IsSyllableWordsFamily, 5);</span>
<free semigroup on the generators [ s1, s2, s3, s4, s5 ]>
</pre></div>
<p>Each free object defines a unique alphabet (and a unique family of words). Its generators are the letters of this alphabet, thus words of length one.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeSemigroup( 5 );</span>
<free semigroup on the generators [ s1, s2, s3, s4, s5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid( "a", "b" );</span>
<free monoid on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeGroup( infinity );</span>
<free group with infinity generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeSemigroup( "x", "y" );</span>
<free semigroup on the generators [ x, y ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid( 7 );</span>
<free monoid on the generators [ m1, m2, m3, m4, m5, m6, m7 ]>
</pre></div>
<p>Remember that names are just a help for printing and do not necessarily distinguish letters. It is possible to create arbitrarily weird situations by choosing strange names for the letters.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeGroup( "x", "x" );</span>
<free group on the generators [ x, x ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfGroup( f );</span>
[ x, x ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gens[1] = gens[2];</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">f:= FreeGroup( "f1*f2", "f2^-1", "Group( [ f1, f2 ] )" );</span>
<free group on the generators [ f1*f2, f2^-1, Group( [ f1, f2 ] ) ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens:= GeneratorsOfGroup( f );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens[1] * gens[2];</span>
f1*f2*f2^-1
<span class="GAPprompt">gap></span> <span class="GAPinput">gens[1] / gens[3];</span>
f1*f2*Group( [ f1, f2 ] )^-1
<span class="GAPprompt">gap></span> <span class="GAPinput">gens[3] / gens[1] / gens[2];</span>
Group( [ f1, f2 ] )*f1*f2^-1*f2^-1^-1
</pre></div>
<p><a id="X7E67E13F7A01F8D3" name="X7E67E13F7A01F8D3"></a></p>
<h5>51.1-11 SemigroupByMultiplicationTable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupByMultiplicationTable</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the semigroup whose multiplication is defined by the square matrix <var class="Arg">A</var> (see <code class="func">MagmaByMultiplicationTable</code> (<a href="chap35.html#X85CD1E7678295CA6"><span class="RefLink">35.3-1</span></a>)) if such a semigroup exists. Otherwise <code class="keyw">fail</code> is returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupByMultiplicationTable([[1,2,3],[2,3,1],[3,1,2]]);</span>
<semigroup of size 3, with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupByMultiplicationTable([[1,2,3],[2,3,1],[3,2,1]]);</span>
fail
</pre></div>
<p><a id="X872FE34A7814C0DC" name="X872FE34A7814C0DC"></a></p>
<h4>51.2 <span class="Heading">Monoids</span></h4>
<p><a id="X861C523483C6248C" name="X861C523483C6248C"></a></p>
<h5>51.2-1 IsMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMonoid</code>( <var class="Arg">D</var> )</td><td class="tdright">( synonym )</td></tr></table></div>
<p>A <em>monoid</em> is a magma-with-one (see <a href="chap35.html#X873E502F7D21C39C"><span class="RefLink">35</span></a>) with associative multiplication.</p>
<p><a id="X7F95328B7C7E49EA" name="X7F95328B7C7E49EA"></a></p>
<h5>51.2-2 <span class="Heading">Monoid</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Monoid</code>( <var class="Arg">gen1</var>, <var class="Arg">gen2</var>, <var class="Arg">...</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">‣ Monoid</code>( <var class="Arg">gens</var>[, <var class="Arg">id</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the first form, <code class="func">Monoid</code> returns the monoid generated by the arguments <var class="Arg">gen1</var>, <var class="Arg">gen2</var>, <span class="SimpleMath">...</span>, that is, the closure of these elements under multiplication and taking the 0-th power. In the second form, <code class="func">Monoid</code> returns the monoid generated by the elements in the homogeneous list <var class="Arg">gens</var>; a square matrix as only argument is treated as one generator, not as a list of generators. In the second form, the identity element <var class="Arg">id</var> may be given as the second argument.</p>
<p>It is <em>not</em> checked whether the underlying multiplication is associative, use <code class="func">MagmaWithOne</code> (<a href="chap35.html#X7854B23286B17321"><span class="RefLink">35.2-2</span></a>) and <code class="func">IsAssociative</code> (<a href="chap35.html#X7C83B5A47FD18FB7"><span class="RefLink">35.4-7</span></a>) if you want to check whether a magma-with-one is in fact a monoid.</p>
<p><a id="X8322D01E84912FD7" name="X8322D01E84912FD7"></a></p>
<h5>51.2-3 Submonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Submonoid</code>( <var class="Arg">M</var>, <var class="Arg">gens</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">‣ SubmonoidNC</code>( <var class="Arg">M</var>, <var class="Arg">gens</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>are just synonyms of <code class="func">SubmagmaWithOne</code> (<a href="chap35.html#X7F295EBC7A9CE87E"><span class="RefLink">35.2-8</span></a>) and <code class="func">SubmagmaWithOneNC</code> (<a href="chap35.html#X7F295EBC7A9CE87E"><span class="RefLink">35.2-8</span></a>), respectively.</p>
<p><a id="X85129EE387CC4D28" name="X85129EE387CC4D28"></a></p>
<h5>51.2-4 MonoidByGenerators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MonoidByGenerators</code>( <var class="Arg">gens</var>[, <var class="Arg">one</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>is the underlying operation of <code class="func">Monoid</code> (<a href="chap51.html#X7F95328B7C7E49EA"><span class="RefLink">51.2-2</span></a>).</p>
<p><a id="X7B22038F832B9C0F" name="X7B22038F832B9C0F"></a></p>
<h5>51.2-5 AsMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsMonoid</code>( <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">C</var> is a collection whose elements form a monoid, then <code class="func">AsMonoid</code> returns this monoid. Otherwise <code class="keyw">fail</code> is returned.</p>
<p><a id="X7C9A12DE8287B2D3" name="X7C9A12DE8287B2D3"></a></p>
<h5>51.2-6 AsSubmonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSubmonoid</code>( <var class="Arg">D</var>, <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Let <var class="Arg">D</var> be a domain and <var class="Arg">C</var> a collection. If <var class="Arg">C</var> is a subset of <var class="Arg">D</var> that forms a monoid then <code class="func">AsSubmonoid</code> returns this monoid, with parent <var class="Arg">D</var>. Otherwise <code class="keyw">fail</code> is returned.</p>
<p><a id="X83CA2E7279C44718" name="X83CA2E7279C44718"></a></p>
<h5>51.2-7 GeneratorsOfMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfMonoid</code>( <var class="Arg">M</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Monoid generators of a monoid <var class="Arg">M</var> are the same as magma-with-one generators (see <code class="func">GeneratorsOfMagmaWithOne</code> (<a href="chap35.html#X87DD93EC8061DD81"><span class="RefLink">35.4-2</span></a>)).</p>
<p><a id="X7EC77C0184587181" name="X7EC77C0184587181"></a></p>
<h5>51.2-8 TrivialSubmonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TrivialSubmonoid</code>( <var class="Arg">M</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>is just a synonym for <code class="func">TrivialSubmagmaWithOne</code> (<a href="chap35.html#X837DA95883CFB985"><span class="RefLink">35.4-13</span></a>).</p>
<p><a id="X79FA3FA978CA2E43" name="X79FA3FA978CA2E43"></a></p>
<h5>51.2-9 <span class="Heading">FreeMonoid</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeMonoid</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">rank</var>[, <var class="Arg">name</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">‣ FreeMonoid</code>( [<var class="Arg">wfilt</var>][,] [<var class="Arg">name1</var>[, <var class="Arg">name2</var>[, <var class="Arg">...</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">‣ FreeMonoid</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">names</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">‣ FreeMonoid</code>( [<var class="Arg">wfilt</var>, ]<var class="Arg">infinity</var>[, <var class="Arg">name</var>][, <var class="Arg">init</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">FreeMonoid</code> returns a free monoid. The number of generators, and the labels given to the generators, can be specified in several different ways. Warning: the labels of generators are only an aid for printing, and do not necessarily distinguish generators; see the examples at the end of <code class="func">FreeSemigroup</code> (<a href="chap51.html#X7C72E4747BF642BB"><span class="RefLink">51.1-10</span></a>) for more information.</p>
<dl>
<dt><strong class="Mark">
1: For a given rank, and an optional generator name prefix
</strong></dt>
<dd><p>Called with a nonnegative integer <var class="Arg">rank</var>, <code class="func">FreeMonoid</code> returns a free monoid on <var class="Arg">rank</var> generators. The optional argument <var class="Arg">name</var> must be a string; its default value is <code class="code">"m"</code>.</p>
<p>If <var class="Arg">name</var> is not given but the <code class="code">generatorNames</code> option is, then this option is respected as described in Section <a href="chap50.html#X7D0FFDA4793995FC"><span class="RefLink">50.1-16</span></a>.</p>
<p>Otherwise, the generators of the returned free monoid are labelled <var class="Arg">name</var><code class="code">1</code>, ..., <var class="Arg">name</var><code class="code">k</code>, where <code class="code">k</code> is the value of <var class="Arg">rank</var>.</p>
</dd>
<dt><strong class="Mark">2: For given generator names</strong></dt>
<dd><p>Called with various nonempty strings, <code class="func">FreeMonoid</code> returns a free monoid on as many generators as arguments, which are labelled <var class="Arg">name1</var>, <var class="Arg">name2</var>, etc.</p>
</dd>
<dt><strong class="Mark">3: For a given list of generator names</strong></dt>
<dd><p>Called with a finite list <var class="Arg">names</var> of nonempty strings, <code class="func">FreeMonoid</code> returns a free monoid on <code class="code">Length(<var class="Arg">names</var>)</code> generators, whose <code class="code">i</code>-th generator is labelled <var class="Arg">names</var><code class="code">[i]</code>.</p>
</dd>
<dt><strong class="Mark">
4: For the rank <code class="keyw">infinity</code>,
an optional default generator name prefix,
and an optional finite list of generator names
</strong></dt>
<dd><p>Called in the fourth form, <code class="func">FreeMonoid</code> returns a free monoid on infinitely many generators. The optional argument <var class="Arg">name</var> must be a string; its default value is <code class="code">"m"</code>, and the optional argument <var class="Arg">init</var> must be a finite list of nonempty strings; its default value is an empty list. The generators are initially labelled according to the list <var class="Arg">init</var>, followed by <var class="Arg">name</var><code class="code">i</code> for each <code class="code">i</code> in the range from <code class="code">Length(<var class="Arg">init</var>)+1</code> to <code class="keyw">infinity</code>.</p>
</dd>
</dl>
<p>If the optional first argument <var class="Arg">wfilt</var> is given, then it must be either <code class="code">IsSyllableWordsFamily</code>, <code class="code">IsLetterWordsFamily</code>, <code class="code">IsWLetterWordsFamily</code>, or <code class="code">IsBLetterWordsFamily</code>. This filter specifies the representation used for the elements of the free monoid (see <a href="chap37.html#X80A9F39582ED296E"><span class="RefLink">37.6</span></a>). If no such filter is given, a letter representation is used.</p>
<p>For more on associative words see Chapter <a href="chap37.html#X78C56A0A87CE380E"><span class="RefLink">37</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(5);</span>
<free monoid on the generators [ m1, m2, m3, m4, m5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(4, "gen");</span>
<free monoid on the generators [ gen1, gen2, gen3, gen4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(3 : generatorNames := "turbo");</span>
<free monoid on the generators [ turbo1, turbo2, turbo3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(2 : generatorNames := ["u", "v", "w"]);</span>
<free monoid on the generators [ u, v ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(); FreeMonoid(0); FreeMonoid([]);</span>
<free monoid of rank zero>
<free monoid of rank zero>
<free monoid of rank zero>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid("a", "b", "c");</span>
<free monoid on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(["x", "y"]);</span>
<free monoid on the generators [ x, y ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(infinity);</span>
<free monoid with infinity generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeMonoid(infinity, "g", ["a", "b"]);</span>
<free monoid with infinity generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfMonoid(F){[1..4]};</span>
[ a, b, g3, g4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfMonoid(FreeMonoid(infinity, "gen")){[1..3]};</span>
[ gen1, gen2, gen3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfMonoid(FreeMonoid(infinity, [ "f", "g" ])){[1..3]};</span>
[ f, g, m3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoid(IsSyllableWordsFamily, 50);</span>
<free monoid with 50 generators>
</pre></div>
<p><a id="X7BFE938E857CA27D" name="X7BFE938E857CA27D"></a></p>
<h5>51.2-10 MonoidByMultiplicationTable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MonoidByMultiplicationTable</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the monoid whose multiplication is defined by the square matrix <var class="Arg">A</var> (see <code class="func">MagmaByMultiplicationTable</code> (<a href="chap35.html#X85CD1E7678295CA6"><span class="RefLink">35.3-1</span></a>)) if such a monoid exists. Otherwise <code class="keyw">fail</code> is returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">MonoidByMultiplicationTable([[1,2,3],[2,3,1],[3,1,2]]);</span>
<monoid of size 3, with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">MonoidByMultiplicationTable([[1,2,3],[2,3,1],[1,3,2]]);</span>
fail
</pre></div>
<p><a id="X840847B6810BD0E1" name="X840847B6810BD0E1"></a></p>
<h4>51.3 <span class="Heading">Inverse semigroups and monoids</span></h4>
<p><a id="X78B13FED7AFB4326" name="X78B13FED7AFB4326"></a></p>
<h5>51.3-1 InverseSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InverseSemigroup</code>( <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An inverse semigroup.</p>
<p>If <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, ... are (any combination) of associative elements with unique semigroup inverses, semigroups of such elements, or collections of such elements, then <code class="code">InverseSemigroup</code> returns the inverse semigroup generated by the union of <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, .... This equals the semigroup generated by the union of <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, ... and their inverses.</p>
<p>For example if <code class="code">S</code> and <code class="code">T</code> are inverse semigroups, then <code class="code">InverseSemigroup(S, f, Idempotents(T));</code> is the inverse semigroup generated by <code class="code">Union(GeneratorsOfInverseSemigroup(S), [f], Idempotents(T)));</code>.</p>
<p>As present, the only associative elements with unique semigroup inverses, which do not always generate a group, are partial permutations; see Chapter <a href="chap54.html#X7D6495F77B8A77BD"><span class="RefLink">54</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseSemigroup(</span>
<span class="GAPprompt">></span> <span class="GAPinput">PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ 7, 1, 4, 3, 2, 6, 5 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseSemigroup(S, f, Idempotents(SymmetricInverseSemigroup(5)));</span>
<inverse partial perm semigroup of rank 10 with 34 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
1233</pre></div>
<p><a id="X80D9B9A98736051B" name="X80D9B9A98736051B"></a></p>
<h5>51.3-2 InverseMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InverseMonoid</code>( <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An inverse monoid.</p>
<p>If <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, ... are (any combination) of associative elements with unique semigroup inverses, semigroups of such elements, or collections of such elements, then <code class="code">InverseMonoid</code> returns the inverse monoid generated by the union of <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, .... This equals the monoid generated by the union of <var class="Arg">obj1</var>, <var class="Arg">obj2</var>, ... and their inverses.</p>
<p>As present, the only associative elements with unique semigroup inverses are partial permutations; see Chapter <a href="chap54.html#X7D6495F77B8A77BD"><span class="RefLink">54</span></a>.</p>
<p>For example if <code class="code">S</code> and <code class="code">T</code> are inverse monoids, then <code class="code">InverseMonoid(S, f, Idempotents(T));</code> is the inverse monoid generated by <code class="code">Union(GeneratorsOfInverseMonoid(S), [f], Idempotents(T)));</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseMonoid(</span>
<span class="GAPprompt">></span> <span class="GAPinput">PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ 7, 1, 4, 3, 2, 6, 5 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseMonoid(S, f, Idempotents(SymmetricInverseSemigroup(5)));</span>
<inverse partial perm monoid of rank 10 with 35 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
1243</pre></div>
<p><a id="X87C373597F787250" name="X87C373597F787250"></a></p>
<h5>51.3-3 GeneratorsOfInverseSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfInverseSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: The generators of an inverse semigroup.</p>
<p>If <var class="Arg">S</var> is an inverse semigroup, then <code class="code">GeneratorsOfInverseSemigroup</code> returns the generators used to define <var class="Arg">S</var>, i.e. an inverse semigroup generating set for <var class="Arg">S</var>.</p>
<p>The value of <code class="code">GeneratorsOfSemigroup(<var class="Arg">S</var>)</code>, for an inverse semigroup <var class="Arg">S</var>, is the union of inverse semigroup generator and their inverses. So, <var class="Arg">S</var> is the semigroup, as opposed to inverse semigroup, generated by the elements of <code class="code">GeneratorsOfInverseSemigroup(<var class="Arg">S</var>)</code> and their inverses.</p>
<p>If <var class="Arg">S</var> is an inverse monoid, then <code class="code">GeneratorsOfInverseSemigroup</code> returns the generators used to define <var class="Arg">S</var>, as described above, and the identity of <var class="Arg">S</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S:=InverseMonoid(</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PartialPerm( [ 1, 2 ], [ 1, 4 ] ),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PartialPerm( [ 1, 2, 4 ], [ 3, 4, 1 ] ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup(S);</span>
[ <identity partial perm on [ 1, 2, 3, 4 ]>, [2,4](1), [2,4,1,3],
[4,2](1), [3,1,4,2] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfInverseSemigroup(S);</span>
[ [2,4](1), [2,4,1,3], <identity partial perm on [ 1, 2, 3, 4 ]> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfMonoid(S);</span>
[ [2,4](1), [2,4,1,3], [4,2](1), [3,1,4,2] ]</pre></div>
<p><a id="X7A3B262C85B6D475" name="X7A3B262C85B6D475"></a></p>
<h5>51.3-4 GeneratorsOfInverseMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfInverseMonoid</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: The generators of an inverse monoid.</p>
<p>If <var class="Arg">S</var> is an inverse monoid, then <code class="code">GeneratorsOfInverseMonoid</code> returns the generators used to define <var class="Arg">S</var>, i.e. an inverse monoid generating set for <var class="Arg">S</var>.</p>
<p>There are four different possible generating sets which define an inverse monoid. More precisely, an inverse monoid can be generated as an inverse monoid, inverse semigroup, monoid, or semigroup. The different generating sets in each case can be obtained using <code class="func">GeneratorsOfInverseMonoid</code>, <code class="func">GeneratorsOfInverseSemigroup</code> (<a href="chap51.html#X87C373597F787250"><span class="RefLink">51.3-3</span></a>), <code class="func">GeneratorsOfMonoid</code> (<a href="chap51.html#X83CA2E7279C44718"><span class="RefLink">51.2-7</span></a>), and <code class="func">GeneratorsOfSemigroup</code> (<a href="chap51.html#X78147A247963F23B"><span class="RefLink">51.1-8</span></a>), respectively.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S:=InverseMonoid(</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PartialPerm( [ 1, 2 ], [ 1, 4 ] ),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PartialPerm( [ 1, 2, 4 ], [ 3, 4, 1 ] ) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfInverseMonoid(S);</span>
[ [2,4](1), [2,4,1,3] ]</pre></div>
<p><a id="X7C4C6EE681E7A57E" name="X7C4C6EE681E7A57E"></a></p>
<h5>51.3-5 IsInverseSubsemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsInverseSubsemigroup</code>( <var class="Arg">S</var>, <var class="Arg">T</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>If the semigroup <var class="Arg">T</var> is an inverse subsemigroup of the semigroup <var class="Arg">S</var>, then this operation returns <code class="keyw">true</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">T:=InverseSemigroup(RandomPartialPerm(4));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsInverseSubsemigroup(SymmetricInverseSemigroup(4), T);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">T:=Semigroup(Transformation( [ 1, 2, 4, 5, 6, 3, 7, 8 ] ),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation( [ 3, 3, 4, 5, 6, 2, 7, 8 ] ),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([ 1, 2, 5, 3, 6, 8, 4, 4 ] ));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsInverseSubsemigroup(FullTransformationSemigroup(8), T);</span>
true</pre></div>
<p><a id="X78274024827F306D" name="X78274024827F306D"></a></p>
<h4>51.4 <span class="Heading">Properties of Semigroups</span></h4>
<p>The following functions determine information about semigroups.</p>
<p><a id="X7C4663827C5ACEF1" name="X7C4663827C5ACEF1"></a></p>
<h5>51.4-1 IsRegularSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRegularSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if <var class="Arg">S</var> is regular, i.e., if every \(\mathcal{D}\)-class of <var class="Arg">S</var> is regular.</p>
<p><a id="X87532A76854347E0" name="X87532A76854347E0"></a></p>
<h5>51.4-2 IsRegularSemigroupElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRegularSemigroupElement</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns <code class="keyw">true</code> if <var class="Arg">x</var> has a general inverse in <var class="Arg">S</var>, i.e., there is an element <span class="SimpleMath">y ∈ <var class="Arg">S</var></span> such that <span class="SimpleMath"><var class="Arg">x</var> y <var class="Arg">x</var> = <var class="Arg">x</var></span> and <span class="SimpleMath">y <var class="Arg">x</var> y = y</span>.</p>
<p><a id="X7AFDE0F17AE516C5" name="X7AFDE0F17AE516C5"></a></p>
<h5>51.4-3 InversesOfSemigroupElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InversesOfSemigroupElement</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of the inverses of an element of a semigroup.</p>
<p><code class="code">InversesOfSemigroupElement</code> returns a list of the inverses of the element <var class="Arg">x</var> in the semigroup <var class="Arg">S</var>.</p>
<p>An element <var class="Arg">y</var> in <var class="Arg">S</var> is an <em>inverse</em> of <var class="Arg">x</var> if <code class="code"><var class="Arg">x</var>*y*<var class="Arg">x</var>=<var class="Arg">x</var></code> and <code class="code">y*<var class="Arg">x</var>*y=y</code>. The element <var class="Arg">x</var> has an inverse if and only if <var class="Arg">x</var> is a regular element of <var class="Arg">S</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([5, 7, 8, 8, 7, 5, 9, 1, 9]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([7, 6, 2, 8, 4, 7, 5, 8, 3])]);</span>
<transformation semigroup of degree 9 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">InversesOfSemigroupElement(S, x);</span>
[ ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRegularSemigroupElement(S, x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([1, 9, 7, 5, 5, 1, 9, 5, 1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Set(InversesOfSemigroupElement(S, x));</span>
[ Transformation( [ 1, 2, 3, 5, 5, 1, 3, 5, 2 ] ),
Transformation( [ 1, 5, 1, 1, 5, 1, 3, 1, 2 ] ),
Transformation( [ 1, 5, 1, 2, 5, 1, 3, 2, 2 ] ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRegularSemigroupElement(S, x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">S := ReesZeroMatrixSemigroup(Group((1,2,3)),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [[(), ()], [(), 0], [(), (1,2,3)]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := ReesZeroMatrixSemigroupElement(S, 2, (1,2,3), 3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">InversesOfSemigroupElement(S, x);</span>
[ (1,(1,2,3),3), (1,(1,3,2),1), (2,(),3), (2,(1,2,3),1) ]</pre></div>
<p><a id="X836F4692839F4874" name="X836F4692839F4874"></a></p>
<h5>51.4-4 IsSimpleSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSimpleSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is <code class="keyw">true</code> if and only if the semigroup <var class="Arg">S</var> has no proper ideals.</p>
<p><a id="X8193A60F839C064E" name="X8193A60F839C064E"></a></p>
<h5>51.4-5 IsZeroSimpleSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsZeroSimpleSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is <code class="keyw">true</code> if and only if the semigroup has no proper ideals except for 0, where <var class="Arg">S</var> is a semigroup with zero. If the semigroup does not find its zero, then a break-loop is entered.</p>
<p><a id="X85F7E5CD86F0643B" name="X85F7E5CD86F0643B"></a></p>
<h5>51.4-6 IsZeroGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsZeroGroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>is <code class="keyw">true</code> if and only if the semigroup <var class="Arg">S</var> is a group with zero adjoined.</p>
<p><a id="X7FFEC81F7F2C4EAA" name="X7FFEC81F7F2C4EAA"></a></p>
<h5>51.4-7 IsReesCongruenceSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsReesCongruenceSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</t | |
