Quelle chap11_mj.html

Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap11_mj.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>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap10_mj.html">[Previous Chapter]</a> <a href="chap12_mj.html">[Next Chapter]</a> </div>

<a href="chap11.html">[MathJax off]</a>
<a id="X7C75B1DB81C7779B" name="X7C75B1DB81C7779B"></a>
<div class="ChapSects"><a href="chap11_mj.html#X7C75B1DB81C7779B">11 
 Attributes and operations for semigroups
 </a>
<div class="ContSect"> <a href="chap11_mj.html#X7AE0630287B8A757">11.1 
 Accessing the elements of a semigroup
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7AC3FAA5826516AD">11.1-1 AsListCanonical</a>
 <a href="chap11_mj.html#X7B4B10AE81602D4E">11.1-2 PositionCanonical</a>
 <a href="chap11_mj.html#X7BCD5342793C7A7E">11.1-3 Enumerate</a>
 <a href="chap11_mj.html#X877FAAA67F834897">11.1-4 IsEnumerated</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X789D5E5A8558AA07">11.2 
 Cayley graphs
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7EA002E27B10CCE0">11.2-1 RightCayleyDigraph</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X824184C785BF12FF">11.3 
 Random elements of a semigroup
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7BB7FDFE7AFFD672">11.3-1 Random</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X80EB463F7E5D8920">11.4 
 Properties of elements in a semigroup
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X869AC4247E2BA4A2">11.4-1 IndexPeriodOfSemigroupElement</a>
 <a href="chap11_mj.html#X84E1A41F84B70DBB">11.4-2 SmallestIdempotentPower</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7A20EC348515E37B">11.5 
 Operations for elements in a semigroup
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7BDAC0B581B71D0F">11.5-1 OneInverseOfSemigroupElement</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X81CEB3717E021643">11.6 
 Expressing semigroup elements as words in generators
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X799D2F3C866B9AED">11.6-1 EvaluateWord</a>
 <a href="chap11_mj.html#X8357294D7B164106">11.6-2 Factorization</a>
 <a href="chap11_mj.html#X83A4D71382C5B6C3">11.6-3 MinimalFactorization</a>
 <a href="chap11_mj.html#X86261F4682DC9842">11.6-4 NonTrivialFactorization</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7E4AA1437A6C7B40">11.7 
 Generating sets
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7BD5B55C802805B4">11.7-1 Generators</a>
 <a href="chap11_mj.html#X814DBABC878D5232">11.7-2 SmallGeneratingSet</a>
 <a href="chap11_mj.html#X7F88DA9487720D2B">11.7-3 IrredundantGeneratingSubset</a>
 <a href="chap11_mj.html#X8409DBED7996D495">11.7-4 MinimalSemigroupGeneratingSet</a>
 <a href="chap11_mj.html#X82B02F0887AD1B78">11.7-5 GeneratorsSmallest</a>
 <a href="chap11_mj.html#X7B4CD8937858A895">11.7-6 IndecomposableElements</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X830E18747A0B5BED">11.8 
 Minimal ideals and multiplicative zeros
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7BC68589879C3BE9">11.8-1 MinimalIdeal</a>
 <a href="chap11_mj.html#X7CA6744182D07C5B">11.8-2 RepresentativeOfMinimalIdeal</a>
 <a href="chap11_mj.html#X7B39F93C8136D642">11.8-3 MultiplicativeZero</a>
 <a href="chap11_mj.html#X7CD6F5CB83B030B6">11.8-4 UnderlyingSemigroupOfSemigroupWithAdjoinedZero</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7CAB17667ED5A6E8">11.9 
 Group of units and identity elements
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X811AEDD88280C277">11.9-1 GroupOfUnits</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7C651C9C78398FFF">11.10 
 Idempotents
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7C651C9C78398FFF">11.10-1 Idempotents</a>
 <a href="chap11_mj.html#X7CFC4DB387452320">11.10-2 NrIdempotents</a>
 <a href="chap11_mj.html#X83970D028143B79B">11.10-3 IdempotentGeneratedSubsemigroup</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7D490B867CEFCBEF">11.11 
 Maximal subsemigroups
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X860A10E387C19150">11.11-1 MaximalSubsemigroups</a>
 <a href="chap11_mj.html#X7A52B4117BCEF379">11.11-2 NrMaximalSubsemigroups</a>
 <a href="chap11_mj.html#X82D74C2478A49FD5">11.11-3 IsMaximalSubsemigroup</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X87696C597F453F4F">11.12 
 Attributes of transformations and transformation semigroups
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X8065DBC48722B085">11.12-1 ComponentRepsOfTransformationSemigroup</a>
 <a href="chap11_mj.html#X8706A72A7F3EE532">11.12-2 ComponentsOfTransformationSemigroup</a>
 <a href="chap11_mj.html#X7AA697B186301F54">11.12-3 CyclesOfTransformationSemigroup</a>
 <a href="chap11_mj.html#X8089CF7182AD1925">11.12-4 DigraphOfAction</a>
 <a href="chap11_mj.html#X7B5ACD5C7E7612A2">11.12-5 DigraphOfActionOnPoints</a>
 <a href="chap11_mj.html#X7C6D8689819AEEE2">11.12-6 FixedPointsOfTransformationSemigroup</a>
 <a href="chap11_mj.html#X83DA161F875F63B1">11.12-7 IsTransitive</a>
 <a href="chap11_mj.html#X7C65202187A9C9F5">11.12-8 SmallestElementSemigroup</a>
 <a href="chap11_mj.html#X84792D3D804413CD">11.12-9 CanonicalTransformation</a>
 <a href="chap11_mj.html#X82ABE03F80B8CA2B">11.12-10 IsConnectedTransformationSemigroup</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X84B8E29C7D7565B0">11.13 
 Attributes of partial perm semigroups
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7BC22CB47C7B5EBB">11.13-1 ComponentRepsOfPartialPermSemigroup</a>
 <a href="chap11_mj.html#X8464BC397ACBF2F1">11.13-2 ComponentsOfPartialPermSemigroup</a>
 <a href="chap11_mj.html#X832937BB87EB4349">11.13-3 CyclesOfPartialPerm</a>
 <a href="chap11_mj.html#X7F7A5E5E8355E230">11.13-4 CyclesOfPartialPermSemigroup</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7AF313CF7CBE98D7">11.14 
 Attributes of Rees (0-)matrix semigroups
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7EA1B28785B9D38C">11.14-1 RZMSDigraph</a>
 <a href="chap11_mj.html#X79B062917AB34542">11.14-2 RZMSConnectedComponents</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X822D030682BC1275">11.15 
 Attributes of inverse semigroups
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7A75A6C486F1DC71">11.15-1 NaturalLeqInverseSemigroup</a>
 <a href="chap11_mj.html#X85CDF93C805AF82A">11.15-2 JoinIrreducibleDClasses</a>
 <a href="chap11_mj.html#X801CC67E80898608">11.15-3 MajorantClosure</a>
 <a href="chap11_mj.html#X84A3DB79816374DB">11.15-4 Minorants</a>
 <a href="chap11_mj.html#X80C0C6C37C4A2ABD">11.15-5 PrimitiveIdempotents</a>
 <a href="chap11_mj.html#X7B5D89A585F8B5EA">11.15-6 RightCosetsOfInverseSemigroup</a>
 <a href="chap11_mj.html#X83298E9E86A343FF">11.15-7 SameMinorantsSubgroup</a>
 <a href="chap11_mj.html#X786D4E397EA4445D">11.15-8 SmallerDegreePartialPermRepresentation</a>
 <a href="chap11_mj.html#X7BC49C3487384364">11.15-9 VagnerPrestonRepresentation</a>
 <a href="chap11_mj.html#X7C83DF9A7973AF6D">11.15-10 CharacterTableOfInverseSemigroup</a>
 <a href="chap11_mj.html#X8383E6747D02D975">11.15-11 EUnitaryInverseCover</a>
</div></div>
<div class="ContSect"> <a href="chap11_mj.html#X7AA4CE887EEA661A">11.16 
 Nambooripad partial order
 </a>

<div class="ContSSBlock">
 <a href="chap11_mj.html#X7A7EB0DA8398886E">11.16-1 NambooripadLeqRegularSemigroup</a>
 <a href="chap11_mj.html#X7928C7D37A9BCBD5">11.16-2 NambooripadPartialOrder</a>
</div></div>
</div>

<h3>11 
 Attributes and operations for semigroups
 </h3>

In this chapter we describe the methods that are available in Semigroups for determining the attributes of a semigroup, and the operations which can be applied to a semigroup.

<a id="X7AE0630287B8A757" name="X7AE0630287B8A757"></a>

<h4>11.1 
 Accessing the elements of a semigroup
 </h4>

<a id="X7AC3FAA5826516AD" name="X7AC3FAA5826516AD"></a>

<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>
Returns: A list, enumerator, or iterator.

When the argument <var class="Arg">S</var> is a semigroup satisfying <code class="func">CanUseFroidurePin</code> (<a href="chap6_mj.html#X7FEE8CFA87E7B872">6.1-4</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_mj.html#X7EA002E27B10CCE0">11.2-1</a>) and <code class="func">LeftCayleyDigraph</code> (<a href="chap11_mj.html#X7EA002E27B10CCE0">11.2-1</a>).

<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>.

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_mj.html#X7EA002E27B10CCE0">11.2-1</a>) and <code class="func">LeftCayleyDigraph</code> (<a href="chap11_mj.html#X7EA002E27B10CCE0">11.2-1</a>).

See also <code class="func">PositionCanonical</code> (<a href="chap11_mj.html#X7B4B10AE81602D4E">11.1-2</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([1, 3, 2]));;
gap> AsListCanonical(S);
[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]
gap> IteratorCanonical(S);
<iterator>
gap> EnumeratorCanonical(S);
[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]
gap> S := Monoid([Matrix(IsBooleanMat, [[1, 0, 0],
> [0, 1, 0],
> [0, 1, 0]])]);
<commutative monoid of 3x3 boolean matrices with 1 generator>
gap> it := IteratorCanonical(S);
<iterator>
gap> NextIterator(it);
Matrix(IsBooleanMat, [[1, 0, 0], [0, 1, 0], [0, 0, 1]])
gap> en := EnumeratorCanonical(S);
<enumerator of <commutative monoid of size 2, 3x3 boolean matrices
with 1 generator>>
gap> en[1];
Matrix(IsBooleanMat, [[1, 0, 0], [0, 1, 0], [0, 0, 1]])
gap> Position(en, en[1]);
1
gap> Length(en);
2</pre></div>

<a id="X7B4B10AE81602D4E" name="X7B4B10AE81602D4E"></a>

<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>
Returns: A positive integer or <code class="keyw">fail</code>.

When the argument <var class="Arg">S</var> is a semigroup satisfying <code class="func">CanUseFroidurePin</code> (<a href="chap6_mj.html#X7FEE8CFA87E7B872">6.1-4</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>.

See also <code class="func">AsListCanonical</code> (<a href="chap11_mj.html#X7AC3FAA5826516AD">11.1-1</a>) and <code class="func">EnumeratorCanonical</code> (<a href="chap11_mj.html#X7AC3FAA5826516AD">11.1-1</a>).

<div class="example"><pre>
gap> S := FullTropicalMaxPlusMonoid(2, 3);
<monoid of 2x2 tropical max-plus matrices with 13 generators>
gap> x := Matrix(IsTropicalMaxPlusMatrix, [[1, 3], [2, 1]], 3);
Matrix(IsTropicalMaxPlusMatrix, [[1, 3], [2, 1]], 3)
gap> PositionCanonical(S, x);
234
gap> EnumeratorCanonical(S)[234] = x;
true</pre></div>

<a id="X7BCD5342793C7A7E" name="X7BCD5342793C7A7E"></a>

<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>
Returns: A semigroup (the argument).

If <var class="Arg">S</var> is a semigroup with representation <code class="func">CanUseFroidurePin</code> (<a href="chap6_mj.html#X7FEE8CFA87E7B872">6.1-4</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.

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.

<div class="example"><pre>
gap> S := FullTransformationMonoid(7);
<full transformation monoid of degree 7>
gap> Enumerate(S, 1000);
<full transformation monoid of degree 7></pre></div>

<a id="X877FAAA67F834897" name="X877FAAA67F834897"></a>

<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>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

If <var class="Arg">S</var> is a semigroup with representation <code class="func">CanUseFroidurePin</code> (<a href="chap6_mj.html#X7FEE8CFA87E7B872">6.1-4</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.

<a id="X789D5E5A8558AA07" name="X789D5E5A8558AA07"></a>

<h4>11.2 
 Cayley graphs
 </h4>

<a id="X7EA002E27B10CCE0" name="X7EA002E27B10CCE0"></a>

<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>
Returns: A digraph.

When the argument <var class="Arg">S</var> is a semigroup satisfying <code class="func">CanUseFroidurePin</code> (<a href="chap6_mj.html#X7FEE8CFA87E7B872">6.1-4</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">Digraphs: Digraph</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.

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">Digraphs: IsCayleyDigraph</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">Digraphs: SemigroupOfCayleyDigraph</a>) and <code class="func">GeneratorsOfCayleyDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap5_mj.html#X8528455987D7D2BF">Digraphs: GeneratorsOfCayleyDigraph</a>).

<div class="example"><pre>
gap> S := FullTransformationMonoid(2);
<full transformation monoid of degree 2>
gap> RightCayleyDigraph(S);
<immutable multidigraph with 4 vertices, 12 edges>
gap> LeftCayleyDigraph(S);
<immutable multidigraph with 4 vertices, 12 edges></pre></div>

<a id="X824184C785BF12FF" name="X824184C785BF12FF"></a>

<h4>11.3 
 Random elements of a semigroup
 </h4>

<a id="X7BB7FDFE7AFFD672" name="X7BB7FDFE7AFFD672"></a>

<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>
Returns: A random element.

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 \(\mathscr{R}\)-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.

<a id="X80EB463F7E5D8920" name="X80EB463F7E5D8920"></a>

<h4>11.4 
 Properties of elements in a semigroup
 </h4>

<a id="X869AC4247E2BA4A2" name="X869AC4247E2BA4A2"></a>

<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>
Returns: A list of two positive integers.

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 index of <var class="Arg">x</var>, and the number<code class="code">r</code> is known as the period of <var class="Arg">x</var>.

<div class="example"><pre>
gap> x := Transformation([2, 6, 3, 5, 6, 1]);;
gap> IndexPeriodOfSemigroupElement(x);
[ 2, 3 ]
gap> m := IndexPeriodOfSemigroupElement(x)[1];;
gap> r := IndexPeriodOfSemigroupElement(x)[2];;
gap> x ^ (m + r) = x ^ m;
true
gap> x := PartialPerm([0, 2, 3, 0, 5]);
<identity partial perm on [ 2, 3, 5 ]>
gap> IsIdempotent(x);
true
gap> IndexPeriodOfSemigroupElement(x);
[ 1, 1 ]
</pre></div>

<a id="X84E1A41F84B70DBB" name="X84E1A41F84B70DBB"></a>

<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>
Returns: A positive integer.

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_mj.html#X869AC4247E2BA4A2">11.4-1</a>).

<div class="example"><pre>
gap> x := Transformation([4, 1, 4, 5, 1]);
Transformation( [ 4, 1, 4, 5, 1 ] )
gap> SmallestIdempotentPower(x);
3
gap> ForAll([1 .. 2], i -> not IsIdempotent(x ^ i));
true
gap> IsIdempotent(x ^ 3);
true
gap> x := Bipartition([[1, 2, -3, -4], [3, -5], [4, -1], [5, -2]]);
<block bijection: [ 1, 2, -3, -4 ], [ 3, -5 ], [ 4, -1 ], [ 5, -2 ]>
gap> SmallestIdempotentPower(x);
4
gap> ForAll([1 .. 3], i -> not IsIdempotent(x ^ i));
true
gap> x := PartialPerm([]);
<empty partial perm>
gap> SmallestIdempotentPower(x);
1
gap> IsIdempotent(x);
true</pre></div>

<a id="X7A20EC348515E37B" name="X7A20EC348515E37B"></a>

<h4>11.5 
 Operations for elements in a semigroup
 </h4>

<a id="X7BDAC0B581B71D0F" name="X7BDAC0B581B71D0F"></a>

<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>
Returns: One inverse of an element of a semigroup.

<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>.

<div class="example"><pre>
gap> S := FullTransformationMonoid(4);
<full transformation monoid of degree 4>
gap> s := Transformation([2, 3, 1, 1]);
Transformation( [ 2, 3, 1, 1 ] )
gap> OneInverseOfSemigroupElement(S, s);
Transformation( [ 3, 1, 2, 2 ] )
gap> e := IdentityTransformation;
IdentityTransformation
gap> OneInverseOfSemigroupElement(S, e);
IdentityTransformation
gap> F := FreeSemigroup(1);
<free semigroup on the generators [ s1 ]>
gap> OneInverseOfSemigroupElement(F, F.1);
Error, the semigroup is not finite</pre></div>

<a id="X81CEB3717E021643" name="X81CEB3717E021643"></a>

<h4>11.6 
 Expressing semigroup elements as words in generators
 </h4>

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 Semigroups.

<a id="X799D2F3C866B9AED" name="X799D2F3C866B9AED"></a>

<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>
Returns: A semigroup element.

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:

<div class="example"><pre>Product(List(w, i -> gens[i]));</pre></div>

see also <code class="func">Factorization</code> (<a href="chap11_mj.html#X8357294D7B164106">11.6-2</a>).

<dl>
<dt>for elements of a semigroup</dt>
<dd>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>.

</dd>
<dt>for elements of an inverse semigroup</dt>
<dd>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>.

</dd>
</dl>
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">Reference: IsMultiplicativeElementWithOne</a>).

<div class="example"><pre>
gap> gens := [
> Transformation([2, 4, 4, 6, 8, 8, 6, 6]),
> Transformation([2, 7, 4, 1, 4, 6, 5, 2]),
> Transformation([3, 6, 2, 4, 2, 2, 2, 8]),
> Transformation([4, 3, 6, 4, 2, 1, 2, 6]),
> Transformation([4, 5, 1, 3, 8, 5, 8, 2])];;
gap> S := Semigroup(gens);;
gap> x := Transformation([1, 4, 6, 1, 7, 2, 7, 6]);;
gap> word := Factorization(S, x);
[ 4, 2 ]
gap> EvaluateWord(gens, word);
Transformation( [ 1, 4, 6, 1, 7, 2, 7, 6 ] )
gap> S := SymmetricInverseMonoid(10);;
gap> x := PartialPerm([2, 6, 7, 0, 0, 9, 0, 1, 0, 5]);
[3,7][8,1,2,6,9][10,5]
gap> word := Factorization(S, x);
[ -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 ]
gap> EvaluateWord(GeneratorsOfSemigroup(S), word);
[3,7][8,1,2,6,9][10,5]</pre></div>

<a id="X8357294D7B164106" name="X8357294D7B164106"></a>

<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>
Returns: A word in the generators.

<dl>
<dt>for semigroups</dt>
<dd>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,

<div class="example"><pre>EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, x)) = x;</pre></div>

</dd>
<dt>for inverse semigroups</dt>
<dd>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,

<div class="example"><pre>EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, x)) = x;</pre></div>

