Anforderungen  |   Konzepte  |   Entwurf  |   Entwicklung  |   Qualitätssicherung  |   Lebenszyklus  |   Steuerung
 
 
 
 

products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 29.7.2025 mit Größe 79 kB image not shown  

Quelle  chap14_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap14_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 14: 
    Semigroup homomorphisms
  </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="chap14"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><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="chap13_mj.html">[Previous Chapter]</a>    <a href="chap15_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap14.html">[MathJax off]</a></p>
<p><a id="X861935DB81A478C2" name="X861935DB81A478C2"></a></p>
<div class="ChapSects"><a href="chap14_mj.html#X861935DB81A478C2">14 <span class="Heading">
    Semigroup homomorphisms
  </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X7F1FDA9C7C25799A">14.1 <span class="Heading">
      Homomorphisms of arbitrary semigroups
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X817596438369885B">14.1-1 SemigroupHomomorphismByImages</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7DAA6AD985C22AD6">14.1-2 SemigroupHomomorphismByFunctionNC</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7C76C6E5780D4A57">14.1-3 IsSemigroupHomomorphismByImages</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7F9CF9457E84BAE2">14.1-4 IsSemigroupHomomorphismByFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7CEBDC767CC184B6">14.1-5 AsSemigroupHomomorphismByImages</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7973F31986CF0DD4">14.1-6 AsSemigroupHomomorphismByFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X86BCE2207E55FC9F">14.1-7 KernelOfSemigroupHomomorphism</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X7A8945817BD44943">14.2 <span class="Heading">
      Isomorphisms of arbitrary semigroups
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7A6D59247F15935E">14.2-1 IsIsomorphicSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7DE212DF7DF0A4E9">14.2-2 SmallestMultiplicationTable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7FFEEFF484039A42">14.2-3 CanonicalMultiplicationTable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X869533A7819EC2F8">14.2-4 CanonicalMultiplicationTablePerm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X83BC6B998479BD27">14.2-5 OnMultiplicationTable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X8248C522825E2684">14.2-6 IsomorphismSemigroups</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X79BFF4E77A8090EF">14.2-7 AutomorphismGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X80FE565183A9410D">14.2-8 SemigroupIsomorphismByImages</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7B44408D8309C3DC">14.2-9 SemigroupIsomorphismByFunctionNC</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7EFDBD2C7A4FB6AF">14.2-10 IsSemigroupIsomorphismByFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X86C4FC857AF125BD">14.2-11 AsSemigroupIsomorphismByFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X794E5DA4872989E4">14.2-12 SmallerDegreeTransformationRepresentation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X867264587CFD0013">14.2-13 MinimalFaithfulTransformationDegree</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14_mj.html#X80DE3DB0782D9358">14.3 <span class="Heading">
      Isomorphisms of Rees (0-)matrix semigroups
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X82FCB1E585429FEA">14.3-1 IsRMSIsoByTriple</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X82B0BDCD7CBDCC2E">14.3-2 RMSIsoByTriple</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X81C4DE427D4A3D6C">14.3-3 ELM_LIST</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7A02528F8721F378">14.3-4 CompositionMapping2</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7F159C1179C93C11">14.3-5 ImagesElm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X8765885F784557B9">14.3-6 CanonicalReesZeroMatrixSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap14_mj.html#X7ED8BF227F4229E2">14.3-7 <span class="Heading">
        Operators for isomorphisms of Rees (0-)matrix semigroups
      </span></a>
</span>
</div></div>
</div>

<h3>14 <span class="Heading">
    Semigroup homomorphisms
  </span></h3>

<p>In this chapter we describe the various ways to define a homomorphism from a semigroup to another semigroup.</p>

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

<h4>14.1 <span class="Heading">
      Homomorphisms of arbitrary semigroups
    </span></h4>

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

<h5>14.1-1 SemigroupHomomorphismByImages</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupHomomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">gens</var>, <var class="Arg">imgs</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">‣ SemigroupHomomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">imgs</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">‣ SemigroupHomomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">T</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">‣ SemigroupHomomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">gens</var>, <var class="Arg">imgs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup homomorphism, or <code class="keyw">fail</code>.</p>

<p><code class="code">SemigroupHomomorphismByImages</code> attempts to construct a homomorphism from the semigroup <var class="Arg">S</var> to the semigroup <var class="Arg">T</var> by mapping the <code class="code">i</code>-th element of <var class="Arg">gens</var> to the <code class="code">i</code>-th element of <var class="Arg">imgs</var>. If this mapping corresponds to a homomorphism, the homomorphism is returned, and if not, then <code class="keyw">fail</code> is returned. Similarly, if <var class="Arg">gens</var> does not generate <var class="Arg">S</var>, <code class="keyw">fail</code> is returned.</p>

<p>If omitted, the arguments <var class="Arg">gens</var> and <var class="Arg">imgs</var> default to the generators of <var class="Arg">S</var> and <var class="Arg">T</var> respectively. See <code class="func">GeneratorsOfSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78147A247963F23B"><span class="RefLink">Reference: GeneratorsOfSemigroup</span></a>).</p>

