<?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 1: The MONOID package</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="chap0.html">Previous Chapter</a> <a href="chap2.html">Next Chapter</a> </div>
<p><a id="X7E0DB6BF8569166D" name="X7E0DB6BF8569166D"></a></p>
<div class="ChapSects"><a href="chap1.html#X7E0DB6BF8569166D">1 <span class="Heading">The <strong class="pkg">MONOID</strong> package</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X7DFB63A97E67C0A1">1.1 <span class="Heading">Introduction</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X7F6B07EE7F61869F">1.2 <span class="Heading">Installing <strong class="pkg">MONOID</strong></span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X8098672E7B4EC324">1.3 <span class="Heading">Testing <strong class="pkg">MONOID</strong></span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X816AD93B7EE39FB9">1.4 <span class="Heading">Changes</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap1.html#X8246DD5B7AF0099A">1.5 <span class="Heading">Forthcoming Features</span></a>
</div>
</div>
<h3>1 <span class="Heading">The <strong class="pkg">MONOID</strong> package</span></h3>
<p><a id="X7DFB63A97E67C0A1" name="X7DFB63A97E67C0A1"></a></p>
<h4>1.1 <span class="Heading">Introduction</span></h4>
<p>This manual describes the <strong class="pkg">MONOID</strong> package version 3.1.3 for computing with transformation semigroups. <strong class="pkg">MONOID</strong> 3.1.3 is an updated version of the package with the same name for <strong class="pkg">GAP</strong> 3; see <span class="URL"><a href="http://schmidt.nuigalway.ie/monoid/index.html">http://schmidt.nuigalway.ie/monoid/index.html</a></span> for more information about the original <strong class="pkg">MONOID</strong> by Goetz Pfeiffer and Steve A. Linton, Edmund F. Robertson and Nik Ruskuc.</p>
<p><strong class="pkg">MONOID</strong> 3.1.3 retains all the functionality of the original <strong class="pkg">MONOID</strong> package. In particular, <strong class="pkg">MONOID</strong> 3.1.3 contains more efficient methods than those available in the <strong class="pkg">GAP</strong> library for computing orbits, calculating Green's classes, finding the size, the elements, and testing membership in transformation semigroups; see Chapters <a href="chap3.html#X849149EF79F824D1"><b>3</b></a> and <a href="chap4.html#X80C6C718801855E9"><b>4</b></a>. After <strong class="pkg">MONOID</strong> has been loaded many of these methods are automatically used in preference to those in the library and do not need to be called explicitly by the user. These methods are described in <a href="chapBib.html#biBpfeiffer1">[LPRR98]</a> and the algorithms themselves are described in <a href="chapBib.html#biBpfeiffer2">[LPRR02]</a>.</p>
<p>In addition, there are new methods for testing if a semigroup satisfies a particular property, such as if it is regular, simple, inverse, or completely regular, see Chapter <a href="chap5.html#X78274024827F306D"><b>5</b></a>; methods for computing the automorphism group of a transformation semigroup see Section <a href="chap7.html#X7A007A0C80D26351"><b>7.4</b></a>; methods for finding homomorphisms and isomorphism between some types of semigroups see Chapter <a href="chap7.html#X861935DB81A478C2"><b>7</b></a>; and functions to create some well-known semigroups see Chapter <a href="chap6.html#X853D15F87F14D36E"><b>6</b></a>. The property testing methods are described in <a href="chapBib.html#biBlargest">[GM05]</a> and the method for computing the automorphism group of a semigroup is described in <a href="chapBib.html#biBcomputing">[ABM07]</a>.</p>
<p>The <strong class="pkg">MONOID</strong> package is written in <strong class="pkg">GAP</strong> code only but relies on the <strong class="pkg">GRAPE</strong> package Version 4.2 or higher in the methods for computing the automorphism group of a semigroup. The following functions can only be used fully if <strong class="pkg">GRAPE</strong> is fully installed (and loaded):</p>
<ul>
<li><p><code class="func">AutomorphismGroup</code> (<a href="chap7.html#X87677B0787B4461A"><b>7.4-1</b></a>) with argument satisfying <code class="func">IsTransformationSemigroup</code> (<a href="/Users/jdm/Maths/Computation/GAP/gapdev/doc/ref/chap49.html#X7EAF835D7FE4026F"><b>Reference: IsTransformationSemigroup</b></a>) or <code class="func">IsReesZeroMatrixSemigroup</code> (<a href="/Users/jdm/Maths/Computation/GAP/gapdev/doc/ref/chap49.html#X7EEBAEE9857C5EBA"><b>Reference: IsReesZeroMatrixSemigroup</b></a>)</p>
</li>
<li><p><code class="func">RightTransStabAutoGroup</code> (<a href="chap7.html#X78060D7C8331F340"><b>7.5-9</b></a>) with argument satisfying <code class="func">IsReesZeroMatrixSemigroup</code> (<a href="/Users/jdm/Maths/Computation/GAP/gapdev/doc/ref/chap49.html#X7EEBAEE9857C5EBA"><b>Reference: IsReesZeroMatrixSemigroup</b></a>)</p>
</li>
<li><p><code class="func">RZMSGraph</code> (<a href="chap7.html#X781757FD7938C9DD"><b>7.5-8</b></a>)</p>
</li>
<li><p><code class="func">RZMSInducedFunction</code> (<a href="chap7.html#X7D17056F79E5649F"><b>7.5-6</b></a>)</p>
</li>
<li><p><code class="func">RZMStoRZMSInducedFunction</code> (<a href="chap7.html#X84BA41977C43EAA3"><b>7.5-7</b></a>)</p>
</li>
<li><p><code class="func">IsomorphismSemigroups</code> (<a href="chap7.html#X8248C522825E2684"><b>7.7-5</b></a>) with both arguments satisfying <code class="func">IsReesZeroMatrixSemigroup</code> (<a href="/Users/jdm/Maths/Computation/GAP/gapdev/doc/ref/chap49.html#X7EEBAEE9857C5EBA"><b>Reference: IsReesZeroMatrixSemigroup</b></a>)</p>
</li>
</ul>
<p>Installation of <strong class="pkg">GRAPE</strong> is described in the <code class="code">README</code> file of the <strong class="pkg">GRAPE</strong> distribution and in the section entitled `Installing the GRAPE Package' of the <strong class="pkg">GRAPE</strong> manual; see <span class="URL"><a href=" http://www.maths.qmul.ac.uk/~leonard/grape/ "> http://www.maths.qmul.ac.uk/~leonard/grape/ </a></span> or the main <strong class="pkg">GAP</strong> webpages for more information.</p>
<p>If you want to take advantage of the online help facilities in <strong class="pkg">MONOID</strong>, then the <strong class="pkg">gapdoc</strong> package Version 1.1 or higher is also required; see <span class="URL"><a href=" http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc/ "> http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc/ </a></span> for further details of how to obtain and install <strong class="pkg">gapdoc</strong>.</p>
<p><a id="X7F6B07EE7F61869F" name="X7F6B07EE7F61869F"></a></p>
<h4>1.2 <span class="Heading">Installing <strong class="pkg">MONOID</strong></span></h4>
<p>In this section we give a brief description of how to start using <strong class="pkg">MONOID</strong>. If you have any problems getting <strong class="pkg">MONOID</strong> working, then please email me directly at <span class="URL"><a href="mailto:jdm3@st-and.ac.uk">jdm3@st-and.ac.uk</a></span>.</p>
<p>It is assumed that you have a working copy of <strong class="pkg">GAP</strong> with version number 4.4.10 or higher. The most up-to-date version of <strong class="pkg">GAP</strong> and instructions on how to install it can be obtained from the main <strong class="pkg">GAP</strong> webpage <span class="URL"><a href=" http://www.gap-system.org "> http://www.gap-system.org </a></span> Those functions in <strong class="pkg">MONOID</strong> described in Chapter <a href="chap7.html#X861935DB81A478C2"><b>7</b></a> relating to automorphism groups of semigroups require the <strong class="pkg">GRAPE</strong> (for computing with graphs and groups) to be loaded. In particular, <strong class="pkg">GRAPE</strong> must be installed in a UNIX operating system so that the automorphism group and isomorphism testing functions (for graphs) can be used.</p>
<p>Please go to <span class="URL"><a href=" http://www.maths.qmul.ac.uk/~leonard/grape/ "> http://www.maths.qmul.ac.uk/~leonard/grape/ </a></span> or the main <strong class="pkg">GAP</strong> webpage for further details on how to obtain and install <strong class="pkg">GRAPE</strong>.</p>
<p>The following is a summary of the steps that should lead to a successful installation of <strong class="pkg">MONOID</strong>.</p>
<ul>
<li><p>download the package archive <code class="code">monoid3r1p3.tar.gz</code> or <code class="code">monoid3r1p3.tar.bz2</code> from <span class="URL"><a href="http://www-history.mcs.st-and.ac.uk/~jamesm/monoid/index.html ">http://www-history.mcs.st-and.ac.uk/~jamesm/monoid/index.html </a></span></p>
</li>
<li><p>unzip & untar the file, this should create a directory called <code class="code">MONOID</code>.</p>
</li>
<li><p>move the directory <code class="code">MONOID</code> into the <code class="code">pkg</code> directory of your <strong class="pkg">GAP</strong> directory (the one containing the directories <code class="code">lib</code>, <code class="code">doc</code>, <code class="code">pkg</code>, and so on)</p>
</li>
<li><p>start <strong class="pkg">GAP</strong> in the usual way</p>
</li>
<li><p>type <code class="code">LoadPackage("monoid");</code></p>
</li>
</ul>
<p>Below is an example of an installation of <strong class="pkg">MONOID</strong> in UNIX where <code class="code">GAPROOT</code> should be substituted with the main <strong class="pkg">GAP</strong> directory (the one containing the folders `bin', `lib', and so on) in your installation of <strong class="pkg">GAP</strong>.</p>
<table class="example">
<tr><td><pre>
> gunzip monoid3r1p3.tar.gz
> tar -xf monoid3r1p3.tar
> mv MONOID GAPROOT/pkg
> gap
[ ... ]
gap> LoadPackage("monoid");
Loading MONOID 3.1.3
by James Mitchell (www-groups.mcs.st-and.ac.uk/~jamesm)
For help, type: ?the monoid package
true
gap>
</pre></td></tr></table>
<p>Presuming that the above steps can be completed successfully you will be running the <strong class="pkg">MONOID</strong> package!</p>
<p>If you want to check that the package is working correctly, please see Section <a href="chap1.html#X8098672E7B4EC324"><b>1.3</b></a>.</p>
<p><strong class="button">Please note:</strong> before you can used <strong class="pkg">MONOID</strong> fully you must install <strong class="pkg">GRAPE</strong> as described above.</p>
<p><a id="X8098672E7B4EC324" name="X8098672E7B4EC324"></a></p>
<h4>1.3 <span class="Heading">Testing <strong class="pkg">MONOID</strong></span></h4>
<p>In this section we describe how to test that <strong class="pkg">MONOID</strong> is working as intended. To test that <strong class="pkg">MONOID</strong> is installed correctly copy the following lines into <strong class="pkg">GAP</strong>.</p>
<table class="example">
<tr><td><pre>
LoadPackage( "monoid" );;
dirs := DirectoriesPackageLibrary( "monoid", "tst" );;
Read(Filename( dirs, "installtest.g" ) );
</pre></td></tr></table>
<p>and press <code class="code">return</code>. Please note that it will take a few moments before the tests are complete.</p>
<p>If the output looks like the following, then it is probable that you have a fully working copy of <strong class="pkg">MONOID</strong> 3.1.3.</p>
<table class="example">
<tr><td><pre>
gap> LoadPackage( "monoid" );;
gap> dirs := DirectoriesPackageLibrary( "monoid", "tst" );;
gap> Read( Filename( dirs, "installtest.g" ) );;
+ install_no_grape.tst 3.1.3
+ GAP4stones: 1
+ install_with_grape.tst 3.1.3
+ GAP4stones: 2
</pre></td></tr></table>
<p>If you want to perform more extensive tests, then copy the following lines into <strong class="pkg">GAP</strong>.</p>
<table class="example">
<tr><td><pre>
LoadPackage( "monoid" );;
dirs := DirectoriesPackageLibrary( "monoid", "tst" );;
Read(Filename( dirs, "testall.g" ) );
</pre></td></tr></table>
<p>Please note that these tests could take a long time to finish.</p>
<p>If something goes wrong, then please review the instructions in Section <a href="chap1.html#X7F6B07EE7F61869F"><b>1.2</b></a> and ensure that <strong class="pkg">MONOID</strong> has been properly installed. If you continue having problems, please email me at <span class="URL"><a href="mailto:jdm3@st-and.ac.uk">jdm3@st-and.ac.uk</a></span>.</p>
<p><a id="X816AD93B7EE39FB9" name="X816AD93B7EE39FB9"></a></p>
<h4>1.4 <span class="Heading">Changes</span></h4>
<ul>
<li><p>from 3.1.2 to 3.1.3: the method for <var class="Arg">PreImagesRepresentative</var> for a semigroup homomorphism by function now tests whether the homomorphism is bijective and total before trying to find preimages. Some other minor corrections were made to the documentation and webpages.</p>
</li>
<li><p>from 3.1.1 to 3.1.2:</p>
<ul>
<li><p>the following new functions have been introduced: <code class="func">TransformationActionNC</code> (<a href="chap2.html#X814B3E6E7D3F1036"><b>2.1-6</b></a>), <code class="func">SmallestIdempotentPower</code> (<a href="chap2.html#X84E1A41F84B70DBB"><b>2.2-6</b></a>), <code class="func">IsKerImgOfTransformation</code> (<a href="chap2.html#X79A3FCED7E8A8B1B"><b>2.2-2</b></a>), <code class="func">TransformationByKernelAndImage</code> (<a href="chap2.html#X82CB17E47CBCFA69"><b>2.1-1</b></a>), <code class="func">AllTransformationsWithKerAndImgNC</code> (<a href="chap2.html#X7D1937FF85B76BB3"><b>2.1-2</b></a>), <code class="func">AsBooleanMatrix</code> (<a href="chap2.html#X7F867C337B18D84E"><b>2.3-1</b></a>), <code class="func">KerImgOfTransformation</code> (<a href="chap2.html#X7E72E6117BFFC74E"><b>2.2-3</b></a>), <code class="func">RandomIdempotent</code> (<a href="chap2.html#X7C5BED247F770ECB"><b>2.1-4</b></a>), <code class="func">InversesOfTransformation</code> (<a href="chap2.html#X846B9EBB86A69BDC"><b>2.2-7</b></a>), <code class="func">KiselmanSemigroup</code> (<a href="chap6.html#X7A6FC6F179394E66"><b>6.1-3</b></a>),</p>
</li>
<li><p>the following functions were renamed:</p>
<ul>
<li><p><code class="code">PermRepTrans</code> was renamed <code class="code">AsPermOfRange</code></p>
</li>
<li><p><code class="code">ImagesTransformationMonoid</code> was renamed <code class="code">ImagesOfTransSemigroup</code></p>
</li>
<li><p><code class="code">GradedImagesTransformationMonoid</code> was renamed <code class="code">GradedImagesOfTransSemigroup</code></p>
</li>
<li><p><code class="code">KernelsTransformationMonoid</code> was renamed <code class="code">KernelsOfTransSemigroup</code></p>
</li>
<li><p><code class="code">GradedKernelsTransformationMonoid</code> was renamed <code class="code">GradedKernelsOfTransSemigroup</code></p>
</li>
</ul>
</li>
<li><p>the following bugs were fixed:</p>
<ul>
<li><p>a bug relating to the definition of the semigroup of order preserving functions was resolved</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>from 3.1 to 3.1.1: fixed a bug that produced an error when loading MONOID with the GRAPE package present but not fully installed.</p>
</li>
<li><p>from 2 to 3:</p>
<ul>
<li><p>new methods for testing if a semigroup satisfies a particular property, such as if it is regular, simple, inverse, or completely regular, see Chapter <a href="chap5.html#X78274024827F306D"><b>5</b></a>;</p>
</li>
<li><p>implementations of new algorithms for computing the automorphism group of an arbitrary semigroup generated by transformations including an interactive function that allows the user to decide how the computation should proceed, see Chapter <a href="chap7.html#X861935DB81A478C2"><b>7</b></a>;</p>
</li>
<li><p>functions for finding automorphisms of Rees matrix semigroups and Rees <code class="code">0</code>-matrix semigroups; see Section <a href="chap7.html#X8225A9EC87A255E6"><b>7.5</b></a>.</p>
</li>
<li><p>functions for defining homomorphisms and isomorphisms between some types of semigroups; see Chapter <a href="chap7.html#X861935DB81A478C2"><b>7</b></a>.</p>
</li>
</ul>
</li>
</ul>
<p><a id="X8246DD5B7AF0099A" name="X8246DD5B7AF0099A"></a></p>
<h4>1.5 <span class="Heading">Forthcoming Features</span></h4>
<p>The features are currently under development and will be available in a future version of <strong class="pkg">MONOID</strong>:</p>
<ul>
<li><p>the number of special types of semigroups available in <strong class="pkg">MONOID</strong> will be expanded to include all of the standard examples of transformation semigroups and some matrix semigroups.</p>
</li>
<li><p>methods analogous to those used to find Green's relations and other structural properties of transformation semigroups in the current version of <strong class="pkg">MONOID</strong> but for semigroups generated by partial transformations, binary relations, and matrix semigroups.</p>
</li>
<li><p>a suite of functions for computing with inverse semigroups generated by partial bijections, including finding faithful representations of smaller degree and small generating sets.</p>
</li>
<li><p>an algorithm for finding a small generating set of a semigroup.</p>
</li>
</ul>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap0.html">Previous Chapter</a> <a href="chap2.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
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2282