</dd>
</dl>
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_mj.html#X83A4D71382C5B6C3">11.6-3</a>).

See also <code class="func">EvaluateWord</code> (<a href="chap11_mj.html#X799D2F3C866B9AED">11.6-1</a>) and <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B">Reference: GeneratorsOfSemigroup</a>).

<div class="example"><pre>
gap> gens := [Transformation([2, 2, 9, 7, 4, 9, 5, 5, 4, 8]),
> Transformation([4, 10, 5, 6, 4, 1, 2, 7, 1, 2])];;
gap> S := Semigroup(gens);;
gap> x := Transformation([1, 10, 2, 10, 1, 2, 7, 10, 2, 7]);;
gap> word := Factorization(S, x);
[ 2, 2, 1, 2 ]
gap> EvaluateWord(gens, word);
Transformation( [ 1, 10, 2, 10, 1, 2, 7, 10, 2, 7 ] )
gap> S := SymmetricInverseMonoid(8);
<symmetric inverse monoid of degree 8>
gap> x := PartialPerm([1, 2, 3, 4, 5, 8], [7, 1, 4, 3, 2, 6]);
[5,2,1,7][8,6](3,4)
gap> word := Factorization(S, x);
[ -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 ]
gap> EvaluateWord(GeneratorsOfSemigroup(S), word);
[5,2,1,7][8,6](3,4)
gap> S := DualSymmetricInverseMonoid(6);;
gap> x := S.1 * S.2 * S.3 * S.2 * S.1;
<block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ],
[ 5, -1 ]>
gap> word := Factorization(S, x);
[ -2, -2, -2, -2, -2, 4, 2 ]
gap> EvaluateWord(GeneratorsOfSemigroup(S), word);
<block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ],
[ 5, -1 ]></pre></div>

<a id="X83A4D71382C5B6C3" name="X83A4D71382C5B6C3"></a>

<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>
Returns: A minimal word in the generators.

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,

<div class="example"><pre>EvaluateWord(GeneratorsOfSemigroup(S), MinimalFactorization(S, x)) = x;</pre></div>

<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_mj.html#X8357294D7B164106">11.6-2</a>) for some semigroups.

Unlike <code class="func">Factorization</code> (<a href="chap11_mj.html#X8357294D7B164106">11.6-2</a>) this operation does not distinguish between semigroups and inverse semigroups. See also <code class="func">EvaluateWord</code> (<a href="chap11_mj.html#X799D2F3C866B9AED">11.6-1</a>) and <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B">Reference: GeneratorsOfSemigroup</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([2, 2, 9, 7, 4, 9, 5, 5, 4, 8]),
> Transformation([4, 10, 5, 6, 4, 1, 2, 7, 1, 2]));
<transformation semigroup of degree 10 with 2 generators>
gap> x := Transformation([8, 8, 2, 2, 9, 2, 8, 8, 9, 9]);
Transformation( [ 8, 8, 2, 2, 9, 2, 8, 8, 9, 9 ] )
gap> Factorization(S, x);
[ 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1 ]
gap> MinimalFactorization(S, x);
[ 1, 2, 1, 1, 1, 1, 2, 2, 1 ]</pre></div>

<a id="X86261F4682DC9842" name="X86261F4682DC9842"></a>

<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>
Returns: A non-trivial word in the generators, or <code class="keyw">fail</code>.

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_mj.html#X8357294D7B164106">11.6-2</a>) for semigroups and inverse semigroups. A word is non-trivial if it has length two or more.

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_mj.html#X7B4CD8937858A895">11.7-6</a>).

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_mj.html#X8357294D7B164106">11.6-2</a>).

See also <code class="func">EvaluateWord</code> (<a href="chap11_mj.html#X799D2F3C866B9AED">11.6-1</a>) and <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B">Reference: GeneratorsOfSemigroup</a>).

<div class="example"><pre>
gap> x := Transformation([5, 4, 2, 1, 3]);;
gap> y := Transformation([4, 4, 2, 4, 1]);;
gap> S := Semigroup([x, y]);
<transformation semigroup of degree 5 with 2 generators>
gap> NonTrivialFactorization(S, x * y);
[ 1, 2 ]
gap> Factorization(S, x);
[ 1 ]
gap> NonTrivialFactorization(S, x);
[ 1, 1, 1, 1, 1, 1 ]
gap> Factorization(S, y);
[ 2 ]
gap> NonTrivialFactorization(S, y);
[ 2, 1, 1, 1, 1, 1 ]
gap> z := PartialPerm([2]);;
gap> S := Semigroup(z);
<commutative partial perm semigroup of rank 1 with 1 generator>
gap> NonTrivialFactorization(S, z);
fail</pre></div>

<a id="X7E4AA1437A6C7B40" name="X7E4AA1437A6C7B40"></a>

<h4>11.7 
 Generating sets
 </h4>

<a id="X7BD5B55C802805B4" name="X7BD5B55C802805B4"></a>

<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>
Returns: A list of generators.

<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.

<dl>
<dt>for a group</dt>
<dd><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">Reference: GeneratorsOfGroup</a>).

</dd>
<dt>for an ideal of semigroup</dt>
<dd><code class="code">Generators(<var class="Arg">S</var>)</code> is a synonym for <code class="func">GeneratorsOfSemigroupIdeal</code> (<a href="chap9_mj.html#X87BB45DB844D41BC">9.2-1</a>).

</dd>
<dt>for a semigroup</dt>
<dd><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">Reference: GeneratorsOfSemigroup</a>).

</dd>
<dt>for a monoid</dt>
<dd><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">Reference: GeneratorsOfMonoid</a>).

</dd>
<dt>for an inverse semigroup</dt>
<dd><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">Reference: GeneratorsOfInverseSemigroup</a>).

</dd>
<dt>for an inverse monoid</dt>
<dd><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">Reference: GeneratorsOfInverseMonoid</a>).

</dd>
</dl>

<div class="example"><pre>
gap> M := Monoid([
> Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]),
> Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9])]);;
gap> GeneratorsOfSemigroup(M);
[ IdentityTransformation,
 Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
 Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> GeneratorsOfMonoid(M);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
 Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> Generators(M);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
 Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> S := Semigroup(Generators(M));;
gap> Generators(S);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
 Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> GeneratorsOfSemigroup(S);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ),
 Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]</pre></div>

<a id="X814DBABC878D5232" name="X814DBABC878D5232"></a>

<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>
Returns: A small generating set for a semigroup.

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

<div class="example"><pre>
 X(SmallXGeneratingSet(coll)) = X(coll);</pre></div>

where <code class="code">X</code> is any of <code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817">Reference: Semigroup</a>), <code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA">Reference: Monoid</a>), <code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326">Reference: InverseSemigroup</a>), or <code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B">Reference: InverseMonoid</a>).

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 GAP sessions.

<code class="code">SmallGeneratingSet</code> returns the smallest of the returned values of <code class="code">SmallXGeneratingSet</code> which is applicable to <var class="Arg">coll</var>; see <code class="func">Generators</code> (<a href="chap11_mj.html#X7BD5B55C802805B4">11.7-1</a>).

As neither irredundancy, nor minimal length are proven, these functions usually return an answer much more quickly than <code class="func">IrredundantGeneratingSubset</code> (<a href="chap11_mj.html#X7F88DA9487720D2B">11.7-3</a>). These functions can be used whenever a small generating set is desired which does not necessarily needs to be minimal.

<div class="example"><pre>
gap> S := Semigroup([
> Transformation([1, 2, 3, 2, 4]),
> Transformation([1, 5, 4, 3, 2]),
> Transformation([2, 1, 4, 2, 2]),
> Transformation([2, 4, 4, 2, 1]),
> Transformation([3, 1, 4, 3, 2]),
> Transformation([3, 2, 3, 4, 1]),
> Transformation([4, 4, 3, 3, 5]),
> Transformation([5, 1, 5, 5, 3]),
> Transformation([5, 4, 3, 5, 2]),
> Transformation([5, 5, 4, 5, 5])]);;
gap> SmallGeneratingSet(S);
[ Transformation( [ 1, 5, 4, 3, 2 ] ), Transformation( [ 3, 2, 3, 4, 1 ] ),
 Transformation( [ 5, 4, 3, 5, 2 ] ), Transformation( [ 1, 2, 3, 2, 4 ] ),
 Transformation( [ 4, 4, 3, 3, 5 ] ) ]
gap> S := RandomInverseMonoid(IsPartialPermMonoid, 10000, 10);;
gap> SmallGeneratingSet(S);
[ [ 1 .. 10 ] -> [ 3, 2, 4, 5, 6, 1, 7, 10, 9, 8 ],
 [ 1 .. 10 ] -> [ 5, 10, 8, 9, 3, 2, 4, 7, 6, 1 ],
 [ 1, 3, 4, 5, 6, 7, 8, 9, 10 ] -> [ 1, 6, 4, 8, 2, 10, 7, 3, 9 ] ]
gap> M := MathieuGroup(24);;
gap> mat := List([1 .. 1000], x -> Random(M));;
gap> Append(mat, [1 .. 1000] * 0);
gap> mat := List([1 .. 138], x -> List([1 .. 57], x -> Random(mat)));;
gap> R := ReesZeroMatrixSemigroup(M, mat);;
gap> U := Semigroup(List([1 .. 200], x -> Random(R)));
<subsemigroup of 57x138 Rees 0-matrix semigroup with 100 generators>
gap> Length(SmallGeneratingSet(U));
84
gap> S := RandomSemigroup(IsBipartitionSemigroup, 100, 4);
<bipartition semigroup of degree 4 with 96 generators>
gap> Length(SmallGeneratingSet(S));
13</pre></div>

<a id="X7F88DA9487720D2B" name="X7F88DA9487720D2B"></a>