<p>If <var class="Arg">T</var> is not given, then it defaults to the semigroup generated by <var class="Arg">imgs</var>, resulting in the mapping being surjective.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTransformationMonoid(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">J := FullTransformationMonoid(4);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">imgs := ListWithIdenticalEntries(4,</span>
<span class="GAPprompt">></span> <span class="GAPinput">ConstantTransformation(3, 1));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByImages(S, J, gens, imgs);</span>
<full transformation monoid of degree 3> ->
<full transformation monoid of degree 4></pre></div>

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

<h5>14.1-2 SemigroupHomomorphismByFunctionNC</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupHomomorphismByFunctionNC</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">fun</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">‣ SemigroupHomomorphismByFunction</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">fun</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup homomorphism or <code class="keyw">fail</code>.</p>

<p><code class="code">SemigroupHomomorphismByFunctionNC</code> returns a semigroup homomorphism with source <var class="Arg">S</var> and range <var class="Arg">T</var>, such that each element <code class="code">s</code> in <var class="Arg">S</var> is mapped to the element <var class="Arg">fun</var><code class="code">(s)</code>, where <var class="Arg">fun</var> is a <strong class="pkg">GAP</strong> function.</p>

<p>The function <code class="code">SemigroupHomomorphismByFunctionNC</code> performs no checks on whether the function actually gives a homomorphism, and so it is possible for this operation to return a mapping from <var class="Arg">S</var> to <var class="Arg">T</var> that is not a homomorphism.</p>

<p>The function <code class="code">SemigroupHomomorphismByFunction</code> checks that the mapping from <var class="Arg">S</var> to <var class="Arg">T</var> defined by <var class="Arg">fun</var> satisfies <code class="func">RespectsMultiplication</code> (<a href="../../../doc/ref/chap32_mj.html#X7BEFF95883EAEC78"><span class="RefLink">Reference: RespectsMultiplication</span></a>), which can be expensive. If <code class="func">RespectsMultiplication</code> (<a href="../../../doc/ref/chap32_mj.html#X7BEFF95883EAEC78"><span class="RefLink">Reference: RespectsMultiplication</span></a>) does not hold, then <code class="keyw">fail</code> is returned.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Semigroup([(1, 2, 3, 4), (1, 2)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">h := Semigroup([(1, 2, 3), (1, 2)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByFunction(g, h,</span>
<span class="GAPprompt">></span> <span class="GAPinput">function(x)</span>
<span class="GAPprompt">></span> <span class="GAPinput">if SignPerm(x) = -1 then return (1, 2);</span>
<span class="GAPprompt">></span> <span class="GAPinput">else return ();</span>
<span class="GAPprompt">></span> <span class="GAPinput">fi; end);</span>
<semigroup of size 24, with 2 generators> ->
<semigroup of size 6, with 2 generators></pre></div>

<p>The following methods relate to semigroup homomorphisms by images or by function:</p>


<ul>
<li><p><code class="func">Range</code> (<a href="../../../doc/ref/chap21_mj.html#X79596BDE7CAF8491"><span class="RefLink">Reference: range</span></a>),</p>

</li>
<li><p><code class="func">Image</code> (<a href="../../../doc/ref/chap32_mj.html#X87F4D35A826599C6"><span class="RefLink">Reference: Image</span></a>),</p>

</li>
<li><p><code class="func">Images</code> (<a href="../../../doc/ref/chap32_mj.html#X86114B2E7E77488C"><span class="RefLink">Reference: Images</span></a>),</p>

</li>
<li><p><code class="func">ImageElm</code> (<a href="../../../doc/ref/chap32_mj.html#X7CFAB0157BFB1806"><span class="RefLink">Reference: ImageElm</span></a>),</p>

</li>
<li><p><code class="func">PreImage</code> (<a href="../../../doc/ref/chap32_mj.html#X836FAEAC78B55BF4"><span class="RefLink">Reference: PreImage</span></a>),</p>

</li>
<li><p><code class="func">PreImages</code> (<a href="../../../doc/ref/chap32_mj.html#X85C8590E832002EF"><span class="RefLink">Reference: PreImages</span></a>),</p>

</li>
<li><p><code class="func">PreImagesRepresentative</code> (<a href="../../../doc/ref/chap32_mj.html#X7AE24A1586B7DE79"><span class="RefLink">Reference: PreImagesRepresentative</span></a>),</p>

</li>
<li><p><code class="func">PreImagesRange</code> (<a href="../../../doc/ref/chap32_mj.html#X78EF1FE77B0973C0"><span class="RefLink">Reference: PreImagesRange</span></a>),</p>

</li>
<li><p><code class="func">PreImagesElm</code> (<a href="../../../doc/ref/chap32_mj.html#X7FBB830C8729E995"><span class="RefLink">Reference: PreImagesElm</span></a>),</p>

</li>
<li><p><code class="func">PreImagesSet</code> (<a href="../../../doc/ref/chap32_mj.html#X856BAFC87B2D2811"><span class="RefLink">Reference: PreImagesSet</span></a>),</p>

</li>
<li><p><code class="func">IsSurjective</code> (<a href="../../../doc/ref/chap32_mj.html#X784ECE847E005B8F"><span class="RefLink">Reference: IsSurjective</span></a>),</p>

</li>
<li><p><code class="func">IsInjective</code> (<a href="../../../doc/ref/chap32_mj.html#X7F065FD7822C0A12"><span class="RefLink">Reference: IsInjective</span></a>),</p>

</li>
<li><p><code class="func">IsBijective</code> (<a href="../../../doc/ref/chap32_mj.html#X878F56AB7B342767"><span class="RefLink">Reference: IsBijective</span></a>),</p>

</li>
<li><p><code class="func">Source</code> (<a href="../../../doc/ref/chap32_mj.html#X7DE8173F80E07AB1"><span class="RefLink">Reference: Source</span></a>),</p>

</li>
<li><p><code class="func">Range</code> (<a href="../../../doc/ref/chap21_mj.html#X79596BDE7CAF8491"><span class="RefLink">Reference: range</span></a>),</p>

</li>
<li><p><code class="func">ImagesSource</code> (<a href="../../../doc/ref/chap32_mj.html#X7D23C1CE863DACD8"><span class="RefLink">Reference: ImagesSource</span></a>),</p>

</li>
<li><p><code class="func">KernelOfSemigroupHomomorphism</code> (<a href="chap14_mj.html#X86BCE2207E55FC9F"><span class="RefLink">14.1-7</span></a>).</p>

</li>
</ul>
<p><a id="X7C76C6E5780D4A57" name="X7C76C6E5780D4A57"></a></p>

<h5>14.1-3 IsSemigroupHomomorphismByImages</h5>

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

<p><code class="code">IsSemigroupHomomorphismByImages</code> returns <code class="keyw">true</code> if <var class="Arg">hom</var> is a semigroup homomorphism by images and <code class="keyw">false</code> if it is not. A semigroup homomorphism is a mapping from a semigroup <code class="code">S</code> to a semigroup <code class="code">T</code> that respects multiplication. This representation describes semigroup homomorphisms internally by the generators of <code class="code">S</code> and their images in <code class="code">T</code>. See <code class="func">SemigroupHomomorphismByImages</code> (<a href="chap14_mj.html#X817596438369885B"><span class="RefLink">14.1-1</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTransformationMonoid(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := FullTransformationMonoid(4);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">imgs := ListWithIdenticalEntries(4, ConstantTransformation(3, 1));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByImages(S, T, gens, imgs);</span>
<full transformation monoid of degree 3> ->
<full transformation monoid of degree 4>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSemigroupHomomorphismByImages(hom);</span>
true</pre></div>

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

<h5>14.1-4 IsSemigroupHomomorphismByFunction</h5>

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

<p><code class="code">IsSemigroupHomomorphismByFunction</code> returns <code class="keyw">true</code> if <var class="Arg">hom</var> was created using <code class="func">SemigroupHomomorphismByFunction</code> (<a href="chap14_mj.html#X7DAA6AD985C22AD6"><span class="RefLink">14.1-2</span></a>) and <code class="keyw">false</code> if it was not. Note that this filter may return <code class="keyw">true</code> even if the underlying <strong class="pkg">GAP</strong> function does not define a homomorphism. A semigroup homomorphism is a mapping from a semigroup <code class="code">S</code> to a semigroup <code class="code">T</code> that respects multiplication. This representation describes semigroup homomorphisms internally using a <strong class="pkg">GAP</strong> function mapping elements of <code class="code">S</code> to their images in <code class="code">T</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([(1, 2, 3, 4), (1, 2)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := Semigroup([(1, 2, 3), (1, 2)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByFunction(S, T,</span>
<span class="GAPprompt">></span> <span class="GAPinput">function(x) if SignPerm(x) = -1 then return (1, 2);</span>
<span class="GAPprompt">></span> <span class="GAPinput">else return ();fi; end);</span>
<semigroup of size 24, with 2 generators> ->
<semigroup of size 6, with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSemigroupHomomorphismByFunction(hom);</span>
true</pre></div>

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

<h5>14.1-5 AsSemigroupHomomorphismByImages</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSemigroupHomomorphismByImages</code>( <var class="Arg">hom</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup homomorphism, or <code class="keyw">fail</code>.</p>

<p><code class="code">AsSemigroupHomomorphismByImages</code> takes <var class="Arg">hom</var>, a semigroup homomorphism, and returns the same mapping but represented internally using the generators of <code class="code">Source(<var class="Arg">hom</var>)</code> and their images in <code class="code">Range(<var class="Arg">hom</var>)</code>. If <var class="Arg">hom</var> not a semigroup homomorphism, then <code class="keyw">fail</code> is returned. For example, this could happen if <var class="Arg">hom</var> was created using <code class="func">SemigroupIsomorphismByFunction</code> (<a href="chap14_mj.html#X7B44408D8309C3DC"><span class="RefLink">14.2-9</span></a>) and a function which does not give a homomorphism.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([(1, 2, 3, 4), (1, 2)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := Semigroup([(1, 2, 3), (1, 2)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByFunction(S, T,</span>
<span class="GAPprompt">></span> <span class="GAPinput">function(x) if SignPerm(x) = -1 then return (1, 2);</span>
<span class="GAPprompt">></span> <span class="GAPinput">else return (); fi; end);</span>
<semigroup of size 24, with 2 generators> ->
<semigroup of size 6, with 2 generators>
</pre></div>

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

<h5>14.1-6 AsSemigroupHomomorphismByFunction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSemigroupHomomorphismByFunction</code>( <var class="Arg">hom</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup homomorphism.</p>

<p><code class="code">AsSemigroupHomomorphismByFunction</code> takes <var class="Arg">hom</var>, a semigroup homomorphism, and returns the same mapping but described by a <strong class="pkg">GAP</strong> function mapping elements of <code class="code">Source(<var class="Arg">hom</var>)</code> to their images in <code class="code">Range(<var class="Arg">hom</var>)</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := TrivialSemigroup();;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := GLM(2, 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">imgs := ListX(gens, x -> IdentityTransformation);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByImages(S, T, gens, imgs);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := AsSemigroupHomomorphismByFunction(hom);</span>
<general linear monoid 2x2 over GF(2)> ->
<trivial transformation group of degree 0 with 1 generator></pre></div>

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

<h5>14.1-7 KernelOfSemigroupHomomorphism</h5>

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

<p><code class="code">KernelOfSemigroupHomomorphism</code> returns the kernel of the semigroup homomorphism <var class="Arg">hom</var>. The kernel of a semigroup homomorphism <var class="Arg">hom</var> is a semigroup congruence relating pairs of elements in <code class="code">Source(<var class="Arg">hom</var>)</code> mapping to the same element under <var class="Arg">hom</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([Transformation([2, 1, 5, 1, 5]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">      Transformation([1, 1, 1, 5, 3]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">      Transformation([2, 5, 3, 5, 3])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">congs := CongruencesOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong := congs[3];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := S / cong;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">images := List(gens, gen -> EquivalenceClassOfElement(cong, gen));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom1 := SemigroupHomomorphismByImages(S, T, gens, images);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">cong = KernelOfSemigroupHomomorphism(hom1);</span>
true</pre></div>

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

<h4>14.2 <span class="Heading">
      Isomorphisms of arbitrary semigroups
    </span></h4>

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

<h5>14.2-1 IsIsomorphicSemigroup</h5>

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

<p>If <var class="Arg">S</var> and <var class="Arg">T</var> are semigroups, then this operation attempts to determine whether <var class="Arg">S</var> and <var class="Arg">T</var> are isomorphic semigroups by using the operation <code class="func">IsomorphismSemigroups</code> (<a href="chap14_mj.html#X8248C522825E2684"><span class="RefLink">14.2-6</span></a>). If <code class="code">IsomorphismSemigroups(<var class="Arg">S</var>, <var class="Arg">T</var>)</code> returns an isomorphism, then <code class="code">IsIsomorphicSemigroup(<var class="Arg">S</var>, <var class="Arg">T</var>)</code> returns <code class="keyw">true</code>, while if <code class="code">IsomorphismSemigroups(<var class="Arg">S</var>, <var class="Arg">T</var>)</code> returns <code class="keyw">fail</code>, then <code class="code">IsIsomorphicSemigroup(<var class="Arg">S</var>, <var class="Arg">T</var>)</code> returns <code class="keyw">false</code>.</p>

<p>Note that in some cases, at present, there is no method for determining whether <var class="Arg">S</var> is isomorphic to <var class="Arg">T</var>, even if it is obvious to the user whether or not <var class="Arg">S</var> and <var class="Arg">T</var> are isomorphic. There are plans to improve this in the future.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(PartialPerm([1, 2, 4], [1, 3, 5]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                  PartialPerm([1, 3, 5], [1, 2, 4]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := AsSemigroup(IsTransformationSemigroup, S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIsomorphicSemigroup(S, T);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIsomorphicSemigroup(FullTransformationMonoid(4),</span>
<span class="GAPprompt">></span> <span class="GAPinput">PartitionMonoid(4));</span>
false</pre></div>

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

<h5>14.2-2 SmallestMultiplicationTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestMultiplicationTable</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: The lex-least multiplication table of a semigroup.</p>

<p>This function returns the lex-least multiplication table of a semigroup isomorphic to the semigroup <var class="Arg">S</var>. <code class="code">SmallestMultiplicationTable</code> returns the lex-least multiplication of any semigroup isomorphic to <var class="Arg">S</var>. Due to the high complexity of computing the smallest multiplication table of a semigroup, this function only performs well for semigroups with at most approximately 50 elements.</p>

<p><code class="code">SmallestMultiplicationTable</code> is based on the function <code class="func">IdSmallSemigroup</code> (<a href="https://gap-packages.github.io/smallsemi/doc/chap4_mj.html#X788211A07D67C282"><span class="RefLink">Smallsemi: IdSmallSemigroup</span></a>) by Andreas Distler.</p>

<p>From Version 3.3.0 of <strong class="pkg">Semigroups</strong> this attribute is computed using <code class="func">MinimalImage</code> (<a href="https://gap-packages.github.io/images/doc/chap2_mj.html#X7E9EFA0E7A997586"><span class="RefLink">images: MinimalImage</span></a>) from the the <span class="URL"><a href="https://gap-packages.github.io/images/">images</a></span> package. See also: <code class="func">CanonicalMultiplicationTable</code> (<a href="chap14_mj.html#X7FFEEFF484039A42"><span class="RefLink">14.2-3</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3, -1, -3], [-2]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3, -1], [-2], [-3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3], [-1], [-2, -3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, -1], [3, -2], [-3]]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestMultiplicationTable(S);</span>
[ [ 1, 1, 3, 4, 5, 6, 7, 8 ], [ 1, 1, 3, 4, 5, 6, 7, 8 ],
  [ 1, 1, 3, 4, 5, 6, 7, 8 ], [ 1, 3, 3, 4, 5, 6, 7, 8 ],
  [ 5, 5, 6, 7, 5, 6, 7, 8 ], [ 5, 5, 6, 7, 5, 6, 7, 8 ],
  [ 5, 6, 6, 7, 5, 6, 7, 8 ], [ 5, 6, 6, 7, 5, 6, 7, 8 ] ]</pre></div>

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

<h5>14.2-3 CanonicalMultiplicationTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalMultiplicationTable</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A canonical multiplication table (up to isomorphism) of a semigroup.</p>

<p>This function returns a multiplication table of a semigroup isomorphic to the semigroup <var class="Arg">S</var>. <code class="code">CanonicalMultiplicationTable</code> returns a multiplication that is canonical, in the sense that if two semigroups <code class="code">S</code> and <code class="code">T</code> are isomorphic, then the return values of <code class="code">CanonicalMultiplicationTable</code> are equal.</p>

<p><code class="code">CanonicalMultiplicationTable</code> uses the machinery for canonical labelling of vertex coloured digraphs in <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> via <code class="func">BlissCanonicalLabelling</code> (<a href="https://gap-packages.github.io/io/doc/chap7_mj.html#X87DA265D803DB337"><span class="RefLink">Digraphs: BlissCanonicalLabelling for a digraph and a list</span></a>).</p>

<p>The multiplication table returned by this function is the result of <code class="code">OnMultiplicationTable(MultiplicationTable(<var class="Arg">S</var>), CanonicalMultiplicationTablePerm(<var class="Arg">S</var>));</code></p>

<p>Note that the performance of <code class="code">CanonicalMultiplicationTable</code> is vastly superior to that of <code class="code">SmallestMultiplicationTable</code>.</p>

<p>See also: <code class="func">CanonicalMultiplicationTablePerm</code> (<a href="chap14_mj.html#X869533A7819EC2F8"><span class="RefLink">14.2-4</span></a>) and <code class="func">OnMultiplicationTable</code> (<a href="chap14_mj.html#X83BC6B998479BD27"><span class="RefLink">14.2-5</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3, -1, -3], [-2]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3, -1], [-2], [-3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3], [-1], [-2, -3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, -1], [3, -2], [-3]]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalMultiplicationTable(S);</span>
[ [ 1, 2, 2, 8, 1, 2, 7, 8 ], [ 1, 2, 2, 8, 1, 2, 7, 8 ],
  [ 1, 2, 6, 4, 5, 6, 7, 8 ], [ 1, 2, 5, 4, 5, 6, 7, 8 ],
  [ 1, 2, 6, 4, 5, 6, 7, 8 ], [ 1, 2, 6, 4, 5, 6, 7, 8 ],
  [ 1, 2, 1, 8, 1, 2, 7, 8 ], [ 1, 2, 1, 8, 1, 2, 7, 8 ] ]</pre></div>

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

<h5>14.2-4 CanonicalMultiplicationTablePerm</h5>

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

<p>This function returns a permutation <code class="code">p</code> such that <code class="code">OnMultiplicationTable(MultiplicationTable(<var class="Arg">S</var>), p);</code> equals <code class="code">CanonicalMultiplicationTable(<var class="Arg">S</var>)</code>.</p>

<p>See <code class="func">CanonicalMultiplicationTable</code> (<a href="chap14_mj.html#X7FFEEFF484039A42"><span class="RefLink">14.2-3</span></a>) for more details.</p>

<p><code class="code">CanonicalMultiplicationTablePerm</code> uses the machinery for canonical labelling of vertex coloured digraphs in <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> via <code class="func">BlissCanonicalLabelling</code> (<a href="https://gap-packages.github.io/io/doc/chap7_mj.html#X87DA265D803DB337"><span class="RefLink">Digraphs: BlissCanonicalLabelling for a digraph and a list</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3, -1, -3], [-2]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3, -1], [-2], [-3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, 3], [-1], [-2, -3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1, 2, -1], [3, -2], [-3]]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalMultiplicationTablePerm(S);</span>
(1,5,8,3,6,7,2,4)</pre></div>

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

<h5>14.2-5 OnMultiplicationTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnMultiplicationTable</code>( <var class="Arg">table</var>, <var class="Arg">p</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A multiplication table.</p>

<p>If <var class="Arg">table</var> is a multiplication table of a semigroup and the second argument <var class="Arg">p</var> is a permutation of <code class="code">[1 .. Length(<var class="Arg">table</var>)]</code>, then this operation returns a multiplication table of a semigroup isomorphic to that defined by <var class="Arg">table</var> where the elements <code class="code">[1 .. Length(<var class="Arg">table</var>)]</code> are relabelled according to <var class="Arg">p</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">table := [[1, 1, 3, 4, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [1, 1, 3, 4, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [1, 1, 3, 4, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [1, 3, 3, 4, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [5, 5, 6, 7, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [5, 5, 6, 7, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [5, 6, 6, 7, 5, 6, 7, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [5, 6, 6, 7, 5, 6, 7, 8]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p := (1, 2, 3, 4)(10, 11, 12);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">OnMultiplicationTable(table, p);</span>
[ [ 1, 2, 4, 4, 5, 6, 7, 8 ], [ 1, 2, 2, 4, 5, 6, 7, 8 ],
  [ 1, 2, 2, 4, 5, 6, 7, 8 ], [ 1, 2, 2, 4, 5, 6, 7, 8 ],
  [ 7, 5, 5, 6, 5, 6, 7, 8 ], [ 7, 5, 5, 6, 5, 6, 7, 8 ],
  [ 7, 5, 6, 6, 5, 6, 7, 8 ], [ 7, 5, 6, 6, 5, 6, 7, 8 ] ]</pre></div>

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

<h5>14.2-6 IsomorphismSemigroups</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismSemigroups</code>( <var class="Arg">S</var>, <var class="Arg">T</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An isomorphism, or <code class="keyw">fail</code>.</p>

<p>This operation attempts to find an isomorphism from the semigroup <var class="Arg">S</var> to the semigroup <var class="Arg">T</var>. If it finds one, then it is returned, and if not, then <code class="keyw">fail</code> is returned.</p>

<p><code class="code">IsomorphismSemigroups</code> uses the machinery for finding isomorphisms between vertex coloured digraphs in <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> via <code class="func">IsomorphismDigraphs</code> (<a href="https://gap-packages.github.io/io/doc/chap7_mj.html#X7ED93C0F86D9D34F"><span class="RefLink">Digraphs: IsomorphismDigraphs for digraphs and homogeneous lists</span></a>) using digraphs constructed from the multiplication tables of <var class="Arg">S</var> and <var class="Arg">T</var>.</p>

<p>Note that finding an isomorphism between two semigroups is difficult, and may not be possible for semigroups whose size exceeds a few hundred elements. On the other hand, <code class="code">IsomorphismSemigroups</code> may be able deduce that <var class="Arg">S</var> and <var class="Arg">T</var> are not isomorphic by finding that some of their semigroup-theoretic properties differ.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := RectangularBand(IsTransformationSemigroup, 4, 5);</span>
<regular transformation semigroup of size 20, degree 9 with 5
 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := RectangularBand(IsBipartitionSemigroup, 4, 5);</span>
<regular bipartition semigroup of size 20, degree 3 with 5 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismSemigroups(S, T) <> fail;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">D := DClass(FullTransformationMonoid(5),</span>
<span class="GAPprompt">></span> <span class="GAPinput">               Transformation([1, 2, 3, 4, 1]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := PrincipalFactor(D);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(UnderlyingSemigroup(S));</span>
"S4"
<span class="GAPprompt">gap></span> <span class="GAPinput">S;</span>
<Rees 0-matrix semigroup 10x5 over S4>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := DClass(PartitionMonoid(5),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Bipartition([[1], [2, -2], [3, -3], [4, -4], [5, -5], [-1]]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := PrincipalFactor(D);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(UnderlyingSemigroup(T));</span>
"S4"
<span class="GAPprompt">gap></span> <span class="GAPinput">T;</span>
<Rees 0-matrix semigroup 15x15 over S4>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismSemigroups(S, T);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">I := SemigroupIdeal(FullTransformationMonoid(5),</span>
<span class="GAPprompt">></span> <span class="GAPinput">                       Transformation([1, 1, 2, 3, 4]));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := PrincipalFactor(DClass(I, I.1));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(UnderlyingSemigroup(T));</span>
"S4"
<span class="GAPprompt">gap></span> <span class="GAPinput">T;</span>
<Rees 0-matrix semigroup 10x5 over S4>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismSemigroups(S, T) <> fail;</span>
true</pre></div>

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

<h5>14.2-7 AutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomorphismGroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A group.</p>

<p>This operation returns the group of automorphisms of the semigroup <var class="Arg">S</var>. <code class="code">AutomorphismGroup</code> uses <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> via <code class="func">AutomorphismGroup</code> (<a href="https://gap-packages.github.io/io/doc/chap7_mj.html#X877732B1783C391B"><span class="RefLink">Digraphs: AutomorphismGroup for a digraph and a homogeneous list</span></a>) using a vertex coloured digraph constructed from the multiplication table of <var class="Arg">S</var>. Consequently, this method is only really feasible for semigroups whose size does not exceed a few hundred elements.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := RectangularBand(IsTransformationSemigroup, 4, 5);</span>
<regular transformation semigroup of size 20, degree 9 with 5
 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(AutomorphismGroup(S));</span>
"S4 x S5"</pre></div>

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

<h5>14.2-8 SemigroupIsomorphismByImages</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupIsomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">gens</var>, <var class="Arg">imgs</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">‣ SemigroupIsomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">imgs</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">‣ SemigroupIsomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">T</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">‣ SemigroupIsomorphismByImages</code>( <var class="Arg">S</var>, <var class="Arg">gens</var>, <var class="Arg">imgs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup isomorphism, or <code class="keyw">fail</code>.</p>

<p><code class="code">SemigroupIsomorphismByImages</code> attempts to construct a isomorphism from the semigroup <var class="Arg">S</var> to the semigroup <var class="Arg">T</var>, by mapping the <code class="code">i</code>-th element of <var class="Arg">gens</var> to the <code class="code">i</code>-th element of <var class="Arg">imgs</var>. If this mapping corresponds to an isomorphism, the isomorphism is returned, and if not, then <code class="keyw">fail</code> is returned. An isomorphism is a bijective homomorphism. See also <code class="func">SemigroupHomomorphismByImages</code> (<a href="chap14_mj.html#X817596438369885B"><span class="RefLink">14.1-1</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Matrix(IsNTPMatrix, [[0, 1, 2], [4, 3, 0], [0, 2, 0]], 9, 4),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Matrix(IsNTPMatrix, [[1, 1, 0], [4, 1, 1], [0, 0, 0]], 9, 4)]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := AsSemigroup(IsTransformationSemigroup, S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso := SemigroupIsomorphismByImages(S, T);</span>
<semigroup of size 46, 3x3 ntp matrices with 2 generators> ->
<transformation semigroup of size 46, degree 47 with 2 generators>
</pre></div>

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

<h5>14.2-9 SemigroupIsomorphismByFunctionNC</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupIsomorphismByFunctionNC</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">fun</var>, <var class="Arg">invFun</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">‣ SemigroupIsomorphismByFunction</code>( <var class="Arg">S</var>, <var class="Arg">T</var>, <var class="Arg">fun</var>, <var class="Arg">invFun</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup isomorphism or <code class="keyw">fail</code>.</p>

<p><code class="code">SemigroupIsomorphismByFunctionNC</code> returns a semigroup isomorphism with source <var class="Arg">S</var> and range <var class="Arg">T</var>, such that each element <code class="code">s</code> in <var class="Arg">S</var> is mapped to the element <var class="Arg">fun</var><code class="code">(s)</code>, where <var class="Arg">fun</var> is a <strong class="pkg">GAP</strong> function, and <var class="Arg">invFun</var> its inverse, mapping <var class="Arg">fun</var><code class="code">(s)</code> back to <code class="code">s</code>.</p>

<p>The function <code class="code">SemigroupIsomorphismByFunctionNC</code> performs no checks on whether the function actually gives an isomorphism, and so it is possible for this operation to return a mapping from <var class="Arg">S</var> to <var class="Arg">T</var> that is not a homomorphism, or not a bijection, or where the return value of <code class="func">InverseGeneralMapping</code> (<a href="../../../doc/ref/chap32_mj.html#X865FC25A87D36F3D"><span class="RefLink">Reference: InverseGeneralMapping</span></a>) is not the inverse of the returned function.</p>

<p>The function <code class="code">SemigroupIsomorphismByFunction</code> checks that: the mapping from <var class="Arg">S</var> to <var class="Arg">T</var> defined by <var class="Arg">fun</var> satisfies <code class="func">RespectsMultiplication</code> (<a href="../../../doc/ref/chap32_mj.html#X7BEFF95883EAEC78"><span class="RefLink">Reference: RespectsMultiplication</span></a>); that the function from <var class="Arg">T</var> to <var class="Arg">S</var> defined by <var class="Arg">invFun</var> satisfies <code class="func">RespectsMultiplication</code> (<a href="../../../doc/ref/chap32_mj.html#X7BEFF95883EAEC78"><span class="RefLink">Reference: RespectsMultiplication</span></a>); and that these functions are mutual inverses. This can be expensive. If any of these checks fails, then <code class="keyw">fail</code> is returned.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := MonogenicSemigroup(IsTransformationSemigroup, 3, 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := MonogenicSemigroup(IsBipartitionSemigroup, 3, 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">map := x -> T.1 ^ Length(Factorization(S, x));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">inv := x -> S.1 ^ Length(Factorization(T, x));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso := SemigroupIsomorphismByFunction(S, T, map, inv);</span>
<commutative non-regular transformation semigroup of size 4, degree 5
  with 1 generator> -> <commutative non-regular block bijection
  semigroup of size 4, degree 6 with 1 generator>
</pre></div>

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

<h5>14.2-10 IsSemigroupIsomorphismByFunction</h5>

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

<p><code class="code">IsSemigroupIsomorphismByFunction</code> returns <code class="keyw">true</code> if <var class="Arg">hom</var> satisfies <code class="func">IsSemigroupHomomorphismByFunction</code> (<a href="chap14_mj.html#X7F9CF9457E84BAE2"><span class="RefLink">14.1-4</span></a>) and <code class="func">IsBijective</code> (<a href="../../../doc/ref/chap32_mj.html#X878F56AB7B342767"><span class="RefLink">Reference: IsBijective</span></a>), and <code class="keyw">false</code> if does not. Note that this filter may return <code class="keyw">true</code> even if the underlying <strong class="pkg">GAP</strong> function does not define a homomorphism. A semigroup isomorphism is a mapping from a semigroup <code class="code">S</code> to a semigroup <code class="code">T</code> that respects multiplication. This representation describes semigroup isomorphisms internally by using a <strong class="pkg">GAP</strong> function mapping elements of <code class="code">S</code> to their images in <code class="code">T</code>. See <code class="func">SemigroupIsomorphismByFunction</code> (<a href="chap14_mj.html#X7B44408D8309C3DC"><span class="RefLink">14.2-9</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := MonogenicSemigroup(IsTransformationSemigroup, 3, 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := MonogenicSemigroup(IsBipartitionSemigroup, 3, 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">map := x -> T.1 ^ Length(Factorization(S, x));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">inv := x -> S.1 ^ Length(Factorization(T, x));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso := SemigroupIsomorphismByFunction(S, T, map, inv);</span>
<commutative non-regular transformation semigroup of size 4, degree 5
  with 1 generator> -> <commutative non-regular block bijection
  semigroup of size 4, degree 6 with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSemigroupIsomorphismByFunction(iso);</span>
true</pre></div>

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

<h5>14.2-11 AsSemigroupIsomorphismByFunction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSemigroupIsomorphismByFunction</code>( <var class="Arg">hom</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup isomorphism, or <code class="keyw">fail</code>.</p>

<p><code class="code">AsSemigroupIsomorphismByFunction</code> takes a semigroup homomorphism <var class="Arg">hom</var> and returns a semigroup isomorphism represented using <strong class="pkg">GAP</strong> functions for the isomorphism and its inverse. If <var class="Arg">hom</var> is not bijective, then <code class="keyw">fail</code> is returned.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullTransformationMonoid(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfSemigroup(S);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">imgs := ListWithIdenticalEntries(4, ConstantTransformation(3, 1));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom := SemigroupHomomorphismByImages(S, S, gens, gens);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSemigroupIsomorphismByFunction(hom);</span>
<full transformation monoid of degree 3> ->
<full transformation monoid of degree 3></pre></div>

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

<h5>14.2-12 SmallerDegreeTransformationRepresentation</h5>

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

<p>This function attempts to find a small degree transformation representation of the semigroup <var class="Arg">S</var>. The implementation attempts to find a right congruence of <var class="Arg">S</var> that <var class="Arg">S</var> acts on (the equivalence classes of) faithfully.</p>

<p>If <var class="Arg">S</var> is not a finitely presented semigroup, then the returned isomorphism is the composition of an isomorphism to a finitely presented semigroup and an isomorphism from that finitely presented semigroup to a transformation semigroup.</p>

<p>The runtime of this function depends on the presentation for <var class="Arg">S</var> that is either given explicitly or computed by the <strong class="pkg">Semigroups</strong> package, but it is difficult to predict what properties of the presentation lead to a shorter runtime. This is unlikely to terminate in a reasonable amount of time for semigroups with more than approx. <code class="code">10000</code> elements, but might also not terminate quickly for smaller semigroups depending on the presentation used.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := BrauerMonoid(3);</span>
<regular bipartition *-monoid of degree 3 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismTransformationSemigroup(S);</span>
<regular bipartition *-monoid of size 15, degree 3 with 3 generators>
-> <transformation monoid of size 15, degree 15 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallerDegreeTransformationRepresentation(S);</span>
CompositionMapping(
<fp semigroup with 4 generators and 20 relations of length 81> ->
<transformation monoid of degree 7 with 3 generators>,
<regular bipartition *-monoid of size 15, degree 3 with 3 generators>
-> <fp semigroup with 4 generators and 20 relations of length 81> )
<span class="GAPprompt">gap></span> <span class="GAPinput">S := JonesMonoid(5);</span>
<regular bipartition *-monoid of degree 5 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(S);</span>
42
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallerDegreeTransformationRepresentation(S);</span>
CompositionMapping(
<fp semigroup with 5 generators and 28 relations of length 120> ->
<transformation monoid of degree 10 with 4 generators>,
<regular bipartition *-monoid of size 42, degree 5 with 4 generators>
-> <fp semigroup with 5 generators and 28 relations of length 120> )
</pre></div>

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

<h5>14.2-13 MinimalFaithfulTransformationDegree</h5>

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

<p>This function returns the minimal degree of a faithful transformation representation of the semigroup <var class="Arg">S</var>. This is currently only implemented for a very small number of types of semigroups.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := RightZeroSemigroup(10);</span>
<transformation semigroup of degree 7 with 10 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalFaithfulTransformationDegree(S);</span>
7
</pre></div>

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

<h4>14.3 <span class="Heading">
      Isomorphisms of Rees (0-)matrix semigroups
    </span></h4>

<p>An isomorphism between two regular finite Rees (0-)matrix semigroups whose underlying semigroups are groups can be described by a triple defined in terms of the matrices and underlying groups of the semigroups. For a full description of the theory involved, see Section 3.4 of <a href="chapBib_mj.html#biBHowie1995aa">[How95]</a>.</p>

<p>An isomorphism described in this way can be constructed using <code class="func">RMSIsoByTriple</code> (<a href="chap14_mj.html#X82B0BDCD7CBDCC2E"><span class="RefLink">14.3-2</span></a>) or <code class="func">RZMSIsoByTriple</code> (<a href="chap14_mj.html#X82B0BDCD7CBDCC2E"><span class="RefLink">14.3-2</span></a>), and will satisfy the filter <code class="func">IsRMSIsoByTriple</code> (<a href="chap14_mj.html#X82FCB1E585429FEA"><span class="RefLink">14.3-1</span></a>) or <code class="func">IsRZMSIsoByTriple</code> (<a href="chap14_mj.html#X82FCB1E585429FEA"><span class="RefLink">14.3-1</span></a>).</p>

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

<h5>14.3-1 IsRMSIsoByTriple</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRMSIsoByTriple</code></td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRZMSIsoByTriple</code></td><td class="tdright">( category )</td></tr></table></div>
<p>The isomorphisms between finite Rees matrix or 0-matrix semigroups <code class="code">S</code> and <code class="code">T</code> over groups <code class="code">G</code> and <code class="code">H</code>, respectively, specified by a triple consisting of:</p>

<ol>
<li><p>an isomorphism of the underlying graph of <code class="code">S</code> to the underlying graph of of <code class="code">T</code></p>

</li>
<li><p>an isomorphism from <code class="code">G</code> to <code class="code">H</code></p>

</li>
<li><p>a function from <code class="code">Rows(S)</code> union <code class="code">Columns(S)</code> to <code class="code">H</code></p>

</li>
</ol>
<p>belong to the categories <code class="code">IsRMSIsoByTriple</code> and <code class="code">IsRZMSIsoByTriple</code>. Basic operators for such isomorphism are given in <a href="chap14_mj.html#X7ED8BF227F4229E2"><span class="RefLink">14.3-7</span></a>, and basic operations are: <code class="func">Range</code> (<a href="../../../doc/ref/chap21_mj.html#X79596BDE7CAF8491"><span class="RefLink">Reference: range</span></a>), <code class="func">Source</code> (<a href="../../../doc/ref/chap32_mj.html#X7DE8173F80E07AB1"><span class="RefLink">Reference: Source</span></a>), <code class="func">ELM_LIST</code> (<a href="chap14_mj.html#X81C4DE427D4A3D6C"><span class="RefLink">14.3-3</span></a>), <code class="func">CompositionMapping</code> (<a href="../../../doc/ref/chap32_mj.html#X7ED1E4E27CCE2DCA"><span class="RefLink">Reference: CompositionMapping</span></a>), <code class="func">ImagesElm</code> (<a href="chap14_mj.html#X7F159C1179C93C11"><span class="RefLink">14.3-5</span></a>), <code class="func">ImagesRepresentative</code> (<a href="chap14_mj.html#X7F159C1179C93C11"><span class="RefLink">14.3-5</span></a>), <code class="func">InverseGeneralMapping</code> (<a href="../../../doc/ref/chap32_mj.html#X865FC25A87D36F3D"><span class="RefLink">Reference: InverseGeneralMapping</span></a>), <code class="func">PreImagesRepresentative</code> (<a href="../../../doc/ref/chap32_mj.html#X7AE24A1586B7DE79"><span class="RefLink">Reference: PreImagesRepresentative</span></a>), <code class="func">IsOne</code> (<a href="../../../doc/ref/chap31_mj.html#X814D78347858EC13"><span class="RefLink">Reference: IsOne</span></a>).</p>

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

<h5>14.3-2 RMSIsoByTriple</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RMSIsoByTriple</code>( <var class="Arg">R1</var>, <var class="Arg">R2</var>, <var class="Arg">triple</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">‣ RZMSIsoByTriple</code>( <var class="Arg">R1</var>, <var class="Arg">R2</var>, <var class="Arg">triple</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An isomorphism.</p>

<p>If <var class="Arg">R1</var> and <var class="Arg">R2</var> are isomorphic regular Rees 0-matrix semigroups whose underlying semigroups are groups then <code class="code">RZMSIsoByTriple</code> returns the isomorphism between <var class="Arg">R1</var> and <var class="Arg">R2</var> defined by <var class="Arg">triple</var>, which should be a list consisting of the following:</p>


<ul>
<li><p><code class="code"><var class="Arg">triple</var>[1]</code> should be a permutation describing an isomorphism from the graph of <var class="Arg">R1</var> to the graph of <var class="Arg">R2</var>, i.e. it should satisfy <code class="code">OnDigraphs(RZMSDigraph(<var class="Arg">R1</var>), <var class="Arg">triple</var>[1]) = RZMSDigraph(<var class="Arg">R2</var>)</code>.</p>

</li>
<li><p><code class="code"><var class="Arg">triple</var>[2]</code> should be an isomorphism from the underlying group of <var class="Arg">R1</var> to the underlying group of <var class="Arg">R2</var> (see <code class="func">UnderlyingSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7D9719F887AFCF8F"><span class="RefLink">Reference: UnderlyingSemigroup for a Rees 0-matrix semigroup</span></a>)).</p>

</li>
<li><p><code class="code"><var class="Arg">triple</var>[3]</code> should be a list of elements from the underlying group of <var class="Arg">R2</var>. If the <code class="func">Matrix</code> (<a href="../../../doc/ref/chap26_mj.html#X879384D479EB1D82"><span class="RefLink">Reference: Matrix</span></a>) of <var class="Arg">R1</var> has <span class="SimpleMath">\(m\)</span> columns and <span class="SimpleMath">\(n\)</span> rows, then the list should have length <span class="SimpleMath">\(m + n\)</span>, where the first <span class="SimpleMath">\(m\)</span> entries should correspond to the columns of <var class="Arg">R1</var>'s matrix, and the last \(n\) entries should correspond to the rows. These column and row entries should correspond to the \(u_i\) and \(v_\lambda\) elements in Theorem 3.4.1 of [How95].



</li>
</ul>
--> --------------------

--> maximum size reached

--> --------------------

100%


¤ Dauer der Verarbeitung: 0.25 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




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 ist noch experimentell.





                                                                                                                                                                                                                                                                                                                                                                                                     

Neuigkeiten

     Aktuelles
     Motto des Tages

Software

     Produkte
     Quellcodebibliothek

Aktivitäten

     Artikel über Sicherheit
     Anleitung zur Aktivierung von SSL

Muße

     Gedichte
     Musik
     Bilder
Jenseits des Üblichen ....

Besucherstatistik

Besucherstatistik

Monitoring

Montastic status badge