SSL chap11.html
Sprache: unbekannt
|
|
<?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 (Semigroups) - Chapter 11:
Attributes and operations for semigroups
</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="chap11" 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="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="chap10.html">[Previous Chapter]</a> <a href="chap12.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap11_mj.html">[MathJax on]</a></p>
<p><a id="X7C75B1DB81C7779B" name="X7C75B1DB81C7779B"></a></p>
<div class="ChapSects"><a href="chap11.html#X7C75B1DB81C7779B">11 <span class="Heading">
Attributes and operations for semigroups
</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7AE0630287B8A757">11.1 <span class="Heading">
Accessing the elements of a semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7AC3FAA5826516AD">11.1-1 AsListCanonical</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7B4B10AE81602D4E">11.1-2 PositionCanonical</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BCD5342793C7A7E">11.1-3 Enumerate</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X877FAAA67F834897">11.1-4 IsEnumerated</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X789D5E5A8558AA07">11.2 <span class="Heading">
Cayley graphs
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7EA002E27B10CCE0">11.2-1 RightCayleyDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X824184C785BF12FF">11.3 <span class="Heading">
Random elements of a semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BB7FDFE7AFFD672">11.3-1 Random</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X80EB463F7E5D8920">11.4 <span class="Heading">
Properties of elements in a semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X869AC4247E2BA4A2">11.4-1 IndexPeriodOfSemigroupElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X84E1A41F84B70DBB">11.4-2 SmallestIdempotentPower</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7A20EC348515E37B">11.5 <span class="Heading">
Operations for elements in a semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BDAC0B581B71D0F">11.5-1 OneInverseOfSemigroupElement</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X81CEB3717E021643">11.6 <span class="Heading">
Expressing semigroup elements as words in generators
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X799D2F3C866B9AED">11.6-1 EvaluateWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8357294D7B164106">11.6-2 Factorization</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X83A4D71382C5B6C3">11.6-3 MinimalFactorization</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X86261F4682DC9842">11.6-4 NonTrivialFactorization</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7E4AA1437A6C7B40">11.7 <span class="Heading">
Generating sets
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BD5B55C802805B4">11.7-1 Generators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X814DBABC878D5232">11.7-2 SmallGeneratingSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7F88DA9487720D2B">11.7-3 IrredundantGeneratingSubset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8409DBED7996D495">11.7-4 MinimalSemigroupGeneratingSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X82B02F0887AD1B78">11.7-5 GeneratorsSmallest</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7B4CD8937858A895">11.7-6 IndecomposableElements</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X830E18747A0B5BED">11.8 <span class="Heading">
Minimal ideals and multiplicative zeros
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BC68589879C3BE9">11.8-1 MinimalIdeal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7CA6744182D07C5B">11.8-2 RepresentativeOfMinimalIdeal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7B39F93C8136D642">11.8-3 MultiplicativeZero</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7CD6F5CB83B030B6">11.8-4 UnderlyingSemigroupOfSemigroupWithAdjoinedZero</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7CAB17667ED5A6E8">11.9 <span class="Heading">
Group of units and identity elements
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X811AEDD88280C277">11.9-1 GroupOfUnits</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7C651C9C78398FFF">11.10 <span class="Heading">
Idempotents
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7C651C9C78398FFF">11.10-1 Idempotents</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7CFC4DB387452320">11.10-2 NrIdempotents</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X83970D028143B79B">11.10-3 IdempotentGeneratedSubsemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7D490B867CEFCBEF">11.11 <span class="Heading">
Maximal subsemigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X860A10E387C19150">11.11-1 MaximalSubsemigroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7A52B4117BCEF379">11.11-2 NrMaximalSubsemigroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X82D74C2478A49FD5">11.11-3 IsMaximalSubsemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X87696C597F453F4F">11.12 <span class="Heading">
Attributes of transformations and transformation semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8065DBC48722B085">11.12-1 ComponentRepsOfTransformationSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8706A72A7F3EE532">11.12-2 ComponentsOfTransformationSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7AA697B186301F54">11.12-3 CyclesOfTransformationSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8089CF7182AD1925">11.12-4 DigraphOfAction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7B5ACD5C7E7612A2">11.12-5 DigraphOfActionOnPoints</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7C6D8689819AEEE2">11.12-6 FixedPointsOfTransformationSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X83DA161F875F63B1">11.12-7 IsTransitive</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7C65202187A9C9F5">11.12-8 SmallestElementSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X84792D3D804413CD">11.12-9 CanonicalTransformation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X82ABE03F80B8CA2B">11.12-10 IsConnectedTransformationSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X84B8E29C7D7565B0">11.13 <span class="Heading">
Attributes of partial perm semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BC22CB47C7B5EBB">11.13-1 ComponentRepsOfPartialPermSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8464BC397ACBF2F1">11.13-2 ComponentsOfPartialPermSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X832937BB87EB4349">11.13-3 CyclesOfPartialPerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7F7A5E5E8355E230">11.13-4 CyclesOfPartialPermSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7AF313CF7CBE98D7">11.14 <span class="Heading">
Attributes of Rees (0-)matrix semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7EA1B28785B9D38C">11.14-1 RZMSDigraph</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X79B062917AB34542">11.14-2 RZMSConnectedComponents</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X822D030682BC1275">11.15 <span class="Heading">
Attributes of inverse semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7A75A6C486F1DC71">11.15-1 NaturalLeqInverseSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X85CDF93C805AF82A">11.15-2 JoinIrreducibleDClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X801CC67E80898608">11.15-3 MajorantClosure</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X84A3DB79816374DB">11.15-4 Minorants</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X80C0C6C37C4A2ABD">11.15-5 PrimitiveIdempotents</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7B5D89A585F8B5EA">11.15-6 RightCosetsOfInverseSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X83298E9E86A343FF">11.15-7 SameMinorantsSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X786D4E397EA4445D">11.15-8 SmallerDegreePartialPermRepresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7BC49C3487384364">11.15-9 VagnerPrestonRepresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7C83DF9A7973AF6D">11.15-10 CharacterTableOfInverseSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X8383E6747D02D975">11.15-11 EUnitaryInverseCover</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11.html#X7AA4CE887EEA661A">11.16 <span class="Heading">
Nambooripad partial order
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7A7EB0DA8398886E">11.16-1 NambooripadLeqRegularSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11.html#X7928C7D37A9BCBD5">11.16-2 NambooripadPartialOrder</a></span>
</div></div>
</div>
<h3>11 <span class="Heading">
Attributes and operations for semigroups
</span></h3>
<p>In this chapter we describe the methods that are available in <strong class="pkg">Semigroups</strong> for determining the attributes of a semigroup, and the operations which can be applied to a semigroup.</p>
<p><a id="X7AE0630287B8A757" name="X7AE0630287B8A757"></a></p>
<h4>11.1 <span class="Heading">
Accessing the elements of a semigroup
</span></h4>
<p><a id="X7AC3FAA5826516AD" name="X7AC3FAA5826516AD"></a></p>
<h5>11.1-1 AsListCanonical</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsListCanonical</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumeratorCanonical</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorCanonical</code>( <var class="Arg">S</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list, enumerator, or iterator.</p>
<p>When the argument <var class="Arg">S</var> is a semigroup satisfying <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>), <code class="code">AsListCanonical</code> returns a list of the elements of <var class="Arg">S</var> in the order they are enumerated by the Froidure-Pin Algorithm. This is the same as the order used to index the elements of <var class="Arg">S</var> in <code class="func">RightCayleyDigraph</code> (<a href="chap11.html#X7EA002E27B10CCE0"><span class="RefLink">11.2-1</span></a>) and <code class="func">LeftCayleyDigraph</code> (<a href="chap11.html#X7EA002E27B10CCE0"><span class="RefLink">11.2-1</span></a>).</p>
<p><code class="code">EnumeratorCanonical</code> and <code class="code">IteratorCanonical</code> return an enumerator and an iterator where the elements are ordered in the same way as <code class="code">AsListCanonical</code>. Using <code class="code">EnumeratorCanonical</code> or <code class="code">IteratorCanonical</code> will often use less memory than <code class="code">AsListCanonical</code>, but may have slightly worse performance if the elements of the semigroup are looped over repeatedly. <code class="code">EnumeratorCanonical</code> returns the same list as <code class="code">AsListCanonical</code> if <code class="code">AsListCanonical</code> has ever been called for <var class="Arg">S</var>.</p>
<p>If <var class="Arg">S</var> is an acting semigroup, then the value returned by <code class="code">AsList</code> may not equal the value returned by <code class="code">AsListCanonical</code>. <code class="code">AsListCanonical</code> exists so that there is a method for obtaining the elements of <var class="Arg">S</var> in the particular order used by <code class="func">RightCayleyDigraph</code> (<a href="chap11.html#X7EA002E27B10CCE0"><span class="RefLink">11.2-1</span></a>) and <code class="func">LeftCayleyDigraph</code> (<a href="chap11.html#X7EA002E27B10CCE0"><span class="RefLink">11.2-1</span></a>).</p>
<p>See also <code class="func">PositionCanonical</code> (<a href="chap11.html#X7B4B10AE81602D4E"><span class="RefLink">11.1-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 3, 2]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsListCanonical(S);</span>
[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IteratorCanonical(S);</span>
<iterator>
<span class="GAPprompt">gap></span> <span class="GAPinput">EnumeratorCanonical(S);</span>
[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid([Matrix(IsBooleanMat, [[1, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [0, 1, 0]])]);</span>
<commutative monoid of 3x3 boolean matrices with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">it := IteratorCanonical(S);</span>
<iterator>
<span class="GAPprompt">gap></span> <span class="GAPinput">NextIterator(it);</span>
Matrix(IsBooleanMat, [[1, 0, 0], [0, 1, 0], [0, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">en := EnumeratorCanonical(S);</span>
<enumerator of <commutative monoid of size 2, 3x3 boolean matrices
with 1 generator>>
<span class="GAPprompt">gap></span> <span class="GAPinput">en[1];</span>
Matrix(IsBooleanMat, [[1, 0, 0], [0, 1, 0], [0, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Position(en, en[1]);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(en);</span>
2</pre></div>
<p><a id="X7B4B10AE81602D4E" name="X7B4B10AE81602D4E"></a></p>
<h5>11.1-2 PositionCanonical</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositionCanonical</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A positive integer or <code class="keyw">fail</code>.</p>
<p>When the argument <var class="Arg">S</var> is a semigroup satisfying <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>) and <var class="Arg">x</var> is an element of <var class="Arg">S</var>, <code class="code">PositionCanonical</code> returns the position of <var class="Arg">x</var> in <code class="code">AsListCanonical(<var class="Arg">S</var>)</code> or equivalently the position of <var class="Arg">x</var> in <code class="code">EnumeratorCanonical(<var class="Arg">S</var>)</code>.</p>
<p>See also <code class="func">AsListCanonical</code> (<a href="chap11.html#X7AC3FAA5826516AD"><span class="RefLink">11.1-1</span></a>) and <code class="func">EnumeratorCanonical</code> (<a href="chap11.html#X7AC3FAA5826516AD"><span class="RefLink">11.1-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTropicalMaxPlusMonoid(2, 3);</span>
<monoid of 2x2 tropical max-plus matrices with 13 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Matrix(IsTropicalMaxPlusMatrix, [[1, 3], [2, 1]], 3);</span>
Matrix(IsTropicalMaxPlusMatrix, [[1, 3], [2, 1]], 3)
<span class="GAPprompt">gap></span> <span class="GAPinput">PositionCanonical(S, x);</span>
234
<span class="GAPprompt">gap></span> <span class="GAPinput">EnumeratorCanonical(S)[234] = x;</span>
true</pre></div>
<p><a id="X7BCD5342793C7A7E" name="X7BCD5342793C7A7E"></a></p>
<h5>11.1-3 Enumerate</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Enumerate</code>( <var class="Arg">S</var>[, <var class="Arg">limit</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup (the argument).</p>
<p>If <var class="Arg">S</var> is a semigroup with representation <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>) and <var class="Arg">limit</var> is a positive integer, then this operation can be used to enumerate at least <var class="Arg">limit</var> elements of <var class="Arg">S</var>, or <code class="code">Size(<var class="Arg">S</var>)</code> elements if this is less than <var class="Arg">limit</var>, using the Froidure-Pin Algorithm.</p>
<p>If the optional second argument <var class="Arg">limit</var> is not given, then the semigroup is enumerated until all of its elements have been found.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTransformationMonoid(7);</span>
<full transformation monoid of degree 7>
<span class="GAPprompt">gap></span> <span class="GAPinput">Enumerate(S, 1000);</span>
<full transformation monoid of degree 7></pre></div>
<p><a id="X877FAAA67F834897" name="X877FAAA67F834897"></a></p>
<h5>11.1-4 IsEnumerated</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEnumerated</code>( <var class="Arg">S</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 <var class="Arg">S</var> is a semigroup with representation <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>), then this operation returns <code class="keyw">true</code> if the Froidure-Pin Algorithm has been run to completion (i.e. all of the elements of <var class="Arg">S</var> have been found) and <code class="keyw">false</code> if <var class="Arg">S</var> has not been fully enumerated.</p>
<p><a id="X789D5E5A8558AA07" name="X789D5E5A8558AA07"></a></p>
<h4>11.2 <span class="Heading">
Cayley graphs
</span></h4>
<p><a id="X7EA002E27B10CCE0" name="X7EA002E27B10CCE0"></a></p>
<h5>11.2-1 RightCayleyDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightCayleyDigraph</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftCayleyDigraph</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A digraph.</p>
<p>When the argument <var class="Arg">S</var> is a semigroup satisfying <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>), <code class="code">RightCayleyDigraph</code> returns the right Cayley graph of <var class="Arg">S</var>, as a <code class="func">Digraph</code> (<a href="https://gap-packages.github.io/io/doc/chap3_mj.html#X834843057CE86655"><span class="RefLink">Digraphs: Digraph</span></a>) <code class="code">digraph</code> where vertex <code class="code">OutNeighbours(digraph)[i][j]</code> is <code class="code">PositionCanonical(<var class="Arg">S</var>, AsListCanonical(<var class="Arg">S</var>)[i] * GeneratorsOfSemigroup(<var class="Arg">S</var>)[j])</code>. The digraph returned by <code class="code">LeftCayleyDigraph</code> is defined analogously.</p>
<p>The digraph returned by this attribute belongs to the category <code class="func">IsCayleyDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap3_mj.html#X7E749324800B38A5"><span class="RefLink">Digraphs: IsCayleyDigraph</span></a>), the semigroup <var class="Arg">S</var> and the generators used to create the digraph can be recovered from the digraph using <code class="func">SemigroupOfCayleyDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap5_mj.html#X7A000B1D7CCF7093"><span class="RefLink">Digraphs: SemigroupOfCayleyDigraph</span></a>) and <code class="func">GeneratorsOfCayleyDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap5_mj.html#X8528455987D7D2BF"><span class="RefLink">Digraphs: GeneratorsOfCayleyDigraph</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTransformationMonoid(2);</span>
<full transformation monoid of degree 2>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightCayleyDigraph(S);</span>
<immutable multidigraph with 4 vertices, 12 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftCayleyDigraph(S);</span>
<immutable multidigraph with 4 vertices, 12 edges></pre></div>
<p><a id="X824184C785BF12FF" name="X824184C785BF12FF"></a></p>
<h4>11.3 <span class="Heading">
Random elements of a semigroup
</span></h4>
<p><a id="X7BB7FDFE7AFFD672" name="X7BB7FDFE7AFFD672"></a></p>
<h5>11.3-1 Random</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Random</code>( <var class="Arg">S</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: A random element.</p>
<p>This function returns a random element of the semigroup <var class="Arg">S</var>. If the elements of <var class="Arg">S</var> have been calculated, then one of these is chosen randomly. Otherwise, if the data structure for <var class="Arg">S</var> is known, then a random element of a randomly chosen <em>R</em>-class is returned. If the data structure for <var class="Arg">S</var> has not been calculated, then a short product (at most <code class="code">2 * Length(GeneratorsOfSemigroup(<var class="Arg">S</var>))</code>) of generators is returned.</p>
<p><a id="X80EB463F7E5D8920" name="X80EB463F7E5D8920"></a></p>
<h4>11.4 <span class="Heading">
Properties of elements in a semigroup
</span></h4>
<p><a id="X869AC4247E2BA4A2" name="X869AC4247E2BA4A2"></a></p>
<h5>11.4-1 IndexPeriodOfSemigroupElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IndexPeriodOfSemigroupElement</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of two positive integers.</p>
<p>If <var class="Arg">x</var> is a semigroup element, then <code class="code">IndexPeriodOfSemigroupElement(<var class="Arg">x</var>)</code> returns the pair <code class="code">[m, r]</code>, where <code class="code">m</code> and <code class="code">r</code> are the least positive integers such that <code class="code"><var class="Arg">x</var>^(m + r) = <var class="Arg">x</var> ^ m</code>. The number <code class="code">m</code> is known as the <em>index</em> of <var class="Arg">x</var>, and the number<code class="code">r</code> is known as the <em>period</em> of <var class="Arg">x</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([2, 6, 3, 5, 6, 1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IndexPeriodOfSemigroupElement(x);</span>
[ 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">m := IndexPeriodOfSemigroupElement(x)[1];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">r := IndexPeriodOfSemigroupElement(x)[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x ^ (m + r) = x ^ m;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([0, 2, 3, 0, 5]);</span>
<identity partial perm on [ 2, 3, 5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdempotent(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IndexPeriodOfSemigroupElement(x);</span>
[ 1, 1 ]
</pre></div>
<p><a id="X84E1A41F84B70DBB" name="X84E1A41F84B70DBB"></a></p>
<h5>11.4-2 SmallestIdempotentPower</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestIdempotentPower</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>
<p>If <var class="Arg">x</var> is a semigroup element, then <code class="code">SmallestIdempotentPower(<var class="Arg">x</var>)</code> returns the least positive integer <code class="code">n</code> such that <code class="code"><var class="Arg">x</var>^n</code> is an idempotent. The smallest idempotent power of <var class="Arg">x</var> is the least multiple of the period of <var class="Arg">x</var> that is greater than or equal to the index of <var class="Arg">x</var>; see <code class="func">IndexPeriodOfSemigroupElement</code> (<a href="chap11.html#X869AC4247E2BA4A2"><span class="RefLink">11.4-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([4, 1, 4, 5, 1]);</span>
Transformation( [ 4, 1, 4, 5, 1 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestIdempotentPower(x);</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([1 .. 2], i -> not IsIdempotent(x ^ i));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdempotent(x ^ 3);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 2, -3, -4], [3, -5], [4, -1], [5, -2]]);</span>
<block bijection: [ 1, 2, -3, -4 ], [ 3, -5 ], [ 4, -1 ], [ 5, -2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestIdempotentPower(x);</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([1 .. 3], i -> not IsIdempotent(x ^ i));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([]);</span>
<empty partial perm>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestIdempotentPower(x);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdempotent(x);</span>
true</pre></div>
<p><a id="X7A20EC348515E37B" name="X7A20EC348515E37B"></a></p>
<h4>11.5 <span class="Heading">
Operations for elements in a semigroup
</span></h4>
<p><a id="X7BDAC0B581B71D0F" name="X7BDAC0B581B71D0F"></a></p>
<h5>11.5-1 OneInverseOfSemigroupElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OneInverseOfSemigroupElement</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: One inverse of an element of a semigroup.</p>
<p><code class="code">OneInverseOfSemigroupElement</code> returns one inverse of the element <code class="code">x</code> in the semigroup <var class="Arg">S</var> and returns fail if this element has no inverse in <var class="Arg">S</var>. <var class="Arg">x</var> in the semigroup <var class="Arg">S</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTransformationMonoid(4);</span>
<full transformation monoid of degree 4>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := Transformation([2, 3, 1, 1]);</span>
Transformation( [ 2, 3, 1, 1 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">OneInverseOfSemigroupElement(S, s);</span>
Transformation( [ 3, 1, 2, 2 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">e := IdentityTransformation;</span>
IdentityTransformation
<span class="GAPprompt">gap></span> <span class="GAPinput">OneInverseOfSemigroupElement(S, e);</span>
IdentityTransformation
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup(1);</span>
<free semigroup on the generators [ s1 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">OneInverseOfSemigroupElement(F, F.1);</span>
Error, the semigroup is not finite</pre></div>
<p><a id="X81CEB3717E021643" name="X81CEB3717E021643"></a></p>
<h4>11.6 <span class="Heading">
Expressing semigroup elements as words in generators
</span></h4>
<p>It is possible to express an element of a semigroup as a word in the generators of that semigroup. This section describes how to accomplish this in <strong class="pkg">Semigroups</strong>.</p>
<p><a id="X799D2F3C866B9AED" name="X799D2F3C866B9AED"></a></p>
<h5>11.6-1 EvaluateWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EvaluateWord</code>( <var class="Arg">gens</var>, <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup element.</p>
<p>The argument <var class="Arg">gens</var> should be a collection of generators of a semigroup and the argument <var class="Arg">w</var> should be a list of positive integers less than or equal to the length of <var class="Arg">gens</var>. This operation evaluates the word <var class="Arg">w</var> in the generators <var class="Arg">gens</var>. More precisely, <code class="code">EvaluateWord(<var class="Arg">gens</var>, <var class="Arg">w</var>)</code> returns the equivalent of:</p>
<div class="example"><pre>Product(List(w, i -> gens[i]));</pre></div>
<p>see also <code class="func">Factorization</code> (<a href="chap11.html#X8357294D7B164106"><span class="RefLink">11.6-2</span></a>).</p>
<dl>
<dt><strong class="Mark">for elements of a semigroup</strong></dt>
<dd><p>When <var class="Arg">gens</var> is a list of elements of a semigroup and <var class="Arg">w</var> is a list of positive integers less than or equal to the length of <var class="Arg">gens</var>, this operation returns the product <code class="code">gens[w[1]] * gens[w[2]] * .. . * gens[w[n]]</code> when the length of <var class="Arg">w</var> is <code class="code">n</code>.</p>
</dd>
<dt><strong class="Mark">for elements of an inverse semigroup</strong></dt>
<dd><p>When <var class="Arg">gens</var> is a list of elements with a semigroup inverse and <var class="Arg">w</var> is a list of non-zero integers whose absolute value does not exceed the length of <var class="Arg">gens</var>, this operation returns the product <code class="code">gens[AbsInt(w[1])] ^ SignInt(w[1]) * .. . * gens[AbsInt(w[n])] ^ SignInt(w[n])</code> where <code class="code">n</code> is the length of <var class="Arg">w</var>.</p>
</dd>
</dl>
<p>Note that <code class="code">EvaluateWord(<var class="Arg">gens</var>, [])</code> returns <code class="code">One(<var class="Arg">gens</var>)</code> if <var class="Arg">gens</var> belongs to the category <code class="func">IsMultiplicativeElementWithOne</code> (<a href="../../../doc/ref/chap31_mj.html#X82BC294F7D388AE8"><span class="RefLink">Reference: IsMultiplicativeElementWithOne</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := [</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([2, 4, 4, 6, 8, 8, 6, 6]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([2, 7, 4, 1, 4, 6, 5, 2]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([3, 6, 2, 4, 2, 2, 2, 8]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([4, 3, 6, 4, 2, 1, 2, 6]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([4, 5, 1, 3, 8, 5, 8, 2])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(gens);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([1, 4, 6, 1, 7, 2, 7, 6]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">word := Factorization(S, x);</span>
[ 4, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">EvaluateWord(gens, word);</span>
Transformation( [ 1, 4, 6, 1, 7, 2, 7, 6 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">S := SymmetricInverseMonoid(10);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([2, 6, 7, 0, 0, 9, 0, 1, 0, 5]);</span>
[3,7][8,1,2,6,9][10,5]
<span class="GAPprompt">gap></span> <span class="GAPinput">word := Factorization(S, x);</span>
[ -2, -2, -2, -2, -3, -2, -2, -2, -2, -2, 5, 2, 5, 5, 2, 5, 2, 2, 2,
2, -3, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">EvaluateWord(GeneratorsOfSemigroup(S), word);</span>
[3,7][8,1,2,6,9][10,5]</pre></div>
<p><a id="X8357294D7B164106" name="X8357294D7B164106"></a></p>
<h5>11.6-2 Factorization</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Factorization</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A word in the generators.</p>
<dl>
<dt><strong class="Mark">for semigroups</strong></dt>
<dd><p>When <var class="Arg">S</var> is a semigroup and <var class="Arg">x</var> belongs to <var class="Arg">S</var>, <code class="code">Factorization</code> return a word in the generators of <var class="Arg">S</var> that is equal to <var class="Arg">x</var>. In this case, a word is a list of positive integers where an entry <code class="code">i</code> corresponds to <code class="code">GeneratorsOfSemigroups(S)[i]</code>. More specifically,</p>
<div class="example"><pre>EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, x)) = x;</pre></div>
</dd>
<dt><strong class="Mark">for inverse semigroups</strong></dt>
<dd><p>When <var class="Arg">S</var> is an inverse semigroup and <var class="Arg">x</var> belongs to <var class="Arg">S</var>, <code class="code">Factorization</code> return a word in the generators of <var class="Arg">S</var> that is equal to <var class="Arg">x</var>. In this case, a word is a list of non-zero integers where an entry <code class="code">i</code> corresponds to <code class="code">GeneratorsOfSemigroup(S)[i]</code> and <code class="code">-i</code> corresponds to <code class="code">GeneratorsOfSemigroup(S)[i] ^ -1</code>. As in the previous case,</p>
<div class="example"><pre>EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, x)) = x;</pre></div>
</dd>
</dl>
<p>Note that <code class="code">Factorization</code> does not always return a word of minimum length; see <code class="func">MinimalFactorization</code> (<a href="chap11.html#X83A4D71382C5B6C3"><span class="RefLink">11.6-3</span></a>).</p>
<p>See also <code class="func">EvaluateWord</code> (<a href="chap11.html#X799D2F3C866B9AED"><span class="RefLink">11.6-1</span></a>) and <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B"><span class="RefLink">Reference: GeneratorsOfSemigroup</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := [Transformation([2, 2, 9, 7, 4, 9, 5, 5, 4, 8]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 10, 5, 6, 4, 1, 2, 7, 1, 2])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(gens);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([1, 10, 2, 10, 1, 2, 7, 10, 2, 7]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">word := Factorization(S, x);</span>
[ 2, 2, 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">EvaluateWord(gens, word);</span>
Transformation( [ 1, 10, 2, 10, 1, 2, 7, 10, 2, 7 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">S := SymmetricInverseMonoid(8);</span>
<symmetric inverse monoid of degree 8>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([1, 2, 3, 4, 5, 8], [7, 1, 4, 3, 2, 6]);</span>
[5,2,1,7][8,6](3,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">word := Factorization(S, x);</span>
[ -2, -2, -2, -2, -2, -2, 2, 4, 4, 2, 3, 2, -3, -2, -2, 3, 2, -3, -2,
-2, 4, -3, -4, 2, 2, 3, -2, -3, 4, -3, -4, 2, 2, 3, -2, -3, 2, 2,
3, -2, -3, 2, 2, 3, -2, -3, 4, -3, -4, 3, 2, -3, -2, -2, 3, 2, -3,
-2, -2, 4, 3, -4, 3, 2, -3, -2, -2, 3, 2, -3, -2, -2, 3, 2, 2, 3,
2, 2, 2, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">EvaluateWord(GeneratorsOfSemigroup(S), word);</span>
[5,2,1,7][8,6](3,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">S := DualSymmetricInverseMonoid(6);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := S.1 * S.2 * S.3 * S.2 * S.1;</span>
<block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ],
[ 5, -1 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">word := Factorization(S, x);</span>
[ -2, -2, -2, -2, -2, 4, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">EvaluateWord(GeneratorsOfSemigroup(S), word);</span>
<block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ],
[ 5, -1 ]></pre></div>
<p><a id="X83A4D71382C5B6C3" name="X83A4D71382C5B6C3"></a></p>
<h5>11.6-3 MinimalFactorization</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalFactorization</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A minimal word in the generators.</p>
<p>This operation returns a minimal length word in the generators of the semigroup <var class="Arg">S</var> that equals the element <var class="Arg">x</var>. In this case, a word is a list of positive integers where an entry <code class="code">i</code> corresponds to <code class="code">GeneratorsOfSemigroups(<var class="Arg">S</var>)[i]</code>. More specifically,</p>
<div class="example"><pre>EvaluateWord(GeneratorsOfSemigroup(S), MinimalFactorization(S, x)) = x;</pre></div>
<p><code class="code">MinimalFactorization</code> involves exhaustively enumerating <var class="Arg">S</var> until the element <var class="Arg">x</var> is found, and so <code class="code">MinimalFactorization</code> may be less efficient than <code class="func">Factorization</code> (<a href="chap11.html#X8357294D7B164106"><span class="RefLink">11.6-2</span></a>) for some semigroups.</p>
<p>Unlike <code class="func">Factorization</code> (<a href="chap11.html#X8357294D7B164106"><span class="RefLink">11.6-2</span></a>) this operation does not distinguish between semigroups and inverse semigroups. See also <code class="func">EvaluateWord</code> (<a href="chap11.html#X799D2F3C866B9AED"><span class="RefLink">11.6-1</span></a>) and <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B"><span class="RefLink">Reference: GeneratorsOfSemigroup</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([2, 2, 9, 7, 4, 9, 5, 5, 4, 8]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 10, 5, 6, 4, 1, 2, 7, 1, 2]));</span>
<transformation semigroup of degree 10 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([8, 8, 2, 2, 9, 2, 8, 8, 9, 9]);</span>
Transformation( [ 8, 8, 2, 2, 9, 2, 8, 8, 9, 9 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">Factorization(S, x);</span>
[ 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalFactorization(S, x);</span>
[ 1, 2, 1, 1, 1, 1, 2, 2, 1 ]</pre></div>
<p><a id="X86261F4682DC9842" name="X86261F4682DC9842"></a></p>
<h5>11.6-4 NonTrivialFactorization</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonTrivialFactorization</code>( <var class="Arg">S</var>, <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A non-trivial word in the generators, or <code class="keyw">fail</code>.</p>
<p>When <var class="Arg">S</var> is a semigroup and <var class="Arg">x</var> belongs to <var class="Arg">S</var>, this operation returns a non-trivial word in the generators of the semigroup <var class="Arg">S</var> that equals <var class="Arg">x</var>, if one exists. The definition of a word in the generators is the same as given in <code class="func">Factorization</code> (<a href="chap11.html#X8357294D7B164106"><span class="RefLink">11.6-2</span></a>) for semigroups and inverse semigroups. A word is non-trivial if it has length two or more.</p>
<p>If no non-trivial word for <var class="Arg">x</var> exists, then <var class="Arg">x</var> is an indecomposable element of <var class="Arg">S</var> and this operation returns <code class="keyw">fail</code>; see <code class="func">IndecomposableElements</code> (<a href="chap11.html#X7B4CD8937858A895"><span class="RefLink">11.7-6</span></a>).</p>
<p>When <var class="Arg">x</var> does not belong to <code class="code">GeneratorsOfSemigroup(<var class="Arg">S</var>)</code>, any factorization of <var class="Arg">x</var> is non-trivial. In this case, <code class="code">NonTrivialFactorization</code> returns the same word as <code class="func">Factorization</code> (<a href="chap11.html#X8357294D7B164106"><span class="RefLink">11.6-2</span></a>).</p>
<p>See also <code class="func">EvaluateWord</code> (<a href="chap11.html#X799D2F3C866B9AED"><span class="RefLink">11.6-1</span></a>) and <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B"><span class="RefLink">Reference: GeneratorsOfSemigroup</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([5, 4, 2, 1, 3]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := Transformation([4, 4, 2, 4, 1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([x, y]);</span>
<transformation semigroup of degree 5 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">NonTrivialFactorization(S, x * y);</span>
[ 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Factorization(S, x);</span>
[ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NonTrivialFactorization(S, x);</span>
[ 1, 1, 1, 1, 1, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Factorization(S, y);</span>
[ 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NonTrivialFactorization(S, y);</span>
[ 2, 1, 1, 1, 1, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">z := PartialPerm([2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(z);</span>
<commutative partial perm semigroup of rank 1 with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">NonTrivialFactorization(S, z);</span>
fail</pre></div>
<p><a id="X7E4AA1437A6C7B40" name="X7E4AA1437A6C7B40"></a></p>
<h4>11.7 <span class="Heading">
Generating sets
</span></h4>
<p><a id="X7BD5B55C802805B4" name="X7BD5B55C802805B4"></a></p>
<h5>11.7-1 Generators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Generators</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of generators.</p>
<p><code class="code">Generators</code> returns a generating set that can be used to define the semigroup <var class="Arg">S</var>. The generators of a monoid or inverse semigroup <var class="Arg">S</var>, say, can be defined in several ways, for example, including or excluding the identity element, including or not the inverses of the generators. <code class="code">Generators</code> uses the definition that returns the least number of generators. If no generating set for <var class="Arg">S</var> is known, then <code class="code">GeneratorsOfSemigroup</code> is used by default.</p>
<dl>
<dt><strong class="Mark">for a group</strong></dt>
<dd><p><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfGroup</code> (<a href="../../../doc/ref/chap39_mj.html#X79C44528864044C5"><span class="RefLink">Reference: GeneratorsOfGroup</span></a>).</p>
</dd>
<dt><strong class="Mark">for an ideal of semigroup</strong></dt>
<dd><p><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfSemigroupIdeal</code> (<a href="chap9.html#X87BB45DB844D41BC"><span class="RefLink">9.2-1</span></a>).</p>
</dd>
<dt><strong class="Mark">for a semigroup</strong></dt>
<dd><p><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B"><span class="RefLink">Reference: GeneratorsOfSemigroup</span></a>).</p>
</dd>
<dt><strong class="Mark">for a monoid</strong></dt>
<dd><p><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X83CA2E7279C44718"><span class="RefLink">Reference: GeneratorsOfMonoid</span></a>).</p>
</dd>
<dt><strong class="Mark">for an inverse semigroup</strong></dt>
<dd><p><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfInverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X87C373597F787250"><span class="RefLink">Reference: GeneratorsOfInverseSemigroup</span></a>).</p>
</dd>
<dt><strong class="Mark">for an inverse monoid</strong></dt>
<dd><p><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfInverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7A3B262C85B6D475"><span class="RefLink">Reference: GeneratorsOfInverseMonoid</span></a>).</p>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M := Monoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup(M);</span>
[ IdentityTransformation,
Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfMonoid(M);</span>
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Generators(M);</span>
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Generators(M));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Generators(S);</span>
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfSemigroup(S);</span>
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]</pre></div>
<p><a id="X814DBABC878D5232" name="X814DBABC878D5232"></a></p>
<h5>11.7-2 SmallGeneratingSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallGeneratingSet</code>( <var class="Arg">coll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallSemigroupGeneratingSet</code>( <var class="Arg">coll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallMonoidGeneratingSet</code>( <var class="Arg">coll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallInverseSemigroupGeneratingSet</code>( <var class="Arg">coll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallInverseMonoidGeneratingSet</code>( <var class="Arg">coll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A small generating set for a semigroup.</p>
<p>The attributes <code class="code">SmallXGeneratingSet</code> return a relatively small generating subset of the collection of elements <var class="Arg">coll</var>, which can also be a semigroup. The returned value of <code class="code">SmallXGeneratingSet</code>, where applicable, has the property that</p>
<div class="example"><pre>
X(SmallXGeneratingSet(coll)) = X(coll);</pre></div>
<p>where <code class="code">X</code> is any of <code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817"><span class="RefLink">Reference: Semigroup</span></a>), <code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA"><span class="RefLink">Reference: Monoid</span></a>), <code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326"><span class="RefLink">Reference: InverseSemigroup</span></a>), or <code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B"><span class="RefLink">Reference: InverseMonoid</span></a>).</p>
<p>If the number of generators for <var class="Arg">S</var> is already relatively small, then these functions will often return the original generating set. These functions may return different results in different < | |