<h5>11.7-3 IrredundantGeneratingSubset</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IrredundantGeneratingSubset</code>( <var class="Arg">coll</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of irredundant generators.

If <var class="Arg">coll</var> is a collection of elements of a semigroup, then this function returns a subset <code class="code">U</code> of <var class="Arg">coll</var> such that no element of <code class="code">U</code> is generated by the other elements of <code class="code">U</code>.

<div class="example"><pre>
gap> S := Semigroup([
> Transformation([5, 1, 4, 6, 2, 3]),
> Transformation([1, 2, 3, 4, 5, 6]),
> Transformation([4, 6, 3, 4, 2, 5]),
> Transformation([5, 4, 6, 3, 1, 3]),
> Transformation([2, 2, 6, 5, 4, 3]),
> Transformation([3, 5, 5, 1, 2, 4]),
> Transformation([6, 5, 1, 3, 3, 4]),
> Transformation([1, 3, 4, 3, 2, 1])]);;
gap> IrredundantGeneratingSubset(S);
[ Transformation( [ 1, 3, 4, 3, 2, 1 ] ),
 Transformation( [ 2, 2, 6, 5, 4, 3 ] ),
 Transformation( [ 3, 5, 5, 1, 2, 4 ] ),
 Transformation( [ 5, 1, 4, 6, 2, 3 ] ),
 Transformation( [ 5, 4, 6, 3, 1, 3 ] ),
 Transformation( [ 6, 5, 1, 3, 3, 4 ] ) ]
gap> S := RandomInverseMonoid(IsPartialPermMonoid, 1000, 10);
<inverse partial perm monoid of degree 10 with 1000 generators>
gap> SmallGeneratingSet(S);
[ [ 1 .. 10 ] -> [ 6, 5, 1, 9, 8, 3, 10, 4, 7, 2 ],
 [ 1 .. 10 ] -> [ 1, 4, 6, 2, 8, 5, 7, 10, 3, 9 ],
 [ 1, 2, 3, 4, 6, 7, 8, 9 ] -> [ 7, 5, 10, 1, 8, 4, 9, 6 ]
 [ 1 .. 9 ] -> [ 4, 3, 5, 7, 10, 9, 1, 6, 8 ] ]
gap> IrredundantGeneratingSubset(last);
[ [ 1 .. 9 ] -> [ 4, 3, 5, 7, 10, 9, 1, 6, 8 ],
 [ 1 .. 10 ] -> [ 1, 4, 6, 2, 8, 5, 7, 10, 3, 9 ],
 [ 1 .. 10 ] -> [ 6, 5, 1, 9, 8, 3, 10, 4, 7, 2 ] ]
gap> S := RandomSemigroup(IsBipartitionSemigroup, 1000, 4);
<bipartition semigroup of degree 4 with 749 generators>
gap> SmallGeneratingSet(S);
[ <bipartition: [ 1, -3 ], [ 2, -2 ], [ 3, -1 ], [ 4, -4 ]>,
 <bipartition: [ 1, 3, -2 ], [ 2, -1, -3 ], [ 4, -4 ]>,
 <bipartition: [ 1, -4 ], [ 2, 4, -1, -3 ], [ 3, -2 ]>,
 <bipartition: [ 1, -1, -3 ], [ 2, -4 ], [ 3, 4, -2 ]>,
 <bipartition: [ 1, -2, -4 ], [ 2 ], [ 3, -3 ], [ 4, -1 ]>,
 <bipartition: [ 1, -2 ], [ 2, -1, -3 ], [ 3, 4, -4 ]>,
 <bipartition: [ 1, 3, -1 ], [ 2, -3 ], [ 4, -2, -4 ]>,
 <bipartition: [ 1, -1 ], [ 2, 4, -4 ], [ 3, -2, -3 ]>,
 <bipartition: [ 1, 3, -1 ], [ 2, -2 ], [ 4, -3, -4 ]>,
 <bipartition: [ 1, 2, -2 ], [ 3, -1, -4 ], [ 4, -3 ]>,
 <bipartition: [ 1, -2, -3 ], [ 2, -4 ], [ 3 ], [ 4, -1 ]>,
 <bipartition: [ 1, -1 ], [ 2, 4, -3 ], [ 3, -2 ], [ -4 ]>,
 <bipartition: [ 1, -3 ], [ 2, -1 ], [ 3, 4, -4 ], [ -2 ]>,
 <bipartition: [ 1, 2, -4 ], [ 3, -1 ], [ 4, -2 ], [ -3 ]>,
 <bipartition: [ 1, -3 ], [ 2, -4 ], [ 3, -1, -2 ], [ 4 ]> ]
gap> IrredundantGeneratingSubset(last);
[ <bipartition: [ 1, 2, -4 ], [ 3, -1 ], [ 4, -2 ], [ -3 ]>,
 <bipartition: [ 1, 3, -1 ], [ 2, -2 ], [ 4, -3, -4 ]>,
 <bipartition: [ 1, 3, -2 ], [ 2, -1, -3 ], [ 4, -4 ]>,
 <bipartition: [ 1, -1 ], [ 2, 4, -3 ], [ 3, -2 ], [ -4 ]>,
 <bipartition: [ 1, -3 ], [ 2, -1 ], [ 3, 4, -4 ], [ -2 ]>,
 <bipartition: [ 1, -3 ], [ 2, -2 ], [ 3, -1 ], [ 4, -4 ]>,
 <bipartition: [ 1, -3 ], [ 2, -4 ], [ 3, -1, -2 ], [ 4 ]>,
 <bipartition: [ 1, -2, -3 ], [ 2, -4 ], [ 3 ], [ 4, -1 ]>,
 <bipartition: [ 1, -2, -4 ], [ 2 ], [ 3, -3 ], [ 4, -1 ]> ]</pre></div>

<a id="X8409DBED7996D495" name="X8409DBED7996D495"></a>

<h5>11.7-4 MinimalSemigroupGeneratingSet</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalSemigroupGeneratingSet</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">‣ MinimalMonoidGeneratingSet</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">‣ MinimalInverseSemigroupGeneratingSet</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">‣ MinimalInverseMonoidGeneratingSet</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A minimal generating set for a semigroup.

The attribute <code class="code">MinimalXGeneratingSet</code> returns a minimal generating set for the semigroup <var class="Arg">S</var>, with respect to length. The returned value of <code class="code">MinimalXGeneratingSet</code>, where applicable, is a minimal-length list of elements of <var class="Arg">S</var> with the property that

<div class="example"><pre>
 X(MinimalXGeneratingSet(S)) = S;
 </pre></div>

where <code class="code">X</code> is one of <code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817">Reference: Semigroup</a>), <code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA">Reference: Monoid</a>), <code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326">Reference: InverseSemigroup</a>), or <code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B">Reference: InverseMonoid</a>).

For many types of semigroup, it is not currently possible to find a <code class="code">MinimalXGeneratingSet</code> with the Semigroups package.

See also <code class="func">SmallGeneratingSet</code> (<a href="chap11_mj.html#X814DBABC878D5232">11.7-2</a>) and <code class="func">IrredundantGeneratingSubset</code> (<a href="chap11_mj.html#X7F88DA9487720D2B">11.7-3</a>).

<div class="example"><pre>
gap> S := MonogenicSemigroup(3, 6);;
gap> MinimalSemigroupGeneratingSet(S);
[ Transformation( [ 2, 3, 4, 5, 6, 1, 6, 7, 8 ] ) ]
gap> S := FullTransformationMonoid(4);;
gap> MinimalSemigroupGeneratingSet(S);
[ Transformation( [ 1, 4, 2, 3 ] ), Transformation( [ 4, 3, 1, 2 ] ),
 Transformation( [ 1, 2, 3, 1 ] ) ]
gap> S := Monoid([
> PartialPerm([2, 3, 4, 5, 1, 0, 6, 7]),
> PartialPerm([3, 4, 5, 1, 2, 0, 0, 6])]);
<partial perm monoid of rank 8 with 2 generators>
gap> IsMonogenicMonoid(S);
true
gap> MinimalMonoidGeneratingSet(S);
[ [8,7,6](1,2,3,4,5) ]</pre></div>

<a id="X82B02F0887AD1B78" name="X82B02F0887AD1B78"></a>

<h5>11.7-5 GeneratorsSmallest</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsSmallest</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A set of elements.

For a semigroup <var class="Arg">S</var>, <code class="code">GeneratorsSmallest</code> returns the lexicographically least set of elements <code class="code">X</code> such that <code class="code">X</code> generates <var class="Arg">S</var> as a semigroup, and such that <code class="code">X</code> is lexicographically ordered and has the property that each <code class="code">X[i]</code> is not generated by <code class="code">X[1], X[2], ..., X[i-1]</code>.

It can be difficult to find the set of generators <code class="code">X</code>, and it might contain a substantial proportion of the elements of <var class="Arg">S</var>.

Two semigroups have the same set of elements if and only if their smallest generating sets are equal. However, due to the complexity of determining the <code class="code">GeneratorsSmallest</code>, this is not the method used by the Semigroups package when comparing semigroups.

<div class="example"><pre>
gap> S := Monoid([
> Transformation([1, 3, 4, 1]),
> Transformation([2, 4, 1, 2]),
> Transformation([3, 1, 1, 3]),
> Transformation([3, 3, 4, 1])]);
<transformation monoid of degree 4 with 4 generators>
gap> GeneratorsSmallest(S);
[ Transformation( [ 1, 1, 1, 1 ] ), Transformation( [ 1, 1, 1, 2 ] ),
 Transformation( [ 1, 1, 1, 3 ] ), Transformation( [ 1, 1, 1 ] ),
 Transformation( [ 1, 1, 2, 1 ] ), Transformation( [ 1, 1, 2, 2 ] ),
 Transformation( [ 1, 1, 3, 1 ] ), Transformation( [ 1, 1, 3, 3 ] ),
 Transformation( [ 1, 1 ] ), Transformation( [ 1, 1, 4, 1 ] ),
 Transformation( [ 1, 2, 1, 1 ] ), Transformation( [ 1, 2, 2, 1 ] ),
 IdentityTransformation, Transformation( [ 1, 3, 1, 1 ] ),
 Transformation( [ 1, 3, 4, 1 ] ), Transformation( [ 2, 1, 1, 2 ] ),
 Transformation( [ 2, 2, 2 ] ), Transformation( [ 2, 4, 1, 2 ] ),
 Transformation( [ 3, 3, 3 ] ), Transformation( [ 3, 3, 4, 1 ] ) ]
gap> T := Semigroup(Bipartition([[1, 2, 3], [4, -1], [-2], [-3], [-4]]),
> Bipartition([[1, -3, -4], [2, 3, 4, -2], [-1]]),
> Bipartition([[1, 2, 3, 4, -2], [-1, -4], [-3]]),
> Bipartition([[1, 2, 3, 4], [-1], [-2], [-3, -4]]),
> Bipartition([[1, 2, -1, -2], [3, 4, -3], [-4]]));
<bipartition semigroup of degree 4 with 5 generators>
gap> GeneratorsSmallest(T);
[ <bipartition: [ 1, 2, 3, 4, -1, -2, -3 ], [ -4 ]>,
 <bipartition: [ 1, 2, 3, 4, -1, -2 ], [ -3 ], [ -4 ]>,
 <bipartition: [ 1, 2, 3, 4, -1 ], [ -2 ], [ -3 ], [ -4 ]>,
 <bipartition: [ 1, 2, 3, 4, -2, -3, -4 ], [ -1 ]>,
 <bipartition: [ 1, 2, 3, 4, -2 ], [ -1, -4 ], [ -3 ]>,
 <bipartition: [ 1, 2, 3, 4, -2 ], [ -1 ], [ -3, -4 ]>,
 <bipartition: [ 1, 2, 3, 4, -3 ], [ -1, -2 ], [ -4 ]>,
 <bipartition: [ 1, 2, 3, 4 ], [ -1, -2, -3 ], [ -4 ]>,
 <bipartition: [ 1, 2, 3, 4, -3, -4 ], [ -1 ], [ -2 ]>,
 <bipartition: [ 1, 2, 3 ], [ 4, -1, -2, -3 ], [ -4 ]>,
 <bipartition: [ 1, 2, -1, -2 ], [ 3, 4, -3 ], [ -4 ]>,
 <bipartition: [ 1, -3 ], [ 2, 3, 4, -1, -2 ], [ -4 ]>,
 <bipartition: [ 1, -3, -4 ], [ 2, 3, 4, -2 ], [ -1 ]> ]</pre></div>

<a id="X7B4CD8937858A895" name="X7B4CD8937858A895"></a>

<h5>11.7-6 IndecomposableElements</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IndecomposableElements</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of elements.

If <var class="Arg">S</var> is a semigroup, then this attribute returns the set of elements of <var class="Arg">S</var> that are not decomposable. A element of <var class="Arg">S</var> is decomposable if it can be written as the product of two elements in <var class="Arg">S</var>. An element of <var class="Arg">S</var> is indecomposable if it is not decomposable.

See also <code class="func">IsSurjectiveSemigroup</code> (<a href="chap12_mj.html#X7C9560A18348AEE3">12.1-6</a>).

Note that any generating set for <var class="Arg">S</var> contains each indecomposable element of <var class="Arg">S</var>. Thus <code class="code">IndecomposableElements(<var class="Arg">S</var>)</code> is a subset of <code class="code">GeneratorsOfSemigroup(<var class="Arg">S</var>)</code>.

<div class="example"><pre>
gap> S := Semigroup([
> Transformation([1, 1, 2, 3]),
> Transformation([1, 1, 1, 2])]);
<transformation semigroup of degree 4 with 2 generators>
gap> x := IndecomposableElements(S);
[ Transformation( [ 1, 1, 2, 3 ] ) ]
gap> IsSubset(GeneratorsOfSemigroup(S), x);
true
gap> T := FullTransformationMonoid(10);
<full transformation monoid of degree 10>
gap> IndecomposableElements(T);
[ ]
gap> B := ZeroSemigroup(IsBipartitionSemigroup, 3);
<commutative non-regular bipartition semigroup of size 3, degree 4
with 2 generators>
gap> IndecomposableElements(B);
[ <bipartition: [ 1, 2, 3, -1 ], [ 4, -2 ], [ -3 ], [ -4 ]>,
 <bipartition: [ 1, 2, 4, -1 ], [ 3, -2 ], [ -3 ], [ -4 ]> ]</pre></div>

<a id="X830E18747A0B5BED" name="X830E18747A0B5BED"></a>

<h4>11.8 
 Minimal ideals and multiplicative zeros
 </h4>

In this section we describe the attributes of a semigroup that can be found using the Semigroups package.

<a id="X7BC68589879C3BE9" name="X7BC68589879C3BE9"></a>

<h5>11.8-1 MinimalIdeal</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalIdeal</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The minimal ideal of a semigroup.

The minimal ideal of a semigroup is the least ideal with respect to containment.

It is significantly easier to find the minimal \(\mathscr{D}\)-class of a semigroup, than to find its \(\mathscr{D}\)-classes.

See also <code class="func">RepresentativeOfMinimalIdeal</code> (<a href="chap11_mj.html#X7CA6744182D07C5B">11.8-2</a>), <code class="func">PartialOrderOfDClasses</code> (<a href="chap10_mj.html#X8140814084748101">10.1-10</a>), <code class="func">IsGreensLessThanOrEqual</code> (<a href="../../../doc/ref/chap51_mj.html#X7AA204C8850F9070">Reference: IsGreensLessThanOrEqual</a>), and <code class="func">MinimalDClass</code> (<a href="chap10_mj.html#X81E5A04F7DA3A1E1">10.1-6</a>).

