<?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 (MONOID) - Chapter 6: Special Classes of Semigroup</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" />
</head>
<body>
<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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<p><a id="X853D15F87F14D36E" name="X853D15F87F14D36E"></a></p>
<div class="ChapSects"><a href="chap6.html#X853D15F87F14D36E">6 <span class="Heading">Special Classes of Semigroup</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X849A9EB37CF9BBB0">6.1 <span class="Heading">Some Classes of Semigroup</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79B1A1127B3B784A">6.1-1 SingularSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X87554F5A85484046">6.1-2 OrderPreservingSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7A6FC6F179394E66">6.1-3 KiselmanSemigroup</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7A88BC6E7AC4E444">6.2 <span class="Heading">Zero Groups and Zero Semigroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X801FC1D97D832A6F">6.2-1 ZeroSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X86A1D1D7832BEA9C">6.2-2 ZeroSemigroupElt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X81E319198527F824">6.2-3 ZeroGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X81DB162A78350E28">6.2-4 ZeroGroupElt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7AA4B9577DC35D54">6.2-5 UnderlyingGroupOfZG</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7AEC4E5E7EAE3CA5">6.2-6 UnderlyingGroupEltOfZGElt</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7C3F130B8362D55A">6.3 <span class="Heading">Random Semigroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7ECD900879DA1FD7">6.3-1 RandomMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X789DE9AB79FCFEB5">6.3-2 RandomSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X858CBA2B7BD64141">6.3-3 RandomReesMatrixSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7F637CA981EFC6BE">6.3-4 RandomReesZeroMatrixSemigroup</a></span>
</div>
</div>
<h3>6 <span class="Heading">Special Classes of Semigroup</span></h3>
<p>In this chapter functions for creating certain semigroups are given.</p>
<p><a id="X849A9EB37CF9BBB0" name="X849A9EB37CF9BBB0"></a></p>
<h4>6.1 <span class="Heading">Some Classes of Semigroup</span></h4>
<p><a id="X79B1A1127B3B784A" name="X79B1A1127B3B784A"></a></p>
<h5>6.1-1 SingularSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SingularSemigroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>creates the semigroup of singular transformations of degree <code class="code">n</code>. That is, the semigroup of all transformations of the <code class="code">n</code>-element set <code class="code"> {1,2,...,n}</code> that are non-invertible.</p>
<p>This semigroup is known to be regular, idempotent generated (satisfies <code class="func">IsSemiBand</code> (<a href="chap5.html#X8434E7C287DBFE1B"><b>5.2-10</b></a>)), and has size <code class="code">n^n-n!</code>.</p>
<p>The generators used here are the idempotents of rank <code class="code">n-1</code>, so there are <code class="code">n(n-1)</code> generators in total.</p>
<table class="example">
<tr><td><pre>
gap> S:=SingularSemigroup(6);
<semigroup with 30 generators>
gap> Size(S);
45936
gap> IsRegularSemigroup(S);
true
gap> IsSemiBand(S);
true
</pre></td></tr></table>
<p><a id="X87554F5A85484046" name="X87554F5A85484046"></a></p>
<h5>6.1-2 OrderPreservingSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> OrderPreservingSemigroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the semigroup of order preserving transformations of the <code class="code">n</code>- element set <code class="code">{1,2,...,n}</code>. That is, the mappings <code class="code">f</code> such that <code class="code">i</code> is at most <code class="code">j</code> implies <code class="code">f(i)</code> is at most <code class="code">f(j)</code> for all <code class="code">i,j</code> in <code class="code">{1,2,...,n}</code>.</p>
<p>This semigroup is known to be regular, idempotent generated (satisfies <code class="func">IsSemiBand</code> (<a href="chap5.html#X8434E7C287DBFE1B"><b>5.2-10</b></a>)), and has size <code class="code">Binomial(2*n-1, n-1)</code>. The generators and relations used here are those specified by Aizenstat as given in <a href="chapBib.html#biBarthur1">[AR00]</a> and <a href="chapBib.html#biBgomes1">[GH92]</a>. That is, <code class="code">OrderPreservingSemigroup(n)</code> has the <code class="code">2n-2</code> idempotent generators</p>
<table class="example">
<tr><td><pre>
u_2:=Transformation([2,2,3,..,n]), u_3:=Transformation([1,3,3,..,n]), ...
v_n-2:=Transformation([1,2,2,...,n]), v_n-3:=Transformation
([1,2,3,3,...,n]), ...
</pre></td></tr></table>
<p>and the presentation obtained using <code class="func">IsomorphismFpMonoid</code> (<a href="chap7.html#X7F2ADC587DF698A2"><b>7.7-4</b></a>) has relations</p>
<table class="example">
<tr><td><pre>
v_n−i u_i = u_i v_n−i+1 (i=2,..., n−1)
u_n−i v_i = v_i u_n−i+1 (i=2,...,n−1),
v_n−i u_i = u_i (i=1,...,n−1),
u_n−i v_i = v_i (i=1,...,n−1),
u_i v_j = v_j u_i (i,j=1,...,n−1; not j=n-i, n-i+1),
u_1 u_2 u_1 = u_1 u_2,
v_1 v_2 v_1 = v_1 v_2.
</pre></td></tr></table>
<p><br /></p>
<table class="example">
<tr><td><pre>
gap> S:=OrderPreservingSemigroup(5);
<monoid with 8 generators>
gap> IsSemiBand(S);
true
gap> IsRegularSemigroup(S);
true
gap> Size(S)=Binomial(2*5-1, 5-1);
true
</pre></td></tr></table>
<p><a id="X7A6FC6F179394E66" name="X7A6FC6F179394E66"></a></p>
<h5>6.1-3 KiselmanSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KiselmanSemigroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the Kiselman semigroup with <code class="code">n</code> generators. That is, the semigroup defined in <a href="chapBib.html#biBmazorchuk">[KM05]</a> with the presentation</p>
<p class="pcenter">
<a_1, a_2, ... , a_n | a_i^2=a_i (i=1,...n) a_ia_ja_i=a_ja_ia_j=a_ja_i
(1<=i< j<=n)>.
</p>
<table class="example">
<tr><td><pre>
gap> S:=KiselmanSemigroup(3);
<fp monoid on the generators [ m1, m2, m3 ]>
gap> Elements(S);
[ <identity ...>, m1, m2, m3, m1*m2, m1*m3, m2*m1, m2*m3, m3*m1, m3*m2,
m1*m2*m3, m1*m3*m2, m2*m1*m3, m2*m3*m1, m3*m1*m2, m3*m2*m1, m2*m1*m3*m2,
m2*m3*m1*m2 ]
gap> Idempotents(S);
[ 1, m1, m2*m1, m3*m2*m1, m3*m1, m2, m3*m2, m3 ]
gap> SetInfoLevel(InfoAutos, 0);
gap> AutomorphismGroup(Range(IsomorphismTransformationSemigroup(S)));
<group of size 1 with 1 generators>
</pre></td></tr></table>
<p><a id="X7A88BC6E7AC4E444" name="X7A88BC6E7AC4E444"></a></p>
<h4>6.2 <span class="Heading">Zero Groups and Zero Semigroups</span></h4>
<p><a id="X801FC1D97D832A6F" name="X801FC1D97D832A6F"></a></p>
<h5>6.2-1 ZeroSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZeroSemigroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the <em>zero semigroup</em> <code class="code">S</code> of order <code class="code">n</code>. That is, the unique semigroup up to isomorphism of order <code class="code">n</code> such that there exists an element <code class="code">0</code> in <code class="code">S</code> such that <code class="code">xy=0</code> for all <code class="code">x,y</code> in <code class="code">S</code>.</p>
<p>A zero semigroup is generated by its nonzero elements, has trivial Green's relations, and is not regular.</p>
<table class="example">
<tr><td><pre>
gap> S:=ZeroSemigroup(10);
<zero semigroup with 10 elements>
gap> Size(S);
10
gap> GeneratorsOfSemigroup(S);
[ z1, z2, z3, z4, z5, z6, z7, z8, z9 ]
gap> Idempotents(S);
[ 0 ]
gap> IsZeroSemigroup(S);
true
gap> GreensRClasses(S);
[ {0}, {z1}, {z2}, {z3}, {z4}, {z5}, {z6}, {z7}, {z8}, {z9} ]
</pre></td></tr></table>
<p><a id="X86A1D1D7832BEA9C" name="X86A1D1D7832BEA9C"></a></p>
<h5>6.2-2 ZeroSemigroupElt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZeroSemigroupElt</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the zero semigroup element <code class="code">zn</code> where <code class="code">n</code> is a positive integer and <code class="code">z0</code> is the multiplicative zero.</p>
<p>The zero semigroup element <code class="code">zn</code> belongs to every zero semigroup with degree at least <code class="code">n</code>.</p>
<table class="example">
<tr><td><pre>
gap> ZeroSemigroupElt(0);
0
gap> ZeroSemigroupElt(4);
z4
</pre></td></tr></table>
<p><a id="X81E319198527F824" name="X81E319198527F824"></a></p>
<h5>6.2-3 ZeroGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZeroGroup</code>( <var class="Arg">G</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the monoid obtained by adjoining a zero element to <code class="code">G</code>. That is, the monoid <code class="code">S</code> obtained by adjoining a zero element <code class="code">0</code> to <code class="code">G</code> with <code class="code">g0=0g=0</code> for all <code class="code">g</code> in <code class="code">S</code>.</p>
<table class="example">
<tr><td><pre>
gap> S:=ZeroGroup(CyclicGroup(10));
<zero group with 3 generators>
gap> IsRegularSemigroup(S);
true
gap> Elements(S);
[ 0, <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2, f2^3, f1*f2^3, f2^4,
f1*f2^4 ]
gap> GreensRClasses(S);
[ {<adjoined zero>}, {ZeroGroup(<identity> of ...)} ]
</pre></td></tr></table>
<p><a id="X81DB162A78350E28" name="X81DB162A78350E28"></a></p>
<h5>6.2-4 ZeroGroupElt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZeroGroupElt</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the zero group element corresponding to the group element <code class="code">g</code>. The function <code class="code">ZeroGroupElt</code> is only used to create an object in the correct category during the creation of a zero group using <code class="func">ZeroGroup</code> (<a href="chap6.html#X81E319198527F824"><b>6.2-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> ZeroGroupElt(Random(DihedralGroup(10)));;
gap> IsZeroGroupElt(last);
true
</pre></td></tr></table>
<p><a id="X7AA4B9577DC35D54" name="X7AA4B9577DC35D54"></a></p>
<h5>6.2-5 UnderlyingGroupOfZG</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnderlyingGroupOfZG</code>( <var class="Arg">ZG</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the group from which the zero group <code class="code">ZG</code> was constructed.</p>
<table class="example">
<tr><td><pre>
gap> G:=DihedralGroup(10);;
gap> S:=ZeroGroup(G);;
gap> UnderlyingGroupOfZG(S)=G;
true
</pre></td></tr></table>
<p><a id="X7AEC4E5E7EAE3CA5" name="X7AEC4E5E7EAE3CA5"></a></p>
<h5>6.2-6 UnderlyingGroupEltOfZGElt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnderlyingGroupEltOfZGElt</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns the group element from which the zero group element <code class="code">g</code> was constructed.</p>
<table class="example">
<tr><td><pre>
gap> G:=DihedralGroup(10);;
gap> S:=ZeroGroup(G);;
gap> Elements(S);
[ 0, <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2, f2^3, f1*f2^3, f2^4,
f1*f2^4 ]
gap> x:=last[5];
f1*f2
gap> UnderlyingGroupEltOfZGElt(x);
f1*f2
</pre></td></tr></table>
<p><a id="X7C3F130B8362D55A" name="X7C3F130B8362D55A"></a></p>
<h4>6.3 <span class="Heading">Random Semigroups</span></h4>
<p><a id="X7ECD900879DA1FD7" name="X7ECD900879DA1FD7"></a></p>
<h5>6.3-1 RandomMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomMonoid</code>( <var class="Arg">m, n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a random transformation monoid of degree <code class="code">n</code> with <code class="code">m</code> generators.</p>
<table class="example">
<tr><td><pre>
gap> S:=RandomMonoid(5,5);
<semigroup with 5 generators>
</pre></td></tr></table>
<p><a id="X789DE9AB79FCFEB5" name="X789DE9AB79FCFEB5"></a></p>
<h5>6.3-2 RandomSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomSemigroup</code>( <var class="Arg">m, n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a random transformation semigroup of degree <code class="code">n</code> with <code class="code">m</code> generators.</p>
<table class="example">
<tr><td><pre>
gap> S:=RandomSemigroup(5,5);
<semigroup with 5 generators>
</pre></td></tr></table>
<p><a id="X858CBA2B7BD64141" name="X858CBA2B7BD64141"></a></p>
<h5>6.3-3 RandomReesMatrixSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomReesMatrixSemigroup</code>( <var class="Arg">i, j, deg</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a random Rees matrix semigroup with an <code class="code">i</code> by <code class="code">j</code> sandwich matrix over a permutation group with maximum degree <code class="code">deg</code>.</p>
<table class="example">
<tr><td><pre>
gap> S:=RandomReesMatrixSemigroup(4,5,5);
Rees Matrix Semigroup over Group([ (1,5,3,4), (1,3,4,2,5) ])
[ [ (), (), (), (), () ],
[ (), (1,3,5)(2,4), (1,3,5)(2,4), (1,5,3), (1,5,3) ],
[ (), (1,3,5), (1,5,3)(2,4), (), (1,5,3) ],
[ (), (), (1,3,5)(2,4), (2,4), (2,4) ] ]
</pre></td></tr></table>
<p><a id="X7F637CA981EFC6BE" name="X7F637CA981EFC6BE"></a></p>
<h5>6.3-4 RandomReesZeroMatrixSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomReesZeroMatrixSemigroup</code>( <var class="Arg">i, j, deg</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a random Rees <code class="code">0</code>-matrix semigroup with an <code class="code">i</code> by <code class="code">j</code> sandwich matrix over a permutation group with maximum degree <code class="code">deg</code>.</p>
<table class="example">
<tr><td><pre>
gap> S:=RandomReesZeroMatrixSemigroup(2,3,2);
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> SandwichMatrixOfReesZeroMatrixSemigroup(S);
[ [ 0, (), 0 ], [ 0, 0, 0 ] ]
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<div class="chlinkbot"><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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1904
