SSL chap6.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/semigroups/doc/chap6.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Semigroups) - Chapter 6:
Semigroups and monoids defined by generating sets
</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="chap6" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap5.html">[Previous Chapter]</a> <a href="chap7.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap6_mj.html">[MathJax on]</a></p>
<p><a id="X7995B4F18672DDB0" name="X7995B4F18672DDB0"></a></p>
<div class="ChapSects"><a href="chap6.html#X7995B4F18672DDB0">6 <span class="Heading">
Semigroups and monoids defined by generating sets
</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7A19D22B7A05CC2F">6.1 <span class="Heading">Underlying algorithms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7A3AC74C7FF85825">6.1-1 <span class="Heading">
Acting semigroups
</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7F69D8FC7D578A0C">6.1-2 IsActingSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E2DE9767D5D82F7">6.1-3 <span class="Heading">The Froidure-Pin Algorithm</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7FEE8CFA87E7B872">6.1-4 CanUseFroidurePin</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X79BD00A682BDED7A">6.2 <span class="Heading">Semigroups represented by generators</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79A15C7C83BBA60B">6.2-1 InverseMonoidByGenerators</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X799EBA2F819D8867">6.3 <span class="Heading">Options when creating semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X78CF5DCC7C697BB3">6.3-1 SEMIGROUPS.DefaultOptionsRec</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X87AA2EB6810B4631">6.4 <span class="Heading">Subsemigroups and supersemigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7BE36790862AE26F">6.4-1 ClosureSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E5B4C5A82F9E0E0">6.4-2 SubsemigroupByProperty</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X832AEDCC7BA9E5F5">6.4-3 InverseSubsemigroupByProperty</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X82CCC1A781650878">6.5 <span class="Heading">Changing the representation of a semigroup</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X838F18E87F765697">6.5-1 IsomorphismSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X83D03BE678C9974F">6.5-2 IsomorphismMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80ED104F85AE5134">6.5-3 AsSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B22038F832B9C0F">6.5-4 AsMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80B7B1C783AA1567">6.5-5 IsomorphismPermGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X870210EA7912B52A">6.5-6 RZMSNormalization</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80DE617E841E5BA0">6.5-7 RMSNormalization</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E2ECC577A1CF7CA">6.5-8 IsomorphismReesMatrixSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X820BB66381737F2D">6.5-9 AntiIsomorphismDualFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7873016586653A44">6.5-10 EmbeddingFpMonoid</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7C3F130B8362D55A">6.6 <span class="Heading">Random semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X789DE9AB79FCFEB5">6.6-1 RandomSemigroup</a></span>
</div></div>
</div>
<h3>6 <span class="Heading">
Semigroups and monoids defined by generating sets
</span></h3>
<p>In this chapter we describe the various ways that semigroups and monoids defined by generating sets can be created in <strong class="pkg">Semigroups</strong>; where the generators are, for example, those elements described in earlier chapters of this manual.</p>
<p><a id="X7A19D22B7A05CC2F" name="X7A19D22B7A05CC2F"></a></p>
<h4>6.1 <span class="Heading">Underlying algorithms</span></h4>
<p>Computing the Green's structure of a semigroup or monoid is a fundamental step in almost every algorithm for semigroups. There are two fundamental algorithms in the Semigroups package for computing the Green's structure of a semigroup defined by a set of generators. In the next two subsections we briefly describe these two algorithms.</p>
<p><a id="X7A3AC74C7FF85825" name="X7A3AC74C7FF85825"></a></p>
<h5>6.1-1 <span class="Heading">
Acting semigroups
</span></h5>
<p>The first of the fundamental algorithms for computing a semigroup defined by a generating set is described in <a href="chapBib.html#biBMitchell2019aa">[EEMP19]</a>. When applied to a semigroup or monoid with relatively large subgroups, or <em>D</em>-classes, these are the most efficient methods in the <strong class="pkg">Semigroups</strong> package. For example, the complexity of computing, say, the size of a transformation semigroup that happens to be a group, is the same as the complexity of the Schreier-Sims Algorithm (polynomial in the number of points acted on by the transformations) for a permutation group.</p>
<p>In theory, these algorithms can be applied to compute any subsemigroup of a regular semigroup; but so far in the <strong class="pkg">Semigroups</strong> package they are only implemented for semigroups of: transformations (see <a href="../../../doc/ref/chap53_mj.html#X860026B880BCB2A5"><span class="RefLink">Reference: Transformations</span></a>), partial permutations (see <a href="../../../doc/ref/chap54_mj.html#X7D6495F77B8A77BD"><span class="RefLink">Reference: Partial permutations</span></a>), bipartitions (see Chapter <a href="chap3.html#X7C18DB427C9C0917"><span class="RefLink">3</span></a>), matrices over a finite field (see Section <a href="chap5.html#X873822B6830CE367"><span class="RefLink">5.4</span></a>); subsemigroups of regular Rees 0-matrix semigroups over permutation groups (see Chapter <a href="../../../doc/ref/chap51_mj.html#X8225A9EC87A255E6"><span class="RefLink">Reference: Rees Matrix Semigroups</span></a>), and subsemigroups of McAlister triples (see Section <a href="chap8.html#X7CC4F6FE87AFE638"><span class="RefLink">8.4</span></a>).</p>
<p>We refer to semigroups to which the algorithms in <a href="chapBib.html#biBMitchell2019aa">[EEMP19]</a> can be applied as <em>acting semigroups</em>, and such semigroups belong to the category <code class="func">IsActingSemigroup</code> (<a href="chap6.html#X7F69D8FC7D578A0C"><span class="RefLink">6.1-2</span></a>).</p>
<p>If you know <em>a priori</em> that the semigroup you want to compute is large and <em>J</em>-trivial, then you can disable the special methods for acting semigroups when you create the semigroups; see Section <a href="chap6.html#X799EBA2F819D8867"><span class="RefLink">6.3</span></a> for more details.</p>
<p>It is harder for the acting semigroup algorithms to compute Green's L- and H-classes of a transformation semigroup and the methods used to compute with Green's <em>R</em>- and <em>D</em>-classes are the most efficient in <strong class="pkg">Semigroups</strong>. Thus, if you are computing with a transformation semigroup, wherever possible, it is advisable to use the commands relating to Green's R- or D-classes rather than those relating to Green's <em>L</em>- or <em>H</em>-classes. No such difficulties are present when computing with the other types of acting semigroups in <strong class="pkg">Semigroups</strong>.</p>
<p>There are methods in <strong class="pkg">Semigroups</strong> for computing individual Green's classes of an acting semigroup without computing the entire data structure of the underlying semigroup; see GreensRClassOfElementNC (10.1-3). It is also possible to compute the R-classes, the number of elements and test membership in a semigroup without computing all the elements; see, for example, GreensRClasses (10.1-4), RClassReps (10.1-5), IteratorOfRClasses (10.2-2), or NrRClasses (10.1-9). This may be useful if you want to study a very large semigroup where computing all the elements of the semigroup is not feasible.
<p><a id="X7F69D8FC7D578A0C" name="X7F69D8FC7D578A0C"></a></p>
<h5>6.1-2 IsActingSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsActingSemigroup</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Every acting semigroup, as defined in Section <a href="chap6.html#X7A3AC74C7FF85825"><span class="RefLink">6.1-1</span></a>, belongs to this category.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 3, 2]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsActingSemigroup(S);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">CanUseFroidurePin(S);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FreeSemigroup(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsActingSemigroup(S);</span>
false</pre></div>
<p><a id="X7E2DE9767D5D82F7" name="X7E2DE9767D5D82F7"></a></p>
<h5>6.1-3 <span class="Heading">The Froidure-Pin Algorithm</span></h5>
<p>The second fundamental algorithm for computing finite semigroups is the Froidure-Pin Algorithm <a href="chapBib.html#biBFroidure1997aa">[FP97]</a>. The <strong class="pkg">Semigroups</strong> package contains two implementations of the Froidure-Pin Algorithm: one in the <span class="URL"><a href="https://libsemigroups.readthedocs.io/en/latest/">libsemigroups</a></span> C++ library and the other within the <strong class="pkg">Semigroups</strong> package kernel module.</p>
<p>Both implementations outperform the algorithms for acting semigroups when applied to semigroups with small (trivial) subgroups. This method is also used to determine the structure of a semigroup when the algorithms described in <a href="chapBib.html#biBMitchell2019aa">[EEMP19]</a> do not apply. It is possible to specify which methods should be applied to a given semigroup; see Section <a href="chap6.html#X799EBA2F819D8867"><span class="RefLink">6.3</span></a>.</p>
<p>A semigroup to which the Froidure-Pin Algorithm can be applied in <strong class="pkg">Semigroups</strong> satisfy <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>). Every acting semigroup in <strong class="pkg">Semigroups</strong> satisfies <code class="func">CanUseFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>) and the Froidure-Pin Algorithm is used to compute certain properties or attributes.</p>
<p>Currently, the <span class="URL"><a href="https://libsemigroups.readthedocs.io/en/latest/">libsemigroups</a></span> implementation of the Froidure-Pin Algorithm can be applied to semigroups consisting of the following types of elements: transformations (see <a href="../../../doc/ref/chap53_mj.html#X860026B880BCB2A5"><span class="RefLink">Reference: Transformations</span></a>), partial permutations (see <a href="../../../doc/ref/chap54_mj.html#X7D6495F77B8A77BD"><span class="RefLink">Reference: Partial permutations</span></a>), bipartitions (see Chapter <a href="chap3.html#X7C18DB427C9C0917"><span class="RefLink">3</span></a>), partitioned binary relations (see Chapter <a href="chap4.html#X85A717D1790B7BB5"><span class="RefLink">4</span></a>) as defined in <a href="chapBib.html#biBMartin2011aa">[MM13]</a>; and matrices over the following semirings:</p>
<ul>
<li><p>the <em>Boolean semiring</em> <span class="SimpleMath">{0, 1}</span> where <span class="SimpleMath">0 + 0 = 0</span>, <span class="SimpleMath">0 + 1 = 1 + 1 = 1 + 0 = 1</span>, and <span class="SimpleMath">1⋅ 0 = 0 ⋅ 0 = 0 ⋅ 1 = 0</span></p>
</li>
<li><p>finite fields;</p>
</li>
<li><p>the <em>max-plus semiring</em> of natural numbers and negative infinity <span class="SimpleMath">N∪ {-∞}</span> with operations max and plus;</p>
</li>
<li><p>the <em>min-plus semiring</em> of natural numbers and infinity <span class="SimpleMath">N∪ {∞}</span> with operations min and plus;</p>
</li>
<li><p>the <em>tropical max-plus semiring</em> <span class="SimpleMath">{-∞, 0, 1, ..., t}</span> for some threshold <span class="SimpleMath">t</span> with operations max and plus;</p>
</li>
<li><p>the <em>tropical min-plus semiring</em> <span class="SimpleMath">{0, 1, ..., t, ∞}</span> for some threshold <span class="SimpleMath">t</span> with operations min and plus;</p>
</li>
<li><p>the semiring <span class="SimpleMath">N_t, p = {0, 1, ..., t, t + 1, ..., t + p - 1}</span> for some threshold <span class="SimpleMath">t</span> and period <span class="SimpleMath">p</span> under addition and multiplication modulo the congruence <span class="SimpleMath">t = t + p</span>.</p>
</li>
</ul>
<p>(see Chapter <a href="chap5.html#X82D6B7FE7CAC0AFA"><span class="RefLink">5</span></a>).</p>
<p>The version of the Froidure-Pin Algorithm <a href="chapBib.html#biBFroidure1997aa">[FP97]</a> written in C within the <strong class="pkg">Semigroups</strong> package kernel module can be used to compute any other semigroup in <strong class="pkg">GAP</strong> which satisfies <code class="func">CanUseGapFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>). In theory, any finite semigroup can be computed using this algorithm. However, the condition that the semigroup has satisfies <code class="func">CanUseGapFroidurePin</code> (<a href="chap6.html#X7FEE8CFA87E7B872"><span class="RefLink">6.1-4</span></a>) is imposed to avoid this method being used when it is inappropriate. If implementing a new type of semigroup in <strong class="pkg">GAP</strong>, then simply do</p>
<div class="example"><pre>InstallTrueMethod(CanUseGapFroidurePin,
MyNewSemigroupType);</pre></div>
<p>to make your new semigroup type <code class="code">MyNewSemigroupType</code> use this version of the Froidure-Pin Algorithm. To make this work efficiently it is necessary that a hash function is implemented for the elements of <code class="code">MyNewSemigroupType</code>; more details will be included in a future edition of this manual.</p>
<p>Mostly due to the way that <strong class="pkg">GAP</strong> handles memory, this implementation is approximately 4 times slower than the implementation in <span class="URL"><a href="https://libsemigroups.readthedocs.io/en/latest/">libsemigroups</a></span> . This version of the Froidure-Pin Algorithm is included because it applies to a wider class of semigroups than those currently implemented in <span class="URL"><a href="https://libsemigroups.readthedocs.io/en/latest/">libsemigroups</a></span> and it is more straightforward to extend the classes of semigroup to which it applies.</p>
<p><a id="X7FEE8CFA87E7B872" name="X7FEE8CFA87E7B872"></a></p>
<h5>6.1-4 CanUseFroidurePin</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanUseFroidurePin</code>( <var class="Arg">obj</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">‣ CanUseGapFroidurePin</code>( <var class="Arg">obj</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">‣ CanUseLibsemigroupsFroidurePin</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Every semigroup satisfying <code class="code">CanUseFroidurePin</code> is a valid input for the Froidure-Pin algorithm; see Section <a href="chap6.html#X7E2DE9767D5D82F7"><span class="RefLink">6.1-3</span></a> for more details.</p>
<p>Basic operations for semigroups satisfying <code class="code">CanUseFroidurePin</code> are: <code class="func">AsListCanonical</code> (<a href="chap11.html#X7AC3FAA5826516AD"><span class="RefLink">11.1-1</span></a>), <code class="func">EnumeratorCanonical</code> (<a href="chap11.html#X7AC3FAA5826516AD"><span class="RefLink">11.1-1</span></a>), <code class="func">IteratorCanonical</code> (<a href="chap11.html#X7AC3FAA5826516AD"><span class="RefLink">11.1-1</span></a>), <code class="func">PositionCanonical</code> (<a href="chap11.html#X7B4B10AE81602D4E"><span class="RefLink">11.1-2</span></a>), <code class="func">Enumerate</code> (<a href="chap11.html#X7BCD5342793C7A7E"><span class="RefLink">11.1-3</span></a>), and <code class="func">IsEnumerated</code> (<a href="chap11.html#X877FAAA67F834897"><span class="RefLink">11.1-4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 3, 2]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CanUseFroidurePin(S);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FreeSemigroup(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CanUseFroidurePin(S);</span>
false
</pre></div>
<p><a id="X79BD00A682BDED7A" name="X79BD00A682BDED7A"></a></p>
<h4>6.2 <span class="Heading">Semigroups represented by generators</span></h4>
<p><a id="X79A15C7C83BBA60B" name="X79A15C7C83BBA60B"></a></p>
<h5>6.2-1 InverseMonoidByGenerators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InverseMonoidByGenerators</code>( <var class="Arg">coll</var>[, <var class="Arg">opts</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InverseSemigroupByGenerators</code>( <var class="Arg">coll</var>[, <var class="Arg">opts</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An inverse monoid or semigroup.</p>
<p>If <var class="Arg">coll</var> is a collection satisfying <code class="code">IsGeneratorsOfInverseSemigroup</code>, then <code class="code">InverseMonoidByGenerators</code> and <code class="code">InverseSemigroupByGenerators</code> return the inverse monoid and semigroup generated by <var class="Arg">coll</var>, respectively.</p>
<p>If present, the optional second argument <var class="Arg">opts</var> should be a record containing the values of the options for the semigroup being created, as described in Section <a href="chap6.html#X799EBA2F819D8867"><span class="RefLink">6.3</span></a>.</p>
<p><a id="X799EBA2F819D8867" name="X799EBA2F819D8867"></a></p>
<h4>6.3 <span class="Heading">Options when creating semigroups</span></h4>
<p>When using any of the functions:</p>
<ul>
<li><p><code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326"><span class="RefLink">Reference: InverseSemigroup</span></a>),</p>
</li>
<li><p><code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B"><span class="RefLink">Reference: InverseMonoid</span></a>),</p>
</li>
<li><p><code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817"><span class="RefLink">Reference: Semigroup</span></a>),</p>
</li>
<li><p><code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA"><span class="RefLink">Reference: Monoid</span></a>),</p>
</li>
<li><p><code class="func">SemigroupByGenerators</code> (<a href="../../../doc/ref/chap51_mj.html#X79FBBEC9841544F3"><span class="RefLink">Reference: SemigroupByGenerators</span></a>),</p>
</li>
<li><p><code class="func">MonoidByGenerators</code> (<a href="../../../doc/ref/chap51_mj.html#X85129EE387CC4D28"><span class="RefLink">Reference: MonoidByGenerators</span></a>),</p>
</li>
<li><p><code class="func">ClosureSemigroup</code> (<a href="chap6.html#X7BE36790862AE26F"><span class="RefLink">6.4-1</span></a>),</p>
</li>
<li><p><code class="func">ClosureMonoid</code> (<a href="chap6.html#X7BE36790862AE26F"><span class="RefLink">6.4-1</span></a>),</p>
</li>
<li><p><code class="func">ClosureInverseSemigroup</code> (<a href="chap6.html#X7BE36790862AE26F"><span class="RefLink">6.4-1</span></a>),</p>
</li>
<li><p><code class="func">ClosureInverseMonoid</code> (<a href="chap6.html#X7BE36790862AE26F"><span class="RefLink">6.4-1</span></a>),</p>
</li>
<li><p><code class="func">SemigroupIdeal</code> (<a href="chap9.html#X78E15B0184A1DC14"><span class="RefLink">9.1-1</span></a>)</p>
</li>
</ul>
<p>a record can be given as an optional final argument. The components of this record specify the values of certain options for the semigroup being created. A list of these options and their default values is given below.</p>
<p>Assume that <var class="Arg">S</var> is the semigroup created by one of the functions given above and that either: <var class="Arg">S</var> is generated by a collection <var class="Arg">gens</var>; or <var class="Arg">S</var> is an ideal of such a semigroup.</p>
<dl>
<dt><strong class="Mark"><code class="code">acting</code></strong></dt>
<dd><p>this component should be <code class="keyw">true</code> or <code class="keyw">false</code>. Roughly speaking, there are two types of methods in the <strong class="pkg">Semigroups</strong> package: those for semigroups which have to be fully enumerated, and those for semigroups that do not; see Section <a href="chap1.html#X7DFB63A97E67C0A1"><span class="RefLink">1.1</span></a>. In order for a semigroup to use the latter methods in <strong class="pkg">Semigroups</strong> it must satisfy <code class="func">IsActingSemigroup</code> (<a href="chap6.html#X7F69D8FC7D578A0C"><span class="RefLink">6.1-2</span></a>). By default any semigroup or monoid of transformations, partial permutations, Rees 0-matrix elements, or bipartitions satisfies <code class="code">IsActingSemigroup</code>.</p>
<p>There are cases (such as when it is known <em>a priori</em> that the semigroup is <em>D</em>-trivial), when it might be preferable to use the methods that involve fully enumerating a semigroup. In other words, it might be desirable to disable the more sophisticated methods for acting semigroups. If this is the case, then the value of this component can be set <code class="keyw">false</code> when the semigroup is created. Following this none of the special methods for acting semigroup will be used to compute anything about the semigroup.</p>
</dd>
<dt><strong class="Mark"><code class="code">regular</code></strong></dt>
<dd><p>this component should be <code class="keyw">true</code> or <code class="keyw">false</code>. If it is known <em>a priori</em> that the semigroup <code class="code">S</code> being created is a regular semigroup, then this component can be set to <code class="keyw">true</code>. In this case, <code class="code">S</code> knows it is a regular semigroup and can take advantage of the methods for regular semigroups in <strong class="pkg">Semigroups</strong>. It is usually much more efficient to compute with a regular semigroup that to compute with a non-regular semigroup.</p>
<p>If this option is set to <code class="keyw">true</code> when the semigroup being defined is <strong class="button">not</strong> regular, then the results might be unpredictable.</p>
<p>The default value for this option is <code class="keyw">false</code>.</p>
</dd>
<dt><strong class="Mark"><code class="code">hashlen</code></strong></dt>
<dd><p>this component should be a positive integer, which roughly specifies the lengths of the hash tables used internally by <strong class="pkg">Semigroups</strong>. <strong class="pkg">Semigroups</strong> uses hash tables in several fundamental methods. The lengths of these tables are a compromise between performance and memory usage; larger tables provide better performance for large computations but use more memory. Note that it is unlikely that you will need to specify this option unless you find that <strong class="pkg">GAP</strong> runs out of memory unexpectedly or that the performance of <strong class="pkg">Semigroups</strong> is poorer than expected. If you find that <strong class="pkg">GAP</strong> runs out of memory unexpectedly, or you plan to do a large number of computations with relatively small semigroups (say with tens of thousands of elements), then you might consider setting <code class="code">hashlen</code> to be less than the default value of <code class="code">12517</code> for each of these semigroups. If you find that the performance of <strong class="pkg">Semigroups</strong> is unexpectedly poor, or you plan to do a computation with a very large semigroup (say, more than 10 million elements), then you might consider setting <code class="code">hashlen</code> to be greater than the default value of <code class="code">12517</code>.</p>
<p>You might find it useful to set the info level of the info class <code class="code">InfoOrb</code> to 2 or higher since this will indicate when hash tables used by <strong class="pkg">Semigroups</strong> are being grown; see <code class="func">SetInfoLevel</code> (<a href="../../../doc/ref/chap7_mj.html#X7B2ADC37783104B9"><span class="RefLink">Reference: InfoLevel</span></a>).</p>
</dd>
<dt><strong class="Mark"><code class="code">small</code></strong></dt>
<dd><p>if this component is set to <code class="keyw">true</code>, then <strong class="pkg">Semigroups</strong> will compute a small subset of <var class="Arg">gens</var> that generates <var class="Arg">S</var> at the time that <var class="Arg">S</var> is created. This will increase the amount of time required to create <var class="Arg">S</var> substantially, but may decrease the amount of time required for subsequent calculations with <var class="Arg">S</var>. If this component is set to <code class="keyw">false</code>, then <strong class="pkg">Semigroups</strong> will return the semigroup generated by <var class="Arg">gens</var> without modifying <var class="Arg">gens</var>. The default value for this component is <code class="keyw">false</code>.</p>
<p>This option is ignored when passed to <code class="func">ClosureSemigroup</code> (<a href="chap6.html#X7BE36790862AE26F"><span class="RefLink">6.4-1</span></a>) or <code class="func">ClosureInverseSemigroup</code> (<a href="chap6.html#X7BE36790862AE26F"><span class="RefLink">6.4-1</span></a>).</p>
</dd>
<dt><strong class="Mark"><code class="code">cong_by_ker_trace_threshold</code></strong></dt>
<dd><p>this should be a positive integer, which specifies a semigroup size. If <var class="Arg">S</var> is a semigroup with inverse op, and <var class="Arg">S</var> has a size greater than or equal to this threshold, then any congruence defined on it may use the "kernel and trace" method to perform calculations. If its size is less than the threshold, then other methods will be used instead. The "kernel and trace" method has better complexity than the generic method, but has large overheads which make it a poor choice for small semigroups. The default value for this component is <code class="code">10 ^ 5</code>. See Section <a href="chap13.html#X7BFDC38178940AE6"><span class="RefLink">13.7</span></a> for more information about the "kernel and trace" method.</p>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 2, 3, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> rec(hashlen := 100003, small := false));</span>
<commutative transformation semigroup of degree 4 with 1 generator></pre></div>
<p>The default values of the options described above are stored in a global variable named <code class="func">SEMIGROUPS.DefaultOptionsRec</code> (<a href="chap6.html#X78CF5DCC7C697BB3"><span class="RefLink">6.3-1</span></a>). If you want to change the default values of these options for a single <strong class="pkg">GAP</strong> session, then you can simply redefine the value in <strong class="pkg">GAP</strong>. For example, to change the option <code class="code">small</code> from the default value of <var class="Arg">false</var> use:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SEMIGROUPS.DefaultOptionsRec.small := true;</span>
true</pre></div>
<p>If you want to change the default values of the options stored in <code class="func">SEMIGROUPS.DefaultOptionsRec</code> (<a href="chap6.html#X78CF5DCC7C697BB3"><span class="RefLink">6.3-1</span></a>) for all <strong class="pkg">GAP</strong> sessions, then you can edit these values in the file <code class="file">semigroups-5.5.4/gap/options.g</code>.</p>
<p><a id="X78CF5DCC7C697BB3" name="X78CF5DCC7C697BB3"></a></p>
<h5>6.3-1 SEMIGROUPS.DefaultOptionsRec</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SEMIGROUPS.DefaultOptionsRec</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This global variable is a record whose components contain the default values of certain options for semigroups. A description of these options is given above in Section <a href="chap6.html#X799EBA2F819D8867"><span class="RefLink">6.3</span></a>.</p>
<p>The value of <code class="code">SEMIGROUPS.DefaultOptionsRec</code> is defined in the file <code class="code">semigroups/gap/options.g</code>.</p>
<p><a id="X87AA2EB6810B4631" name="X87AA2EB6810B4631"></a></p>
<h4>6.4 <span class="Heading">Subsemigroups and supersemigroups</span></h4>
<p><a id="X7BE36790862AE26F" name="X7BE36790862AE26F"></a></p>
<h5>6.4-1 ClosureSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClosureSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">coll</var>[, <var class="Arg">opts</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClosureMonoid</code>( <var class="Arg">S</var>, <var class="Arg">coll</var>[, <var class="Arg">opts</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClosureInverseSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">coll</var>[, <var class="Arg">opts</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClosureInverseMonoid</code>( <var class="Arg">S</var>, <var class="Arg">coll</var>[, <var class="Arg">opts</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup, monoid, inverse semigroup, or inverse monoid.</p>
<p>These operations return the semigroup, monoid, inverse semigroup or inverse monoid generated by the argument <var class="Arg">S</var> and the collection of elements <var class="Arg">coll</var> after removing duplicates and elements from <var class="Arg">coll</var> that are already in <var class="Arg">S</var>. In most cases, the new semigroup knows at least as much information about its structure as was already known about that of <var class="Arg">S</var>.</p>
<p>When <code class="code">X</code> is any of <code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817"><span class="RefLink">Reference: Semigroup</span></a>), <code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA"><span class="RefLink">Reference: Monoid</span></a>), <code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326"><span class="RefLink">Reference: InverseSemigroup</span></a>), or <code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B"><span class="RefLink">Reference: InverseMonoid</span></a>), the argument <var class="Arg">S</var> of the operation <code class="code">ClosureX</code> must belong to the category <code class="code">IsX</code>, and <code class="code">ClosureX(<var class="Arg">S</var>, <var class="Arg">coll</var>)</code> returns an object in the category <code class="code">IsX</code> such that</p>
<div class="example"><pre>
ClosureX(S, coll) = X(S, coll);</pre></div>
<p>but may have fewer generators, if for example, <var class="Arg">coll</var> contains a duplicates or elements already known to belong to <var class="Arg">S</var>.</p>
<p>For example, the argument <var class="Arg">S</var> of <code class="code">ClosureInverseSemigroup</code> must be an inverse semigroup in the category <code class="func">IsInverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X83F1529479D56665"><span class="RefLink">Reference: IsInverseSemigroup</span></a>). <code class="code">ClosureInverseSemigroup(<var class="Arg">S</var>, <var class="Arg">coll</var>)</code> returns an inverse semigroup which is equal to <code class="code">InverseSemigroup(<var class="Arg">S</var>, <var class="Arg">coll</var>)</code>.</p>
<p>If present, the optional third argument <var class="Arg">opts</var> should be a record containing the values of the options for the semigroup being created as described in Section <a href="chap6.html#X799EBA2F819D8867"><span class="RefLink">6.3</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := [Transformation([2, 6, 7, 2, 6, 1, 1, 5]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([3, 8, 1, 4, 5, 6, 7, 1]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([4, 3, 2, 7, 7, 6, 6, 5]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([7, 1, 7, 4, 2, 5, 6, 3])];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid(gens[1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for x in gens do</span>
<span class="GAPprompt">></span> <span class="GAPinput"> S := ClosureSemigroup(S, x);</span>
<span class="GAPprompt">></span> <span class="GAPinput"> od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S;</span>
<transformation monoid of degree 8 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
233606
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid(PartialPerm([1]));</span>
<trivial partial perm group of rank 1 with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := ClosureMonoid(S, [PartialPerm([2 .. 5])]);</span>
<partial perm monoid of rank 5 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">One(T);</span>
<identity partial perm on [ 1, 2, 3, 4, 5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := ClosureSemigroup(S, [PartialPerm([2 .. 5])]);</span>
<partial perm semigroup of rank 4 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">One(T);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">ClosureInverseMonoid(DualSymmetricInverseMonoid(3),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> DClass(DualSymmetricInverseMonoid(3),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> IdentityBipartition(3)));</span>
<inverse block bijection monoid of degree 3 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseSemigroup(Bipartition([[1, -1, -3], [2, 3, -2]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Bipartition([[1, -3], [2, -2], [3, -1]]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := ClosureInverseSemigroup(S, DClass(PartitionMonoid(3),</span>
<span class="GAPprompt">></span> <span class="GAPinput">IdentityBipartition(3)));</span>
<inverse block bijection semigroup of degree 3 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := ClosureInverseSemigroup(T, [T.1, T.1, T.1]);</span>
<inverse block bijection semigroup of degree 3 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseMonoid([</span>
<span class="GAPprompt">></span> <span class="GAPinput">PartialPerm([5, 9, 10, 0, 6, 3, 8, 4, 0]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">PartialPerm([10, 7, 0, 8, 0, 0, 5, 9, 1])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([</span>
<span class="GAPprompt">></span> <span class="GAPinput">5, 1, 7, 3, 10, 0, 2, 12, 0, 14, 11, 0, 16, 0, 0, 0, 0, 6, 9, 15]);</span>
[4,3,7,2,1,5,10,14][8,12][13,16][18,6][19,9][20,15](11)
<span class="GAPprompt">gap></span> <span class="GAPinput">S := ClosureInverseSemigroup(S, x);</span>
<inverse partial perm semigroup of rank 19 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
9744
<span class="GAPprompt">gap></span> <span class="GAPinput">T := Idempotents(SymmetricInverseSemigroup(10));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := ClosureInverseSemigroup(S, T);</span>
<inverse partial perm semigroup of rank 19 with 14 generators></pre></div>
<p><a id="X7E5B4C5A82F9E0E0" name="X7E5B4C5A82F9E0E0"></a></p>
<h5>6.4-2 SubsemigroupByProperty</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubsemigroupByProperty</code>( <var class="Arg">S</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubsemigroupByProperty</code>( <var class="Arg">S</var>, <var class="Arg">func</var>, <var class="Arg">limit</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup.</p>
<p><code class="code">SubsemigroupByProperty</code> returns the subsemigroup of the semigroup <var class="Arg">S</var> generated by those elements of <var class="Arg">S</var> fulfilling <var class="Arg">func</var> (which should be a function returning <code class="keyw">true</code> or <code class="keyw">false</code>).</p>
<p>If no elements of <var class="Arg">S</var> fulfil <var class="Arg">func</var>, then <code class="keyw">fail</code> is returned.</p>
<p>If the optional third argument <var class="Arg">limit</var> is present and a positive integer, then once the subsemigroup has at least <var class="Arg">limit</var> elements the computation stops.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">func := function(x)</span>
<span class="GAPprompt">></span> <span class="GAPinput"> local n;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n := DegreeOfTransformation(x);</span>
<span class="GAPprompt">></span> <span class="GAPinput"> return 1 ^ x <> 1 and ForAll([1 .. n], y -> y = 1 or y ^ x = y);</span>
<span class="GAPprompt">></span> <span class="GAPinput"> end;</span>
function( x ) ... end
<span class="GAPprompt">gap></span> <span class="GAPinput">T := SubsemigroupByProperty(FullTransformationSemigroup(3), func);</span>
<transformation semigroup of size 2, degree 3 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := SubsemigroupByProperty(FullTransformationSemigroup(4), func);</span>
<transformation semigroup of size 3, degree 4 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := SubsemigroupByProperty(FullTransformationSemigroup(5), func);</span>
<transformation semigroup of size 4, degree 5 with 4 generators></pre></div>
<p><a id="X832AEDCC7BA9E5F5" name="X832AEDCC7BA9E5F5"></a></p>
<h5>6.4-3 InverseSubsemigroupByProperty</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InverseSubsemigroupByProperty</code>( <var class="Arg">S</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An inverse semigroup.</p>
<p><code class="code">InverseSubsemigroupByProperty</code> returns the inverse subsemigroup of the inverse semigroup <var class="Arg">S</var> generated by those elements of <var class="Arg">S</var> fulfilling <var class="Arg">func</var> (which should be a function returning <code class="keyw">true</code> or <code class="keyw">false</code>).</p>
<p>If no elements of <var class="Arg">S</var> fulfil <var class="Arg">func</var>, then <code class="keyw">fail</code> is returned.</p>
<p>If the optional third argument <var class="Arg">limit</var> is present and a positive integer, then once the subsemigroup has at least <var class="Arg">limit</var> elements the computation stops.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIsometry := function(f)</span>
<span class="GAPprompt">></span> <span class="GAPinput">local n, i, j, k, l;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> n := RankOfPartialPerm(f);</span>
<span class="GAPprompt">></span> <span class="GAPinput"> for i in [1 .. n - 1] do</span>
<span class="GAPprompt">></span> <span class="GAPinput"> k := DomainOfPartialPerm(f)[i];</span>
<span class="GAPprompt">></span> <span class="GAPinput"> for j in [i + 1 .. n] do</span>
<span class="GAPprompt">></span> <span class="GAPinput"> l := DomainOfPartialPerm(f)[j];</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if not AbsInt(k ^ f - l ^ f) = AbsInt(k - l) then</span>
<span class="GAPprompt">></span> <span class="GAPinput"> return false;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> fi;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> od;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> od;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> return true;</span>
<span class="GAPprompt">></span> <span class="GAPinput">end;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := InverseSubsemigroupByProperty(SymmetricInverseSemigroup(5),</span>
<span class="GAPprompt">></span> <span class="GAPinput">IsIsometry);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
142</pre></div>
<p><a id="X82CCC1A781650878" name="X82CCC1A781650878"></a></p>
<h4>6.5 <span class="Heading">Changing the representation of a semigroup</span></h4>
<p>The <strong class="pkg">Semigroups</strong> package provides two convenient constructors <code class="func">IsomorphismSemigroup</code> (<a href="chap6.html#X838F18E87F765697"><span class="RefLink">6.5-1</span></a>) and <code class="func">IsomorphismMonoid</code> (<a href="chap6.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>) for changing the representation of a given semigroup or monoid. These methods can be used to find an isomorphism from any semigroup to a semigroup of any other type, provided such an isomorphism exists.</p>
<p>Note that at present neither <code class="func">IsomorphismSemigroup</code> (<a href="chap6.html#X838F18E87F765697"><span class="RefLink">6.5-1</span></a>) nor <code class="func">IsomorphismMonoid</code> (<a href="chap6.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>) can be used to determine whether two given semigroups, or monoids, are isomorphic.</p>
<p>Some methods for <code class="func">IsomorphismSemigroup</code> (<a href="chap6.html#X838F18E87F765697"><span class="RefLink">6.5-1</span></a>) and <code class="func">IsomorphismMonoid</code> (<a href="chap6.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>) are based on methods for the <strong class="pkg">GAP</strong> library operations:</p>
<ul>
<li><p><code class="func">IsomorphismReesMatrixSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7964B5C97FB9C07D"><span class="RefLink">Reference: IsomorphismReesMatrixSemigroup</span></a>),</p>
</li>
<li><p><code class="func">AntiIsomorphismTransformationSemigroup</code> (<a href="../../../doc/ref/chap53_mj.html#X820ECE00846E480F"><span class="RefLink">Reference: AntiIsomorphismTransformationSemigroup</span></a>),</p>
</li>
<li><p><code class="func">IsomorphismTransformationSemigroup</code> (<a href="../../../doc/ref/chap53_mj.html#X78F29C817CF6827F"><span class="RefLink">Reference: IsomorphismTransformationSemigroup</span></a>) and <code class="func">IsomorphismTransformationMonoid</code> (<a href="../../../doc/ref/chap53_mj.html#X78F29C817CF6827F"><span class="RefLink">Reference: IsomorphismTransformationMonoid</span></a>),</p>
</li>
<li><p><code class="func">IsomorphismPartialPermSemigroup</code> (<a href="../../../doc/ref/chap54_mj.html#X7FE18EBE79B9C17C"><span class="RefLink">Reference: IsomorphismPartialPermSemigroup</span></a>) and <code class="func">IsomorphismPartialPermMonoid</code> (<a href="../../../doc/ref/chap54_mj.html#X7FE18EBE79B9C17C"><span class="RefLink">Reference: IsomorphismPartialPermMonoid</span></a>),</p>
</li>
<li><p><code class="func">IsomorphismFpSemigroup</code> (<a href="../../../doc/ref/chap52_mj.html#X869F966B8196F28C"><span class="RefLink">Reference: IsomorphismFpSemigroup</span></a>) and <code class="code">IsomorphismFpMonoid</code>.</p>
</li>
</ul>
<p>The operation <code class="func">IsomorphismMonoid</code> (<a href="chap6.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>) can be used to return an isomorphism from a semigroup which is mathematically a monoid (but does not below to the category of monoids in <strong class="pkg">GAP</strong> <code class="func">IsMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X861C523483C6248C"><span class="RefLink">Reference: IsMonoid</span></a>)) into a monoid. This is the primary purpose of the operation <code class="func">IsomorphismMonoid</code> (<a href="chap6.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>). Either <code class="func">IsomorphismSemigroup</code> (<a href="chap6.html#X838F18E87F765697"><span class="RefLink">6.5-1</span></a>) or <code class="func">IsomorphismMonoid</code> (<a href="chap6.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>) can be used to change the representation of a monoid, but only the latter is guaranteed to return an object in the category of monoids.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Monoid(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSemigroup(IsBooleanMatSemigroup, S);</span>
<monoid of 10x10 boolean matrices with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMonoid(IsBooleanMatMonoid, S);</span>
<monoid of 10x10 boolean matrices with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSemigroup(IsBooleanMatSemigroup, S);</ | |