<div class="example"><pre>
gap> S := Semigroup(
> Transformation([3, 4, 1, 3, 6, 3, 4, 6, 10, 1]),
> Transformation([8, 2, 3, 8, 4, 1, 3, 4, 9, 7]));;
gap> MinimalIdeal(S);
<simple transformation semigroup ideal of degree 10 with 1 generator>
gap> Elements(MinimalIdeal(S));
[ Transformation( [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ),
 Transformation( [ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 ] ),
 Transformation( [ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ] ),
 Transformation( [ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 ] ),
 Transformation( [ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ] ) ]
gap> x := Transformation([8, 8, 8, 8, 8, 8, 8, 8, 8, 8]);;
gap> D := DClass(S, x);;
gap> ForAll(GreensDClasses(S), x -> IsGreensLessThanOrEqual(D, x));
true
gap> MinimalIdeal(POI(10));
<partial perm group of rank 0>
gap> MinimalIdeal(BrauerMonoid(6));
<simple bipartition *-semigroup ideal of degree 6 with 1 generator></pre></div>

<a id="X7CA6744182D07C5B" name="X7CA6744182D07C5B"></a>

<h5>11.8-2 RepresentativeOfMinimalIdeal</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RepresentativeOfMinimalIdeal</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">‣ RepresentativeOfMinimalDClass</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An element of the minimal ideal of a semigroup.

The minimal ideal of a semigroup is the least ideal with respect to containment.

This method returns a representative element of the minimal ideal of <var class="Arg">S</var> without having to create the minimal ideal itself. In general, beyond being a member of the minimal ideal, the returned element is not guaranteed to have any special properties. However, the element will coincide with the zero element of <var class="Arg">S</var> if one exists.

This method works particularly well if <var class="Arg">S</var> is a semigroup of transformations or partial permutations.

See also <code class="func">MinimalIdeal</code> (<a href="chap11_mj.html#X7BC68589879C3BE9">11.8-1</a>) and <code class="func">MinimalDClass</code> (<a href="chap10_mj.html#X81E5A04F7DA3A1E1">10.1-6</a>).

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(10);;
gap> RepresentativeOfMinimalIdeal(S);
<empty partial perm>
gap> B := Semigroup([
> Bipartition([[1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]),
> Bipartition([[1, -1], [2], [3], [4, -3], [5, 6, -5, -6],
> [-2, -4]])]);;
gap> RepresentativeOfMinimalIdeal(B);
<bipartition: [ 1, 2 ], [ 3, 6 ], [ 4, 5 ], [ -1, -5, -6 ],
[ -2, -4 ], [ -3 ]>
gap> S := Semigroup(Transformation([5, 1, 6, 2, 2, 4]),
> Transformation([3, 5, 5, 1, 6, 2]));;
gap> RepresentativeOfMinimalDClass(S);
Transformation( [ 5, 6, 6, 3, 3, 5 ] )
gap> MinimalDClass(S);
<Green's D-class: Transformation( [ 5, 6, 6, 3, 3, 5 ] )></pre></div>

<a id="X7B39F93C8136D642" name="X7B39F93C8136D642"></a>

<h5>11.8-3 MultiplicativeZero</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MultiplicativeZero</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The zero element of a semigroup.

<code class="code">MultiplicativeZero</code> returns the zero element of the semigroup <var class="Arg">S</var> if it exists and <code class="keyw">fail</code> if it does not. See also <code class="func">MultiplicativeZero</code> (<a href="../../../doc/ref/chap35_mj.html#X7B39F93C8136D642">Reference: MultiplicativeZero</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([1, 4, 2, 6, 6, 5, 2]),
> Transformation([1, 6, 3, 6, 2, 1, 6]));;
gap> MultiplicativeZero(S);
Transformation( [ 1, 1, 1, 1, 1, 1, 1 ] )
gap> S := Semigroup(Transformation([2, 8, 3, 7, 1, 5, 2, 6]),
> Transformation([3, 5, 7, 2, 5, 6, 3, 8]),
> Transformation([6, 7, 4, 1, 4, 1, 6, 2]),
> Transformation([8, 8, 5, 1, 7, 5, 2, 8]));;
gap> MultiplicativeZero(S);
fail
gap> S := InverseSemigroup(
> PartialPerm([1, 3, 4], [5, 3, 1]),
> PartialPerm([1, 2, 3, 4], [4, 3, 1, 2]),
> PartialPerm([1, 3, 4, 5], [2, 4, 5, 3]));;
gap> MultiplicativeZero(S);
<empty partial perm>
gap> S := PartitionMonoid(6);
<regular bipartition *-monoid of size 4213597, degree 6 with 4
generators>
gap> MultiplicativeZero(S);
fail
gap> S := DualSymmetricInverseMonoid(6);
<inverse block bijection monoid of degree 6 with 3 generators>
gap> MultiplicativeZero(S);
<block bijection: [ 1, 2, 3, 4, 5, 6, -1, -2, -3, -4, -5, -6 ]>
</pre></div>

<a id="X7CD6F5CB83B030B6" name="X7CD6F5CB83B030B6"></a>

<h5>11.8-4 UnderlyingSemigroupOfSemigroupWithAdjoinedZero</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UnderlyingSemigroupOfSemigroupWithAdjoinedZero</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A semigroup, or <code class="keyw">fail</code>.

If <var class="Arg">S</var> is a semigroup for which the property <code class="func">IsSemigroupWithAdjoinedZero</code> (<a href="chap12_mj.html#X7826DDF8808EC4D9">12.1-20</a>) is true, (i.e. <var class="Arg">S</var> has a <code class="func">MultiplicativeZero</code> (<a href="chap11_mj.html#X7B39F93C8136D642">11.8-3</a>) and the set \(\textit{S} \setminus \{ 0 \}\) is a subsemigroup of <var class="Arg">S</var>), then this method returns the semigroup \(\textit{S} \setminus \{ 0 \}\).

Otherwise, if <var class="Arg">S</var> is a semigroup for which the property <code class="func">IsSemigroupWithAdjoinedZero</code> (<a href="chap12_mj.html#X7826DDF8808EC4D9">12.1-20</a>) is <code class="keyw">false</code>, then this method returns <code class="keyw">fail</code>.

<div class="example"><pre>
gap> S := Semigroup([
> Transformation([2, 3, 4, 5, 1, 6]),
> Transformation([2, 1, 3, 4, 5, 6]),
> Transformation([6, 6, 6, 6, 6, 6])]);
<transformation semigroup of degree 6 with 3 generators>
gap> MultiplicativeZero(S);
Transformation( [ 6, 6, 6, 6, 6, 6 ] )
gap> G := UnderlyingSemigroupOfSemigroupWithAdjoinedZero(S);
<transformation semigroup of degree 5 with 2 generators>
gap> IsGroupAsSemigroup(G);
true
gap> IsZeroGroup(S);
true
gap> S := SymmetricInverseMonoid(6);;
gap> MultiplicativeZero(S);
<empty partial perm>
gap> G := UnderlyingSemigroupOfSemigroupWithAdjoinedZero(S);
fail
</pre></div>

<a id="X7CAB17667ED5A6E8" name="X7CAB17667ED5A6E8"></a>

<h4>11.9 
 Group of units and identity elements
 </h4>

<a id="X811AEDD88280C277" name="X811AEDD88280C277"></a>

<h5>11.9-1 GroupOfUnits</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GroupOfUnits</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The group of units of a semigroup or <code class="keyw">fail</code>.

<code class="code">GroupOfUnits</code> returns the group of units of the semigroup <var class="Arg">S</var> as a subsemigroup of <var class="Arg">S</var> if it exists and returns <code class="keyw">fail</code> if it does not. Use <code class="func">IsomorphismPermGroup</code> (<a href="chap6_mj.html#X80B7B1C783AA1567">6.5-5</a>) if you require a permutation representation of the group of units.

If a semigroup <var class="Arg">S</var> has an identity <code class="code">e</code>, then the group of units of <var class="Arg">S</var> is the set of those <code class="code">s</code> in <var class="Arg">S</var> such that there exists <code class="code">t</code> in <var class="Arg">S</var> where <code class="code">s*t=t*s=e</code>. Equivalently, the group of units is the \(\mathscr{H}\)-class of the identity of <var class="Arg">S</var>.

See also <code class="func">GreensHClassOfElement</code> (<a href="../../../doc/ref/chap51_mj.html#X87C75A9D86122D93">Reference: GreensHClassOfElement</a>), <code class="func">IsMonoidAsSemigroup</code> (<a href="chap12_mj.html#X7E4DEECD7CD9886D">12.1-13</a>), and <code class="func">MultiplicativeNeutralElement</code> (<a href="../../../doc/ref/chap35_mj.html#X7EE2EA5F7EB7FEC2">Reference: MultiplicativeNeutralElement</a>).

<div class="example"><pre>
gap> S := Semigroup(
> Transformation([1, 2, 5, 4, 3, 8, 7, 6]),
> Transformation([1, 6, 3, 4, 7, 2, 5, 8]),
> Transformation([2, 1, 6, 7, 8, 3, 4, 5]),
> Transformation([3, 2, 3, 6, 1, 6, 1, 2]),
> Transformation([5, 2, 3, 6, 3, 4, 7, 4]));;
gap> Size(S);
5304
gap> StructureDescription(GroupOfUnits(S));
"C2 x S4"
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
> [2, 4, 5, 3, 6, 7, 10, 9, 8, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 10],
> [8, 2, 3, 1, 4, 5, 10, 6, 9]));;
gap> StructureDescription(GroupOfUnits(S));
"C8"
gap> S := InverseSemigroup(
> PartialPerm([1, 3, 4], [4, 3, 5]),
> PartialPerm([1, 2, 3, 5], [3, 1, 5, 2]));;
gap> GroupOfUnits(S);
fail
gap> S := Semigroup(
> Bipartition([[1, 2, 3, -1, -3], [-2]]),
> Bipartition([[1, -1], [2, 3, -2, -3]]),
> Bipartition([[1, -2], [2, -3], [3, -1]]),
> Bipartition([[1], [2, 3, -2], [-1, -3]]));;
gap> StructureDescription(GroupOfUnits(S));
"C3"</pre></div>

<a id="X7C651C9C78398FFF" name="X7C651C9C78398FFF"></a>

<h4>11.10 
 Idempotents
 </h4>

<a id="X7C651C9C78398FFF" name="X7C651C9C78398FFF"></a>

<h5>11.10-1 Idempotents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Idempotents</code>( <var class="Arg">obj</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of idempotents.

The argument <var class="Arg">obj</var> should be a semigroup, \(\mathscr{D}\)-class, \(\mathscr{H}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{R}\)-class.

If the optional second argument <var class="Arg">n</var> is present and <var class="Arg">obj</var> is a semigroup, then a list of the idempotents in <var class="Arg">obj</var> of rank <var class="Arg">n</var> is returned. If you are only interested in the idempotents of a given rank, then the second version of the function will probably be faster. However, if the optional second argument is present, then nothing is stored in <var class="Arg">obj</var> and so every time the function is called the computation must be repeated.

This functions produce essentially the same output as the GAP library function with the same name; see <code class="func">Idempotents</code> (<a href="../../../doc/ref/chap35_mj.html#X7C651C9C78398FFF">Reference: Idempotents</a>). The main difference is that this function can be applied to a wider class of objects as described above.

See also <code class="func">IsRegularDClass</code> (<a href="../../../doc/ref/chap51_mj.html#X7F5860927CAD920F">Reference: IsRegularDClass</a>), <code class="func">IsRegularGreensClass</code> (<a href="chap10_mj.html#X859DD1C079C80DCC">10.3-2</a>) <code class="func">IsGroupHClass</code> (<a href="../../../doc/ref/chap51_mj.html#X79D740EF7F0E53BD">Reference: IsGroupHClass</a>), <code class="func">NrIdempotents</code> (<a href="chap11_mj.html#X7CFC4DB387452320">11.10-2</a>), and <code class="func">GroupHClass</code> (<a href="chap10_mj.html#X8723756387DD4C0F">10.4-1</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([2, 3, 4, 1]),
> Transformation([3, 3, 1, 1]));;
gap> Idempotents(S, 1);
[ ]
gap> AsSet(Idempotents(S, 2));
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ),
 Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> AsSet(Idempotents(S));
[ Transformation( [ 1, 1, 3, 3 ] ), IdentityTransformation,
 Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 2, 2, 4, 4 ] ),
 Transformation( [ 4, 2, 2, 4 ] ) ]
gap> x := Transformation([2, 2, 4, 4]);;
gap> R := GreensRClassOfElement(S, x);;
gap> Idempotents(R);
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 2, 2, 4, 4 ] ) ]
gap> x := Transformation([4, 2, 2, 4]);;
gap> L := GreensLClassOfElement(S, x);;
gap> AsSet(Idempotents(L));
[ Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> D := DClassOfLClass(L);;
gap> AsSet(Idempotents(D));
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ),
 Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> L := GreensLClassOfElement(S, Transformation([3, 1, 1, 3]));;
gap> AsSet(Idempotents(L));
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ) ]
gap> H := GroupHClass(D);
<Green's H-class: Transformation( [ 1, 1, 3, 3 ] )>
gap> Idempotents(H);
[ Transformation( [ 1, 1, 3, 3 ] ) ]
gap> S := InverseSemigroup(
> PartialPerm([10, 6, 3, 4, 9, 0, 1]),
> PartialPerm([6, 10, 7, 4, 8, 2, 9, 1]));;
gap> Idempotents(S, 1);
[ <identity partial perm on [ 4 ]> ]
gap> Idempotents(S, 0);
[ ]</pre></div>

<a id="X7CFC4DB387452320" name="X7CFC4DB387452320"></a>

<h5>11.10-2 NrIdempotents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrIdempotents</code>( <var class="Arg">obj</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A positive integer.

This function returns the number of idempotents in <var class="Arg">obj</var> where <var class="Arg">obj</var> can be a semigroup, \(\mathscr{D}\)-, \(\mathscr{L}\)-, \(\mathscr{H}\)-, or \(\mathscr{R}\)-class. If the actual idempotents are not required, then it is more efficient to use <code class="code">NrIdempotents(obj)</code> than <code class="code">Length(Idempotents(obj))</code> since the idempotents themselves are not created when <code class="code">NrIdempotents</code> is called.

See also <code class="func">Idempotents</code> (<a href="../../../doc/ref/chap35_mj.html#X7C651C9C78398FFF">Reference: Idempotents</a>) and <code class="func">Idempotents</code> (<a href="chap11_mj.html#X7C651C9C78398FFF">11.10-1</a>), <code class="func">IsRegularDClass</code> (<a href="../../../doc/ref/chap51_mj.html#X7F5860927CAD920F">Reference: IsRegularDClass</a>), <code class="func">IsRegularGreensClass</code> (<a href="chap10_mj.html#X859DD1C079C80DCC">10.3-2</a>) <code class="func">IsGroupHClass</code> (<a href="../../../doc/ref/chap51_mj.html#X79D740EF7F0E53BD">Reference: IsGroupHClass</a>), and <code class="func">GroupHClass</code> (<a href="chap10_mj.html#X8723756387DD4C0F">10.4-1</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([2, 3, 4, 1]),
> Transformation([3, 3, 1, 1]));;
gap> NrIdempotents(S);
5
gap> f := Transformation([2, 2, 4, 4]);;
gap> R := GreensRClassOfElement(S, f);;
gap> NrIdempotents(R);
2
gap> f := Transformation([4, 2, 2, 4]);;
gap> L := GreensLClassOfElement(S, f);;
gap> NrIdempotents(L);
2
gap> D := DClassOfLClass(L);;
gap> NrIdempotents(D);
4
gap> L := GreensLClassOfElement(S, Transformation([3, 1, 1, 3]));;
gap> NrIdempotents(L);
2
gap> H := GroupHClass(D);;
gap> NrIdempotents(H);
1
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 5, 7, 9, 10],
> [6, 7, 2, 9, 1, 5, 3]),
> PartialPerm([1, 2, 3, 5, 6, 7, 9, 10],
> [8, 1, 9, 4, 10, 5, 6, 7]));;
gap> NrIdempotents(S);
236
gap> f := PartialPerm([2, 3, 7, 9, 10],
> [7, 2, 1, 5, 3]);;
gap> D := DClassNC(S, f);;
gap> NrIdempotents(D);
13</pre></div>

<a id="X83970D028143B79B" name="X83970D028143B79B"></a>

<h5>11.10-3 IdempotentGeneratedSubsemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IdempotentGeneratedSubsemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A semigroup.

<code class="code">IdempotentGeneratedSubsemigroup</code> returns the subsemigroup of the semigroup <var class="Arg">S</var> generated by the idempotents of <var class="Arg">S</var>.

See also <code class="func">Idempotents</code> (<a href="chap11_mj.html#X7C651C9C78398FFF">11.10-1</a>) and <code class="func">SmallGeneratingSet</code> (<a href="chap11_mj.html#X814DBABC878D5232">11.7-2</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([1, 1]),
> Transformation([2, 1]),
> Transformation([1, 2, 2]),
> Transformation([1, 2, 3, 4, 5, 1]),
> Transformation([1, 2, 3, 4, 5, 5]),
> Transformation([1, 2, 3, 4, 6, 5]),
> Transformation([1, 2, 3, 5, 4]),
> Transformation([1, 2, 3, 7, 4, 5, 7]),
> Transformation([1, 2, 4, 8, 8, 3, 8, 7]),
> Transformation([1, 2, 8, 4, 5, 6, 7, 8]),
> Transformation([7, 7, 7, 4, 5, 6, 1]));;
gap> IdempotentGeneratedSubsemigroup(S) =
> Monoid(Transformation([1, 1]),
> Transformation([1, 2, 1]),
> Transformation([1, 2, 2]),
> Transformation([1, 2, 3, 1]),
> Transformation([1, 2, 3, 2]),
> Transformation([1, 2, 3, 4, 1]),
> Transformation([1, 2, 3, 4, 2]),
> Transformation([1, 2, 3, 4, 4]),
> Transformation([1, 2, 3, 4, 5, 1]),
> Transformation([1, 2, 3, 4, 5, 2]),
> Transformation([1, 2, 3, 4, 5, 5]),
> Transformation([1, 2, 3, 4, 5, 7, 7]),
> Transformation([1, 2, 3, 4, 7, 6, 7]),
> Transformation([1, 2, 3, 6, 5, 6]),
> Transformation([1, 2, 3, 7, 5, 6, 7]),
> Transformation([1, 2, 8, 4, 5, 6, 7, 8]),
> Transformation([2, 2]));
true
gap> S := SymmetricInverseSemigroup(5);
<symmetric inverse monoid of degree 5>
gap> IdempotentGeneratedSubsemigroup(S);
<inverse partial perm monoid of rank 5 with 5 generators>
gap> S := DualSymmetricInverseSemigroup(5);
<inverse block bijection monoid of degree 5 with 3 generators>
gap> IdempotentGeneratedSubsemigroup(S);
<inverse block bijection monoid of degree 5 with 10 generators>
gap> IsSemilattice(last);
true</pre></div>

<a id="X7D490B867CEFCBEF" name="X7D490B867CEFCBEF"></a>

<h4>11.11 
 Maximal subsemigroups
 </h4>

The Semigroups package provides methods to calculate the maximal subsemigroups of a finite semigroup, subject to various conditions. A maximal subsemigroup of a semigroup is a proper subsemigroup that is contained in no other proper subsemigroup of the semigroup.

When computing the maximal subsemigroups of a regular Rees (0-)matrix semigroup over a group, additional functionality is available. As described in <a href="chapBib_mj.html#biBGraham1968aa">[GGR68]</a>, a maximal subsemigroup of a finite regular Rees (0-)matrix semigroup over a group is one of 6 possible types. Using the Semigroups package, it is possible to search for only those maximal subsemigroups of certain types.

A maximal subsemigroup of such a Rees (0-)matrix semigroup <code class="code">R</code> over a group <code class="code">G</code> is either:

<ol>
<li><code class="code">{0};</code>

</li>
<li>formed by removing <code class="code">0</code>;

</li>
<li>formed by removing a column (a non-zero \(\mathscr{L}\)-class);

</li>
<li>formed by removing a row (a non-zero \(\mathscr{R}\)-class);

</li>
<li>formed by removing a set of both rows and columns;

</li>
<li>isomorphic to a Rees (0-)matrix semigroup of the same dimensions over a maximal subgroup of <code class="code">G</code> (in particular, the maximal subsemigroup intersects every \(\mathscr{H}\)-class of <code class="code">R</code>).

</li>
</ol>
Note that if <code class="code">R</code> is a Rees matrix semigroup then it has no maximal subsemigroups of types 1, 2, or 5. Only types 3, 4, and 6 are relevant to a Rees matrix semigroup.

<a id="X860A10E387C19150" name="X860A10E387C19150"></a>

<h5>11.11-1 MaximalSubsemigroups</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MaximalSubsemigroups</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">‣ MaximalSubsemigroups</code>( <var class="Arg">S</var>, <var class="Arg">opts</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: The maximal subsemigroups of <var class="Arg">S</var>.

If <var class="Arg">S</var> is a finite semigroup, then the attribute <code class="code">MaximalSubsemigroups</code> returns a list of the non-empty maximal subsemigroups of <var class="Arg">S</var>. The methods used by <code class="code">MaximalSubsemigroups</code> are based on <a href="chapBib_mj.html#biBGraham1968aa">[GGR68]</a>, and are described in <a href="chapBib_mj.html#biBDonoven2018aa">[DMW18]</a>.

It is computationally expensive to search for the maximal subsemigroups of a semigroup, and so computations involving <code class="code">MaximalSubsemigroups</code> may be very lengthy. A substantial amount of information on the progress of <code class="code">MaximalSubsemigroups</code> is provided through the info class <code class="func">InfoSemigroups</code> (<a href="chap2_mj.html#X85CD4E6C82BECAF3">2.5-1</a>), with increasingly detailed information given at levels 1, 2, and 3.

The behaviour of <code class="code">MaximalSubsemigroups</code> can be altered via the second argument <var class="Arg">opts</var>, which should be a record. The optional components of <var class="Arg">opts</var> are:

<dl>
<dt>gens (a boolean)</dt>
<dd>If <code class="code"><var class="Arg">opts</var>.gens</code> is <code class="keyw">false</code> or unspecified, then the maximal subsemigroups themselves are returned and not just generating sets for these subsemigroups.

It can be more computationally expensive to return the generating sets for the maximal subsemigroups, than to return the maximal subsemigroups themselves.

</dd>
<dt>contain (a list)</dt>
<dd>If <code class="code"><var class="Arg">opts</var>.contain</code> is duplicate-free list of elements of <var class="Arg">S</var>, then <code class="code">MaximalSubsemigroups</code> will search for the maximal subsemigroups of <var class="Arg">S</var> which contain those elements.

</dd>
<dt>D (a \(\mathscr{D}\)-class)</dt>
<dd>For a maximal subsemigroup <code class="code">M</code> of a finite semigroup <var class="Arg">S</var>, there exists a unique \(\mathscr{D}\)-class which contains the complement of <code class="code">M</code> in <var class="Arg">S</var>. In other words, the elements of <var class="Arg">S</var> which <code class="code">M</code> lacks are contained in a unique \(\mathscr{D}\)-class.

If <code class="code"><var class="Arg">opts</var>.D</code> is a \(\mathscr{D}\)-class of <var class="Arg">S</var>, then <code class="code">MaximalSubsemigroups</code> will search exclusively for those maximal subsemigroups of <var class="Arg">S</var> whose complement is contained in <code class="code"><var class="Arg">opts</var>.D</code>.

</dd>
<dt>types (a list)</dt>
<dd>This option is relevant only if <var class="Arg">S</var> is a regular Rees (0-)matrix semigroup over a group.

As described at the start of this subsection, <a href="chap11_mj.html#X7D490B867CEFCBEF">11.11</a>, a maximal subsemigroup of a regular Rees (0-)matrix semigroup over a group is one of 6 possible types.

If <var class="Arg">S</var> is a regular Rees (0-)matrix semigroup over a group and <code class="code"><var class="Arg">opts</var>.types</code> is a subset of <code class="code">[1 .. 6]</code>, then <code class="code">MaximalSubsemigroups</code> will search for those maximal subsemigroups of <var class="Arg">S</var> of the types enumerated by <code class="code"><var class="Arg">opts</var>.types</code>.

The default value for this option is <code class="code">[1 .. 6]</code> (i.e. no restriction).

</dd>
</dl>

<div class="example"><pre>
gap> S := FullTransformationSemigroup(3);
<full transformation monoid of degree 3>
gap> MaximalSubsemigroups(S);
[ <transformation semigroup of degree 3 with 7 generators>,
 <transformation semigroup of degree 3 with 7 generators>,
 <transformation semigroup of degree 3 with 7 generators>,
 <transformation semigroup of degree 3 with 7 generators>,
 <transformation monoid of degree 3 with 5 generators> ]
gap> MaximalSubsemigroups(S,
> rec(gens := true, D := DClass(S, Transformation([2, 2, 3]))));
[ [ Transformation( [ 1, 1, 1 ] ), Transformation( [ 3, 3, 3 ] ),
 Transformation( [ 2, 2, 2 ] ), IdentityTransformation,
 Transformation( [ 2, 3, 1 ] ), Transformation( [ 2, 1 ] ) ] ]
gap> MaximalSubsemigroups(S,
> rec(contain := [Transformation([2, 3, 1])]));
[ <transformation semigroup of degree 3 with 7 generators>,
 <transformation monoid of degree 3 with 5 generators> ]
gap> R := PrincipalFactor(
> DClass(FullTransformationMonoid(4), Transformation([2, 2])));
<Rees 0-matrix semigroup 6x4 over Group([ (2,3,4), (2,4) ])>
gap> MaximalSubsemigroups(R, rec(types := [5],
> contain := [RMSElement(R, 1, (), 1),
> RMSElement(R, 1, (2, 3), 2)]));
[ <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators>,
 <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators>,
 <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators>,
 <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators> ]</pre></div>

<a id="X7A52B4117BCEF379" name="X7A52B4117BCEF379"></a>

<h5>11.11-2 NrMaximalSubsemigroups</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrMaximalSubsemigroups</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The number of maximal subsemigroups of <var class="Arg">S</var>.

If <var class="Arg">S</var> is a finite semigroup, then <code class="code">NrMaximalSubsemigroups</code> returns the number of non-empty maximal subsemigroups of <var class="Arg">S</var>. The methods used by <code class="code">MaximalSubsemigroups</code> are based on <a href="chapBib_mj.html#biBGraham1968aa">[GGR68]</a>, and are described in <a href="chapBib_mj.html#biBDonoven2018aa">[DMW18]</a>.

It can be significantly faster to find the number of maximal subsemigroups of a semigroup than to find the maximal subsemigroups themselves.

Unless the maximal subsemigroups of <var class="Arg">S</var> are already known, the command <code class="code">NrMaximalSubsemigroups(<var class="Arg">S</var>)</code> simply calls the command <code class="code">MaximalSubsemigroups(<var class="Arg">S</var>, rec(number := true))</code>.

For more information about searching for maximal subsemigroups of a finite semigroup in the Semigroups package, and for information about the options available to alter the search, see <code class="func">MaximalSubsemigroups</code> (<a href="chap11_mj.html#X860A10E387C19150">11.11-1</a>). By supplying the additional option <code class="code"><var class="Arg">opts</var>.number :=</code> <code class="keyw">true</code>, the number of maximal subsemigroups will be returned rather than the subsemigroups themselves.

<div class="example"><pre>
gap> S := FullTransformationSemigroup(3);
<full transformation monoid of degree 3>
gap> NrMaximalSubsemigroups(S);
5
gap> S := RectangularBand(3, 4);;
gap> NrMaximalSubsemigroups(S);
7
gap> R := PrincipalFactor(
> DClass(FullTransformationMonoid(4), Transformation([2, 2])));
<Rees 0-matrix semigroup 6x4 over Group([ (2,3,4), (2,4) ])>
gap> MaximalSubsemigroups(R, rec(number := true, types := [3, 4]));
10</pre></div>

<a id="X82D74C2478A49FD5" name="X82D74C2478A49FD5"></a>

<h5>11.11-3 IsMaximalSubsemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMaximalSubsemigroup</code>( <var class="Arg">S</var>, <var class="Arg">T</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

If <var class="Arg">S</var> and <var class="Arg">T</var> are semigroups, then <code class="code">IsMaximalSubsemigroup</code> returns <code class="keyw">true</code> if and only if <var class="Arg">T</var> is a maximal subsemigroup of <var class="Arg">S</var>.

A maximal subsemigroup of <var class="Arg">S</var> is a proper subsemigroup of <var class="Arg">S</var> which is contained in no other proper subsemigroup of <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := ZeroSemigroup(2);;
gap> IsMaximalSubsemigroup(S, Semigroup(MultiplicativeZero(S)));
true
gap> S := FullTransformationSemigroup(4);
<full transformation monoid of degree 4>
gap> T := Semigroup(Transformation([3, 4, 1, 2]),
> Transformation([1, 4, 2, 3]),
> Transformation([2, 1, 1, 3]));
<transformation semigroup of degree 4 with 3 generators>
gap> IsMaximalSubsemigroup(S, T);
true
gap> R := Semigroup(Transformation([3, 4, 1, 2]),
> Transformation([1, 4, 2, 2]),
> Transformation([2, 1, 1, 3]));
<transformation semigroup of degree 4 with 3 generators>
gap> IsMaximalSubsemigroup(S, R);
false</pre></div>

<a id="X87696C597F453F4F" name="X87696C597F453F4F"></a>

<h4>11.12 
 Attributes of transformations and transformation semigroups
 </h4>

<a id="X8065DBC48722B085" name="X8065DBC48722B085"></a>

<h5>11.12-1 ComponentRepsOfTransformationSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ComponentRepsOfTransformationSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The representatives of components of a transformation semigroup.

This function returns the representatives of the components of the action of the transformation semigroup <var class="Arg">S</var> on the set of positive integers not greater than the degree of <var class="Arg">S</var>.

The representatives are the least set of points such that every point can be reached from some representative under the action of <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := Semigroup(
> Transformation([11, 11, 9, 6, 4, 1, 4, 1, 6, 7, 12, 5]),
> Transformation([12, 10, 7, 10, 4, 1, 12, 9, 11, 9, 1, 12]));;
gap> ComponentRepsOfTransformationSemigroup(S);
[ 2, 3, 8 ]</pre></div>

<a id="X8706A72A7F3EE532" name="X8706A72A7F3EE532"></a>

<h5>11.12-2 ComponentsOfTransformationSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ComponentsOfTransformationSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The components of a transformation semigroup.

This function returns the components of the action of the transformation semigroup <var class="Arg">S</var> on the set of positive integers not greater than the degree of <var class="Arg">S</var>; the components of <var class="Arg">S</var> partition this set.

<div class="example"><pre>
gap> S := Semigroup(
> Transformation([11, 11, 9, 6, 4, 1, 4, 1, 6, 7, 12, 5]),
> Transformation([12, 10, 7, 10, 4, 1, 12, 9, 11, 9, 1, 12]));;
gap> ComponentsOfTransformationSemigroup(S);
[ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] ]</pre></div>

<a id="X7AA697B186301F54" name="X7AA697B186301F54"></a>

<h5>11.12-3 CyclesOfTransformationSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CyclesOfTransformationSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The cycles of a transformation semigroup.

This function returns the cycles, or strongly connected components, of the action of the transformation semigroup <var class="Arg">S</var> on the set of positive integers not greater than the degree of <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := Semigroup(
> Transformation([11, 11, 9, 6, 4, 1, 4, 1, 6, 7, 12, 5]),
> Transformation([12, 10, 7, 10, 4, 1, 12, 9, 11, 9, 1, 12]));;
gap> CyclesOfTransformationSemigroup(S);
[ [ 1, 11, 12, 5, 4, 6, 10, 7, 9 ], [ 2 ], [ 3 ], [ 8 ] ]</pre></div>

<a id="X8089CF7182AD1925" name="X8089CF7182AD1925"></a>

<h5>11.12-4 DigraphOfAction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOfAction</code>( <var class="Arg">S</var>, <var class="Arg">list</var>, <var class="Arg">act</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A digraph, or <code class="keyw">fail</code>.

If <var class="Arg">S</var> is a transformation semigroup and <var class="Arg">list</var> is list such that <var class="Arg">S</var> acts on the items in <var class="Arg">list</var> via the function <var class="Arg">act</var>, then <code class="code">DigraphOfAction</code> returns a digraph representing the action of <var class="Arg">S</var> on the items in <var class="Arg">list</var> and any further items output by <code class="code"><var class="Arg">act</var>(<var class="Arg">list</var>[i], <var class="Arg">S</var>.j)</code>.

If <code class="code"><var class="Arg">act</var>(<var class="Arg">list</var>[i], <var class="Arg">S</var>.j)</code> is the <code class="code">k</code>-th item in <var class="Arg">list</var>, then in the output digraph there is an edge from the vertex <code class="code">i</code> to the vertex <code class="code">k</code> labelled by <code class="code">j</code>.

The values in <var class="Arg">list</var> and the additional values generated are stored in the vertex labels of the output digraph; see <code class="func">DigraphVertexLabels</code> (<a href="https://gap-packages.github.io/io/doc/chap5_mj.html#X7E51F2FE87140B32">Digraphs: DigraphVertexLabels</a>), and the edge labels are stored in the <code class="func">DigraphEdgeLabels</code> (<a href="https://gap-packages.github.io/io/doc/chap5_mj.html#X7C24851087D4A8FB">Digraphs: DigraphEdgeLabels</a>)

The digraph returned by <code class="code">DigraphOfAction</code> has no multiple edges; see <code class="func">IsMultiDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap6_mj.html#X7BB84CFC7E8B2B26">Digraphs: IsMultiDigraph</a>).

<div class="example"><pre>
gap> S := Semigroup(Transformation([2, 4, 3, 4, 7, 1, 6]),
> Transformation([3, 3, 2, 3, 5, 1, 5]));
<transformation semigroup of degree 7 with 2 generators>
gap> list := Concatenation(List([1 .. 7], x -> [x]),
> Combinations([1 .. 7], 2));
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ], [ 1, 2 ],
 [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 1, 7 ], [ 2, 3 ],
 [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 2, 7 ], [ 3, 4 ], [ 3, 5 ],
 [ 3, 6 ], [ 3, 7 ], [ 4, 5 ], [ 4, 6 ], [ 4, 7 ], [ 5, 6 ],
 [ 5, 7 ], [ 6, 7 ] ]
gap> D := DigraphOfAction(S, list, OnSets);
<immutable digraph with 28 vertices, 54 edges>
gap> OnSets([2, 5], S.1);
[ 4, 7 ]
gap> Position(DigraphVertexLabels(D), [2, 5]);
16
gap> DigraphVertexLabel(D, 25);
[ 4, 7 ]
gap> DigraphEdgeLabel(D, 16, 25);
1</pre></div>

<a id="X7B5ACD5C7E7612A2" name="X7B5ACD5C7E7612A2"></a>

<h5>11.12-5 DigraphOfActionOnPoints</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOfActionOnPoints</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">‣ DigraphOfActionOnPoints</code>( <var class="Arg">S</var>, <var class="Arg">n</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A digraph.

If <var class="Arg">S</var> is a transformation semigroup and <var class="Arg">n</var> is a non-negative integer, then <code class="code">DigraphOfActionOnPoints(<var class="Arg">S</var>, <var class="Arg">n</var>)</code> returns a digraph representing the <code class="func">OnPoints</code> (<a href="../../../doc/ref/chap41_mj.html#X7FE417DD837987B4">Reference: OnPoints</a>) action of <var class="Arg">S</var> on the set <code class="code">[1 .. <var class="Arg">n</var>]</code>.

If the optional argument <var class="Arg">n</var> is not specified, then by default the degree of <var class="Arg">S</var> will be chosen for <var class="Arg">n</var>; see <code class="func">DegreeOfTransformationSemigroup</code> (<a href="../../../doc/ref/chap53_mj.html#X7EA699C687952544">Reference: DegreeOfTransformationSemigroup</a>).

The digraph returned by <code class="code">DigraphOfActionOnPoints</code> has <var class="Arg">n</var> vertices, where the vertex <code class="code">i</code> corresponds to the point <code class="code">i</code>. For each point <code class="code">i</code> in <code class="code">[1 .. <var class="Arg">n</var>]</code>, and for each generator <code class="code">f</code> in <code class="code">GeneratorsOfSemigroup(<var class="Arg">S</var>)</code>, there is an edge from the vertex <code class="code">i</code> to the vertex <code class="code">i ^ f</code>. See <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B">Reference: GeneratorsOfSemigroup</a>) for further information.

<div class="example"><pre>
gap> S := Semigroup(Transformation([2, 4, 2, 4, 7, 1, 6]),
> Transformation([3, 3, 2, 3, 5, 1, 5]));
<transformation semigroup of degree 7 with 2 generators>
gap> D1 := DigraphOfActionOnPoints(S);
<immutable digraph with 7 vertices, 12 edges>
gap> OnPoints(2, S.1);
4
gap> D2 := DigraphOfActionOnPoints(S, 4);
<immutable digraph with 4 vertices, 7 edges>
gap> D2 = InducedSubdigraph(D1, [1 .. 4]);
true
gap> DigraphOfActionOnPoints(S, 5);
<immutable digraph with 5 vertices, 8 edges></pre></div>

<a id="X7C6D8689819AEEE2" name="X7C6D8689819AEEE2"></a>

<h5>11.12-6 FixedPointsOfTransformationSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FixedPointsOfTransformationSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A set of positive integers.

If <var class="Arg">S</var> is a transformation semigroup, then <code class="code">FixedPointsOfTransformationSemigroup(<var class="Arg">S</var>)</code> returns the set of points <code class="code">i</code> in <code class="code">[1 .. DegreeOfTransformationSemigroup(<var class="Arg">S</var>)]</code> such that <code class="code">i ^ f = i</code> for all <code class="code">f</code> in <var class="Arg">S</var>.

<div class="example"><pre>
gap> f := Transformation([1, 4, 2, 4, 3, 7, 7]);
Transformation( [ 1, 4, 2, 4, 3, 7, 7 ] )
gap> S := Semigroup(f);
<commutative transformation semigroup of degree 7 with 1 generator>
gap> FixedPointsOfTransformationSemigroup(S);
[ 1, 4, 7 ]</pre></div>

<a id="X83DA161F875F63B1" name="X83DA161F875F63B1"></a>

<h5>11.12-7 IsTransitive</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsTransitive</code>( <var class="Arg">S</var>[, <var class="Arg">X</var>] )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsTransitive</code>( <var class="Arg">S</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( property )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

A transformation semigroup <var class="Arg">S</var> is transitive or strongly connected on the set <var class="Arg">X</var> if for every <code class="code">i, j</code> in <var class="Arg">X</var> there is an element <code class="code">s</code> in <var class="Arg">S</var> such that <code class="code">i ^ s = j</code>.

If the optional second argument is a positive integer <var class="Arg">n</var>, then <code class="code">IsTransitive</code> returns <code class="keyw">true</code> if <var class="Arg">S</var> is transitive on <code class="code">[1 .. <var class="Arg">n</var>]</code>, and <code class="keyw">false</code> if it is not.

If the optional second argument is not provided, then the degree of <var class="Arg">S</var> is used by default; see <code class="func">DegreeOfTransformationSemigroup</code> (<a href="../../../doc/ref/chap53_mj.html#X7EA699C687952544">Reference: DegreeOfTransformationSemigroup</a>).

<div class="example"><pre>
gap> S := Semigroup([
> Bipartition([
> [1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]),
> Bipartition([
> [1, -4], [2, 3, 4, 5], [6], [-1, -6], [-2, -3], [-5]])]);
<bipartition semigroup of degree 6 with 2 generators>
gap> AsSemigroup(IsTransformationSemigroup, S);
<transformation semigroup of size 11, degree 12 with 2 generators>
gap> IsTransitive(last);
false
gap> IsTransitive(AsSemigroup(Group((1, 2, 3))));
true</pre></div>

<a id="X7C65202187A9C9F5" name="X7C65202187A9C9F5"></a>

<h5>11.12-8 SmallestElementSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestElementSemigroup</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">‣ LargestElementSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A transformation.

These attributes return the smallest and largest element of the transformation semigroup <var class="Arg">S</var>, respectively. Smallest means the first element in the sorted set of elements of <var class="Arg">S</var> and largest means the last element in the set of elements.

It is not necessary to find the elements of the semigroup to determine the smallest or largest element, and this function has considerable better performance than the equivalent <code class="code">Elements(<var class="Arg">S</var>)[1]</code> and <code class="code">Elements(<var class="Arg">S</var>)[Size(<var class="Arg">S</var>)]</code>.

<div class="example"><pre>
gap> S := Monoid(
> Transformation([1, 4, 11, 11, 7, 2, 6, 2, 5, 5, 10]),
> Transformation([2, 4, 4, 2, 10, 5, 11, 11, 11, 6, 7]));
<transformation monoid of degree 11 with 2 generators>
gap> SmallestElementSemigroup(S);
IdentityTransformation
gap> LargestElementSemigroup(S);
Transformation( [ 11, 11, 10, 10, 7, 6, 5, 6, 2, 2, 4 ] )</pre></div>

<a id="X84792D3D804413CD" name="X84792D3D804413CD"></a>

<h5>11.12-9 CanonicalTransformation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalTransformation</code>( <var class="Arg">trans</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( function )</td></tr></table></div>
Returns: A transformation.

If <var class="Arg">trans</var> is a transformation, and <var class="Arg">n</var> is a non-negative integer such that the restriction of <var class="Arg">trans</var> to <code class="keyw">[1 .. n]</code> defines a transformation of <code class="code">[1 .. n]</code>, then <code class="code">CanonicalTransformation</code> returns a canonical representative of the transformation <var class="Arg">trans</var> restricted to <code class="code">[1 .. n]</code>.

More specifically, let <code class="code">C(n)</code> be a class of transformations of degree <var class="Arg">n</var> such that <code class="code">AsDigraph</code> returns isomorphic digraphs for every pair of element elements in <code class="code">C(n)</code>. Recall that for a transformation <var class="Arg">trans</var> and integer <var class="Arg">n</var> the function <code class="code">AsDigraph</code> returns a digraph with <var class="Arg">n</var> vertices and an edge with source <code class="code">x</code> and range <code class="code">x^trans</code> for every <code class="code">x</code> in <code class="code">[1 .. n]</code>. See <code class="func">AsDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap3_mj.html#X86834E307EACC670">Digraphs: AsDigraph for a binary relation</a>). Then <code class="code">CanonicalTransformation</code> returns a canonical representative of the class <code class="code">C(n)</code> that contains <var class="Arg">trans</var>.

<div class="example"><pre>
gap> x := Transformation([5, 1, 4, 1, 1]);
Transformation( [ 5, 1, 4, 1, 1 ] )
gap> y := Transformation([3, 3, 2, 3, 1]);
Transformation( [ 3, 3, 2, 3, 1 ] )
gap> CanonicalTransformation(x);
Transformation( [ 3, 5, 2, 2, 2 ] )
gap> CanonicalTransformation(y);
Transformation( [ 3, 5, 2, 2, 2 ] )</pre></div>

<a id="X82ABE03F80B8CA2B" name="X82ABE03F80B8CA2B"></a>

<h5>11.12-10 IsConnectedTransformationSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsConnectedTransformationSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

A transformation semigroup <var class="Arg">S</var> is connected if the digraph returned by the function <code class="code">DigraphOfActionOnPoints</code> is connected. See <code class="func">IsConnectedDigraph</code> (<a href="https://gap-packages.github.io/io/doc/chap6_mj.html#X83C08C0B7EC1A91F">Digraphs: IsConnectedDigraph</a>) and <code class="func">DigraphOfActionOnPoints</code> (<a href="chap11_mj.html#X7B5ACD5C7E7612A2">11.12-5</a>). The function <code class="code">IsConnectedTransformationSemigroup</code> returns <code class="keyw">true</code> if the semigroup <var class="Arg">S</var> is connected and <code class="keyw">false</code> otherwise.

<div class="example"><pre>
gap> S := Semigroup([
> Transformation([2, 4, 3, 4]),
> Transformation([3, 3, 2, 3, 3])]);
<transformation semigroup of degree 5 with 2 generators>
gap> IsConnectedTransformationSemigroup(S);
true</pre></div>

<a id="X84B8E29C7D7565B0" name="X84B8E29C7D7565B0"></a>

<h4>11.13 
 Attributes of partial perm semigroups
 </h4>

<a id="X7BC22CB47C7B5EBB" name="X7BC22CB47C7B5EBB"></a>

<h5>11.13-1 ComponentRepsOfPartialPermSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ComponentRepsOfPartialPermSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The representatives of components of a partial perm semigroup.

This function returns the representatives of the components of the action of the partial perm semigroup <var class="Arg">S</var> on the set of positive integers where it is defined.

The representatives are the least set of points such that every point can be reached from some representative under the action of <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := Semigroup([
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19],
> [9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20],
> [13, 1, 8, 5, 4, 14, 11, 12, 9, 20, 2, 18, 7, 3, 19])]);;
gap> ComponentRepsOfPartialPermSemigroup(S);
[ 6, 10, 15, 17 ]</pre></div>

<a id="X8464BC397ACBF2F1" name="X8464BC397ACBF2F1"></a>

<h5>11.13-2 ComponentsOfPartialPermSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ComponentsOfPartialPermSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The components of a partial perm semigroup.

This function returns the components of the action of the partial perm semigroup <var class="Arg">S</var> on the set of positive integers where it is defined; the components of <var class="Arg">S</var> partition this set.

<div class="example"><pre>
gap> S := Semigroup([
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19],
> [9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20],
> [13, 1, 8, 5, 4, 14, 11, 12, 9, 20, 2, 18, 7, 3, 19])]);;
gap> ComponentsOfPartialPermSemigroup(S);
[ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 18, 19, 20 ],
 [ 15 ], [ 17 ] ]</pre></div>

<a id="X832937BB87EB4349" name="X832937BB87EB4349"></a>

<h5>11.13-3 CyclesOfPartialPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CyclesOfPartialPerm</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The cycles of a partial perm.

This function returns the cycles, or strongly connected components, of the action of the partial perm <var class="Arg">x</var> on the set of positive integers where it is defined.

<div class="example"><pre>
gap> x := PartialPerm([3, 1, 4, 2, 5, 0, 0, 6, 0, 7]);
[8,6][10,7](1,3,4,2)(5)
gap> CyclesOfPartialPerm(x);
[ [ 5 ], [ 1, 3, 4, 2 ] ]</pre></div>

<a id="X7F7A5E5E8355E230" name="X7F7A5E5E8355E230"></a>

<h5>11.13-4 CyclesOfPartialPermSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CyclesOfPartialPermSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The cycles of a partial perm semigroup.

This function returns the cycles, or strongly connected components, of the action of the partial perm semigroup <var class="Arg">S</var> on the set of positive integers where it is defined.

<div class="example"><pre>
gap> S := Semigroup([
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19],
> [9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20],
> [13, 1, 8, 5, 4, 14, 11, 12, 9, 20, 2, 18, 7, 3, 19])]);;
gap> CyclesOfPartialPermSemigroup(S);
[ [ 18, 7, 16 ], [ 1, 9, 12, 14, 2, 20, 19, 3, 8, 11 ], [ 4, 5 ] ]
</pre></div>

<a id="X7AF313CF7CBE98D7" name="X7AF313CF7CBE98D7"></a>

<h4>11.14 
 Attributes of Rees (0-)matrix semigroups
 </h4>

<a id="X7EA1B28785B9D38C" name="X7EA1B28785B9D38C"></a>

<h5>11.14-1 RZMSDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RZMSDigraph</code>( <var class="Arg">R</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A digraph.

If <var class="Arg">R</var> is an \(n\) by \(m\) Rees 0-matrix semigroup \(M^{0}[I, T, \Lambda; P]\) (so that \(I = \{1,2,\ldots,n\}\) and \(\Lambda = \{1,2,\ldots,m\}\)) then <code class="code">RZMSDigraph</code> returns a symmetric bipartite digraph with \(n+m\) vertices. An index \(i \in I\) corresponds to the vertex \(i\) and an index \(j \in \Lambda\) corresponds to the vertex \(j + n\).

Two vertices \(v\) and \(w\) in <code class="code">RZMSDigraph(</code><var class="Arg">R</var><code class="code">)</code> are adjacent if and only if \(v\in I\), \(w - n\in \Lambda\), and <code class="code">P[w - n][v]</code> \(\neq 0\).

This digraph is commonly called the Graham-Houghton graph of <var class="Arg">R</var>.

<div class="example"><pre>
gap> R := PrincipalFactor(
> DClass(FullTransformationMonoid(5),
> Transformation([2, 4, 1, 5, 5])));
<Rees 0-matrix semigroup 10x5 over Group([ (1,2,3,4), (1,2) ])>
gap> gr := RZMSDigraph(R);
<immutable bipartite digraph with bicomponent sizes 10 and 5>
gap> e := DigraphEdges(gr)[1];
[ 1, 11 ]
gap> Matrix(R)[e[2] - 10][e[1]] <> 0;
true</pre></div>

<a id="X79B062917AB34542" name="X79B062917AB34542"></a>

<h5>11.14-2 RZMSConnectedComponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RZMSConnectedComponents</code>( <var class="Arg">R</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The connected components of a Rees 0-matrix semigroup.

If <var class="Arg">R</var> is an \(n\) by \(m\) Rees 0-matrix semigroup \(M^{0}[I, T, \Lambda; P]\) (so that \(I = \{1,2,\ldots,n\}\) and \(\Lambda = \{1,2,\ldots,m\}\)) then <code class="code">RZMSConnectedComponents</code> returns the connected components of <var class="Arg">R</var>.

Connectedness is an equivalence relation on the indices of <var class="Arg">R</var>: the equivalence classes of the relation are called the connected components of <var class="Arg">R</var>, and two indices in \(I \cup \Lambda\) are connected if and only if their corresponding vertices in <code class="code">RZMSDigraph(</code><var class="Arg">R</var><code class="code">)</code> are connected (see <code class="func">RZMSDigraph</code> (<a href="chap11_mj.html#X7EA1B28785B9D38C">11.14-1</a>)). If <var class="Arg">R</var> has \(n\) connected components, then <code class="code">RZMSConnectedComponents</code> will return a list of pairs:

<code class="code">[ [ </code>\(I_{1}, \Lambda_{1}\)<code class="code"> ], </code>\(\ldots\)<code class="code">, [ </code>\(I_{k}, \Lambda_{k}\)<code class="code"> ] ]</code>

where \(I = I_1 \sqcup \cdots \sqcup I_k\), \(\Lambda = \Lambda_1 \sqcup \cdots \sqcup \Lambda_k\), and for each \(l\) the set \(I_{l}\cup\Lambda_{l}\) is a connected component of <var class="Arg">R</var>. Note that at most one of \(I_l\) and \(\Lambda_l\) is possibly empty. The ordering of the connected components in the result in unspecified.

<div class="example"><pre>
gap> R := ReesZeroMatrixSemigroup(SymmetricGroup(5),
> [[(), 0, (1, 3), (4, 5), 0],
> [0, (), 0, 0, (1, 3, 4, 5)],
> [0, 0, (1, 5)(2, 3), 0, 0],
> [0, (2, 3)(1, 4), 0, 0, 0]]);
<Rees 0-matrix semigroup 5x4 over Sym( [ 1 .. 5 ] )>
gap> RZMSConnectedComponents(R);
[ [ [ 1, 3, 4 ], [ 1, 3 ] ], [ [ 2, 5 ], [ 2, 4 ] ] ]</pre></div>

<a id="X822D030682BC1275" name="X822D030682BC1275"></a>

<h4>11.15 
 Attributes of inverse semigroups
 </h4>

<a id="X7A75A6C486F1DC71" name="X7A75A6C486F1DC71"></a>

<h5>11.15-1 NaturalLeqInverseSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NaturalLeqInverseSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An function.

<code class="code">NaturalLeqInverseSemigroup</code> returns a function that, when given two elements <code class="code">x, y</code> of the inverse semigroup <var class="Arg">S</var>, returns <code class="keyw">true</code> if <code class="code">x</code> is less than or equal to <code class="code">y</code> in the natural partial order on <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := Monoid(Transformation([1, 3, 4, 4]),
> Transformation([1, 4, 2, 4]));
<transformation monoid of degree 4 with 2 generators>
gap> IsInverseSemigroup(S);
true
gap> Size(S);
6
gap> NaturalPartialOrder(S);
[ [ 2, 5, 6 ], [ 6 ], [ 6 ], [ 6 ], [ 6 ], [ ] ]</pre></div>

<a id="X85CDF93C805AF82A" name="X85CDF93C805AF82A"></a>

<h5>11.15-2 JoinIrreducibleDClasses</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ JoinIrreducibleDClasses</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of \(\mathscr{D}\)-classes.

<code class="code">JoinIrreducibleDClasses</code> returns a list of the join irreducible \(\mathscr{D}\)-classes of the inverse semigroup of partial permutations, block bijections or partial permutation bipartitions <var class="Arg">S</var>.

A join irreducible \(\mathscr{D}\)-class is a \(\mathscr{D}\)-class containing only join irreducible elements. See <code class="func">IsJoinIrreducible</code> (<a href="chap12_mj.html#X817F9F3984FC842C">12.2-7</a>). If a \(\mathscr{D}\)-class contains one join irreducible element, then all of the elements in the \(\mathscr{D}\)-class are join irreducible.

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(3);
<symmetric inverse monoid of degree 3>
gap> JoinIrreducibleDClasses(S);
[ <Green's D-class: <identity partial perm on [ 2 ]>> ]
gap> T := InverseSemigroup([
> PartialPerm([1, 2, 4, 3]),
> PartialPerm([1]),
> PartialPerm([0, 2])]);
<inverse partial perm semigroup of rank 4 with 3 generators>
gap> JoinIrreducibleDClasses(T);
[ <Green's D-class: <identity partial perm on [ 1, 2, 3, 4 ]>>,
 <Green's D-class: <identity partial perm on [ 1 ]>>,
 <Green's D-class: <identity partial perm on [ 2 ]>> ]
gap> D := DualSymmetricInverseSemigroup(3);
<inverse block bijection monoid of degree 3 with 3 generators>
gap> JoinIrreducibleDClasses(D);
[ <Green's D-class: <block bijection: [ 1, 2, -1, -2 ], [ 3, -3 ]>> ]</pre></div>

<a id="X801CC67E80898608" name="X801CC67E80898608"></a>

<h5>11.15-3 MajorantClosure</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MajorantClosure</code>( <var class="Arg">S</var>, <var class="Arg">T</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A majorantly closed list of elements.

<code class="code">MajorantClosure</code> returns a majorantly closed subset of an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions, <var class="Arg">S</var>, as a list. See <code class="func">IsMajorantlyClosed</code> (<a href="chap12_mj.html#X81E6D24F852A7937">12.2-8</a>).

The result contains all elements of <var class="Arg">S</var> which are greater than or equal to any element of <var class="Arg">T</var> (with respect to the natural partial order <code class="func">NaturalLeqPartialPerm</code> (<a href="../../../doc/ref/chap54_mj.html#X87B1ED93785257C1">Reference: NaturalLeqPartialPerm</a>)). In particular, the result is a superset of <var class="Arg">T</var>.

Note that <var class="Arg">T</var> can be a subset of <var class="Arg">S</var> or a subsemigroup of <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(4);
<symmetric inverse monoid of degree 4>
gap> T := [PartialPerm([1, 0, 3, 0])];
[ <identity partial perm on [ 1, 3 ]> ]
gap> U := MajorantClosure(S, T);
[ <identity partial perm on [ 1, 3 ]>,
 <identity partial perm on [ 1, 2, 3 ]>, [2,4](1)(3), [4,2](1)(3),
 <identity partial perm on [ 1, 3, 4 ]>,
 <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2,4)(3) ]
gap> B := InverseSemigroup([
> Bipartition([[1, -2], [2, -1], [3, -3], [4, 5, -4, -5]]),
> Bipartition([[1, -3], [2, -4], [3, -2], [4, -1], [5, -5]])]);;
gap> T := [Bipartition([[1, -2], [2, 3, 5, -1, -3, -5], [4, -4]]),
> Bipartition([[1, -4], [2, 3, 5, -1, -3, -5], [4, -2]])];;
gap> IsMajorantlyClosed(B, T);
false
gap> MajorantClosure(B, T);
[ <block bijection: [ 1, -2 ], [ 2, 3, 5, -1, -3, -5 ], [ 4, -4 ]>,
 <block bijection: [ 1, -4 ], [ 2, 3, 5, -1, -3, -5 ], [ 4, -2 ]>,
 <block bijection: [ 1, -2 ], [ 2, 5, -1, -5 ], [ 3, -3 ], [ 4, -4 ]>
 , <block bijection: [ 1, -2 ], [ 2, -1 ], [ 3, 5, -3, -5 ],
 [ 4, -4 ]>,
 <block bijection: [ 1, -4 ], [ 2, 5, -3, -5 ], [ 3, -1 ], [ 4, -2 ]>
 , <block bijection: [ 1, -4 ], [ 2, -3 ], [ 3, 5, -1, -5 ],
 [ 4, -2 ]>, <block bijection: [ 1, -4 ], [ 2, -3 ], [ 3, -1 ],
 [ 4, -2 ], [ 5, -5 ]> ]
gap> IsMajorantlyClosed(B, last);
true
</pre></div>

<a id="X84A3DB79816374DB" name="X84A3DB79816374DB"></a>

<h5>11.15-4 Minorants</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Minorants</code>( <var class="Arg">S</var>, <var class="Arg">f</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of elements.

<code class="code">Minorants</code> takes an element <var class="Arg">f</var> from an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions <var class="Arg">S</var>, and returns a list of the minorants of <var class="Arg">f</var> in <var class="Arg">S</var>.

A minorant of <var class="Arg">f</var> is an element of <var class="Arg">S</var> which is strictly less than <var class="Arg">f</var> in the natural partial order of <var class="Arg">S</var>. See <code class="func">NaturalLeqPartialPerm</code> (<a href="../../../doc/ref/chap54_mj.html#X87B1ED93785257C1">Reference: NaturalLeqPartialPerm</a>).

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(3);
<symmetric inverse monoid of degree 3>
gap> x := Elements(S)[13];
[1,3](2)
gap> Minorants(S, x);
[ <empty partial perm>, [1,3], <identity partial perm on [ 2 ]> ]
gap> x := PartialPerm([3, 2, 4, 0]);
[1,3,4](2)
gap> S := InverseSemigroup(x);
<inverse partial perm semigroup of rank 4 with 1 generator>
gap> Minorants(S, x);
[ <identity partial perm on [ 2 ]>, [1,3](2), [3,4](2) ]</pre></div>

<a id="X80C0C6C37C4A2ABD" name="X80C0C6C37C4A2ABD"></a>

<h5>11.15-5 PrimitiveIdempotents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimitiveIdempotents</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of elements.

An idempotent in an inverse semigroup <var class="Arg">S</var> is primitive if it is non-zero and minimal with respect to the <code class="func">NaturalPartialOrder</code> (<a href="../../../doc/ref/chap54_mj.html#X7EA51F087CF7621F">Reference: NaturalPartialOrder</a>) on <var class="Arg">S</var>. <code class="code">PrimitiveIdempotents</code> returns the list of primitive idempotents in the inverse semigroup <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := InverseMonoid(
> PartialPerm([1], [4]),
> PartialPerm([1, 2, 3], [2, 1, 3]),
> PartialPerm([1, 2, 3], [3, 1, 2]));;
gap> MultiplicativeZero(S);
<empty partial perm>
gap> Set(PrimitiveIdempotents(S));
[ <identity partial perm on [ 1 ]>, <identity partial perm on [ 2 ]>,
 <identity partial perm on [ 3 ]>, <identity partial perm on [ 4 ]> ]
gap> S := DualSymmetricInverseMonoid(4);
<inverse block bijection monoid of degree 4 with 3 generators>
gap> Set(PrimitiveIdempotents(S));
[ <block bijection: [ 1, 2, 3, -1, -2, -3 ], [ 4, -4 ]>,
 <block bijection: [ 1, 2, 4, -1, -2, -4 ], [ 3, -3 ]>,
 <block bijection: [ 1, 2, -1, -2 ], [ 3, 4, -3, -4 ]>,
 <block bijection: [ 1, 3, 4, -1, -3, -4 ], [ 2, -2 ]>,
 <block bijection: [ 1, 3, -1, -3 ], [ 2, 4, -2, -4 ]>,
 <block bijection: [ 1, 4, -1, -4 ], [ 2, 3, -2, -3 ]>,
 <block bijection: [ 1, -1 ], [ 2, 3, 4, -2, -3, -4 ]> ]</pre></div>

<a id="X7B5D89A585F8B5EA" name="X7B5D89A585F8B5EA"></a>

<h5>11.15-6 RightCosetsOfInverseSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightCosetsOfInverseSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">T</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of lists of elements.

<code class="code">RightCosetsOfInverseSemigroup</code> takes a majorantly closed inverse subsemigroup <var class="Arg">T</var> of an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions <var class="Arg">S</var>. See <code class="func">IsMajorantlyClosed</code> (<a href="chap12_mj.html#X81E6D24F852A7937">12.2-8</a>). The result is a list of the right cosets of <var class="Arg">T</var> in <var class="Arg">S</var>.

For \(s \in S\), the right coset \(\overline{Ts}\) is defined if and only if \(ss^{-1} \in T\), in which case it is defined to be the majorant closure of the set \(Ts\). See <code class="func">MajorantClosure</code> (<a href="chap11_mj.html#X801CC67E80898608">11.15-3</a>). Distinct cosets are disjoint but do not necessarily partition <var class="Arg">S</var>.

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(3);
<symmetric inverse monoid of degree 3>
gap> T := InverseSemigroup(MajorantClosure(S, [PartialPerm([1])]));
<inverse partial perm monoid of rank 3 with 6 generators>
gap> IsMajorantlyClosed(S, T);
true
gap> RC := RightCosetsOfInverseSemigroup(S, T);
[ [ <identity partial perm on [ 1 ]>,
 <identity partial perm on [ 1, 2 ]>, [2,3](1), [3,2](1),
 <identity partial perm on [ 1, 3 ]>,
 <identity partial perm on [ 1, 2, 3 ]>, (1)(2,3) ],
 [ [1,3], [2,1,3], [1,3](2), (1,3), [1,3,2], (1,3,2), (1,3)(2) ],
 [ [1,2], (1,2), [1,2,3], [3,1,2], [1,2](3), (1,2)(3), (1,2,3) ] ]</pre></div>

<a id="X83298E9E86A343FF" name="X83298E9E86A343FF"></a>

<h5>11.15-7 SameMinorantsSubgroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SameMinorantsSubgroup</code>( <var class="Arg">H</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of elements of the group \(\mathscr{H}\)-class <var class="Arg">H</var>.

Given a group \(\mathscr{H}\)-class <var class="Arg">H</var> in an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions <code class="code">S</code>, <code class="code">SameMinorantsSubgroup</code> returns a list of the elements of <var class="Arg">H</var> which have the same strict minorants as the identity element of <var class="Arg">H</var>. A strict minorant of <code class="code">x</code> in <var class="Arg">H</var> is an element of <code class="code">S</code> which is less than <code class="code">x</code> (with respect to the natural partial order), but is not equal to <code class="code">x</code>.

The returned list of elements of <var class="Arg">H</var> describe a subgroup of <var class="Arg">H</var>.

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(3);
<symmetric inverse monoid of degree 3>
gap> H := GroupHClass(DClass(S, PartialPerm([1, 2, 3])));
<Green's H-class: <identity partial perm on [ 1, 2, 3 ]>>
gap> Elements(H);
[ <identity partial perm on [ 1, 2, 3 ]>, (1)(2,3), (1,2)(3),
 (1,2,3), (1,3,2), (1,3)(2) ]
gap> SameMinorantsSubgroup(H);
[ <identity partial perm on [ 1, 2, 3 ]> ]
gap> T := InverseSemigroup(
> PartialPerm([1, 2, 3, 4], [1, 2, 4, 3]),
> PartialPerm([1], [1]), PartialPerm([2], [2]));
<inverse partial perm semigroup of rank 4 with 3 generators>
gap> Elements(T);
[ <empty partial perm>, <identity partial perm on [ 1 ]>,
 <identity partial perm on [ 2 ]>,
 <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4) ]
gap> x := GroupHClass(DClass(T, PartialPerm([1, 2, 3, 4])));
<Green's H-class: <identity partial perm on [ 1, 2, 3, 4 ]>>
gap> Elements(x);
[ <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4) ]
gap> AsSet(SameMinorantsSubgroup(x));
[ <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4) ]</pre></div>

<a id="X786D4E397EA4445D" name="X786D4E397EA4445D"></a>

<h5>11.15-8 SmallerDegreePartialPermRepresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallerDegreePartialPermRepresentation</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An isomorphism.

<code class="code">SmallerDegreePartialPermRepresentation</code> attempts to find an isomorphism from the inverse semigroup <var class="Arg">S</var> to an inverse semigroup of partial permutations with small degree. If <var class="Arg">S</var> is already a partial permutation semigroup, and the function cannot reduce the degree, the identity mapping is returned.

There is no guarantee that the smallest possible degree representation is returned. For more information see <a href="chapBib_mj.html#biBSchein1992aa">[Sch92]</a>.

<div class="example"><pre>
gap> S := InverseSemigroup(PartialPerm([2, 1, 4, 3, 6, 5, 8, 7]));
<partial perm group of rank 8 with 1 generator>
gap> Elements(S);
[ <identity partial perm on [ 1, 2, 3, 4, 5, 6, 7, 8 ]>,
 (1,2)(3,4)(5,6)(7,8) ]
gap> iso := SmallerDegreePartialPermRepresentation(S);;
gap> Source(iso) = S;
true
gap> R := Range(iso);
<partial perm group of rank 2 with 1 generator>
gap> Elements(R);
[ <identity partial perm on [ 1, 2 ]>, (1,2) ]
gap> S := DualSymmetricInverseMonoid(5);;
gap> T := Range(IsomorphismPartialPermSemigroup(S));
<inverse partial perm monoid of size 6721, rank 6721 with 3
generators>
gap> SmallerDegreePartialPermRepresentation(T);
<inverse partial perm monoid of size 6721, rank 6721 with 3
 generators> -> <inverse partial perm monoid of rank 30 with 3
 generators></pre></div>

<a id="X7BC49C3487384364" name="X7BC49C3487384364"></a>

<h5>11.15-9 VagnerPrestonRepresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ VagnerPrestonRepresentation</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An isomorphism to an inverse semigroup of partial permutations.

<code class="code">VagnerPrestonRepresentation</code> returns an isomorphism from an inverse semigroup <var class="Arg">S</var> where the elements of <var class="Arg">S</var> have a unique semigroup inverse accessible via <code class="func">Inverse</code> (<a href="../../../doc/ref/chap31_mj.html#X78EE524E83624057">Reference: Inverse</a>), to the inverse semigroup of partial permutations <var class="Arg">T</var> of degree equal to the size of <var class="Arg">S</var>, which is obtained using the Vagner-Preston Representation Theorem.

More precisely, if \(f:S\to T\) is the isomorphism returned by <code class="code">VagnerPrestonRepresentation(<var class="Arg">S</var>)</code> and \(x\) is in <var class="Arg">S</var>, then \(f(x)\) is the partial permutation with domain \(Sx^{-1}\) and range \(Sx^{-1}x\) defined by \(f(x): sx^{-1}\mapsto sx^{-1}x\).

In many cases, it is possible to find a smaller degree representation than that provided by <code class="code">VagnerPrestonRepresentation</code> using <code class="func">IsomorphismPartialPermSemigroup</code> (<a href="../../../doc/ref/chap54_mj.html#X7FE18EBE79B9C17C">Reference: IsomorphismPartialPermSemigroup</a>) or <code class="func">SmallerDegreePartialPermRepresentation</code> (<a href="chap11_mj.html#X786D4E397EA4445D">11.15-8</a>).

<div class="example"><pre>
gap> S := SymmetricInverseSemigroup(2);
<symmetric inverse monoid of degree 2>
gap> Size(S);
7
gap> iso := VagnerPrestonRepresentation(S);
<symmetric inverse monoid of degree 2> ->
<inverse partial perm monoid of rank 7 with 2 generators>
gap> RespectsMultiplication(iso);
true
gap> inv := InverseGeneralMapping(iso);;
gap> ForAll(S, x -> (x ^ iso) ^ inv = x);
true
gap> V := InverseSemigroup(
> Bipartition([[1, -4], [2, -1], [3, -5], [4], [5], [-2], [-3]]),
> Bipartition([[1, -5], [2, -1], [3, -3], [4], [5], [-2], [-4]]),
> Bipartition([[1, -2], [2, -4], [3, -5], [4, -1], [5, -3]]));
<inverse bipartition semigroup of degree 5 with 3 generators>
gap> IsInverseSemigroup(V);
true
gap> VagnerPrestonRepresentation(V);
<inverse bipartition semigroup of size 394, degree 5 with 3
 generators> -> <inverse partial perm semigroup of rank 394 with 5
 generators></pre></div>

<a id="X7C83DF9A7973AF6D" name="X7C83DF9A7973AF6D"></a>

<h5>11.15-10 CharacterTableOfInverseSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CharacterTableOfInverseSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The character table of the inverse semigroup <var class="Arg">S</var> and a list of conjugacy class representatives of <var class="Arg">S</var>.

Returns a list with two entries: the first entry being the character table of the inverse semigroup <var class="Arg">S</var> as a matrix, while the second entry is a list of conjugacy class representatives of <var class="Arg">S</var>.

The order of the columns in the character table matrix follows the order of the conjugacy class representatives list. The conjugacy representatives are grouped by \(\mathscr{D}\)-class and then sorted by rank. Also, as is typical of character tables, the rows of the matrix correspond to the irreducible characters and the columns correspond to the conjugacy classes.

This function was contributed by Jhevon Smith and Ben Steinberg.

<div class="example"><pre>
gap> S := InverseMonoid([
> PartialPerm([1, 2], [3, 1]),
> PartialPerm([1, 2, 3], [1, 3, 4]),
> PartialPerm([1, 2, 3], [2, 4, 1]),
> PartialPerm([1, 3, 4], [3, 4, 1])]);;
gap> CharacterTableOfInverseSemigroup(S);
[ [ [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 3, 1, 1, 1, 0, 0, 0, 0 ],
 [ 3, 1, E(3), E(3)^2, 0, 0, 0, 0 ],
 [ 3, 1, E(3)^2, E(3), 0, 0, 0, 0 ], [ 6, 3, 0, 0, 1, -1, 0, 0 ],
 [ 6, 3, 0, 0, 1, 1, 0, 0 ], [ 4, 3, 0, 0, 2, 0, 1, 0 ],
 [ 1, 1, 1, 1, 1, 1, 1, 1 ] ],
 [ <identity partial perm on [ 1, 2, 3, 4 ]>,
 <identity partial perm on [ 1, 3, 4 ]>, (1,3,4), (1,4,3),
 <identity partial perm on [ 1, 3 ]>, (1,3),
 <identity partial perm on [ 3 ]>, <empty partial perm> ] ]
gap> S := SymmetricInverseMonoid(4);;
gap> CharacterTableOfInverseSemigroup(S);
[ [ [ 1, -1, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0 ],
 [ 3, -1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0 ],
 [ 2, 0, -1, 2, 0, 0, 0, 0, 0, 0, 0, 0 ],
 [ 3, 1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0 ],
 [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 ],
 [ 4, -2, 1, 0, 0, 1, -1, 1, 0, 0, 0, 0 ],
 [ 8, 0, -1, 0, 0, 2, 0, -1, 0, 0, 0, 0 ],
 [ 4, 2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0 ],
 [ 6, 0, 0, -2, 0, 3, -1, 0, 1, -1, 0, 0 ],
 [ 6, 2, 0, 2, 0, 3, 1, 0, 1, 1, 0, 0 ],
 [ 4, 2, 1, 0, 0, 3, 1, 0, 2, 0, 1, 0 ],
 [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ],
 [ <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4),
 (1)(2,3,4), (1,2)(3,4), (1,2,3,4),
 <identity partial perm on [ 1, 2, 3 ]>, (1)(2,3), (1,2,3),
 <identity partial perm on [ 2, 3 ]>, (2,3),
 <identity partial perm on [ 1 ]>, <empty partial perm> ] ]</pre></div>

<a id="X8383E6747D02D975" name="X8383E6747D02D975"></a>

<h5>11.15-11 EUnitaryInverseCover</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EUnitaryInverseCover</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A homomorphism between semigroups.

If the argument <var class="Arg">S</var> is an inverse semigroup then this function returns a finite E-unitary inverse cover of <var class="Arg">S</var>. A finite E-unitary cover of <var class="Arg">S</var> is a surjective idempotent separating homomorphism from a finite semigroup satisfying <code class="func">IsEUnitaryInverseSemigroup</code> (<a href="chap12_mj.html#X843EA0E37C968BBF">12.2-3</a>) to <var class="Arg">S</var>. A semigroup homomorphism is said to be idempotent separating if no two idempotents are mapped to the same element of the image.

<div class="example"><pre>
gap> S := InverseSemigroup([PartialPermNC([1, 2], [2, 1]),
> PartialPermNC([1], [1])]);
<inverse partial perm semigroup of rank 2 with 2 generators>
gap> cov := EUnitaryInverseCover(S);
<inverse partial perm semigroup of rank 4 with 2 generators> ->
<inverse partial perm semigroup of rank 2 with 2 generators>
gap> IsEUnitaryInverseSemigroup(Source(cov));
true
gap> S = Range(cov);
true</pre></div>

<a id="X7AA4CE887EEA661A" name="X7AA4CE887EEA661A"></a>

<h4>11.16 
 Nambooripad partial order
 </h4>

<a id="X7A7EB0DA8398886E" name="X7A7EB0DA8398886E"></a>

<h5>11.16-1 NambooripadLeqRegularSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NambooripadLeqRegularSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A function.

<code class="code">NambooripadLeqRegularSemigroup</code> returns a function that, when given two elements <code class="code">x, y</code> of the regular semigroup <var class="Arg">S</var>, returns <code class="keyw">true</code> if <code class="code">x</code> is less than or equal to <code class="code">y</code> in the Nambooripad partial order on <var class="Arg">S</var>. See also <code class="func">NambooripadPartialOrder</code> (<a href="chap11_mj.html#X7928C7D37A9BCBD5">11.16-2</a>).

<div class="example"><pre>
gap> S := BrauerMonoid(3);
<regular bipartition *-monoid of degree 3 with 3 generators>
gap> IsRegularSemigroup(S);
true
gap> Size(S);
15
gap> NambooripadPartialOrder(S);
[ [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ],
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] ]
gap> NambooripadLeqRegularSemigroup(S)(Elements(S)[3], Elements(S)[9]);
false
gap> NambooripadLeqRegularSemigroup(S)(Elements(S)[2], Elements(S)[15]);
true</pre></div>

<a id="X7928C7D37A9BCBD5" name="X7928C7D37A9BCBD5"></a>

<h5>11.16-2 NambooripadPartialOrder</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NambooripadPartialOrder</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The Nambooripad partial order on a regular semigroup.

The Nambooripad partial order \(\leq\) on a regular semigroup <var class="Arg">S</var> is defined by <code class="code">s</code>\(\leq\)<code class="code">t</code> if the principal right ideal of <code class="code">S</code> generated by <code class="code">s</code> is contained in the principal right ideal of <code class="code">S</code> generated by <code class="code">t</code> and there is an idempotent <code class="code">e</code> in the \(\mathscr{R}\)-class of <code class="code">s</code> such that <code class="code">s</code>\(=\)<code class="code">et</code>. The Nambooripad partial order coincides with the natural partial order when considering inverse semigroups <code class="func">NaturalPartialOrder</code> (<a href="../../../doc/ref/chap54_mj.html#X7EA51F087CF7621F">Reference: NaturalPartialOrder</a>).

<code class="code">NambooripadPartialOrder</code> returns the Nambooripad partial order on the regular semigroup <var class="Arg">S</var> as a list of sets of positive integers where entry <code class="code">i</code> in <code class="code">NambooripadPartialOrder(<var class="Arg">S</var>)</code> is the set of positions in <code class="code">Elements(<var class="Arg">S</var>)</code> of elements which are less than <code class="code">Elements(<var class="Arg">S</var>)[i]</code>. See also <code class="func">NambooripadLeqRegularSemigroup</code> (<a href="chap11_mj.html#X7A7EB0DA8398886E">11.16-1</a>).

<div class="example"><pre>
gap> S := BrauerMonoid(3);
<regular bipartition *-monoid of degree 3 with 3 generators>
gap> IsRegularSemigroup(S);
true
gap> Size(S);
15
gap> NambooripadPartialOrder(S);
[ [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ],
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] ]
gap> NambooripadLeqRegularSemigroup(S)(Elements(S)[3], Elements(S)[9]);
false
gap> NambooripadLeqRegularSemigroup(S)(Elements(S)[2], Elements(S)[15]);
true</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap10_mj.html">[Previous Chapter]</a> <a href="chap12_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.66 Sekunden (vorverarbeitet am 2026-04-28) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.