% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}
\usepackage{fancyvrb}
\usepackage{pslatex}
\usepackage[pdftex=true,
a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
pdfcreator={LaTeX with hyperref package / GAPDoc},
colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
citecolor=RoyalGreen,filecolor=RoyalRed,
urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}
% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
%% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
\begin{document}
\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{The \textsf{MONOID} Package\mbox{}}}\\[1cm]
\hypersetup{pdftitle=The \textsf{MONOID} Package}
\markright{\scriptsize \mbox{}\hfill The \textsf{MONOID} Package \hfill\mbox{}}
{Version 3.1.3\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{J. D. Mitchell \mbox{}}}\\
\hypersetup{pdfauthor=J. D. Mitchell }
\end{center}\vfill
\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{J. D. Mitchell } --- Email: \href{mailto://jdm3@st-and.ac.uk} {\texttt{jdm3@st-and.ac.uk}}}\\
\end{titlepage}
\newpage\setcounter{page}{2}
{\small
\section*{Copyright}
\logpage{[ 0, 0, 1 ]}
{\copyright} 2008 J. D. Mitchell.
\mbox{}}\\[1cm]
{\small
\section*{Acknowledgements}
\logpage{[ 0, 0, 3 ]}
The author would like to thank P. v. Bunau, A. Distler, S. Linton, J.
Neubueser, V. Maltcev, M. Neuhoeffer, M. R. Quick, E. F. Robertson, and N.
Ruskuc for their help and suggestions. Special thanks go to J. Araujo for his
mathematical suggestions.
I would also like to acknowledge the support of the Centre of Algebra at the
University of Lisbon, and of EPSRC grant number GR/S/56085/01. \\
\\
\mbox{}}\\[1cm]
{\small
\section*{Colophon}
\logpage{[ 0, 0, 2 ]}
If you use the \textsf{MONOID} package, I would really appreciate it if you would let me know by sending me
an email to \href{mailto://jdm3@st-and.ac.uk} {\texttt{jdm3@st-and.ac.uk}}. If you notice that there are any features missing that you think are
important or if you find a bug, please let me know. \mbox{}}\\[1cm]
\newpage
\def\contentsname{Contents\logpage{[ 0, 0, 4 ]}}
\tableofcontents
\newpage
\chapter{\textcolor{Chapter }{The \textsf{MONOID} package}}\label{Monoid}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X7E0DB6BF8569166D}{}
{
\section{\textcolor{Chapter }{Introduction}}\logpage{[ 1, 1, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
This manual describes the \textsf{MONOID} package version 3.1.3 for computing with transformation semigroups. \textsf{MONOID} 3.1.3 is an updated version of the package with the same name for \textsf{GAP} 3; see \href{http://schmidt.nuigalway.ie/monoid/index.html} {\texttt{http://schmidt.nuigalway.ie/monoid/index.html}} for more information about the original \textsf{MONOID} by Goetz Pfeiffer and Steve A. Linton, Edmund F. Robertson and Nik Ruskuc.
\textsf{MONOID} 3.1.3 retains all the functionality of the original \textsf{MONOID} package. In particular, \textsf{MONOID} 3.1.3 contains more efficient methods than those available in the \textsf{GAP} library for computing orbits, calculating Green's classes, finding the size,
the elements, and testing membership in transformation semigroups; see
Chapters \ref{orbits} and \ref{greens}. After \textsf{MONOID} 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 \cite{pfeiffer1} and the algorithms themselves are described in \cite{pfeiffer2}.
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 \ref{properties}; methods for computing the automorphism group of a transformation semigroup
see Section \ref{autos}; methods for finding homomorphisms and isomorphism between some types of
semigroups see Chapter \ref{homo}; and functions to create some well-known semigroups see Chapter \ref{special}. The property testing methods are described in \cite{largest} and the method for computing the automorphism group of a semigroup is
described in \cite{computing}.
The \textsf{MONOID} package is written in \textsf{GAP} code only but relies on the \textsf{GRAPE} 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 \textsf{GRAPE} is fully installed (and loaded):
\begin{itemize}
\item \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) with argument satisfying \texttt{IsTransformationSemigroup} (\textbf{Reference: IsTransformationSemigroup}) or \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup})
\item \texttt{RightTransStabAutoGroup} (\ref{RightTransStabAutoGroup}) with argument satisfying \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup})
\item \texttt{RZMSGraph} (\ref{RZMSGraph})
\item \texttt{RZMSInducedFunction} (\ref{RZMSInducedFunction})
\item \texttt{RZMStoRZMSInducedFunction} (\ref{RZMStoRZMSInducedFunction})
\item \texttt{IsomorphismSemigroups} (\ref{IsomorphismSemigroups}) with both arguments satisfying \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup})
\end{itemize}
Installation of \textsf{GRAPE} is described in the \texttt{README} file of the \textsf{GRAPE} distribution and in the section entitled `Installing the GRAPE Package' of the \textsf{GRAPE} manual; see \href{ http://www.maths.qmul.ac.uk/~leonard/grape/ } {\texttt{ http://www.maths.qmul.ac.uk/\texttt{\symbol{126}}leonard/grape/ }} or the main \textsf{GAP} webpages for more information.
If you want to take advantage of the online help facilities in \textsf{MONOID}, then the \textsf{gapdoc} package Version 1.1 or higher is also required; see \href{ http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc/ } {\texttt{ http://www.math.rwth-aachen.de/\texttt{\symbol{126}}Frank.Luebeck/GAPDoc/ }} for further details of how to obtain and install \textsf{gapdoc}. }
\section{\textcolor{Chapter }{Installing \textsf{MONOID}}}\label{install}
\logpage{[ 1, 2, 0 ]}
\hyperdef{L}{X7F6B07EE7F61869F}{}
{
In this section we give a brief description of how to start using \textsf{MONOID}. If you have any problems getting \textsf{MONOID} working, then please email me directly at \href{mailto://jdm3@st-and.ac.uk} {\texttt{jdm3@st-and.ac.uk}}.
It is assumed that you have a working copy of \textsf{GAP} with version number 4.4.10 or higher. The most up-to-date version of \textsf{GAP} and instructions on how to install it can be obtained from the main \textsf{GAP} webpage \href{ http://www.gap-system.org } {\texttt{ http://www.gap-system.org }} Those functions in \textsf{MONOID} described in Chapter \ref{homo} relating to automorphism groups of semigroups require the \textsf{GRAPE} (for computing with graphs and groups) to be loaded. In particular, \textsf{GRAPE} must be installed in a UNIX operating system so that the automorphism group
and isomorphism testing functions (for graphs) can be used.
Please go to \href{ http://www.maths.qmul.ac.uk/~leonard/grape/ } {\texttt{ http://www.maths.qmul.ac.uk/\texttt{\symbol{126}}leonard/grape/ }} or the main \textsf{GAP} webpage for further details on how to obtain and install \textsf{GRAPE}.
The following is a summary of the steps that should lead to a successful
installation of \textsf{MONOID}.
\begin{itemize}
\item download the package archive \texttt{monoid3r1p3.tar.gz} or \texttt{monoid3r1p3.tar.bz2} from \href{http://www-history.mcs.st-and.ac.uk/~jamesm/monoid/index.html } {\texttt{http://www-history.mcs.st-and.ac.uk/\texttt{\symbol{126}}jamesm/monoid/index.html }}
\item unzip \& untar the file, this should create a directory called \texttt{MONOID}.
\item move the directory \texttt{MONOID} into the \texttt{pkg} directory of your \textsf{GAP} directory (the one containing the directories \texttt{lib}, \texttt{doc}, \texttt{pkg}, and so on)
\item start \textsf{GAP} in the usual way
\item type \texttt{LoadPackage("monoid");}
\end{itemize}
Below is an example of an installation of \textsf{MONOID} in UNIX where \texttt{GAPROOT} should be substituted with the main \textsf{GAP} directory (the one containing the folders `bin', `lib', and so on) in your
installation of \textsf{GAP}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
> 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>
\end{Verbatim}
Presuming that the above steps can be completed successfully you will be
running the \textsf{MONOID} package!
If you want to check that the package is working correctly, please see Section \ref{testing}.
\textsc{Please note:} before you can used \textsf{MONOID} fully you must install \textsf{GRAPE} as described above. }
\section{\textcolor{Chapter }{Testing \textsf{MONOID}}}\label{testing}
\logpage{[ 1, 3, 0 ]}
\hyperdef{L}{X8098672E7B4EC324}{}
{
In this section we describe how to test that \textsf{MONOID} is working as intended. To test that \textsf{MONOID} is installed correctly copy the following lines into \textsf{GAP}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
LoadPackage( "monoid" );;
dirs := DirectoriesPackageLibrary( "monoid", "tst" );;
Read(Filename( dirs, "installtest.g" ) );
\end{Verbatim}
and press \texttt{return}. Please note that it will take a few moments before the tests are complete.
If the output looks like the following, then it is probable that you have a
fully working copy of \textsf{MONOID} 3.1.3.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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
\end{Verbatim}
If you want to perform more extensive tests, then copy the following lines
into \textsf{GAP}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
LoadPackage( "monoid" );;
dirs := DirectoriesPackageLibrary( "monoid", "tst" );;
Read(Filename( dirs, "testall.g" ) );
\end{Verbatim}
Please note that these tests could take a long time to finish.
If something goes wrong, then please review the instructions in Section \ref{install} and ensure that \textsf{MONOID} has been properly installed. If you continue having problems, please email me
at \href{mailto://jdm3@st-and.ac.uk} {\texttt{jdm3@st-and.ac.uk}}. }
\section{\textcolor{Chapter }{Changes}}\logpage{[ 1, 4, 0 ]}
\hyperdef{L}{X816AD93B7EE39FB9}{}
{
\begin{itemize}
\item from 3.1.2 to 3.1.3: the method for \mbox{\texttt{\slshape PreImagesRepresentative}} 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.
\item from 3.1.1 to 3.1.2:
\begin{itemize}
\item the following new functions have been introduced: \texttt{TransformationActionNC} (\ref{TransformationActionNC}), \texttt{SmallestIdempotentPower} (\ref{SmallestIdempotentPower}), \texttt{IsKerImgOfTransformation} (\ref{IsKerImgOfTransformation}), \texttt{TransformationByKernelAndImage} (\ref{TransformationByKernelAndImage}), \texttt{AllTransformationsWithKerAndImgNC} (\ref{AllTransformationsWithKerAndImgNC}), \texttt{AsBooleanMatrix} (\ref{AsBooleanMatrix}), \texttt{KerImgOfTransformation} (\ref{KerImgOfTransformation}), \texttt{RandomIdempotent} (\ref{RandomIdempotent}), \texttt{InversesOfTransformation} (\ref{InversesOfTransformation}), \texttt{KiselmanSemigroup} (\ref{KiselmanSemigroup}),
\item the following functions were renamed:
\begin{itemize}
\item \texttt{PermRepTrans} was renamed \texttt{AsPermOfRange}
\item \texttt{ImagesTransformationMonoid} was renamed \texttt{ImagesOfTransSemigroup}
\item \texttt{GradedImagesTransformationMonoid} was renamed \texttt{GradedImagesOfTransSemigroup}
\item \texttt{KernelsTransformationMonoid} was renamed \texttt{KernelsOfTransSemigroup}
\item \texttt{GradedKernelsTransformationMonoid} was renamed \texttt{GradedKernelsOfTransSemigroup}
\end{itemize}
\item the following bugs were fixed:
\begin{itemize}
\item a bug relating to the definition of the semigroup of order preserving
functions was resolved
\end{itemize}
\end{itemize}
\item 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.
\item from 2 to 3:
\begin{itemize}
\item new methods for testing if a semigroup satisfies a particular property, such
as if it is regular, simple, inverse, or completely regular, see Chapter \ref{properties};
\item 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 \ref{homo};
\item functions for finding automorphisms of Rees matrix semigroups and Rees \texttt{0}-matrix semigroups; see Section \ref{rees}.
\item functions for defining homomorphisms and isomorphisms between some types of
semigroups; see Chapter \ref{homo}.
\end{itemize}
\end{itemize}
}
\section{\textcolor{Chapter }{Forthcoming Features}}\logpage{[ 1, 5, 0 ]}
\hyperdef{L}{X8246DD5B7AF0099A}{}
{
The features are currently under development and will be available in a future
version of \textsf{MONOID}:
\begin{itemize}
\item the number of special types of semigroups available in \textsf{MONOID} will be expanded to include all of the standard examples of transformation
semigroups and some matrix semigroups.
\item methods analogous to those used to find Green's relations and other structural
properties of transformation semigroups in the current version of \textsf{MONOID} but for semigroups generated by partial transformations, binary relations, and
matrix semigroups.
\item a suite of functions for computing with inverse semigroups generated by
partial bijections, including finding faithful representations of smaller
degree and small generating sets.
\item an algorithm for finding a small generating set of a semigroup.
\end{itemize}
}
}
\chapter{\textcolor{Chapter }{Transformations}}\label{general}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X860026B880BCB2A5}{}
{
The functions described in this section extend the functionality of \textsf{GAP} relating to transformations.
\section{\textcolor{Chapter }{Creating Transformations}}\logpage{[ 2, 1, 0 ]}
\hyperdef{L}{X80F3086F87E93DF8}{}
{
\subsection{\textcolor{Chapter }{TransformationByKernelAndImage}}\logpage{[ 2, 1, 1 ]}
\hyperdef{L}{X82CB17E47CBCFA69}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TransformationByKernelAndImage({\slshape ker, img})\index{TransformationByKernelAndImage@\texttt{TransformationByKernelAndImage}}
\label{TransformationByKernelAndImage}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TransformationByKernelAndImageNC({\slshape ker, img})\index{TransformationByKernelAndImageNC@\texttt{TransformationByKernelAndImageNC}}
\label{TransformationByKernelAndImageNC}
}\hfill{\scriptsize (operation)}}\\
returns the transformation \texttt{f} with kernel \texttt{ker} and image \texttt{img} where \texttt{(x)f=img[i]} for all \texttt{x} in \texttt{ker[i]}. The argument \texttt{ker} should be a set of sets that partition the set \texttt{1,...n} for some \texttt{n} and \texttt{img} should be a sublist of \texttt{1,...n}.
\texttt{TransformationByKernelAndImage} first checks that \texttt{ker} and \texttt{img} describe the kernel and image of a transformation whereas \texttt{TransformationByKernelAndImageNC} performs no such check.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> TransformationByKernelAndImageNC([[1,2,3,4],[5,6,7],[8]],[1,2,8]);
Transformation( [ 1, 1, 1, 1, 2, 2, 2, 8 ] )
gap> TransformationByKernelAndImageNC([[1,6],[2,5],[3,4]], [4,5,6]);
Transformation( [ 4, 5, 6, 6, 5, 4 ] )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{AllTransformationsWithKerAndImg}}\logpage{[ 2, 1, 2 ]}
\hyperdef{L}{X7D1937FF85B76BB3}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllTransformationsWithKerAndImg({\slshape ker, img})\index{AllTransformationsWithKerAndImg@\texttt{AllTransformationsWithKerAndImg}}
\label{AllTransformationsWithKerAndImg}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AllTransformationsWithKerAndImgNC({\slshape ker, img})\index{AllTransformationsWithKerAndImgNC@\texttt{AllTransformationsWithKerAndImgNC}}
\label{AllTransformationsWithKerAndImgNC}
}\hfill{\scriptsize (operation)}}\\
returns a list of all transformations with kernel \texttt{ker} and image \texttt{img}. The argument \texttt{ker} should be a set of sets that partition the set \texttt{1,...n} for some \texttt{n} and \texttt{img} should be a sublist of \texttt{1,...n}.
\texttt{AllTransformationsWithKerAndImg} first checks that \texttt{ker} and \texttt{img} describe the kernel and image of a transformation whereas \texttt{AllTransformationsWithKerAndImgNC} performs no such check.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> AllTransformationsWithKerAndImg([[1,6],[2,5],[3,4]], [4,5,6]);
[ Transformation( [ 4, 5, 6, 6, 5, 4 ] ),
Transformation( [ 6, 5, 4, 4, 5, 6 ] ),
Transformation( [ 6, 4, 5, 5, 4, 6 ] ),
Transformation( [ 4, 6, 5, 5, 6, 4 ] ),
Transformation( [ 5, 6, 4, 4, 6, 5 ] ),
Transformation( [ 5, 4, 6, 6, 4, 5 ] ) ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{Idempotent}}\logpage{[ 2, 1, 3 ]}
\hyperdef{L}{X85D1071484CE004C}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IdempotentNC({\slshape ker, img})\index{IdempotentNC@\texttt{IdempotentNC}}
\label{IdempotentNC}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Idempotent({\slshape ker, img})\index{Idempotent@\texttt{Idempotent}}
\label{Idempotent}
}\hfill{\scriptsize (function)}}\\
\texttt{IdempotentNC} returns an idempotent with kernel \texttt{ker} and image \texttt{img} without checking \texttt{IsTransversal} (\ref{IsTransversal}) with arguments \texttt{ker} and \texttt{im}.
\texttt{Idempotent} returns an idempotent with kernel \texttt{ker} and image \texttt{img} after checking that \texttt{IsTransversal} (\ref{IsTransversal}) with arguments \texttt{ker} and \texttt{im} returns \texttt{true}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([2,2,4,4,5,6]);;
gap> g2:=Transformation([5,3,4,4,6,6]);;
gap> ker:=KernelOfTransformation(g2*g1);;
gap> im:=ImageListOfTransformation(g2);;
gap> Idempotent(ker, im);
Error, the image must be a transversal of the kernel
[ ... ]
gap> Idempotent([[1,2,3],[4,5],[6,7]], [1,5,6]);
Transformation( [ 1, 1, 1, 5, 5, 6, 6 ] )
gap> IdempotentNC([[1,2,3],[4,5],[6,7]], [1,5,6]);
Transformation( [ 1, 1, 1, 5, 5, 6, 6 ] )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RandomIdempotent}}\logpage{[ 2, 1, 4 ]}
\hyperdef{L}{X7C5BED247F770ECB}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomIdempotent({\slshape arg})\index{RandomIdempotent@\texttt{RandomIdempotent}}
\label{RandomIdempotent}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomIdempotentNC({\slshape arg})\index{RandomIdempotentNC@\texttt{RandomIdempotentNC}}
\label{RandomIdempotentNC}
}\hfill{\scriptsize (operation)}}\\
If the argument is a kernel, then a random idempotent is return that has that
kernel. A \emph{kernel} is a set of sets that partition the set \texttt{1,...n} for some \texttt{n} and an \emph{image} is a sublist of \texttt{1,...n}.
If the first argument is an image \texttt{img} and the second a positive integer \texttt{n}, then a random idempotent of degree \texttt{n} is returned with image \texttt{img}.
The no check version does not check that the arguments can be the kernel and
image of an idempotent.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> RandomIdempotent([[1,2,3], [4,5], [6,7,8]], [1,2,3]);;
fail
gap> RandomIdempotent([1,2,3],5);
Transformation( [ 1, 2, 3, 1, 3 ] )
gap> RandomIdempotent([[1,6], [2,4], [3,5]]);
Transformation( [ 1, 2, 5, 2, 5, 1 ] )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RandomTransformation}}\logpage{[ 2, 1, 5 ]}
\hyperdef{L}{X8475448F87E8CB8A}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomTransformation({\slshape arg})\index{RandomTransformation@\texttt{RandomTransformation}}
\label{RandomTransformation}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomTransformationNC({\slshape arg})\index{RandomTransformationNC@\texttt{RandomTransformationNC}}
\label{RandomTransformationNC}
}\hfill{\scriptsize (operation)}}\\
These are new methods for the existing library function \texttt{RandomTransformation}.
If the first argument is a kernel and the second an image, then a random
transformation is returned with this kernel and image.A \emph{kernel} is a set of sets that partition the set \texttt{1,...n} for some \texttt{n} and an \emph{image} is a sublist of \texttt{1,...n}.
If the argument is a kernel, then a random transformation is returned that has
that kernel.
If the first argument is an image \texttt{img} and the second a positive integer \texttt{n}, then a random transformation of degree \texttt{n} is returned with image \texttt{img}.
The no check version does not check that the arguments can be the kernel and
image of a transformation.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> RandomTransformation([[1,2,3], [4,5], [6,7,8]], [1,2,3]);;
Transformation( [ 2, 2, 2, 1, 1, 3, 3, 3 ] )
gap> RandomTransformation([[1,2,3],[5,7],[4,6]]);
Transformation( [ 3, 3, 3, 6, 1, 6, 1 ] )
gap> RandomTransformation([[1,2,3],[5,7],[4,6]]);
Transformation( [ 4, 4, 4, 7, 3, 7, 3 ] )
gap> RandomTransformationNC([[1,2,3],[5,7],[4,6]]);
Transformation( [ 1, 1, 1, 7, 5, 7, 5 ] )
gap> RandomTransformation([1,2,3], 6);
Transformation( [ 2, 1, 2, 1, 1, 2 ] )
gap> RandomTransformationNC([1,2,3], 6);
Transformation( [ 3, 1, 2, 2, 1, 2 ] )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{TransformationActionNC}}
\logpage{[ 2, 1, 6 ]}\nobreak
\hyperdef{L}{X814B3E6E7D3F1036}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TransformationActionNC({\slshape list, act, elm})\index{TransformationActionNC@\texttt{TransformationActionNC}}
\label{TransformationActionNC}
}\hfill{\scriptsize (operation)}}\\
returns the list \texttt{list} acted on by \texttt{elm} via the action \texttt{act}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> mat:=OneMutable(GeneratorsOfGroup(GL(3,3))[1]);
[ [ Z(3)^0, 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3) ],
[ 0*Z(3), 0*Z(3), Z(3)^0 ] ]
gap> mat[3][3]:=Z(3)*0;
0*Z(3)
gap> F:=BaseDomain(mat);
GF(3)
gap> TransformationActionNC(Elements(F^3), OnRight, mat);
Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 10, 10, 10, 13, 13, 13, 16, 16,
16, 19, 19, 19, 22, 22, 22, 25, 25, 25 ] )
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Properties \& Attributes}}\logpage{[ 2, 2, 0 ]}
\hyperdef{L}{X84DD0B3981E5735B}{}
{
\subsection{\textcolor{Chapter }{IsTransversal}}
\logpage{[ 2, 2, 1 ]}\nobreak
\hyperdef{L}{X79E9FFC97AFCEE61}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsTransversal({\slshape list1, list2})\index{IsTransversal@\texttt{IsTransversal}}
\label{IsTransversal}
}\hfill{\scriptsize (function)}}\\
returns \texttt{true} if the list \texttt{list2} is a transversal of the list of lists \texttt{list1}. That is, if every list in \texttt{list1} contains exactly one element in \texttt{list2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([2,2,4,4,5,6]);;
gap> g2:=Transformation([5,3,4,4,6,6]);;
gap> ker:=KernelOfTransformation(g2*g1);
[ [ 1 ], [ 2, 3, 4 ], [ 5, 6 ] ]
gap> im:=ImageListOfTransformation(g2);
[ 5, 3, 4, 4, 6, 6 ]
gap> IsTransversal(ker, im);
false
gap> IsTransversal([[1,2,3],[4,5],[6,7]], [1,5,6]);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsKerImgOfTransformation}}
\logpage{[ 2, 2, 2 ]}\nobreak
\hyperdef{L}{X79A3FCED7E8A8B1B}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsKerImgOfTransformation({\slshape ker, img})\index{IsKerImgOfTransformation@\texttt{IsKerImgOfTransformation}}
\label{IsKerImgOfTransformation}
}\hfill{\scriptsize (function)}}\\
returns \texttt{true} if the arguments \texttt{ker} and \texttt{img} can be the kernel and image of a single transformation, respectively. The
argument \texttt{ker} should be a set of sets that partition the set \texttt{1,...n} for some \texttt{n} and \texttt{img} should be a sublist of \texttt{1,...n}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> ker:=[[1,2,3],[5,6],[8]];
[ [ 1, 2, 3 ], [ 5, 6 ], [ 8 ] ]
gap> img:=[1,2,9];
[ 1, 2, 9 ]
gap> IsKerImgOfTransformation(ker,img);
false
gap> ker:=[[1,2,3,4],[5,6,7],[8]];
[ [ 1, 2, 3, 4 ], [ 5, 6, 7 ], [ 8 ] ]
gap> IsKerImgOfTransformation(ker,img);
false
gap> img:=[1,2,8];
[ 1, 2, 8 ]
gap> IsKerImgOfTransformation(ker,img);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{KerImgOfTransformation}}
\logpage{[ 2, 2, 3 ]}\nobreak
\hyperdef{L}{X7E72E6117BFFC74E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KerImgOfTransformation({\slshape f})\index{KerImgOfTransformation@\texttt{KerImgOfTransformation}}
\label{KerImgOfTransformation}
}\hfill{\scriptsize (operation)}}\\
returns the kernel and image set of the transformation \texttt{f}. These attributes of \texttt{f} can be obtain separately using \texttt{KernelOfTransformation} (\textbf{Reference: KernelOfTransformation}) and \texttt{ImageSetOfTransformation} (\textbf{Reference: ImageSetOfTransformation}), respectively.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> t:=Transformation( [ 10, 8, 7, 2, 8, 2, 2, 6, 4, 1 ] );;
gap> KerImgOfTransformation(t);
[ [ [ 1 ], [ 2, 5 ], [ 3 ], [ 4, 6, 7 ], [ 8 ], [ 9 ], [ 10 ] ],
[ 1, 2, 4, 6, 7, 8, 10 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsRegularTransformation}}
\logpage{[ 2, 2, 4 ]}\nobreak
\hyperdef{L}{X7856A73E80DAF56F}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsRegularTransformation({\slshape S, f})\index{IsRegularTransformation@\texttt{IsRegularTransformation}}
\label{IsRegularTransformation}
}\hfill{\scriptsize (operation)}}\\
if \texttt{f} is a regular element of the transformation semigroup \texttt{S}, then \texttt{true} is returned. Otherwise \texttt{false} is returned.
A transformation \texttt{f} is regular inside a transformation semigroup \texttt{S} if it lies inside a regular D-class. This is equivalent to the orbit of the
image of \texttt{f} containing a transversal of the kernel of \texttt{f}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([2,2,4,4,5,6]);;
gap> g2:=Transformation([5,3,4,4,6,6]);;
gap> m1:=Monoid(g1,g2);;
gap> IsRegularTransformation(m1, g1);
true
gap> img:=ImageSetOfTransformation(g1);
[ 2, 4, 5, 6 ]
gap> ker:=KernelOfTransformation(g1);
[ [ 1, 2 ], [ 3, 4 ], [ 5 ], [ 6 ] ]
gap> ForAny(MonoidOrbit(m1, img), x-> IsTransversal(ker, x));
true
gap> IsRegularTransformation(m1, g2);
false
gap> IsRegularTransformation(FullTransformationSemigroup(6), g2);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IndexPeriodOfTransformation}}
\logpage{[ 2, 2, 5 ]}\nobreak
\hyperdef{L}{X863216CB7AF88BED}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IndexPeriodOfTransformation({\slshape f})\index{IndexPeriodOfTransformation@\texttt{IndexPeriodOfTransformation}}
\label{IndexPeriodOfTransformation}
}\hfill{\scriptsize (attribute)}}\\
returns the minimum numbers \texttt{m, r} such that \texttt{f\texttt{\symbol{94}}(m+r)=f\texttt{\symbol{94}}m}; known as the \emph{index} and \emph{period} of the transformation.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> f:=Transformation( [ 3, 4, 4, 6, 1, 3, 3, 7, 1 ] );;
gap> IndexPeriodOfTransformation(f);
[ 2, 3 ]
gap> f^2=f^5;
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{SmallestIdempotentPower}}
\logpage{[ 2, 2, 6 ]}\nobreak
\hyperdef{L}{X84E1A41F84B70DBB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SmallestIdempotentPower({\slshape f})\index{SmallestIdempotentPower@\texttt{SmallestIdempotentPower}}
\label{SmallestIdempotentPower}
}\hfill{\scriptsize (attribute)}}\\
returns the least natural number \texttt{n} such that the transformation \texttt{f\texttt{\symbol{94}}n} is an idempotent.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> t:=Transformation( [ 6, 7, 4, 1, 7, 4, 6, 1, 3, 4 ] );;
gap> SmallestIdempotentPower(t);
6
gap> t:=Transformation( [ 6, 6, 6, 2, 7, 1, 5, 3, 10, 6 ] );;
gap> SmallestIdempotentPower(t);
4
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{InversesOfTransformation}}\logpage{[ 2, 2, 7 ]}
\hyperdef{L}{X846B9EBB86A69BDC}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InversesOfTransformation({\slshape S, f})\index{InversesOfTransformation@\texttt{InversesOfTransformation}}
\label{InversesOfTransformation}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InversesOfTransformationNC({\slshape S, f})\index{InversesOfTransformationNC@\texttt{InversesOfTransformationNC}}
\label{InversesOfTransformationNC}
}\hfill{\scriptsize (operation)}}\\
returns a list of the inverses of the transformation \texttt{f} in the transformation semigroup \texttt{S}. The function \texttt{InversesOfTransformationNC} does not check that \texttt{f} is an element of \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=Semigroup([ Transformation( [ 3, 1, 4, 2, 5, 2, 1, 6, 1 ] ),
Transformation( [ 5, 7, 8, 8, 7, 5, 9, 1, 9 ] ),
Transformation( [ 7, 6, 2, 8, 4, 7, 5, 8, 3 ] ) ]);;
gap> f:=Transformation( [ 3, 1, 4, 2, 5, 2, 1, 6, 1 ] );;
gap> InversesOfTransformationNC(S, f);
[ ]
gap> IsRegularTransformation(S, f);
false
gap> f:=Transformation( [ 1, 9, 7, 5, 5, 1, 9, 5, 1 ] );;
gap> inv:=InversesOfTransformation(S, f);
[ Transformation( [ 1, 5, 1, 1, 5, 1, 3, 1, 2 ] ),
Transformation( [ 1, 5, 1, 2, 5, 1, 3, 2, 2 ] ),
Transformation( [ 1, 2, 3, 5, 5, 1, 3, 5, 2 ] ) ]
gap> IsRegularTransformation(S, f);
true
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Changing Representation}}\logpage{[ 2, 3, 0 ]}
\hyperdef{L}{X80B8EF3D78E711BB}{}
{
\subsection{\textcolor{Chapter }{AsBooleanMatrix}}
\logpage{[ 2, 3, 1 ]}\nobreak
\hyperdef{L}{X7F867C337B18D84E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AsBooleanMatrix({\slshape f[, n]})\index{AsBooleanMatrix@\texttt{AsBooleanMatrix}}
\label{AsBooleanMatrix}
}\hfill{\scriptsize (operation)}}\\
returns the transformation or permutation \texttt{f} represented as an \texttt{n} by \texttt{n} Boolean matrix where \texttt{i,f(i)}th entries equal \texttt{1} and all other entries are \texttt{0}.
If \texttt{f} is a transformation, then \texttt{n} is the size of the domain of \texttt{f}.
If \texttt{f} is a permutation, then \texttt{n} is the number of points moved by \texttt{f}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> t:=Transformation( [ 4, 2, 2, 1 ] );;
gap> AsBooleanMatrix(t);
[ [ 0, 0, 0, 1 ], [ 0, 1, 0, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ] ]
gap> t:=(1,4,5);;
gap> AsBooleanMatrix(t);
[ [ 0, 0, 0, 1, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1 ],
[ 1, 0, 0, 0, 0 ] ]
gap> AsBooleanMatrix(t,3);
fail
gap> AsBooleanMatrix(t,5);
[ [ 0, 0, 0, 1, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1 ],
[ 1, 0, 0, 0, 0 ] ]
gap> AsBooleanMatrix(t,6);
[ [ 0, 0, 0, 1, 0, 0 ], [ 0, 1, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{AsPermOfRange}}
\logpage{[ 2, 3, 2 ]}\nobreak
\hyperdef{L}{X7A249D7781F31C22}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AsPermOfRange({\slshape x})\index{AsPermOfRange@\texttt{AsPermOfRange}}
\label{AsPermOfRange}
}\hfill{\scriptsize (operation)}}\\
converts a transformation \texttt{x} that is a permutation of its image into that permutation.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> t:=Transformation([1,2,9,9,9,8,8,8,4]);
Transformation( [ 1, 2, 9, 9, 9, 8, 8, 8, 4 ] )
gap> AsPermOfRange(t);
(4,9)
gap> t*last;
Transformation( [ 1, 2, 4, 4, 4, 8, 8, 8, 9 ] )
gap> AsPermOfRange(last);
()
\end{Verbatim}
}
}
}
\chapter{\textcolor{Chapter }{Monoid Actions and Orbits }}\label{orbits}
\logpage{[ 3, 0, 0 ]}
\hyperdef{L}{X849149EF79F824D1}{}
{
\section{\textcolor{Chapter }{Introduction}}\logpage{[ 3, 1, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
The functions described in this section relate to how a transformation
semigroup acts on its underlying set.
Let \texttt{S} be a transformation semigroup of degree \texttt{n}. Then the \emph{orbit} of \texttt{i} in \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}} is the set of elements \texttt{j} in \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}} such that there exists \texttt{f} in \texttt{S} where \texttt{(i)f=j}. Note that the essential difference between monoid orbits and group orbits is
that monoid orbits do not describe an equivalence relation on \texttt{S}. In particular, the relation described by monoid orbits is not symmetric.
The \emph{strong orbit} of \texttt{i} in \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}} is the set of elements \texttt{j} in \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}} such that there exists \texttt{f, g} in \texttt{S} where \texttt{(i)f=j} and \texttt{(j)g=i}.
Recall that a \emph{grading} is a function \texttt{f} from a transformation semigroup \texttt{S} of degree \texttt{n} to the natural numbers such that if \texttt{s} in \texttt{S} and \texttt{X} is a subset of \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}}, then \texttt{(Xs)f} is at most \texttt{(X)f}. }
\section{\textcolor{Chapter }{Actions}}\logpage{[ 3, 2, 0 ]}
\hyperdef{L}{X833C5DA683E4EA15}{}
{
In addition to the actions define in the reference manual (\textbf{Reference: Basic Actions}) the following two actions are available in \textsf{MONOID}.
\subsection{\textcolor{Chapter }{OnTuplesOfSetsAntiAction}}
\logpage{[ 3, 2, 1 ]}\nobreak
\hyperdef{L}{X785CA2537B553454}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OnTuplesOfSetsAntiAction({\slshape tup, f})\index{OnTuplesOfSetsAntiAction@\texttt{OnTuplesOfSetsAntiAction}}
\label{OnTuplesOfSetsAntiAction}
}\hfill{\scriptsize (function)}}\\
returns the preimages of each of the sets in the tuple of sets \texttt{tup} under the transformation \texttt{f}. The tuple of sets \texttt{tup} can have any number of elements.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> f:=Transformation( [ 8, 7, 5, 3, 1, 3, 8, 8 ] );;
gap> OnTuplesOfSetsAntiAction([ [ 1, 2 ], [ 3 ], [ 4 ], [ 5 ] ], f);
[ [ 5 ], [ 4, 6 ], [ 3 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{OnKernelsAntiAction}}
\logpage{[ 3, 2, 2 ]}\nobreak
\hyperdef{L}{X849A43DE7AF3C639}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OnKernelsAntiAction({\slshape ker, f})\index{OnKernelsAntiAction@\texttt{OnKernelsAntiAction}}
\label{OnKernelsAntiAction}
}\hfill{\scriptsize (function)}}\\
returns the kernel of the product \texttt{f*g} of the transformation \texttt{f} with a transformation \texttt{g} having kernel \texttt{ker}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> f:=Transformation( [ 8, 7, 5, 3, 1, 3, 8, 8 ] );;
gap> OnKernelsAntiAction([ [ 1, 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6, 7, 8 ] ], f);
[ [ 1, 2, 7, 8 ], [ 3 ], [ 4, 6 ], [ 5 ] ]
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{General Orbits}}\logpage{[ 3, 3, 0 ]}
\hyperdef{L}{X8545BED37C1BD760}{}
{
The following functions allow the calculation of arbitrary orbits in
transformation semigroups. Several more specific orbits that are often useful
are given in Section \ref{specorbits}.
\subsection{\textcolor{Chapter }{MonoidOrbit}}
\logpage{[ 3, 3, 1 ]}\nobreak
\hyperdef{L}{X8647538A7C892DCB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MonoidOrbit({\slshape S, obj[, act]})\index{MonoidOrbit@\texttt{MonoidOrbit}}
\label{MonoidOrbit}
}\hfill{\scriptsize (operation)}}\\
returns the orbit of \texttt{obj} under the action \texttt{act} of the transformation semigroup \texttt{S}. Usually, \texttt{obj} would be a point, list of points, or list of lists, and \texttt{act} would be \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), \texttt{OnTuples} (\textbf{Reference: OnTuples}), or another action defined in (\textbf{Reference: Basic Actions}). The argument \texttt{act} can be any function.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> MonoidOrbit(S, 1);
[ 1, 3, 4, 2, 6 ]
gap> MonoidOrbit(S, [1,2], OnSets);
[ [ 1, 2 ], [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ]
gap> MonoidOrbit(S, [1,2], OnTuples);
[ [ 1, 2 ], [ 3, 3 ], [ 4, 4 ], [ 2, 2 ], [ 6, 6 ], [ 1, 1 ] ]
gap> MonoidOrbit(S, 2, OnPoints);
[ 2, 3, 4, 6, 1 ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{MonoidOrbits}}
\logpage{[ 3, 3, 2 ]}\nobreak
\hyperdef{L}{X7F6DD5368778DC55}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MonoidOrbits({\slshape S, list[, act]})\index{MonoidOrbits@\texttt{MonoidOrbits}}
\label{MonoidOrbits}
}\hfill{\scriptsize (operation)}}\\
returns a list of the orbits of the elements of \texttt{list} under the action \texttt{act} of the transformation semigroup \texttt{S} using the \texttt{MonoidOrbit} (\ref{MonoidOrbit}) function.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> MonoidOrbits(S, [1,2]);
[ [ 1, 3, 4, 2, 6 ], [ 2, 3, 4, 6, 1 ] ]
gap> MonoidOrbits(S, [[1,2], [2,3]], OnSets);
[ [ [ 1, 2 ], [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ],
[ [ 2, 3 ], [ 4, 6 ], [ 1, 3 ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{StrongOrbit}}
\logpage{[ 3, 3, 3 ]}\nobreak
\hyperdef{L}{X84E7C5037BA23DEE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{StrongOrbit({\slshape S, obj[, act]})\index{StrongOrbit@\texttt{StrongOrbit}}
\label{StrongOrbit}
}\hfill{\scriptsize (operation)}}\\
returns the strong orbit of \texttt{obj} under the action \texttt{act} of the transformation semigroup \texttt{S}. Usually, \texttt{obj} would be a point, list of points, or list of lists, and \texttt{act} would be \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), \texttt{OnTuples} (\textbf{Reference: OnTuples}), or another action defined in (\textbf{Reference: Basic Actions}). The argument \texttt{act} can be any function.
If the optional third argument \texttt{act} is not given and \texttt{obj} is a point, then \texttt{OnPoints} (\textbf{Reference: OnPoints}) is the default action.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> StrongOrbit(S, 4, OnPoints);
[ 1, 3, 2, 4, 6 ]
gap> StrongOrbit(S, 4);
[ 1, 3, 2, 4, 6 ]
gap> StrongOrbit(S, [2,3], OnSets);
[ [ 2, 3 ], [ 4, 6 ], [ 1, 3 ] ]
gap> StrongOrbit(S, [2,3], OnTuples);
[ [ 2, 3 ], [ 3, 2 ], [ 4, 6 ], [ 6, 4 ], [ 1, 3 ], [ 3, 1 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{StrongOrbits}}
\logpage{[ 3, 3, 4 ]}\nobreak
\hyperdef{L}{X7989C5CE8053CC70}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{StrongOrbits({\slshape S, obj[, act]})\index{StrongOrbits@\texttt{StrongOrbits}}
\label{StrongOrbits}
}\hfill{\scriptsize (operation)}}\\
returns a list of the strong orbits of the elements of \texttt{list} under the action \texttt{act} of the transformation semigroup \texttt{S} using the \texttt{StrongOrbit} (\ref{StrongOrbit}) function.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> StrongOrbits(S, [1..6]);
[ [ 1, 3, 2, 4, 6 ], [ 5 ] ]
gap> StrongOrbits(S, [[1,2],[2,3]], OnSets);
[ [ [ 1, 2 ] ], [ [ 2, 3 ], [ 4, 6 ], [ 1, 3 ] ] ]
gap> StrongOrbits(S, [[1,2],[2,3]], OnTuples);
[ [ [ 1, 2 ] ], [ [ 2, 3 ], [ 3, 2 ], [ 4, 6 ], [ 6, 4 ],
[ 1, 3 ], [ 3, 1 ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GradedOrbit}}
\logpage{[ 3, 3, 5 ]}\nobreak
\hyperdef{L}{X811F9D387CE86748}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GradedOrbit({\slshape S, obj[, act], grad})\index{GradedOrbit@\texttt{GradedOrbit}}
\label{GradedOrbit}
}\hfill{\scriptsize (operation)}}\\
returns the orbit of \texttt{obj} under the action \texttt{act} of the transformation semigroup \texttt{S} partitioned by the grading \texttt{grad}. That is, two elements lie in the same class if they have the same value
under \texttt{grad}.
(Recall that a \emph{grading} is a function \texttt{f} from a transformation semigroup \texttt{S} of degree \texttt{n} to the natural numbers such that if \texttt{s} in \texttt{S} and \texttt{X} is a subset of \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}}, then \texttt{(Xs)f} is at most \texttt{(X)f}. )
Note that this function will not check if \texttt{grad} actually defines a grading or not.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> GradedOrbit(S, [1,2], OnSets, Size);
[ [ [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ], [ [ 1, 2 ] ] ]
gap> GradedOrbit(S, [1,2], Size);
[ [ [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ], [ [ 1, 2 ] ] ]
gap> GradedOrbit(S, [1,3,4], OnTuples, function(x)
> if 1 in x then return 2;
> else return 1;
> fi;
> end);
[ [ [ 3, 2, 6 ], [ 2, 3, 4 ], [ 6, 4, 3 ], [ 4, 6, 2 ] ],
[ [ 1, 3, 4 ], [ 4, 6, 1 ], [ 3, 1, 6 ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{ShortOrbit}}
\logpage{[ 3, 3, 6 ]}\nobreak
\hyperdef{L}{X87F0AFE17E02E878}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ShortOrbit({\slshape S, obj[, act], grad})\index{ShortOrbit@\texttt{ShortOrbit}}
\label{ShortOrbit}
}\hfill{\scriptsize (operation)}}\\
returns the elements of the orbit of \texttt{obj} under the action \texttt{act} of the transformation semigroup \texttt{S} with the same value as \texttt{obj} under the grading \texttt{grad}.
(Recall that a \emph{grading} is a function \texttt{f} from a transformation semigroup \texttt{S} of degree \texttt{n} to the natural numbers such that if \texttt{s} in \texttt{S} and \texttt{X} is a subset of \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}}, then \texttt{(Xs)f} is at most \texttt{(X)f}. )
Note that this function will not check if \texttt{grad} actually defines a grading or not.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> ShortOrbit(S, [1,2], Size);
[ [ 1, 2 ] ]
gap> ShortOrbit(S, [2,4], Size);
[ [ 2, 4 ], [ 3, 6 ], [ 1, 4 ] ]
gap> ShortOrbit(S, [1,2], OnTuples, Size);
[ [ 1, 2 ], [ 3, 3 ], [ 4, 4 ], [ 2, 2 ], [ 6, 6 ], [ 1, 1 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GradedStrongOrbit}}
\logpage{[ 3, 3, 7 ]}\nobreak
\hyperdef{L}{X87632B32847A5B87}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GradedStrongOrbit({\slshape S, obj[, act], grad})\index{GradedStrongOrbit@\texttt{GradedStrongOrbit}}
\label{GradedStrongOrbit}
}\hfill{\scriptsize (operation)}}\\
returns the strong orbit of \texttt{obj} under the action \texttt{act} of the transformation semigroup \texttt{S} partitioned by the grading \texttt{grad}. That is, two elements lie in the same class if they have the same value
under \texttt{grad}.
(Recall that a \emph{grading} is a function \texttt{f} from a transformation semigroup \texttt{S} of degree \texttt{n} to the natural numbers such that if \texttt{s} in \texttt{S} and \texttt{X} is a subset of \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}}, then \texttt{(Xs)f} is at most \texttt{(X)f}. )
Note that this function will not check if \texttt{grad} actually defines a grading or not.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap> GradedStrongOrbit(S, [1,3,4], OnTuples, function(x)
> if 1 in x then return 2; else return 1; fi; end);
[ [ [ 3, 2, 6 ], [ 2, 3, 4 ], [ 6, 4, 3 ], [ 4, 6, 2 ] ],
[ [ 1, 3, 4 ], [ 4, 6, 1 ], [ 3, 1, 6 ] ] ]
gap> GradedStrongOrbit(S, [1,3,4], OnTuples, Size);
[ [ [ 1, 3, 4 ], [ 3, 2, 6 ], [ 4, 6, 1 ], [ 2, 3, 4 ], [ 6, 4, 3 ],
[ 4, 6, 2 ], [ 3, 1, 6 ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{ShortStrongOrbit}}
\logpage{[ 3, 3, 8 ]}\nobreak
\hyperdef{L}{X7C957B0B810C99F1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ShortStrongOrbit({\slshape S, obj[, act], grad})\index{ShortStrongOrbit@\texttt{ShortStrongOrbit}}
\label{ShortStrongOrbit}
}\hfill{\scriptsize (operation)}}\\
returns the elements of the orbit of \texttt{obj} under the action \texttt{act} of the transformation semigroup \texttt{S} with the same value as \texttt{obj} under the grading \texttt{grad}.
(Recall that a \emph{grading} is a function \texttt{f} from a transformation semigroup \texttt{S} of degree \texttt{n} to the natural numbers such that if \texttt{s} in \texttt{S} and \texttt{X} is a subset of \texttt{\texttt{\symbol{123}}1,...,n\texttt{\symbol{125}}}, then \texttt{(Xs)f} is at most \texttt{(X)f}. )
Note that this function will not check if \texttt{grad} actually defines a grading or not.
If the optional third argument \texttt{act} is not given, then \texttt{OnPoints} (\textbf{Reference: OnPoints}), \texttt{OnSets} (\textbf{Reference: OnSets}), or \texttt{OnSetsSets} (\textbf{Reference: OnSetsSets}) is used as the default action depending on what \texttt{obj} is.
Further details can be found in Algorithm A and B of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
gap> S:=Monoid(g1,g2,g3);;
gap>ShortStrongOrbit(S, [1,3,4], OnTuples, function(x)
> if 1 in x then return 2; else return 1; fi; end);
[ [ 1, 3, 4 ], [ 4, 6, 1 ], [ 3, 1, 6 ] ]
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Some Specific Orbits}}\label{specorbits}
\logpage{[ 3, 4, 0 ]}
\hyperdef{L}{X7EF224A884952A63}{}
{
The following specific orbits are used in the computation of Green's relations
and to test if an arbitrary transformation semigroup has a particular
property; see Chapter \ref{greens} and Chapter \ref{properties}.
\subsection{\textcolor{Chapter }{ImagesOfTransSemigroup}}
\logpage{[ 3, 4, 1 ]}\nobreak
\hyperdef{L}{X7DD82E597AE6CA98}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ImagesOfTransSemigroup({\slshape S[, n]})\index{ImagesOfTransSemigroup@\texttt{ImagesOfTransSemigroup}}
\label{ImagesOfTransSemigroup}
}\hfill{\scriptsize (attribute)}}\\
returns the set of all the image sets that elements of \texttt{S} admit. That is, the union of the orbits of the image sets of the generators of \texttt{S} under the action \texttt{OnSets} (\textbf{Reference: OnSets}).
If the optional second argument \texttt{n} (a positive integer) is present, then the list of image sets of size \texttt{n} is returned. If you are only interested in the images of a given size, then
the second version of the function will likely be faster.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=Semigroup([ Transformation( [ 6, 4, 4, 4, 6, 1 ] ),
> Transformation( [ 6, 5, 1, 6, 2, 2 ] ) ];;
gap> ImagesOfTransSemigroup(S, 6);
[ ]
gap> ImagesOfTransSemigroup(S, 5);
[ ]
gap> ImagesOfTransSemigroup(S, 4);
[ [ 1, 2, 5, 6 ] ]
gap> ImagesOfTransSemigroup(S, 3);
[ [ 1, 4, 6 ], [ 2, 5, 6 ] ]
gap> ImagesOfTransSemigroup(S, 2);
[ [ 1, 4 ], [ 2, 5 ], [ 2, 6 ], [ 4, 6 ] ]
gap> ImagesOfTransSemigroup(S, 1);
[ [ 1 ], [ 2 ], [ 4 ], [ 5 ], [ 6 ] ]
gap> ImagesOfTransSemigroup(S);
[ [ 1 ], [ 1, 2, 5, 6 ], [ 1, 4 ], [ 1, 4, 6 ], [ 2 ], [ 2, 5 ], [ 2, 5, 6 ],
[ 2, 6 ], [ 4 ], [ 4, 6 ], [ 5 ], [ 6 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GradedImagesOfTransSemigroup}}
\logpage{[ 3, 4, 2 ]}\nobreak
\hyperdef{L}{X8763B61787D60EB5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GradedImagesOfTransSemigroup({\slshape S})\index{GradedImagesOfTransSemigroup@\texttt{GradedImagesOfTransSemigroup}}
\label{GradedImagesOfTransSemigroup}
}\hfill{\scriptsize (attribute)}}\\
returns the set of all the image sets that elements of \texttt{S} admit in a list where the \texttt{i}th entry contains all the images with size \texttt{i} (including the empty list when there are no image sets with size \texttt{i}).
This is just the union of the orbits of the images of the generators of \texttt{S} under the action \texttt{OnSets} (\textbf{Reference: OnSets}) graded according to size.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 5, 1, 1, 1 ] ),
> Transformation( [ 4, 4, 5, 2, 2 ] ) ];;
gap> S:=Semigroup(gens);;
gap> GradedImagesOfTransSemigroup(S);
[ [ [ 1 ], [ 4 ], [ 2 ], [ 5 ] ], [ [ 1, 5 ], [ 2, 4 ] ], [ [ 2, 4, 5 ] ],
[ ], [ [ 1 .. 5 ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{KernelsOfTransSemigroup}}
\logpage{[ 3, 4, 3 ]}\nobreak
\hyperdef{L}{X785C76B28671B8FC}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KernelsOfTransSemigroup({\slshape S[, n]})\index{KernelsOfTransSemigroup@\texttt{KernelsOfTransSemigroup}}
\label{KernelsOfTransSemigroup}
}\hfill{\scriptsize (attribute)}}\\
returns the set of all the kernels that elements of \texttt{S} admit. This is just the union of the orbits of the kernels of the generators
of \texttt{S} under the action \texttt{OnKernelsAntiAction} (\ref{OnKernelsAntiAction}).
If the optional second argument \texttt{n} (a positive integer) is present, then the list of image sets of size \texttt{n} is returned. If you are only interested in the images of a given size, then
the second version of the function will likely be faster.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=Semigroup([ Transformation( [ 2, 4, 1, 2 ] ),
> Transformation( [ 3, 3, 4, 1 ] ) ]);
gap> KernelsOfTransSemigroup(S);
[ [ [ 1, 2 ], [ 3 ], [ 4 ] ], [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 2, 3 ],
[ 4 ] ],
[ [ 1, 2, 3, 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ], [ [ 1, 3, 4 ], [ 2 ] ],
[ [ 1, 4 ], [ 2 ], [ 3 ] ], [ [ 1, 4 ], [ 2, 3 ] ] ]
gap> KernelsOfTransSemigroup(S,1);
[ [ [ 1, 2, 3, 4 ] ] ]
gap> KernelsOfTransSemigroup(S,2);
[ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 2, 3 ], [ 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ],
[ [ 1, 3, 4 ], [ 2 ] ], [ [ 1, 4 ], [ 2, 3 ] ] ]
gap> KernelsOfTransSemigroup(S,3);
[ [ [ 1, 2 ], [ 3 ], [ 4 ] ], [ [ 1, 4 ], [ 2 ], [ 3 ] ] ]
gap> KernelsOfTransSemigroup(S,4);
[ ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GradedKernelsOfTransSemigroup}}
\logpage{[ 3, 4, 4 ]}\nobreak
\hyperdef{L}{X8550CC457B87C8C1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GradedKernelsOfTransSemigroup({\slshape S})\index{GradedKernelsOfTransSemigroup@\texttt{GradedKernelsOfTransSemigroup}}
\label{GradedKernelsOfTransSemigroup}
}\hfill{\scriptsize (attribute)}}\\
returns the set of all the kernels that elements of \texttt{S} admit in a list where the \texttt{i}th entry contains all the kernels with \texttt{i} classes (including the empty list when there are no kernels with \texttt{i} classes).
This is just the union of the orbits of the kernels of the generators of \texttt{S} under the action \texttt{OnKernelsAntiAction} (\ref{OnKernelsAntiAction}) graded according to size.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 1, 2, 1, 4 ] ),
> Transformation( [ 2, 5, 3, 2, 3 ] ) ];;
gap> S:=Semigroup(gens);;
gap> GradedKernelsOfTransSemigroup(S);
[ [ [ [ 1, 2, 3, 4, 5 ] ] ],
[ [ [ 1, 2, 4, 5 ], [ 3 ] ], [ [ 1, 4 ], [ 2, 3, 5 ] ],
[ [ 1, 2, 4 ], [ 3, 5 ] ] ],
[ [ [ 1, 2, 4 ], [ 3 ], [ 5 ] ], [ [ 1, 4 ], [ 2 ], [ 3, 5 ] ] ], [ ],
[ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{StrongOrbitOfImage}}
\logpage{[ 3, 4, 5 ]}\nobreak
\hyperdef{L}{X7E53FA7D85258453}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{StrongOrbitOfImage({\slshape S, f})\index{StrongOrbitOfImage@\texttt{StrongOrbitOfImage}}
\label{StrongOrbitOfImage}
}\hfill{\scriptsize (operation)}}\\
returns a triple where
\begin{itemize}
\item the first entry \texttt{imgs} is the strong orbit of the image set \texttt{A} of \texttt{f} under the action of \texttt{S}. That is, the set of image sets \texttt{B} of elements of \texttt{S} such that there exist \texttt{g,h} in \texttt{S} with \texttt{OnSets(A, g)=B} and \texttt{OnSet(B, h)=A}. If the strong orbit of the image of \texttt{f} has already been calculated, then the image of \texttt{f} might not be the first entry in the list \texttt{imgs}.
\item the second entry is a list of permutations \texttt{mults} such that \texttt{OnSets(imgs[i], mults[i])=imgs[1]}.
\item the third entry is the Right Schutzenberger group associated to the first
entry in the list \texttt{imgs} (that is, the group of permutations arising from elements of the semigroup
that stabilise the set \texttt{imgs[1]}).
\end{itemize}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 3, 5, 2, 5, 1 ] ),
> Transformation( [ 4, 3, 2, 1, 5 ] ) ];;
gap> S:=Semigroup(gens);;
gap> f:=Transformation( [ 2, 1, 1, 1, 5 ] );;
gap> StrongOrbitOfImage(S, f);
[ [ [ 1, 2, 5 ], [ 1, 3, 5 ], [ 1, 2, 3 ], [ 2, 3, 5 ], [ 2, 3, 4 ],
[ 2, 4, 5 ], [ 3, 4, 5 ] ],
[ (), (1,5,2,3), (1,2)(3,5,4), (1,3,2,5), (1,3)(2,5,4), (1,3,4,5,2),
(1,3,2,4) ], Group([ (), (2,5), (1,5) ]) ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{StrongOrbitsOfImages}}
\logpage{[ 3, 4, 6 ]}\nobreak
\hyperdef{L}{X80BA8DD07E0E00D5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{StrongOrbitsOfImages({\slshape S})\index{StrongOrbitsOfImages@\texttt{StrongOrbitsOfImages}}
\label{StrongOrbitsOfImages}
}\hfill{\scriptsize (attribute)}}\\
this is a mutable attribute that stores the result of \texttt{StrongOrbitOfImage} (\ref{StrongOrbitOfImage}) every time it is used. If \texttt{StrongOrbitOfImage} (\ref{StrongOrbitOfImage}) has not been invoked for \texttt{S}, then an error is returned.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 3, 5, 2, 5, 1 ] ),
> Transformation( [ 4, 3, 2, 1, 5 ] ) ];;
gap> S:=Semigroup(gens);;
gap> f:=Transformation( [ 2, 1, 1, 1, 5 ] );;
gap> StrongOrbitOfImage(S, f);;
gap> StrongOrbitsOfImages(S);
[ [ [ [ 1, 2, 5 ], [ 1, 3, 5 ], [ 1, 2, 3 ], [ 2, 3, 5 ], [ 2, 3, 4 ],
[ 2, 4, 5 ], [ 3, 4, 5 ] ] ],
[ [ (), (1,5,2,3), (1,2)(3,5,4), (1,3,2,5), (1,3)(2,5,4), (1,3,4,5,2),
(1,3,2,4) ] ], [ Group([ (), (2,5), (1,5) ]) ] ]
gap> f:=Transformation( [ 5, 5, 5, 5, 2 ] );
gap> StrongOrbitOfImage(S, f);;
gap> StrongOrbitsOfImages(S);
[ [ [ [ 1, 2, 5 ], [ 1, 3, 5 ], [ 1, 2, 3 ], [ 2, 3, 5 ], [ 2, 3, 4 ],
[ 2, 4, 5 ], [ 3, 4, 5 ] ],
[ [ 2, 5 ], [ 1, 5 ], [ 1, 3 ], [ 2, 3 ], [ 2, 4 ], [ 4, 5 ], [ 3, 5 ],
[ 1, 2 ], [ 3, 4 ] ] ],
[ [ (), (1,5,2,3), (1,2)(3,5,4), (1,3,2,5), (1,3)(2,5,4), (1,3,4,5,2),
(1,3,2,4) ],
[ (), (1,5,2), (1,2)(3,5,4), (2,5,4,3), (2,5,4), (2,3,4,5), (2,3),
(1,5,4,3), (2,3)(4,5) ] ],
[ Group([ (), (2,5), (1,5) ]), Group([ (), (2,5) ]) ] ]
\end{Verbatim}
}
}
}
\chapter{\textcolor{Chapter }{Green's Relations}}\label{greens}
\logpage{[ 4, 0, 0 ]}
\hyperdef{L}{X80C6C718801855E9}{}
{
\section{\textcolor{Chapter }{Introduction}}\logpage{[ 4, 1, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
This chapter contains instructions on how to use the functions for computing
Green's relations and related notions for transformation semigroups and
monoids that are implemented in \textsf{MONOID}.
The theory behind these algorithms is developed in \cite{pfeiffer1} and the algorithms themselves are described in \cite{pfeiffer2}. Another reference is \cite{lallement}.
Green's relations can be calculated when \textsf{MONOID} is loaded using the same commands that you would used when \textsf{MONOID} is not loaded; see (\textbf{Reference: Semigroups}). For example, in \textsf{GAP} with the \textsf{MONOID} package loaded:
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> a:=Transformation([2,1,1,2,1]);;
gap> b:=Transformation([3,4,3,4,4]);;
gap> c:=Transformation([3,4,3,4,3]);;
gap> d:=Transformation([4,3,3,4,4]);;
gap> S:=Semigroup(a,b,c,d);
<semigroup with 4 generators>
gap> GreensRClasses(S);
[ {Transformation( [ 2, 1, 1, 2, 1 ] )}, {Transformation( [ 1, 2, 1, 2, 2 ] )}
, {Transformation( [ 1, 2, 1, 2, 1 ] )},
{Transformation( [ 2, 1, 1, 2, 2 ] )} ]
\end{Verbatim}
Without the \textsf{MONOID} package loaded:
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> a:=Transformation([2,1,1,2,1]);;
gap> b:=Transformation([3,4,3,4,4]);;
gap> c:=Transformation([3,4,3,4,3]);;
gap> d:=Transformation([4,3,3,4,4]);;
gap> S:=Semigroup(a,b,c,d);
<semigroup with 4 generators>
gap> GreensRClasses(S);
[ {Transformation( [ 1, 2, 1, 2, 1 ] )}, {Transformation( [ 1, 2, 1, 2, 2 ] )}
, {Transformation( [ 1, 2, 2, 1, 1 ] )},
{Transformation( [ 1, 2, 2, 1, 2 ] )} ]
\end{Verbatim}
The only noticable differences are the representatives of the classes and the
order the classes appear in the list. These differences are caused by the
differences in the methods for \texttt{GreensRClasses} in \textsf{MONOID } and the \textsf{GAP} library.
Most of the commands in this section relate to how Green's relations are
calculated in \textsf{MONOID}. Although some of the commands might be used for other purposes, if all that
is required is to calculate Green's classes, relations and so on, then this is
done in the exactly the same way as described in the \textsf{GAP} manual; see (\textbf{Reference: Green's Relations}).
Due to inherent difficulties with computing Green's L- and D-classes, the
methods used to compute with Green's R-classes are the most efficient in \textsf{MONOID}. Thus wherever possible it is advisable to use the commands relating to
Green's R-classes rather than those relating to Green's L-classes, D-classes,
or H-classes.
For small examples of semigroups, say with fewer than 40 elements, it may be
more efficient to use the methods from the library than those in \textsf{MONOID}. This stems from the fact that there are higher overheads in the methods used
in \textsf{MONOID}. In either case, with such small examples computing Green's relations does
not take much time.
The methods in \textsf{MONOID} allow the computation of individual Green's classes without the need to
compute all the elements of the underlying semigroup. It is also possible to
compute all the R-classes, the number of elements and test membership in a
transformation semigroup without computing all the elements. This may be
useful if you want to study a very large semigroup where computing all the
elements of the semigroup is infeasible. }
\section{\textcolor{Chapter }{Data Structures}}\logpage{[ 4, 2, 0 ]}
\hyperdef{L}{X81F7D3887DA80890}{}
{
\subsection{\textcolor{Chapter }{GreensData}}
\logpage{[ 4, 2, 1 ]}\nobreak
\hyperdef{L}{X7B9C0CC77C24D4F8}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GreensData({\slshape C})\index{GreensData@\texttt{GreensData}}
\label{GreensData}
}\hfill{\scriptsize (operation)}}\\
\begin{itemize}
\item if \texttt{C} satisfies \texttt{IsGreensRClass} (\textbf{Reference: IsGreensRClass}), then \texttt{GreensData} returns the value of \texttt{GreensRClassData} (\ref{GreensRClassData}) with argument \texttt{C}.
\item if \texttt{C} satisfies \texttt{IsGreensLClass} (\textbf{Reference: IsGreensLClass}), then \texttt{GreensData} returns the value of \texttt{GreensLClassData} (\ref{GreensLClassData}) with argument \texttt{C}.
\item if \texttt{C} satisfies \texttt{IsGreensHClass} (\textbf{Reference: IsGreensHClass}), then \texttt{GreensData} returns the value of \texttt{GreensHClassData} (\ref{GreensHClassData}) with argument \texttt{C}.
\item if \texttt{C} satisfies \texttt{IsGreensDClass} (\textbf{Reference: IsGreensDClass}), then \texttt{GreensData} returns the value of \texttt{GreensDClassData} (\ref{GreensDClassData}) with argument \texttt{C}.
\end{itemize}
}
\subsection{\textcolor{Chapter }{GreensRClassData}}
\logpage{[ 4, 2, 2 ]}\nobreak
\hyperdef{L}{X833F00AE810DCF28}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GreensRClassData({\slshape C})\index{GreensRClassData@\texttt{GreensRClassData}}
\label{GreensRClassData}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{C} satisfies \texttt{IsGreensRClass} (\textbf{Reference: IsGreensRClass}), then \texttt{GreensRClassData} returns an object in the category \texttt{IsGreensRClassData} (\ref{IsGreensRClassData}) with representation \texttt{IsGreensRClassDataRep} (\ref{IsGreensRClassDataRep}) and the following four components:
\begin{itemize}
\item \texttt{rep} the representative of the $R$-class.
\item \texttt{strongorb} the strong orbit of the image of \texttt{rep} under the action of the semigroup on sets.
\item \texttt{perms} a list of permutations that map the image of \texttt{rep} to the corresponding image in \texttt{strongorb}, that is, \texttt{OnSets(strongorb[i], perms[i])=strongorb[1]}.
\item \texttt{schutz} the group of permutations arising from elements of the semigroup that
stabilise the image of \texttt{rep} (called the \emph{ (generalized) right Schutzenberger group}).
\end{itemize}
The components \texttt{strongorb}, \texttt{perms}, and \texttt{schutz} are obtained using the function \texttt{StrongOrbitOfImage} (\ref{StrongOrbitOfImage}). Further details can be found in Algorithm C, D, E, F, and U of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> a:=Transformation( [ 2, 1, 4, 5, 6, 3 ] );;
gap> b:=Transformation( [ 2, 3, 1, 5, 4, 1 ] );;
gap> M:=Semigroup(a,b);;
gap> rc:=GreensRClassOfElement(M, a*b*a);
{Transformation( [ 4, 1, 6, 5, 2, 2 ] )}
gap> GreensRClassData(rc);
GreensRClassData( Transformation( [ 4, 1, 6, 5, 2, 2 ] ), [ [ 1, 2, 4, 5, 6 ],
[ 1, 2, 3, 5, 6 ], [ 1, 2, 3, 4, 6 ], [ 1, 2, 3, 4, 5 ] ], [ (), (1,2)
(3,6,5,4), (3,5)(4,6), (1,6,3,2)(4,5) ], Group( [ (), (2,4,6), (2,6,4),
(1,2,6)(4,5) ] ) )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GreensLClassData}}
\logpage{[ 4, 2, 3 ]}\nobreak
\hyperdef{L}{X80A97BBB8273D151}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GreensLClassData({\slshape S, f})\index{GreensLClassData@\texttt{GreensLClassData}}
\label{GreensLClassData}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{C} satisfies \texttt{IsGreensLClass} (\textbf{Reference: IsGreensLClass}), then \texttt{GreensLClassData} returns an object in the category \texttt{IsGreensLClassData} (\ref{IsGreensLClassData}) with representation \texttt{IsGreensLClassDataRep} (\ref{IsGreensLClassDataRep}) and the following five components:
\begin{itemize}
\item \texttt{rep} the representative of the $L$-class.
\item \texttt{strongorb} the strong orbit of the kernel of \texttt{rep} under the action of the semigroup by \texttt{OnTuplesOfSetsAntiAction} (\ref{OnTuplesOfSetsAntiAction}).
\item \texttt{relts} a list of relations such that
\begin{verbatim} KernelOfTransformation(relts[i]*x)=strongorb[1]
\end{verbatim}
whenever \texttt{x} has
\begin{verbatim} KernelOfTransformation(x)=strongorb[i].
\end{verbatim}
\item \texttt{invrelts} the inverses of the relations \texttt{relts}, so that
\begin{verbatim} KernelOfTransformation(invrelts[i]*rep)=strongorb[i].
\end{verbatim}
\item \texttt{schutz} the (generalised) left Schutzenberger group.
\end{itemize}
Further details can be found in Algorithm G, H, I, and J of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 4, 1, 4, 5, 3 ] ),
> Transformation( [ 5, 3, 5, 4, 3 ] ) ];;
gap> S:=Semigroup(gens);;
gap> C:=GreensLClassOfElement(S, gens[1]*gens[2]*gens[1]);
{Transformation( [ 5, 3, 5, 4, 3 ] )}
gap> GreensLClassData(C);
GreensLClassData( Transformation( [ 5, 3, 5, 4, 3 ] ),
[ [ [ 1, 3 ], [ 2, 5 ], [ 4 ] ] ], [ Binary Relation on 5 points ],
[ Binary Relation on 5 points ], Group( [ (), (3,5,4), (3,5) ] ) )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GreensHClassData}}
\logpage{[ 4, 2, 4 ]}\nobreak
\hyperdef{L}{X8037C1BC7D372310}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GreensHClassData({\slshape S, f})\index{GreensHClassData@\texttt{GreensHClassData}}
\label{GreensHClassData}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{C} satisfies \texttt{IsGreensHClass} (\textbf{Reference: IsGreensHClass}), then \texttt{GreensLClassData} returns an object in the category \texttt{IsGreensHClassData} (\ref{IsGreensHClassData}) with representation \texttt{IsGreensHClassDataRep} (\ref{IsGreensHClassDataRep}) and the following two components:
\begin{itemize}
\item \texttt{rep} the representative of the $H$-class.
\item \texttt{schutz} the intersection of the left Schutzenberger group and right Schutzenberger
group of the $L$-class and $R$-class containing the representative \texttt{rep} (that is, the intersection of the \texttt{schutz} component of \texttt{GreensRClassData} (\ref{GreensRClassData}) and the \texttt{schutz} component of \texttt{GreensLClassData} (\ref{GreensLClassData})).
\end{itemize}
Further details can be found in Algorithm K, L, M, and N of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 2, 5, 2, 3 ] ),
> Transformation( [ 2, 5, 3, 5, 3 ] ) ];;
gap> S:=Semigroup(gens);;
gap> f:=Transformation( [ 5, 5, 3, 5, 3 ] );;
gap> GreensHClassData(GreensHClassOfElement(S, f));
GreensHClassData( Transformation( [ 5, 5, 3, 5, 3 ] ), Group( () ) )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{GreensDClassData}}
\logpage{[ 4, 2, 5 ]}\nobreak
\hyperdef{L}{X81940FB4814D25B7}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GreensDClassData({\slshape S, f})\index{GreensDClassData@\texttt{GreensDClassData}}
\label{GreensDClassData}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{C} satisfies \texttt{IsGreensDClass} (\textbf{Reference: IsGreensDClass}), then \texttt{GreensDClassData} returns an object in the category \texttt{IsGreensDClassData} (\ref{IsGreensDClassData}) with representation \texttt{IsGreensDClassDataRep} (\ref{IsGreensDClassDataRep}) and the following five components:
\begin{itemize}
\item \texttt{rep} the representative of the $D$-class.
\item \texttt{R} the result of \texttt{GreensRClassData} (\ref{GreensRClassData}) with argument \texttt{rep}.
\item \texttt{L} the result of \texttt{GreensLClassData} (\ref{GreensLClassData}) with argument \texttt{rep}.
\item \texttt{H} the result of \texttt{GreensHClassData} (\ref{GreensHClassData}) with argument \texttt{rep}.
\item \texttt{cosets} a transversal of right cosets of the Schutzenberger group of \texttt{H} in the Schutzenberger group of \texttt{R}.
\end{itemize}
Note that only the first three components are displayed. Further details can
be found in Algorithm O, P, Q, R, S, and T of \cite{pfeiffer2}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 4, 1, 5, 2, 4 ] ),
> Transformation( [ 4, 4, 1, 5, 3 ] ) ];;
gap> S:=Semigroup(gens);;
gap> f:=Transformation( [ 5, 5, 3, 3, 3 ] );;
gap> GreensDClassData(GreensDClassOfElement(S, f));
GreensDClassData( Transformation( [ 5, 5, 3, 3, 3
] ), GreensRClassData( Transformation( [ 5, 5, 3, 3, 3
] ) ), GreensLClassData( Transformation( [ 5, 5, 3, 3, 3 ] ) ) )
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsGreensData}}\logpage{[ 4, 2, 6 ]}
\hyperdef{L}{X82F882B37DFAA974}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensData({\slshape obj})\index{IsGreensData@\texttt{IsGreensData}}
\label{IsGreensData}
}\hfill{\scriptsize (Category)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensRClassData({\slshape obj})\index{IsGreensRClassData@\texttt{IsGreensRClassData}}
\label{IsGreensRClassData}
}\hfill{\scriptsize (Category)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensLClassData({\slshape obj})\index{IsGreensLClassData@\texttt{IsGreensLClassData}}
\label{IsGreensLClassData}
}\hfill{\scriptsize (Category)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensHClassData({\slshape obj})\index{IsGreensHClassData@\texttt{IsGreensHClassData}}
\label{IsGreensHClassData}
}\hfill{\scriptsize (Category)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensDClassData({\slshape obj})\index{IsGreensDClassData@\texttt{IsGreensDClassData}}
\label{IsGreensDClassData}
}\hfill{\scriptsize (Category)}}\\
returns \texttt{true} if \texttt{obj} lies in the category \texttt{IsGreensData}, \texttt{IsGreensRClassData}, \texttt{IsGreensLClassData}, \texttt{IsGreensHClassData}, \texttt{IsGreensDClassData}, respectively. The objects created using the functions \texttt{RClassData} (\ref{RClassData}), \texttt{LClassData} (\ref{LClassData}), \texttt{HClassData} (\ref{HClassData}), and \texttt{DClassData} (\ref{DClassData}) lie in the categories \texttt{IsGreensRClassData}, \texttt{IsGreensLClassData}, \texttt{IsGreensHClassData}, \texttt{IsGreensDClassData}, respectively, and all these categories are contained in the category \texttt{IsGreensData}. }
\subsection{\textcolor{Chapter }{XClassData}}\logpage{[ 4, 2, 7 ]}
\hyperdef{L}{X780966E58045F9E8}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RClassData({\slshape rec})\index{RClassData@\texttt{RClassData}}
\label{RClassData}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LClassData({\slshape rec})\index{LClassData@\texttt{LClassData}}
\label{LClassData}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{HClassData({\slshape rec})\index{HClassData@\texttt{HClassData}}
\label{HClassData}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DClassData({\slshape rec})\index{DClassData@\texttt{DClassData}}
\label{DClassData}
}\hfill{\scriptsize (function)}}\\
These function construct objects in the categories \texttt{IsGreensRClassData} (\ref{IsGreensRClassData}), \texttt{IsGreensLClassData} (\ref{IsGreensLClassData}), \texttt{IsGreensHClassData} (\ref{IsGreensHClassData}), and \texttt{IsGreensDClassData} (\ref{IsGreensDClassData}) subcategories of \texttt{IsGreensData} (\ref{IsGreensData}) using the output from \texttt{GreensRClassData} (\ref{GreensRClassData}), \texttt{GreensLClassData} (\ref{GreensLClassData}), \texttt{GreensHClassData} (\ref{GreensHClassData}), \texttt{GreensDClassData} (\ref{GreensDClassData}). }
\subsection{\textcolor{Chapter }{IsGreensXClassDataRep}}\logpage{[ 4, 2, 8 ]}
\hyperdef{L}{X81ECD8BE78E41393}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensRClassDataRep({\slshape obj})\index{IsGreensRClassDataRep@\texttt{IsGreensRClassDataRep}}
\label{IsGreensRClassDataRep}
}\hfill{\scriptsize (Representation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensLClassDataRep({\slshape obj})\index{IsGreensLClassDataRep@\texttt{IsGreensLClassDataRep}}
\label{IsGreensLClassDataRep}
}\hfill{\scriptsize (Representation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensHClassDataRep({\slshape obj})\index{IsGreensHClassDataRep@\texttt{IsGreensHClassDataRep}}
\label{IsGreensHClassDataRep}
}\hfill{\scriptsize (Representation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGreensDClassDataRep({\slshape obj})\index{IsGreensDClassDataRep@\texttt{IsGreensDClassDataRep}}
\label{IsGreensDClassDataRep}
}\hfill{\scriptsize (Representation)}}\\
returns \texttt{true} if \texttt{obj} has \texttt{IsGreensRClassDataRep}, \texttt{IsGreensLClassDataRep}, \texttt{IsGreensHClassDataRep}, or \texttt{IsGreensDClassDataRep}, respectively as a representation.
These representations each have several components detailed in \texttt{GreensRClassData} (\ref{GreensRClassData}), \texttt{GreensLClassData} (\ref{GreensLClassData}), \texttt{GreensHClassData} (\ref{GreensHClassData}), \texttt{GreensDClassData} (\ref{GreensDClassData}), respectively. }
\subsection{\textcolor{Chapter }{IsAssociatedSemigpTransSemigp}}
\logpage{[ 4, 2, 9 ]}\nobreak
\hyperdef{L}{X7F75BAA87A79F569}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAssociatedSemigpTransSemigp({\slshape C})\index{IsAssociatedSemigpTransSemigp@\texttt{IsAssociatedSemigpTransSemigp}}
\label{IsAssociatedSemigpTransSemigp}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{C} is a Green's class of a transformation semigroup and returns \texttt{false} otherwise.
This attribute is required so that a Green's class knowns that it belongs to a
transformation semigroup, so that the methods defined in the \textsf{MONOID} are used in preference to those in the library.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> a:=Transformation( [ 2, 1, 4, 5, 6, 3 ] );;
gap> b:=Transformation( [ 2, 3, 1, 5, 4, 1 ] );;
gap> M:=Semigroup(a,b);;
gap> GreensLClassOfElement(M,a);
{Transformation( [ 2, 1, 4, 5, 6, 3 ] )}
gap> IsAssociatedSemigpTransSemigp(last);
true
gap> f:=FreeSemigroup(3);;
gap> a:=f.1;; b:=f.2;; c:=f.3;;
gap> s:=f/[[a^2, a], [b^2,b], [c^2,c], [a*b,a], [b*a,b], [a*c,a],
> [c*a,c], [b*c,b],[c*b,c]];
<fp semigroup on the generators [ s1, s2, s3 ]>
gap> Size(s);
3
gap> GreensLClassOfElement(s,a);
{s1}
gap> IsAssociatedSemigpTransSemigp(last);
false
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{SchutzenbergerGroup}}
\logpage{[ 4, 2, 10 ]}\nobreak
\hyperdef{L}{X84F1321E8217D2A8}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SchutzenbergerGroup({\slshape D})\index{SchutzenbergerGroup@\texttt{SchutzenbergerGroup}}
\label{SchutzenbergerGroup}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{D} satisfies \texttt{IsGreensRClassData} (\ref{IsGreensRClassData}), \texttt{IsGreensLClassData} (\ref{IsGreensLClassData}), \texttt{IsGreensHClassData} (\ref{IsGreensHClassData}), or \texttt{IsGreensDClassData} (\ref{IsGreensDClassData}), then \texttt{SchutzenbergerGroup} returns the \texttt{schutz} component of \texttt{D}.
If \texttt{D} satisfies \texttt{IsGreensRClass} (\textbf{Reference: IsGreensRClass}), \texttt{IsGreensLClass} (\textbf{Reference: IsGreensLClass}), \texttt{IsGreensHClass} (\textbf{Reference: IsGreensHClass}), \texttt{IsGreensDClass} (\textbf{Reference: IsGreensDClass}), then \texttt{SchutzenbergerGroup} returns the \texttt{schutz} component of \texttt{GreensData} with argument \texttt{D}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 4, 4, 3, 5, 3 ] ),
> Transformation( [ 5, 1, 1, 4, 1 ] ),
> Transformation( [ 5, 5, 4, 4, 5 ] ) ];;
gap> f:=Transformation( [ 4, 5, 5, 5, 5 ] );;
gap> SchutzenbergerGroup(GreensDClassOfElement(S, f));
Group([ (), (4,5) ])
gap> SchutzenbergerGroup(GreensRClassOfElement(S, f));
Group([ (), (4,5) ])
gap> SchutzenbergerGroup(GreensLClassOfElement(S, f));
Group([ (), (4,5) ])
gap> SchutzenbergerGroup(GreensHClassOfElement(S, f));
Group([ (), (4,5) ])
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{Idempotents}}
\logpage{[ 4, 2, 11 ]}\nobreak
\hyperdef{L}{X7C651C9C78398FFF}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Idempotents({\slshape X[, n]})\index{Idempotents@\texttt{Idempotents}}
\label{Idempotents}
}\hfill{\scriptsize (function)}}\\
returns a list of the idempotents in the transformation semigroup or Green's
class \texttt{X}.
If the optional second argument \texttt{n} is present, then a list of the idempotents in \texttt{S} of rank \texttt{n} is returned. If you are only interested in the idempotents of a given rank,
then the second version of the function will likely be faster.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=Semigroup([ Transformation( [ 2, 3, 4, 1 ] ),
> Transformation( [ 3, 3, 1, 1 ] ) ]);;
gap> Idempotents(S, 1);
[ ]
gap> Idempotents(S, 2);
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ),
Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> Idempotents(S, 3);
[ ]
gap> Idempotents(S, 4);
[ Transformation( [ 1, 2, 3, 4 ] ) ]
gap> Idempotents(S);
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 2, 3, 4 ] ),
Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 2, 2, 4, 4 ] ),
Transformation( [ 4, 2, 2, 4 ] ) ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{PartialOrderOfDClasses}}
\logpage{[ 4, 2, 12 ]}\nobreak
\hyperdef{L}{X83F1C306846DF26B}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{PartialOrderOfDClasses({\slshape S})\index{PartialOrderOfDClasses@\texttt{PartialOrderOfDClasses}}
\label{PartialOrderOfDClasses}
}\hfill{\scriptsize (attribute)}}\\
returns the partial order of the \texttt{D}-classes of \texttt{S} as a directed graph in \textsf{GRAPE}, if it is installed, using the command
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
Graph(Group(()), [1..Length(GreensDClasses(S))], OnPoints, function(x,y)
return y in poset[x]; end, true); ;
\end{Verbatim}
where \texttt{y} in \texttt{poset[x]} if and only if \texttt{S\texttt{\symbol{94}}1yS\texttt{\symbol{94}}1} is a subset of \texttt{S\texttt{\symbol{94}}1 xS\texttt{\symbol{94}}1}.
If \textsf{GRAPE} is not loaded, then the list \texttt{poset} is returned instead. }
}
}
\chapter{\textcolor{Chapter }{Properties of Semigroups}}\label{properties}
\logpage{[ 5, 0, 0 ]}
\hyperdef{L}{X78274024827F306D}{}
{
\section{\textcolor{Chapter }{Introduction}}\logpage{[ 5, 1, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
In this section we give the theoretical results and the corresponding \textsf{GAP} functions that can be used to determine whether a set of transformations
generates a semigroup of a given type. Let \texttt{S} be a semigroup. Then
\begin{itemize}
\item \texttt{S} is a \emph{left zero semigroup} if \texttt{xy=x} for all \texttt{x,y} in \texttt{S}.
\item \texttt{S} is a \emph{right zero semigroup} if \texttt{xy=y} for all \texttt{x,y} in \texttt{S}.
\item \texttt{S} is \emph{commutative} if \texttt{xy=yx} for all \texttt{x,y} in \texttt{S}.
\item \texttt{S} is \emph{simple} if it has no proper two-sided ideals.
\item \texttt{S} is \emph{regular} if for all \texttt{x} in \texttt{S} there exists \texttt{y} in \texttt{S} such that \texttt{xyx=x}.
\item \texttt{S} is \emph{completely regular} if every element of \texttt{S} lies in a subgroup.
\item \texttt{S} is an \emph{inverse semigroup} if for all elements \texttt{x} in \texttt{S} there exists a unique semigroup inverse, that is, a unique element \texttt{y} such that \texttt{xyx=x} and \texttt{yxy=y}.
\item \texttt{S} is a \emph{Clifford semigroup} if it is a regular semigroup whose idempotents are central, that is, for all \texttt{e} in \texttt{S} with \texttt{e\texttt{\symbol{94}}2=e} and \texttt{x} in \texttt{S} we have that \texttt{ex=xe}.
\item \texttt{S} is a \emph{band} if every element is an idempotent, that is, \texttt{x\texttt{\symbol{94}}2=x} for all \texttt{x} in \texttt{S}.
\item \texttt{S} is a \emph{rectangular band} if for all \texttt{x,y,z} in \texttt{S} we have that \texttt{x\texttt{\symbol{94}}2=x} and \texttt{xyz=xz}.
\item \texttt{S} is a \emph{semiband} if it is generated by its idempotent elements, that is, elements satisfying \texttt{x\texttt{\symbol{94}}2=x}.
\item \texttt{S} is an \emph{orthodox semigroup} if its idempotents (elements satisfying \texttt{x\texttt{\symbol{94}}2=x}) form a subsemigroup.
\item \texttt{S} is a \emph{zero semigroup} if there exists an element \texttt{0} in \texttt{S} such that \texttt{xy=0} for all \texttt{x,y} in \texttt{S}.
\item \texttt{S} is a \emph{zero group} if there exists an element \texttt{0} in \texttt{S} such that \texttt{S} without \texttt{0} is a group and for all \texttt{x} in \texttt{S} we have that \texttt{x0=0x=0}.
\end{itemize}
The following results provide efficient methods to determine if an arbitrary
transformation semigroup is a left zero, right zero, simple, completely
regular, inverse or Clifford semigroup. Proofs of these results can be found
in \cite{largest}.
Let \texttt{S} be a semigroup generated by a set of transformations \texttt{U} on a finite set. Then the following hold:
\begin{itemize}
\item \texttt{S} is a left zero semigroup if and only if for all \texttt{f, g} in \texttt{U} the image of \texttt{f} equals the image of \texttt{g} and \texttt{f\texttt{\symbol{94}}2=f}.
\item \texttt{S} is a right zero semigroup if and only if for all \texttt{f, g} in \texttt{U} the kernel of \texttt{f} equals the kernel of \texttt{g} and \texttt{f\texttt{\symbol{94}}2=f}.
\item \texttt{S} is simple if and only if for all \texttt{f, g} in \texttt{U} every class of the kernel of \texttt{f} contains exactly \texttt{1} element of the image of \texttt{g}.
\item \texttt{S} is completely regular if and only if for all \texttt{f} in \texttt{U} and \texttt{g} in \texttt{S}, every class of the kernel of \texttt{f} contains at most \texttt{1} element of the set found by applying \texttt{g} to the image of \texttt{f}.
\item \texttt{S} is inverse if and only if it is regular and there is a bijection \texttt{\texttt{\symbol{92}}phi} from the set of kernels of elements of \texttt{S} to the set of images of elements of \texttt{S} such that every class of a kernel \texttt{K} contains exactly \texttt{1} element in \texttt{(K)\texttt{\symbol{92}}phi}.
\item \texttt{S} is a Clifford semigroup if and only if for all \texttt{f, g} in \texttt{U}
\begin{itemize}
\item \texttt{f} permutes its image
\item \texttt{f} commutes with the power of \texttt{g} that acts as the identity on its image.
\end{itemize}
\end{itemize}
It is straightforward to verify that a transformation semigroup \texttt{S} generated by \texttt{U} is a group if and only if for all \texttt{f, g} in \texttt{U}
\begin{itemize}
\item the kernel of \texttt{f} equals the kernel of \texttt{g}.
\item the image of \texttt{f} equals the image of \texttt{g}.
\item \texttt{f} permutes its image.
\end{itemize}
At first glance it might not be obvious why these conditions are an
improvement over the original definitions. The main point is that it can be
easily determined whether a semigroup \texttt{S} generated by a set \texttt{U} of mappings satisfies these conditions by considering the generators \texttt{U} and their action on the underlying set only. }
\section{\textcolor{Chapter }{Property Tests}}\logpage{[ 5, 2, 0 ]}
\hyperdef{L}{X86E50CE27AB1317A}{}
{
\subsection{\textcolor{Chapter }{IsCompletelyRegularSemigroup}}
\logpage{[ 5, 2, 1 ]}\nobreak
\hyperdef{L}{X7AFA23AF819FBF3D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsCompletelyRegularSemigroup({\slshape S})\index{IsCompletelyRegularSemigroup@\texttt{IsCompletelyRegularSemigroup}}
\label{IsCompletelyRegularSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is completely regular and \texttt{false} otherwise.
A semigroup is \emph{completely regular} if every element is contained in a subgroup.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 2, 4, 3, 6, 5, 4 ] ),
> Transformation( [ 1, 2, 5, 6, 3, 4, 5 ] ),
> Transformation( [ 2, 1, 2, 2, 2, 2, 2 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsCompletelyRegularSemigroup(S);
true
gap> S:=RandomSemigroup(5,5);;
gap> IsSimpleSemigroup(S);
false
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsSimpleSemigroup}}\logpage{[ 5, 2, 2 ]}
\hyperdef{L}{X836F4692839F4874}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsSimpleSemigroup({\slshape S})\index{IsSimpleSemigroup@\texttt{IsSimpleSemigroup}}
\label{IsSimpleSemigroup}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsCompletelySimpleSemigroup({\slshape S})\index{IsCompletelySimpleSemigroup@\texttt{IsCompletelySimpleSemigroup}}
\label{IsCompletelySimpleSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is simple and \texttt{false} otherwise.
A semigroup is \emph{simple} if it has no proper 2-sided ideals. A semigroup is \emph{completely simple} if it is simple and possesses minimal left and right ideals. A finite
semigroup is simple if and only if it is completely simple.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 2 ] ),
> Transformation( [ 1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 3 ] ),
> Transformation( [ 1, 7, 3, 9, 5, 11, 7, 1, 9, 3, 11, 5, 5 ] ),
> Transformation( [ 7, 7, 9, 9, 11, 11, 1, 1, 3, 3, 5, 5, 7 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsSimpleSemigroup(S);
true
gap> IsCompletelySimpleSemigroup(S);
true
gap> S:=RandomSemigroup(5,5);;
gap> IsSimpleSemigroup(S);
false
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsGroupAsSemigroup}}
\logpage{[ 5, 2, 3 ]}\nobreak
\hyperdef{L}{X852F29E8795FA489}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGroupAsSemigroup({\slshape S})\index{IsGroupAsSemigroup@\texttt{IsGroupAsSemigroup}}
\label{IsGroupAsSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a group and \texttt{false} otherwise.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ),
> Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsGroupAsSemigroup(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsCommutativeSemigroup}}
\logpage{[ 5, 2, 4 ]}\nobreak
\hyperdef{L}{X843EFDA4807FDC31}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsCommutativeSemigroup({\slshape S})\index{IsCommutativeSemigroup@\texttt{IsCommutativeSemigroup}}
\label{IsCommutativeSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is commutative and \texttt{false} otherwise. The function \texttt{IsCommutative} (\textbf{Reference: IsCommutative}) can also be used to test if a semigroup is commutative.
A semigroup \texttt{S} is \emph{commutative} if \texttt{xy=yx} for all \texttt{x,y} in \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ),
> Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsCommutativeSemigroup(S);
true
gap> IsCommutative(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsRegularSemigroup}}
\logpage{[ 5, 2, 5 ]}\nobreak
\hyperdef{L}{X7C4663827C5ACEF1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsRegularSemigroup({\slshape S})\index{IsRegularSemigroup@\texttt{IsRegularSemigroup}}
\label{IsRegularSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a regular semigroup and \texttt{false} otherwise. The algorithm used here is essentially the same algorithm as that
used for \texttt{GreensRClasses} (\textbf{Reference: GreensRClasses}) in \textsf{MONOID}. If \texttt{S} is regular, then \texttt{S} will have the attribute \texttt{GreensRClasses} after \texttt{IsRegularSemigroup} is invoked.
A semigroup \texttt{S} is \emph{regular} if for all \texttt{x} in \texttt{S} there exists \texttt{y} in \texttt{S} such that \texttt{xyx=x}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> IsRegularSemigroup(FullTransformationSemigroup(5));
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsInverseSemigroup}}
\logpage{[ 5, 2, 6 ]}\nobreak
\hyperdef{L}{X83F1529479D56665}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsInverseSemigroup({\slshape S})\index{IsInverseSemigroup@\texttt{IsInverseSemigroup}}
\label{IsInverseSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is an inverse semigroup and \texttt{false} otherwise.
A semigroup \texttt{S} is an \emph{inverse semigroup} if every element \texttt{x} in \texttt{S} has a unique semigroup inverse, that is, a unique element \texttt{y} such that \texttt{xyx=x} and \texttt{yxy=y}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[Transformation([1,2,4,5,6,3,7,8]),
> Transformation([3,3,4,5,6,2,7,8]),
>Transformation([1,2,5,3,6,8,4,4])];;
gap> S:=Semigroup(gens);;
gap> IsInverseSemigroup(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsCliffordSemigroup}}
\logpage{[ 5, 2, 7 ]}\nobreak
\hyperdef{L}{X81DE11987BB81017}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsCliffordSemigroup({\slshape S})\index{IsCliffordSemigroup@\texttt{IsCliffordSemigroup}}
\label{IsCliffordSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a Clifford semigroup and \texttt{false} otherwise.
A semigroup \texttt{S} is a \emph{Clifford semigroup} if it is a regular semigroup whose idempotents are central, that is, for all \texttt{e} in \texttt{S} with \texttt{e\texttt{\symbol{94}}2=e} and \texttt{x} in \texttt{S} we have that \texttt{ex=xe}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[Transformation([1,2,4,5,6,3,7,8]),
> Transformation([3,3,4,5,6,2,7,8]),
>Transformation([1,2,5,3,6,8,4,4])];;
gap> S:=Semigroup(gens);;
gap> IsCliffordSemigroup(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsBand}}
\logpage{[ 5, 2, 8 ]}\nobreak
\hyperdef{L}{X7C8DB14587D1B55A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsBand({\slshape S})\index{IsBand@\texttt{IsBand}}
\label{IsBand}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a band and \texttt{false} otherwise.
A semigroup \texttt{S} is a \emph{band} if every element is an idempotent, that is, \texttt{x\texttt{\symbol{94}}2=x} for all \texttt{x} in \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ),
> Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ),
> Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ),
> Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ),
> Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsBand(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsRectangularBand}}
\logpage{[ 5, 2, 9 ]}\nobreak
\hyperdef{L}{X7E9B674D781B072C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsRectangularBand({\slshape S})\index{IsRectangularBand@\texttt{IsRectangularBand}}
\label{IsRectangularBand}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a rectangular band and \texttt{false} otherwise.
A semigroup \texttt{S} is a \emph{rectangular band} if for all \texttt{x,y,z} in \texttt{S} we have that \texttt{x\texttt{\symbol{94}}2=x} and \texttt{xyz=xz}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ),
> Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ),
> Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ),
> Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ),
> Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsRectangularBand(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsSemiBand}}
\logpage{[ 5, 2, 10 ]}\nobreak
\hyperdef{L}{X8434E7C287DBFE1B}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsSemiBand({\slshape S})\index{IsSemiBand@\texttt{IsSemiBand}}
\label{IsSemiBand}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a semiband and \texttt{false} otherwise.
A semigroup \texttt{S} is a \emph{semiband} if it is generated by its idempotent elements, that is, elements satisfying \texttt{x\texttt{\symbol{94}}2=x}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=FullTransformationSemigroup(4);;
gap> x:=Transformation( [ 1, 2, 3, 1 ] );;
gap> D:=GreensDClassOfElement(S, x);;
gap> T:=Semigroup(Elements(D));;
gap> IsSemiBand(T);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsOrthodoxSemigroup}}
\logpage{[ 5, 2, 11 ]}\nobreak
\hyperdef{L}{X7935C476808C8773}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsOrthodoxSemigroup({\slshape S})\index{IsOrthodoxSemigroup@\texttt{IsOrthodoxSemigroup}}
\label{IsOrthodoxSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is orthodox and \texttt{false} otherwise.
A semigroup is an \emph{orthodox semigroup} if its idempotent elements form a subsemigroup.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 1, 1, 4, 5, 4 ] ),
> Transformation( [ 1, 2, 3, 1, 1, 2 ] ),
> Transformation( [ 1, 2, 3, 1, 1, 3 ] ),
> Transformation( [ 5, 5, 5, 5, 5, 5 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsOrthodoxSemigroup(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsRightZeroSemigroup}}
\logpage{[ 5, 2, 12 ]}\nobreak
\hyperdef{L}{X7CB099958658F979}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsRightZeroSemigroup({\slshape S})\index{IsRightZeroSemigroup@\texttt{IsRightZeroSemigroup}}
\label{IsRightZeroSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a right zero semigroup and \texttt{false} otherwise.
A semigroup \texttt{S} is a \emph{right zero semigroup} if \texttt{xy=y} for all \texttt{x,y} in \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 1, 4, 3, 5 ] ),
> Transformation( [ 3, 2, 3, 1, 1 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsRightZeroSemigroup(S);
false
gap> gens:=[Transformation( [ 1, 2, 3, 3, 1 ] ),
> Transformation( [ 1, 2, 4, 4, 1 ] )];;
gap> S:=Semigroup(gens);;
gap> IsRightZeroSemigroup(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsLeftZeroSemigroup}}
\logpage{[ 5, 2, 13 ]}\nobreak
\hyperdef{L}{X7E9261367C8C52C0}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsLeftZeroSemigroup({\slshape S})\index{IsLeftZeroSemigroup@\texttt{IsLeftZeroSemigroup}}
\label{IsLeftZeroSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a left zero semigroup and \texttt{false} otherwise.
A semigroup \texttt{S} is a \emph{left zero semigroup} if \texttt{xy=x} for all \texttt{x,y} in \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 1, 4, 3, 5 ] ),
> Transformation( [ 3, 2, 3, 1, 1 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsRightZeroSemigroup(S);
false
gap> gens:=[Transformation( [ 1, 2, 3, 3, 1 ] ),
> Transformation( [ 1, 2, 3, 3, 3 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsLeftZeroSemigroup(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsZeroSemigroup}}
\logpage{[ 5, 2, 14 ]}\nobreak
\hyperdef{L}{X81A1882181B75CC9}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsZeroSemigroup({\slshape S})\index{IsZeroSemigroup@\texttt{IsZeroSemigroup}}
\label{IsZeroSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a zero semigroup or if \texttt{S} was created using the \texttt{ZeroSemigroup} (\ref{ZeroSemigroup}) command. Otherwise \texttt{false} is returned.
A semigroup \texttt{S} is a \emph{zero semigroup} if there exists an element \texttt{0} in \texttt{S} such that \texttt{xy=0} for all \texttt{x,y} in \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 4, 7, 6, 3, 1, 5, 3, 6, 5, 9 ] ),
> Transformation( [ 5, 3, 5, 1, 9, 3, 8, 7, 4, 3 ] ),
> Transformation( [ 5, 10, 10, 1, 7, 6, 6, 8, 7, 7 ] ),
> Transformation( [ 7, 4, 3, 3, 2, 2, 3, 2, 9, 3 ] ),
> Transformation( [ 8, 1, 3, 4, 9, 6, 3, 7, 1, 6 ] ) ];;
gap> S:=Semigroup(gens);;
gap> IsZeroSemigroup(S);
false
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsZeroGroup}}
\logpage{[ 5, 2, 15 ]}\nobreak
\hyperdef{L}{X85F7E5CD86F0643B}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsZeroGroup({\slshape S})\index{IsZeroGroup@\texttt{IsZeroGroup}}
\label{IsZeroGroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the transformation semigroup \texttt{S} is a zero group or if \texttt{S} was created using the \texttt{ZeroGroup} (\ref{ZeroGroup}) command. Otherwise \texttt{false} is returned.
A semigroup \texttt{S} \texttt{S} is a \emph{zero group} if there exists an element \texttt{0} in \texttt{S} such that \texttt{S} without \texttt{0} is a group and for all \texttt{x} in \texttt{S} we have that \texttt{x0=0x=0}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=ZeroGroup(DihedralGroup(10));;
gap> iso:=IsomorphismTransformationSemigroup(S);;
gap> T:=Range(iso);;
gap> IsZeroGroup(T);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{MultiplicativeZero}}
\logpage{[ 5, 2, 16 ]}\nobreak
\hyperdef{L}{X7B39F93C8136D642}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MultiplicativeZero({\slshape S})\index{MultiplicativeZero@\texttt{MultiplicativeZero}}
\label{MultiplicativeZero}
}\hfill{\scriptsize (property)}}\\
returns the multiplicative zero of the transformation semigroup \texttt{S} if it has one and returns \texttt{fail} otherwise.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 4, 2, 6, 6, 5, 2 ] ),
> Transformation( [ 1, 6, 3, 6, 2, 1, 6 ] ) ];;
gap> S:=Semigroup(gens);;
gap> MultiplicativeZero(S);
Transformation( [ 1, 1, 1, 1, 1, 1, 1 ] )
\end{Verbatim}
}
}
}
\chapter{\textcolor{Chapter }{Special Classes of Semigroup}}\label{special}
\logpage{[ 6, 0, 0 ]}
\hyperdef{L}{X853D15F87F14D36E}{}
{
In this chapter functions for creating certain semigroups are given.
\section{\textcolor{Chapter }{Some Classes of Semigroup}}\label{trans}
\logpage{[ 6, 1, 0 ]}
\hyperdef{L}{X849A9EB37CF9BBB0}{}
{
\subsection{\textcolor{Chapter }{SingularSemigroup}}
\logpage{[ 6, 1, 1 ]}\nobreak
\hyperdef{L}{X79B1A1127B3B784A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SingularSemigroup({\slshape n})\index{SingularSemigroup@\texttt{SingularSemigroup}}
\label{SingularSemigroup}
}\hfill{\scriptsize (function)}}\\
creates the semigroup of singular transformations of degree \texttt{n}. That is, the semigroup of all transformations of the \texttt{n}-element set \texttt{ \texttt{\symbol{123}}1,2,...,n\texttt{\symbol{125}}} that are non-invertible.
This semigroup is known to be regular, idempotent generated (satisfies \texttt{IsSemiBand} (\ref{IsSemiBand})), and has size \texttt{n\texttt{\symbol{94}}n-n!}.
The generators used here are the idempotents of rank \texttt{n-1}, so there are \texttt{n(n-1)} generators in total.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=SingularSemigroup(6);
<semigroup with 30 generators>
gap> Size(S);
45936
gap> IsRegularSemigroup(S);
true
gap> IsSemiBand(S);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{OrderPreservingSemigroup}}
\logpage{[ 6, 1, 2 ]}\nobreak
\hyperdef{L}{X87554F5A85484046}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrderPreservingSemigroup({\slshape n})\index{OrderPreservingSemigroup@\texttt{OrderPreservingSemigroup}}
\label{OrderPreservingSemigroup}
}\hfill{\scriptsize (operation)}}\\
returns the semigroup of order preserving transformations of the \texttt{n}- element set \texttt{\texttt{\symbol{123}}1,2,...,n\texttt{\symbol{125}}}. That is, the mappings \texttt{f} such that \texttt{i} is at most \texttt{j} implies \texttt{f(i)} is at most \texttt{f(j)} for all \texttt{i,j} in \texttt{\texttt{\symbol{123}}1,2,...,n\texttt{\symbol{125}}}.
This semigroup is known to be regular, idempotent generated (satisfies \texttt{IsSemiBand} (\ref{IsSemiBand})), and has size \texttt{Binomial(2*n-1, n-1)}. The generators and relations used here are those specified by Aizenstat as
given in \cite{arthur1} and \cite{gomes1}. That is, \texttt{OrderPreservingSemigroup(n)} has the \texttt{2n-2} idempotent generators
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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]), ...
\end{Verbatim}
and the presentation obtained using \texttt{IsomorphismFpMonoid} (\ref{IsomorphismFpMonoid}) has relations
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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.
\end{Verbatim}
\\
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{KiselmanSemigroup}}
\logpage{[ 6, 1, 3 ]}\nobreak
\hyperdef{L}{X7A6FC6F179394E66}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KiselmanSemigroup({\slshape n})\index{KiselmanSemigroup@\texttt{KiselmanSemigroup}}
\label{KiselmanSemigroup}
}\hfill{\scriptsize (operation)}}\\
returns the Kiselman semigroup with \texttt{n} generators. That is, the semigroup defined in \cite{mazorchuk} with the presentation
\[ <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)>. \]
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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>
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Zero Groups and Zero Semigroups}}\label{zeros}
\logpage{[ 6, 2, 0 ]}
\hyperdef{L}{X7A88BC6E7AC4E444}{}
{
\subsection{\textcolor{Chapter }{ZeroSemigroup}}
\logpage{[ 6, 2, 1 ]}\nobreak
\hyperdef{L}{X801FC1D97D832A6F}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroSemigroup({\slshape n})\index{ZeroSemigroup@\texttt{ZeroSemigroup}}
\label{ZeroSemigroup}
}\hfill{\scriptsize (operation)}}\\
returns the \emph{zero semigroup} \texttt{S} of order \texttt{n}. That is, the unique semigroup up to isomorphism of order \texttt{n} such that there exists an element \texttt{0} in \texttt{S} such that \texttt{xy=0} for all \texttt{x,y} in \texttt{S}.
A zero semigroup is generated by its nonzero elements, has trivial Green's
relations, and is not regular.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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} ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{ZeroSemigroupElt}}
\logpage{[ 6, 2, 2 ]}\nobreak
\hyperdef{L}{X86A1D1D7832BEA9C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroSemigroupElt({\slshape n})\index{ZeroSemigroupElt@\texttt{ZeroSemigroupElt}}
\label{ZeroSemigroupElt}
}\hfill{\scriptsize (operation)}}\\
returns the zero semigroup element \texttt{zn} where \texttt{n} is a positive integer and \texttt{z0} is the multiplicative zero.
The zero semigroup element \texttt{zn} belongs to every zero semigroup with degree at least \texttt{n}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> ZeroSemigroupElt(0);
0
gap> ZeroSemigroupElt(4);
z4
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{ZeroGroup}}
\logpage{[ 6, 2, 3 ]}\nobreak
\hyperdef{L}{X81E319198527F824}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroGroup({\slshape G})\index{ZeroGroup@\texttt{ZeroGroup}}
\label{ZeroGroup}
}\hfill{\scriptsize (operation)}}\\
returns the monoid obtained by adjoining a zero element to \texttt{G}. That is, the monoid \texttt{S} obtained by adjoining a zero element \texttt{0} to \texttt{G} with \texttt{g0=0g=0} for all \texttt{g} in \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ...)} ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{ZeroGroupElt}}
\logpage{[ 6, 2, 4 ]}\nobreak
\hyperdef{L}{X81DB162A78350E28}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroGroupElt({\slshape g})\index{ZeroGroupElt@\texttt{ZeroGroupElt}}
\label{ZeroGroupElt}
}\hfill{\scriptsize (operation)}}\\
returns the zero group element corresponding to the group element \texttt{g}. The function \texttt{ZeroGroupElt} is only used to create an object in the correct category during the creation
of a zero group using \texttt{ZeroGroup} (\ref{ZeroGroup}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> ZeroGroupElt(Random(DihedralGroup(10)));;
gap> IsZeroGroupElt(last);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{UnderlyingGroupOfZG}}
\logpage{[ 6, 2, 5 ]}\nobreak
\hyperdef{L}{X7AA4B9577DC35D54}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{UnderlyingGroupOfZG({\slshape ZG})\index{UnderlyingGroupOfZG@\texttt{UnderlyingGroupOfZG}}
\label{UnderlyingGroupOfZG}
}\hfill{\scriptsize (attribute)}}\\
returns the group from which the zero group \texttt{ZG} was constructed.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> G:=DihedralGroup(10);;
gap> S:=ZeroGroup(G);;
gap> UnderlyingGroupOfZG(S)=G;
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{UnderlyingGroupEltOfZGElt}}
\logpage{[ 6, 2, 6 ]}\nobreak
\hyperdef{L}{X7AEC4E5E7EAE3CA5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{UnderlyingGroupEltOfZGElt({\slshape g})\index{UnderlyingGroupEltOfZGElt@\texttt{UnderlyingGroupEltOfZGElt}}
\label{UnderlyingGroupEltOfZGElt}
}\hfill{\scriptsize (attribute)}}\\
returns the group element from which the zero group element \texttt{g} was constructed.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Random Semigroups}}\label{random}
\logpage{[ 6, 3, 0 ]}
\hyperdef{L}{X7C3F130B8362D55A}{}
{
\subsection{\textcolor{Chapter }{RandomMonoid}}
\logpage{[ 6, 3, 1 ]}\nobreak
\hyperdef{L}{X7ECD900879DA1FD7}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomMonoid({\slshape m, n})\index{RandomMonoid@\texttt{RandomMonoid}}
\label{RandomMonoid}
}\hfill{\scriptsize (function)}}\\
returns a random transformation monoid of degree \texttt{n} with \texttt{m} generators.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=RandomMonoid(5,5);
<semigroup with 5 generators>
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RandomSemigroup}}
\logpage{[ 6, 3, 2 ]}\nobreak
\hyperdef{L}{X789DE9AB79FCFEB5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomSemigroup({\slshape m, n})\index{RandomSemigroup@\texttt{RandomSemigroup}}
\label{RandomSemigroup}
}\hfill{\scriptsize (function)}}\\
returns a random transformation semigroup of degree \texttt{n} with \texttt{m} generators.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=RandomSemigroup(5,5);
<semigroup with 5 generators>
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RandomReesMatrixSemigroup}}
\logpage{[ 6, 3, 3 ]}\nobreak
\hyperdef{L}{X858CBA2B7BD64141}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomReesMatrixSemigroup({\slshape i, j, deg})\index{RandomReesMatrixSemigroup@\texttt{RandomReesMatrixSemigroup}}
\label{RandomReesMatrixSemigroup}
}\hfill{\scriptsize (function)}}\\
returns a random Rees matrix semigroup with an \texttt{i} by \texttt{j} sandwich matrix over a permutation group with maximum degree \texttt{deg}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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) ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RandomReesZeroMatrixSemigroup}}
\logpage{[ 6, 3, 4 ]}\nobreak
\hyperdef{L}{X7F637CA981EFC6BE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomReesZeroMatrixSemigroup({\slshape i, j, deg})\index{RandomReesZeroMatrixSemigroup@\texttt{RandomReesZeroMatrixSemigroup}}
\label{RandomReesZeroMatrixSemigroup}
}\hfill{\scriptsize (function)}}\\
returns a random Rees \texttt{0}-matrix semigroup with an \texttt{i} by \texttt{j} sandwich matrix over a permutation group with maximum degree \texttt{deg}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=RandomReesZeroMatrixSemigroup(2,3,2);
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> SandwichMatrixOfReesZeroMatrixSemigroup(S);
[ [ 0, (), 0 ], [ 0, 0, 0 ] ]
\end{Verbatim}
}
}
}
\chapter{\textcolor{Chapter }{Semigroup Homomorphisms}}\label{homo}
\logpage{[ 7, 0, 0 ]}
\hyperdef{L}{X861935DB81A478C2}{}
{
\section{\textcolor{Chapter }{Introduction}}\logpage{[ 7, 1, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
In this chapter we give instructions on how to create semigroup homomorphisms
using \textsf{MONOID} in several different ways.
In Section \ref{create}, we give functions for creating arbitrary semigroup homomorphism specified by
a function on the elements, the images of the generators, or the images of all
the semigroup elements. These functions were written to support the functions
for computing the automorphism group of an arbitrary transformation semigroup
and to specify isomorphisms between different classes of semigroup, such as
finitely presented semigroups and transformation semigroups.
In Section \ref{inner}, we show how to specify and compute the inner automorphisms of a
transformation semigroup. The functions that can be used to find the entire
automorphism group of an arbitrary transformation semigroup are given in
Section \ref{autos}. The \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) has an interactive mode that allows the user to decide how the computation
should proceed. This can be invoked by using the command \texttt{SetInfoLevel(InfoAutos, 4);} see \texttt{InfoAutos} (\ref{InfoAutos}).
In Section \ref{rees}, commands for creating automorphisms and finding all automorphisms of Rees
matrix semigroups and Rees \texttt{0}-matrix semigroups are given.
In Section \ref{zerogp}, functions for specifying the automorphisms of a zero group are given.
In the final section (\ref{iso}), functions for finding isomorphisms between various kinds of semigroups are
given.
The methods behind the commands in this chapter are taken from \cite{computing}.
\textsc{Please note}: the following functions can only be used fully if \textsf{GRAPE} is fully installed (and loaded):
\begin{itemize}
\item \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) with argument satisfying \texttt{IsTransformationSemigroup} (\textbf{Reference: IsTransformationSemigroup}) or \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup})
\item \texttt{RightTransStabAutoGroup} (\ref{RightTransStabAutoGroup}) with argument satisfying \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup})
\item \texttt{RZMSGraph} (\ref{RZMSGraph})
\item \texttt{RZMSInducedFunction} (\ref{RZMSInducedFunction})
\item \texttt{RZMStoRZMSInducedFunction} (\ref{RZMStoRZMSInducedFunction})
\item \texttt{IsomorphismSemigroups} (\ref{IsomorphismSemigroups}) with both arguments satisfying \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup})
\end{itemize}
Please see Chapter \ref{Monoid} for further details on how to obtain \textsf{GRAPE}.
\subsection{\textcolor{Chapter }{InfoAutos}}
\logpage{[ 7, 1, 1 ]}\nobreak
\hyperdef{L}{X86E4761480D700DF}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InfoAutos\index{InfoAutos@\texttt{InfoAutos}}
\label{InfoAutos}
}\hfill{\scriptsize (info class)}}\\
This is the InfoClass for the functions in this chapter. Setting the value of \texttt{InfoAutos} to \texttt{1, 2, 3,} or \texttt{4} using the command \texttt{SetInfoLevel} (\textbf{Reference: SetInfoLevel}) will give different levels of information about what \texttt{GAP} is doing during a computation. In particular, if the level of \texttt{InfoAutos} is set to \texttt{4}, then \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) runs in interactive mode. }
}
\section{\textcolor{Chapter }{Creating Homomorphisms}}\label{create}
\logpage{[ 7, 2, 0 ]}
\hyperdef{L}{X7DB1B2FD7DFAEBEC}{}
{
The principal functions for creating arbitrary semigroup homomorphisms are the
following three.
\subsection{\textcolor{Chapter }{SemigroupHomomorphismByFunction}}\logpage{[ 7, 2, 1 ]}
\hyperdef{L}{X8199CBA57C36C666}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupHomomorphismByFunction({\slshape S, T, func})\index{SemigroupHomomorphismByFunction@\texttt{SemigroupHomomorphismByFunction}}
\label{SemigroupHomomorphismByFunction}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupHomomorphismByFunctionNC({\slshape S, T, func})\index{SemigroupHomomorphismByFunctionNC@\texttt{SemigroupHomomorphismByFunctionNC}}
\label{SemigroupHomomorphismByFunctionNC}
}\hfill{\scriptsize (operation)}}\\
returns a semigroup homomorphism with representation \texttt{IsSemigroupHomomorphismByFunctionRep} from the semigroup \texttt{S} to the semigroup \texttt{T} defined by the function \texttt{func}.
\texttt{SemigroupHomomorphismByFunction} will find an isomorphism from \texttt{S} to a finitely presented semigroup or monoid (using \texttt{IsomorphismFpSemigroup} (\ref{IsomorphismFpSemigroup}) or \texttt{IsomorphismFpMonoid} (\ref{IsomorphismFpMonoid})) and then check that the list of values under \texttt{func} of the generators of \texttt{S} satisfy the relations of this presentation.
\texttt{SemigroupHomomorphismByFunctionNC} does not check that \texttt{func} defines a homomorphism and, in this case \texttt{S} and \texttt{T} can be semigroups, $D$-classes, $H$-classes or any combination of these.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 4, 3, 5, 2 ] ),
> Transformation( [ 2, 3, 1, 1, 2 ] ) ];;
gap> S:=Semigroup(gens);;
gap> gens:=[ Transformation( [ 1, 5, 1, 2, 1 ] ),
> Transformation( [ 5, 1, 4, 3, 2 ] ) ];;
gap> T:=Semigroup(gens);;
gap> idem:=Random(Idempotents(T));;
gap> hom:=SemigroupHomomorphismByFunction(S, T, x-> idem);
SemigroupHomomorphism ( <semigroup with 2 generators>-><semigroup with
2 generators>)
gap> hom:=SemigroupHomomorphismByFunctionNC(S, T, x-> idem);
SemigroupHomomorphism ( <semigroup with 2 generators>-><semigroup with
2 generators>)
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{SemigroupHomomorphismByImagesOfGens}}\logpage{[ 7, 2, 2 ]}
\hyperdef{L}{X8662F27B868CE7F2}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupHomomorphismByImagesOfGens({\slshape S, T, list})\index{SemigroupHomomorphismByImagesOfGens@\texttt{SemigroupHomomorphismByImagesOfGens}}
\label{SemigroupHomomorphismByImagesOfGens}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupHomomorphismByImagesOfGensNC({\slshape S, T, list})\index{SemigroupHomomorphismByImagesOfGensNC@\texttt{SemigroupHomomorphismByImagesOfGensNC}}
\label{SemigroupHomomorphismByImagesOfGensNC}
}\hfill{\scriptsize (operation)}}\\
returns a semigroup homomorphism with representation \texttt{IsSemigroupHomomorphismByImagesOfGensRep} from \texttt{S} to \texttt{T} where the image of the \texttt{i}th generator of \texttt{S} is the \texttt{i}th position in \texttt{list}.
\texttt{SemigroupHomomorphismByImagesOfGens} will find an isomorphism from \texttt{S} to a finitely presented semigroup or monoid (using \texttt{IsomorphismFpSemigroup} (\ref{IsomorphismFpSemigroup}) or \texttt{IsomorphismFpMonoid} (\ref{IsomorphismFpMonoid})) and then check that \texttt{list} satisfies the relations of this presentation.
\texttt{SemigroupHomomorphismByImagesOfGensNC} does not check that \texttt{list} induces a homomorphism.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 1, 4, 3, 5, 2 ] ),
> Transformation( [ 2, 3, 1, 1, 2 ] ) ];;
gap> S:=Semigroup(gens);;
gap> gens:=[ Transformation( [ 1, 5, 1, 2, 1 ] ),
> Transformation( [ 5, 1, 4, 3, 2 ] ) ];;
gap> T:=Semigroup(gens);;
gap> SemigroupHomomorphismByImagesOfGens(S, T, GeneratorsOfSemigroup(T));
fail
gap> SemigroupHomomorphismByImagesOfGens(S, S, GeneratorsOfSemigroup(S));
SemigroupHomomorphismByImagesOfGens ( <trans. semigroup of size 161 with
2 generators>-><trans. semigroup of size 161 with 2 generators>)
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{SemigroupHomomorphismByImages}}\logpage{[ 7, 2, 3 ]}
\hyperdef{L}{X7D3A1B087C95CD84}{}
{
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupHomomorphismByImages({\slshape S, T, list})\index{SemigroupHomomorphismByImages@\texttt{SemigroupHomomorphismByImages}}
\label{SemigroupHomomorphismByImages}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupHomomorphismByImagesNC({\slshape S, T, list})\index{SemigroupHomomorphismByImagesNC@\texttt{SemigroupHomomorphismByImagesNC}}
\label{SemigroupHomomorphismByImagesNC}
}\hfill{\scriptsize (operation)}}\\
returns a semigroup homomorphism with representation \texttt{IsSemigroupHomomorphismByImagesRep} from \texttt{S} to \texttt{T} where the image of the \texttt{i}th element of \texttt{S} is the \texttt{i}th position in \texttt{list}.
\texttt{SemigroupHomomorphismByImages} will find an isomorphism from \texttt{S} to a finitely presented semigroup or monoid (using \texttt{IsomorphismFpSemigroup} (\ref{IsomorphismFpSemigroup}) or \texttt{IsomorphismFpMonoid} (\ref{IsomorphismFpMonoid})) and then check that \texttt{list} satisfies the relations of this presentation.
\texttt{SemigroupHomomorphismByImagesNC} does not check that \texttt{list} induces a homomorphism.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 2, 3, 4, 2, 4 ] ),
> Transformation( [ 3, 4, 2, 1, 4 ] ) ];;
gap> S:=Semigroup(gens);;
gap> gens:=[ Transformation( [ 2, 4, 4, 1, 2 ] ),
> Transformation( [ 5, 1, 1, 5, 1 ] ) ];;
gap> T:=Semigroup(gens);;
gap> idem:=Transformation( [ 5, 5, 5, 5, 5 ] );;
gap> list:=List([1..Size(S)], x-> idem);;
gap> hom:=SemigroupHomomorphismByImages(S, T, list);
SemigroupHomomorphismByImagesOfGens ( <trans. semigroup of size 164 with
2 generators>-><trans. semigroup with 2 generators>)
gap> SemigroupHomomorphismByImagesNC(S, T, list);
SemigroupHomomorphismByImages ( <trans. semigroup of size 164 with
2 generators>-><trans. semigroup with 2 generators>)
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Inner Automorphisms}}\label{inner}
\logpage{[ 7, 3, 0 ]}
\hyperdef{L}{X7EC237ED7E1978B0}{}
{
\subsection{\textcolor{Chapter }{InnerAutomorphismOfSemigroup}}
\logpage{[ 7, 3, 1 ]}\nobreak
\hyperdef{L}{X7BED661C83148D0C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InnerAutomorphismOfSemigroup({\slshape S, perm})\index{InnerAutomorphismOfSemigroup@\texttt{InnerAutomorphismOfSemigroup}}
\label{InnerAutomorphismOfSemigroup}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InnerAutomorphismOfSemigroupNC({\slshape S, perm})\index{InnerAutomorphismOfSemigroupNC@\texttt{InnerAutomorphismOfSemigroupNC}}
\label{InnerAutomorphismOfSemigroupNC}
}\hfill{\scriptsize (operation)}}\\
returns the inner automorphism of the transformation semigroup \texttt{S} given by the permutation \texttt{perm}. The degree of \texttt{perm} should be at most the degree of \texttt{S}.
The notion of inner automorphisms of semigroups differs from the notion of the
same name for groups. Indeed, if \texttt{S} is a semigroup of transformations of degree \texttt{n}, then \texttt{g} in the symmetric group \texttt{S{\textunderscore}n} induces an inner automorphism of \texttt{S} if the mapping that takes \texttt{s} to \texttt{g\texttt{\symbol{94}}-1sg} for all \texttt{s} in \texttt{S} is an automorphism of \texttt{S}.
\texttt{InnerAutomorphismOfSemigroup} checks that the mapping induced by \texttt{perm} is an automorphism and \texttt{InnerAutomorphismOfSemigroupNC} only creates the appropriate object without performing a check that the
permutation actually induces an automorphism.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 6, 2, 7, 5, 3, 5, 4 ] ),
> Transformation( [ 7, 7, 5, 7, 2, 4, 3 ] ) ];;
gap> S:=Monoid(gens);;
gap> InnerAutomorphismOfSemigroup(S, (1,2,3,4,5));
fail
gap> InnerAutomorphismOfSemigroupNC(S, (1,2,3,4,5));
^(1,2,3,4,5)
gap> InnerAutomorphismOfSemigroup(S, ());
^()
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{ConjugatorOfInnerAutomorphismOfSemigroup}}
\logpage{[ 7, 3, 2 ]}\nobreak
\hyperdef{L}{X87562E2079AE7608}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ConjugatorOfInnerAutomorphismOfSemigroup({\slshape f})\index{ConjugatorOfInnerAutomorphismOfSemigroup@\texttt{ConjugatorOfInnerAutomorphismOfSemigroup}}
\label{ConjugatorOfInnerAutomorphismOfSemigroup}
}\hfill{\scriptsize (attribute)}}\\
returns the permutation \texttt{perm} used to construct the inner automorphism \texttt{f} of a semigroup; see \texttt{InnerAutomorphismOfSemigroup} (\ref{InnerAutomorphismOfSemigroup}) for further details.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=RandomSemigroup(3,8);;
gap> f:=InnerAutomorphismOfSemigroupNC(S, (1,2)(3,4));
^(1,2)(3,4)
gap> ConjugatorOfInnerAutomorphismOfSemigroup(f);
(1,2)(3,4)
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsInnerAutomorphismOfSemigroup}}
\logpage{[ 7, 3, 3 ]}\nobreak
\hyperdef{L}{X87254FED7D1E0881}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsInnerAutomorphismOfSemigroup({\slshape f})\index{IsInnerAutomorphismOfSemigroup@\texttt{IsInnerAutomorphismOfSemigroup}}
\label{IsInnerAutomorphismOfSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if the general mapping \texttt{f} is an inner automorphism of a semigroup; see \texttt{InnerAutomorphismOfSemigroup} (\ref{InnerAutomorphismOfSemigroup}) for further details.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=RandomSemigroup(2,9);;
gap> f:=InnerAutomorphismOfSemigroupNC(S, (1,2)(3,4));
^(1,2)(3,4)
gap> IsInnerAutomorphismOfSemigroup(f);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{InnerAutomorphismsOfSemigroup}}
\logpage{[ 7, 3, 4 ]}\nobreak
\hyperdef{L}{X84B1A484829EC33E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InnerAutomorphismsOfSemigroup({\slshape S})\index{InnerAutomorphismsOfSemigroup@\texttt{InnerAutomorphismsOfSemigroup}}
\label{InnerAutomorphismsOfSemigroup}
}\hfill{\scriptsize (attribute)}}\\
\texttt{InnerAutomorphismsOfSemigroup} returns the group of inner automorphisms of the transformation semigroup \texttt{S}.
The same result can be obtained by applying \texttt{InnerAutomorphismsAutomorphismGroup} (\ref{InnerAutomorphismsAutomorphismGroup}) to the result of \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) of \texttt{S}. It is possible that the inner automorphism of \texttt{S} have been calculated at the same time as the entire automorphism group of \texttt{S} but it might not be. If the degree of \texttt{S} is high, then this function may take a long time to return a value.
The notion of inner automorphisms of semigroups differs from the notion of the
same name for groups. Indeed, if \texttt{S} is a semigroup of transformations of degree \texttt{n}, then \texttt{g} in the symmetric group \texttt{S{\textunderscore}n} induces an inner automorphism of \texttt{S} if the mapping that takes \texttt{s} to \texttt{g\texttt{\symbol{94}}-1sg} for all \texttt{s} in \texttt{S} is an automorphism of \texttt{S}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> x:=Transformation([2,3,4,5,6,7,8,9,1]);;
gap> y:=Transformation([4,2,3,4,5,6,7,8,9]);;
gap> S:=Semigroup(x,y);;
gap> G:=InnerAutomorphismsOfSemigroup(S);
<group of size 54 with 2 generators>
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{InnerAutomorphismsOfSemigroupInGroup}}
\logpage{[ 7, 3, 5 ]}\nobreak
\hyperdef{L}{X7B03F09484162578}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InnerAutomorphismsOfSemigroupInGroup({\slshape S, G[, bval]})\index{InnerAutomorphismsOfSemigroupInGroup@\texttt{InnerAutomorphismsOfSemigroupInGroup}}
\label{InnerAutomorphismsOfSemigroupInGroup}
}\hfill{\scriptsize (operation)}}\\
\texttt{InnerAutomorphismsOfSemigroupInGroup} returns the group of inner automorphisms of the transformation semigroup \texttt{S} that also belong to the group \texttt{G}. The default setting is that the inner automorphisms of \texttt{S} are calculated first, then filtered to see which elements also belong to \texttt{G}.
If the optional argument \texttt{bval} is present and \texttt{true}, then the filtering is done as the inner automorphisms are found rather than
after they have all been found. Otherwise, then this is equivalent to doing \texttt{InnerAutomorphismsOfSemigroupInGroup(S, G)}.
If \texttt{InfoAutos} (\ref{InfoAutos}) is set to level \texttt{4}, then a prompt will appear during the procedure to let you decide when the
filtering should be done. In this case the value of \texttt{bval} is irrelevant.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [1,8,11,2,5,16,13,14,3,6,15,10,7,4,9,12 ] ),
> Transformation( [1,16,9,6,5,8,13,12,15,2,3,4,7,10,11,14] ),
> Transformation( [1,3,7,9,1,15,5,11,13,11,13,3,5,15,7,9 ] ) ];;
gap> S:=Semigroup(gens);;
gap> InnerAutomorphismsOfSemigroup(S);
<group of size 16 with 3 generators>
gap> G:=Group(SemigroupHomomorphismByImagesOfGensNC(S, S, gens));
<group with 1 generators>
gap> InnerAutomorphismsOfSemigroupInGroup(S, G);
<group of size 1 with 1 generators>
gap> InnerAutomorphismsOfSemigroupInGroup(S, G, true);
<group of size 1 with 1 generators>
gap> InnerAutomorphismsOfSemigroupInGroup(S, G, false);
<group of size 1 with 1 generators>
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{InnerAutomorphismsAutomorphismGroup}}
\logpage{[ 7, 3, 6 ]}\nobreak
\hyperdef{L}{X8476738A7BF9BADA}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InnerAutomorphismsAutomorphismGroup({\slshape autgroup})\index{InnerAutomorphismsAutomorphismGroup@\texttt{InnerAutomorphismsAutomorphismGroup}}
\label{InnerAutomorphismsAutomorphismGroup}
}\hfill{\scriptsize (attribute)}}\\
If \texttt{autgroup} satisfies \texttt{IsAutomorphismGroupOfSemigroup} (\ref{IsAutomorphismGroupOfSemigroup}) then, this attribute stores the subgroup of inner automorphisms of the
original semigroup.
It is possible that the inner automorphisms of \texttt{autgroup} have been calculated at the same time as \texttt{autgroup} was calculated but they might not be. If the degree of underlying semigroup is
high, then this function may take a long time to return a value.
The notion of inner automorphisms of semigroups differs from the notion of the
same name for groups. Indeed, if \texttt{S} is a semigroup of transformations of degree \texttt{n}, then \texttt{g} in the symmetric group \texttt{S{\textunderscore}n} induces an inner automorphism of \texttt{S} if the mapping that takes \texttt{s} to \texttt{g\texttt{\symbol{94}}-1sg} for all \texttt{s} in \texttt{S} is an automorphism of \texttt{S}.
If \texttt{autgroup} satisfies \texttt{IsAutomorphismGroupOfZeroGroup} (\ref{IsAutomorphismGroupOfZeroGroup}), then \texttt{InnerAutomorphismsAutomorphismGroup} returns the subgroup of inner automorphisms inside the automorphism group of
the zero group by computing the inner automorphisms of the underlying group.
Note that in this case the notion of inner automorphisms corresponds to that
of the group theoretic notion.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6]);;
gap> g2:=Transformation([5,1,7,8,7,5,8,1]);;
gap> m6:=Semigroup(g1,g2);;
gap> A:=AutomorphismGroup(m6);
<group of size 12 with 2 generators>
gap> InnerAutomorphismsAutomorphismGroup(A);
<group of size 12 with 2 generators>
gap> last=InnerAutomorphismsOfSemigroup(m6);
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsInnerAutomorphismsOfSemigroup}}
\logpage{[ 7, 3, 7 ]}\nobreak
\hyperdef{L}{X85FD796978788EF5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsInnerAutomorphismsOfSemigroup({\slshape G})\index{IsInnerAutomorphismsOfSemigroup@\texttt{IsInnerAutomorphismsOfSemigroup}}
\label{IsInnerAutomorphismsOfSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the inner automorphism group of a transformation semigroup.
The notion of inner automorphisms of semigroups differs from the notion of the
same name for groups. Indeed, if \texttt{S} is a semigroup of transformations of degree \texttt{n}, then \texttt{g} in the symmetric group \texttt{S{\textunderscore}n} induces an inner automorphism of \texttt{S} if the mapping that takes \texttt{s} to \texttt{g\texttt{\symbol{94}}-1sg} for all \texttt{s} in \texttt{S} is an automorphism of \texttt{S}.
Note that this property is set to \texttt{true} when the computation of the inner automorphisms is performed. Otherwise, there
is no method to check if an arbitrary group satisfies this property.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=RandomSemigroup(5,5);
<semigroup with 5 generators>
gap> I:=InnerAutomorphismsOfSemigroup(S);;
gap> IsInnerAutomorphismsOfSemigroup(I);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsInnerAutomorphismsOfZeroGroup}}
\logpage{[ 7, 3, 8 ]}\nobreak
\hyperdef{L}{X7B4BB2FF799D0D36}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsInnerAutomorphismsOfZeroGroup({\slshape G})\index{IsInnerAutomorphismsOfZeroGroup@\texttt{IsInnerAutomorphismsOfZeroGroup}}
\label{IsInnerAutomorphismsOfZeroGroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the inner automorphism group of a zero group. This property is set to \texttt{true} when the computation of the inner automorphism group of the zero group is
performed. Otherwise, there is no method to check if an arbitrary group
satisfies this property.
Every inner automorphism of a zero group is just an inner automorphism of the
underlying group that fixes the zero element. So, this notion of inner
automorphism corresponds to the notion of inner automorphisms of a group.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> zg:=ZeroGroup(CyclicGroup(70));
<zero group with 4 generators>
gap> I:=InnerAutomorphismsAutomorphismGroup(AutomorphismGroup(zg));
<group of size 1 with 1 generators>
gap> IsInnerAutomorphismsOfZeroGroup(I);
true
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Automorphism Groups}}\label{autos}
\logpage{[ 7, 4, 0 ]}
\hyperdef{L}{X7A007A0C80D26351}{}
{
\subsection{\textcolor{Chapter }{AutomorphismGroup}}
\logpage{[ 7, 4, 1 ]}\nobreak
\hyperdef{L}{X87677B0787B4461A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AutomorphismGroup({\slshape S})\index{AutomorphismGroup@\texttt{AutomorphismGroup}}
\label{AutomorphismGroup}
}\hfill{\scriptsize (attribute)}}\\
\texttt{AutomorphismGroup} returns the group of automorphisms of the transformation semigroup, zero
group, zero semigroup, Rees matrix semigroup, or Rees 0-matrix semigroup \texttt{S}; that is, semigroups satisfying the properties \texttt{IsTransformationSemigroup} (\textbf{Reference: IsTransformationSemigroup}), \texttt{IsZeroGroup} (\ref{IsZeroGroup}), \texttt{IsZeroSemigroup} (\ref{IsZeroSemigroup}), \texttt{IsReesMatrixSemigroup} (\textbf{Reference: IsReesMatrixSemigroup}), or \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup}).
If \texttt{S} is a transformation semigroup, then \texttt{AutomorphismGroup} computes the automorphism group of \texttt{S} using the algorithm described in \cite{computing}.
If \texttt{S} is a (completely) simple transformation semigroup, then the automorphism group
is computed by passing to an isomorphic Rees matrix semigroup. If \texttt{S} is a transformation group, then the automorphism group is computed by passing
to an isomorphic permutation group. If \texttt{S} has order \texttt{{\textless}10} and knows its Cayley table (\texttt{MultiplicationTable} (\textbf{Reference: MultiplicationTable})), then the automorphism group is calculated by finding the setwise stabilizer
of the Cayley table in the symmetric group of degree \texttt{|S|} under the action on the Cayley table.
If \texttt{S} is a zero group, then \texttt{AutomorphismGroup} computes the automorphism group of the underlying group. Obviously, every
automorphism of a zero group is the extension of an automorphism of the
underlying group that fixes the zero element.
If \texttt{S} is a zero semigroup, then every permutation of the elements of \texttt{S} that fixes the zero element is an automorphism. Thus the automorphism group of
a zero semigroup of order \texttt{n} is isomorphic to the symmetric group on \texttt{n-1} elements.
If \texttt{S} is a Rees matrix semigroup or a Rees 0-matrix semigroup, then the automorphism
group of \texttt{S} is calculated using the algorithm described in \cite[Section 2]{computing}. In this case, the returned group has as many generators as elements. This
may be changed in the future.
If \texttt{InfoAutos} (\ref{InfoAutos}) is set to level \texttt{4}, then prompts will appear during the procedure to allow you interactive
control over the computation.
\textsc{Please note:} if \textsf{grape} is not loaded, then this function will not work when \texttt{S} satisfies \texttt{IsTransformationSemigroup} (\textbf{Reference: IsTransformationSemigroup}) or \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([5,4,4,2,1]);;
gap> g2:=Transformation([2,5,5,4,1]);;
gap> m2:=Monoid(g1,g2);;
gap> IsTransformationSemigroup(m2);
true
gap> AutomorphismGroup(m2);
<group of size 24 with 5 generators>
gap> IsAutomorphismGroupOfSemigroup(last);
true
gap> zg:=ZeroGroup(CyclicGroup(70));
<zero group with 4 generators>
gap> IsZeroGroup(zg);
true
gap> AutomorphismGroup(zg);
<group with 3 generators>
gap> IsAutomorphismGroupOfZeroGroup(last);
true
gap> InnerAutomorphismsOfSemigroup(zg);
<group of size 1 with 1 generators>
gap> InnerAutomorphismsAutomorphismGroup(AutomorphismGroup(zg));
<group of size 1 with 1 generators>
gap> last2=InnerAutomorphismsAutomorphismGroup(AutomorphismGroup(zg));
true
gap> S:=ZeroSemigroup(10);
<zero semigroup with 10 elements>
gap> Size(S);
10
gap> Elements(S);
[ 0, z1, z2, z3, z4, z5, z6, z7, z8, z9 ]
gap> A:=AutomorphismGroup(S);
<group with 2 generators>
gap> IsAutomorphismGroupOfZeroSemigroup(A);
true
gap> Factorial(9)=Size(A);
true
gap> G:=Group([ (2,5)(3,4) ]);;
gap> mat:=[ [ (), (), (), (), () ],
> [ (), (), (2,5)(3,4), (2,5)(3,4), () ],
> [ (), (), (), (2,5)(3,4), (2,5)(3,4) ],
> [ (), (2,5)(3,4), (), (2,5)(3,4), () ],
> [ (), (2,5)(3,4), (), (2,5)(3,4), () ] ];;
gap> rms:=ReesMatrixSemigroup(G, mat);
Rees Matrix Semigroup over Group([ (2,5)(3,4) ])
gap> A:=AutomorphismGroup(rms);
<group of size 12 with 12 generators>
gap> IsAutomorphismGroupOfRMS(A);
true
gap> G:=ZeroGroup(Group([ (1,3)(2,5), (1,3,2,5) ]));;
gap> elts:=Elements(G);;
gap> mat:=[ [ elts[7], elts[1], elts[9], elts[1], elts[1] ],
> [ elts[1], elts[1], elts[1], elts[9], elts[1] ],
> [ elts[9], elts[1], elts[1], elts[4], elts[9] ],
> [ elts[1], elts[1], elts[1], elts[1], elts[1] ],
> [ elts[1], elts[5], elts[1], elts[1], elts[1] ] ];;
gap> rzms:=ReesZeroMatrixSemigroup(G, mat);;
gap> AutomorphismGroup(rzms);
gap> IsAutomorphismGroupOfRZMS(A);
true
<group of size 512 with 512 generators>
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{AutomorphismsSemigroupInGroup}}
\logpage{[ 7, 4, 2 ]}\nobreak
\hyperdef{L}{X7F13DCF886671C0C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AutomorphismsSemigroupInGroup({\slshape S, G[, bvals]})\index{AutomorphismsSemigroupInGroup@\texttt{AutomorphismsSemigroupInGroup}}
\label{AutomorphismsSemigroupInGroup}
}\hfill{\scriptsize (operation)}}\\
\texttt{AutomorphismsSemigroupInGroup} returns the group of automorphisms of the transformation semigroup \texttt{S} that also belong to the group \texttt{G}. If the value of \texttt{G} is \texttt{fail}, then \texttt{AutomorphismsSemigroupInGroup} returns the same value as \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}). The default setting is that the automorphisms of \texttt{S} are calculated first, then filtered to see which elements also belong to \texttt{G}.
The optional argument \texttt{bvals} is a list of \texttt{5} Boolean variables that correspond to the following options:
\begin{itemize}
\item if \texttt{bvals[1]} is \texttt{true}, then \textsf{GAP} will run a cheap check to see if all the automorphisms are inner. Note that
this can return \texttt{false} when all the automorphisms are inner, that is the condition is sufficient but
not necessary. The default setting is \texttt{false}.
\item if \texttt{bvals[2]} is \texttt{true}, then \textsf{GAP} will try to compute the inner automorphisms of \texttt{S} before computing the entire automorphism group. For semigroups of large degree
this may not be sensible. The default setting is \texttt{false}.
\item if \texttt{bvals[3]} is \texttt{true}, then \textsf{GAP} will test elements in the inner automorphism search space to see if they are
in \texttt{G} as the inner automorphisms are found rather than after they have all been
found. The default setting is \texttt{false}.
\item if \texttt{bvals[4]} is \texttt{true}, then \textsf{GAP} will test elements in the outer (i.e. not inner) automorphism search space to
see if they are in \texttt{G} as they are found rather than after they have all been found. The default
setting is \texttt{false}.
\item if \texttt{bvals[5]} is \texttt{true}, then \textsf{GAP} will keep track of non-automorphisms in the search for outer automorphisms.
The default setting is \texttt{false}.
\end{itemize}
\textsc{Please note:} if \textsf{grape} is not loaded, then this function will not work when \texttt{S} satisfies \texttt{IsTransformationSemigroup} (\textbf{Reference: IsTransformationSemigroup}) or \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([5,4,4,2,1]);;
gap> g2:=Transformation([2,5,5,4,1]);;
gap> m2:=Monoid(g1,g2);;
gap> A:=AutomorphismsSemigroupInGroup(m2, fail,
> [false, true, true, false, true]);
<group of size 24 with 3 generators>
gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
gap> m7:=Monoid(g1,g2);;
gap> A:=AutomorphismsSemigroupInGroup(m7, fail,
> [false, true, false, false, true]);
<group of size 2 with 2 generators>
gap> imgs:=[ [ Transformation( [ 1, 1, 5, 4, 3, 6, 7, 8, 9, 10, 11, 12 ] ),
> Transformation( [ 1, 1, 5, 7, 4, 3, 6, 8, 9, 10, 11, 12 ] ),
> Transformation( [ 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 8 ] ) ],
> [ Transformation( [ 1, 1, 5, 4, 3, 6, 7, 8, 9, 10, 11, 12 ] ),
> Transformation( [ 1, 1, 5, 3, 7, 4, 6, 8, 9, 10, 11, 12 ] ),
> Transformation( [ 1, 2, 3, 4, 5, 6, 7, 11, 12, 8, 9, 10 ] ) ] ];;
gap> gens:=List(imgs, x-> SemigroupHomomorphismByImagesOfGensNC(S, S, x));;
gap> G:=Group(gens);
<group with 2 generators>
gap> A:=AutomorphismsSemigroupInGroup(S, G,
> [false, false, false, true, false]);
<group of size 48 with 4 generators>
gap> Size(G);
48
gap> A:=AutomorphismsSemigroupInGroup(S, G);
<group of size 48 with 4 generators>
gap> gens:=[ Transformation( [ 1, 1, 4, 3, 5, 6, 7, 8, 9, 10, 11, 12 ] ),
> Transformation( [ 1, 1, 4, 5, 6, 7, 3, 8, 9, 10, 11, 12 ] ),
> Transformation( [ 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 8 ] ) ];;
gap> S:=Semigroup(gens);;
gap> A:=AutomorphismsSemigroupInGroup(S, G);
<group of size 48 with 4 generators>
gap> HasAutomorphismGroup(S);
true
gap> AutomorphismGroup(S);
<group of size 480 with 7 generators>
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsAutomorphismGroupOfSemigroup}}
\logpage{[ 7, 4, 3 ]}\nobreak
\hyperdef{L}{X8196EC9384EC69BC}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAutomorphismGroupOfSemigroup({\slshape G})\index{IsAutomorphismGroupOfSemigroup@\texttt{IsAutomorphismGroupOfSemigroup}}
\label{IsAutomorphismGroupOfSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the automorphism group of a semigroup. Note that this property is set to \texttt{true} when the computation of the automorphism group is performed. Otherwise, there
is no method to check if an arbitrary group satisfies this property; see \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) for an example of the usage of this command.
}
\subsection{\textcolor{Chapter }{IsAutomorphismGroupOfSimpleSemigp}}
\logpage{[ 7, 4, 4 ]}\nobreak
\hyperdef{L}{X7EBC9D1C7CEE5DC1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAutomorphismGroupOfSimpleSemigp({\slshape G})\index{IsAutomorphismGroupOfSimpleSemigp@\texttt{IsAutomorphismGroupOfSimpleSemigp}}
\label{IsAutomorphismGroupOfSimpleSemigp}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the automorphism group of a simple transformation semigroup. This property
is set to \texttt{true} when the computation of the automorphism group of the simple transformation
semigroup is performed. Otherwise, there is no method to check if an arbitrary
group satisfies this property; see \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) for an example of the usage of this command.
}
\subsection{\textcolor{Chapter }{IsAutomorphismGroupOfZeroGroup}}
\logpage{[ 7, 4, 5 ]}\nobreak
\hyperdef{L}{X7F20270581708C15}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAutomorphismGroupOfZeroGroup({\slshape G})\index{IsAutomorphismGroupOfZeroGroup@\texttt{IsAutomorphismGroupOfZeroGroup}}
\label{IsAutomorphismGroupOfZeroGroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the automorphism group of a zero group. This property is set to \texttt{true} when the computation of the automorphism group of the zero group is performed.
Otherwise, there is no method to check if an arbitrary group satisfies this
property; see \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) for an example of the usage of this command.
Every automorphism of a zero group is just an automorphism of the underlying
group that fixes the zero element. }
\subsection{\textcolor{Chapter }{IsAutomorphismGroupOfZeroSemigroup}}
\logpage{[ 7, 4, 6 ]}\nobreak
\hyperdef{L}{X7C8903DD85C40824}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAutomorphismGroupOfZeroSemigroup({\slshape G})\index{IsAutomorphismGroupOfZeroSemigroup@\texttt{IsAutomorphismGroupOfZeroSemigroup}}
\label{IsAutomorphismGroupOfZeroSemigroup}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the automorphism group of a zero semigroup. This property is set to \texttt{true} when the computation of the automorphism group of the zero semigroup is
performed. Otherwise, there is no method to check if an arbitrary group
satisfies this property; see \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) for an example of the usage of this command.
Every permutation of a zero semigroup that fixes the zero element is an
automorphism. Thus the automorphism group of a zero semigroup of order \texttt{n} is isomorphic to the symmetric group on \texttt{n-1} elements. }
\subsection{\textcolor{Chapter }{IsAutomorphismGroupOfRMS}}
\logpage{[ 7, 4, 7 ]}\nobreak
\hyperdef{L}{X7F77F02583731C84}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAutomorphismGroupOfRMS({\slshape G})\index{IsAutomorphismGroupOfRMS@\texttt{IsAutomorphismGroupOfRMS}}
\label{IsAutomorphismGroupOfRMS}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the automorphism group of a Rees matrix semigroup; that is, a semigroup
created using the command \texttt{ReesMatrixSemigroup} (\textbf{Reference: ReesMatrixSemigroup}) and/or satisfying \texttt{IsReesMatrixSemigroup} (\textbf{Reference: IsReesMatrixSemigroup}).
Note that this property is set to \texttt{true} when the computation of the automorphism group is performed. Otherwise, there
is no method to check if an arbitrary group satisfies this property; see \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) for an example of the usage of this command.
}
\subsection{\textcolor{Chapter }{IsAutomorphismGroupOfRZMS}}
\logpage{[ 7, 4, 8 ]}\nobreak
\hyperdef{L}{X868D5404867566F9}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsAutomorphismGroupOfRZMS({\slshape G})\index{IsAutomorphismGroupOfRZMS@\texttt{IsAutomorphismGroupOfRZMS}}
\label{IsAutomorphismGroupOfRZMS}
}\hfill{\scriptsize (property)}}\\
returns \texttt{true} if \texttt{G} is the automorphism group of a Rees matrix semigroup; that is, a semigroup
created using the command \texttt{ReesZeroMatrixSemigroup} (\textbf{Reference: ReesZeroMatrixSemigroup}) and/or satisfying \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup}).
Note that this property is set to \texttt{true} when the computation of the automorphism group is performed. Otherwise, there
is no method to check if an arbitrary group satisfies this property; see \texttt{AutomorphismGroup} (\ref{AutomorphismGroup}) for an example of the usage of this command.
}
}
\section{\textcolor{Chapter }{Rees Matrix Semigroups}}\label{rees}
\logpage{[ 7, 5, 0 ]}
\hyperdef{L}{X8225A9EC87A255E6}{}
{
\subsection{\textcolor{Chapter }{RMSIsoByTriple}}
\logpage{[ 7, 5, 1 ]}\nobreak
\hyperdef{L}{X82B0BDCD7CBDCC2E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RMSIsoByTriple({\slshape rms1, rms2, triple})\index{RMSIsoByTriple@\texttt{RMSIsoByTriple}}
\label{RMSIsoByTriple}
}\hfill{\scriptsize (function)}}\\
this is a function to create an isomorphism between the Rees matrix semigroups \texttt{rms1} and \texttt{rms2} defined by \texttt{triple}. The first component of \texttt{triple} should be an isomorphism from the underlying group of \texttt{rms1} to the underlying group of \texttt{rms2}, the second component should be an isomorphism from the graph associated to
the matrix of \texttt{rms1} to the graph associated with the matrix of \texttt{rms2}, and the third component should be a function (given as a list of image
elements) from the index sets of \texttt{rms1} to the underlying group of \texttt{rms2}; see \cite[Section 2]{computing} for further details.
Note that this function only creates an object with representation \texttt{IsRMSIsoByTripleRep} (\ref{IsRMSIsoByTripleRep}) and does not check that \texttt{triple} actually defines an isomorphism from \texttt{rms1} to \texttt{rms2} or that the arguments even make sense. To create an isomorphism from \texttt{rms1} to \texttt{rms2} use \texttt{IsomorphismSemigroups} (\ref{IsomorphismSemigroups}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> G:=Group((1,4,3,5,2));;
gap> mat:=[ [ (), (), () ], [ (), (1,4,3,5,2), () ], [ (), (1,3,2,4,5), () ] ];;
gap> rms:=ReesMatrixSemigroup(G, mat);;
gap> l:=(4,6);;
gap> g:=GroupHomomorphismByImages(G, G, [(1,4,3,5,2)], [(1,2,5,3,4)]);
[ (1,4,3,5,2) ] -> [ (1,2,5,3,4) ]
gap> map:=[(), (1,5,4,2,3), (), (), (), () ];;
gap> RMSIsoByTriple(rms, rms, [l, g, map]);
[ (4,6), GroupHomomorphismByImages( Group( [ (1,4,3,5,2) ] ), Group(
[ (1,4,3,5,2) ] ), [ (1,4,3,5,2) ], [ (1,2,5,3,4) ] ),
[ (), (1,5,4,2,3), (), (), (), () ] ]
gap> IsRMSIsoByTripleRep(last);
true
gap> #the previous actually defines an automorphism of rms
gap> #on the other hand, the next example is nonsense but no error
gap> #is given
gap> RMSIsoByTriple(rms, rms, [l, g, [()]]);
[ (4,6), GroupHomomorphismByImages( Group( [ (1,4,3,5,2) ] ), Group(
[ (1,4,3,5,2) ] ), [ (1,4,3,5,2) ], [ (1,2,5,3,4) ] ), [ () ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RZMSIsoByTriple}}
\logpage{[ 7, 5, 2 ]}\nobreak
\hyperdef{L}{X8169BFEA84877310}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RZMSIsoByTriple({\slshape rzms1, rzms2, triple})\index{RZMSIsoByTriple@\texttt{RZMSIsoByTriple}}
\label{RZMSIsoByTriple}
}\hfill{\scriptsize (function)}}\\
this is a function to create an isomorphism between the Rees 0-matrix
semigroups \texttt{rzms1} and \texttt{rzms2} defined by \texttt{triple}. The first component of \texttt{triple} should be an isomorphism from the underlying zero group of \texttt{rzms1} to the underlying zero group of \texttt{rzms2}, the second component should be an isomorphism from the graph associated to
the matrix of \texttt{rzms1} to the graph associated with the matrix of \texttt{rzms2}, and the third component should be a function (given as a list of image
elements) from the index sets of \texttt{rzms1} to the underlying zero group of \texttt{rzms2}; see \cite[Section 2]{computing} for further details.
Note that this function only creates an object with representation \texttt{IsRZMSIsoByTripleRep} (\ref{IsRZMSIsoByTripleRep}) and does not check that \texttt{triple} actually defines an isomorphism from \texttt{rzms1} to \texttt{rzms2} or that the arguments even make sense. To create an isomorphism from \texttt{rzms1} to \texttt{rzms2} use \texttt{IsomorphismSemigroups} (\ref{IsomorphismSemigroups}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> G:=Group((1,4,3,5,2));;
gap> ZG:=ZeroGroup(G);
<zero group with 2 generators>
gap> mat:=[ [ (), (), () ], [ (), (1,4,3,5,2), () ], [ (), (1,3,2,4,5), () ] ];;
gap> mat:=List(mat, x-> List(x, ZeroGroupElt));
[ [ (), (), () ], [ (), (1,4,3,5,2), () ], [ (), (1,3,2,4,5), () ] ]
gap> rms:=ReesZeroMatrixSemigroup(ZG, mat);
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> l:=(4,6);;
gap> g:=GroupHomomorphismByImages(G, G, [(1,4,3,5,2)], [(1,2,5,3,4)]);
[ (1,4,3,5,2) ] -> [ (1,2,5,3,4) ]
gap> g:=ZeroGroupAutomorphism(ZG, g);
<mapping: <zero group with 2 generators> -> <zero group with 2 generators> >
gap> map:=List([(), (1,5,4,2,3), (), (), (), () ], ZeroGroupElt);;
gap> RZMSIsoByTriple(rms, rms, [l, g, map]);
[ (4,6), <mapping: <zero group with 2 generators> -> <zero group with
2 generators> >,
[ ZeroGroup(()), ZeroGroup((1,5,4,2,3)), ZeroGroup(()), ZeroGroup(()),
ZeroGroup(()), ZeroGroup(()) ] ]
gap> RZMSIsoByTriple(rms, rms, [l, g, [()]]);
[ (4,6), <mapping: <zero group with 2 generators> -> <zero group with
2 generators> >, [ () ] ]
gap> IsRZMSIsoByTripleRep(last);
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsRMSIsoByTripleRep}}
\logpage{[ 7, 5, 3 ]}\nobreak
\hyperdef{L}{X7A5A209283929D7C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsRMSIsoByTripleRep({\slshape f})\index{IsRMSIsoByTripleRep@\texttt{IsRMSIsoByTripleRep}}
\label{IsRMSIsoByTripleRep}
}\hfill{\scriptsize (Representation)}}\\
returns \texttt{true} if the object \texttt{f} is represented as an isomorphism of Rees matrix semigroups by a triple; as
explained in \cite[Section 2]{computing}; see \texttt{RMSIsoByTriple} (\ref{RMSIsoByTriple}) for an example of the usage of this command.
}
\subsection{\textcolor{Chapter }{IsRZMSIsoByTripleRep}}
\logpage{[ 7, 5, 4 ]}\nobreak
\hyperdef{L}{X7FFE01D17DC054E8}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsRZMSIsoByTripleRep({\slshape f})\index{IsRZMSIsoByTripleRep@\texttt{IsRZMSIsoByTripleRep}}
\label{IsRZMSIsoByTripleRep}
}\hfill{\scriptsize (Representation)}}\\
returns \texttt{true} if the object \texttt{f} is represented as an isomorphism of Rees matrix semigroups by a triple; as
explained in \cite[Section 2]{computing}; see \texttt{RZMSIsoByTriple} (\ref{RZMSIsoByTriple}) for an example of the usage of this command.
}
\subsection{\textcolor{Chapter }{RMSInducedFunction}}
\logpage{[ 7, 5, 5 ]}\nobreak
\hyperdef{L}{X7F0CCB2B83C07D54}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RMSInducedFunction({\slshape RMS, lambda, gamma, g})\index{RMSInducedFunction@\texttt{RMSInducedFunction}}
\label{RMSInducedFunction}
}\hfill{\scriptsize (operation)}}\\
\texttt{lambda} is an automorphism of the graph associated to the Rees matrix semigroup \texttt{RMS}, \texttt{gamma} an automorphism of the underlying group of \texttt{RMS}, and \texttt{g} an element of the underlying group of \texttt{RMS}. The function \texttt{RMSInducedFunction} attempts to find the function determined by \texttt{lambda} and \texttt{gamma} from the union of the index sets \texttt{I} and \texttt{J} to the group \texttt{G} of the Rees matrix semigroup \texttt{RMS} over \texttt{G}, \texttt{I}, and \texttt{J} with respect to \texttt{P} where the first element is given by the element \texttt{g}. If a conflict is found, then \texttt{false} is returned together with the induced map; see \cite[Section 2]{computing} for further details.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> G:=Group([ (1,2) ]);;
gap> mat:=[ [ (), (), () ], [ (), (1,2), () ], [ (), (1,2), (1,2) ],
> [ (), (), () ], [ (), (1,2), () ] ];;
gap> rms:=ReesMatrixSemigroup(G, mat);;
gap> l:=(1,2)(4,5,6);
(1,2)(4,5,6)
gap> gam:=One(AutomorphismGroup(G));
IdentityMapping( Group([ (1,2) ]) )
gap> g:=(1,2);
gap> RMSInducedFunction(rms, l, gam, g);
[ false, [ (1,2), (), (), (), (), (1,2), (1,2), () ] ]
gap> RMSInducedFunction(rms, (4,7), gam, ());
[ true, [ (), (), (), (), (), (), (), () ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RZMSInducedFunction}}
\logpage{[ 7, 5, 6 ]}\nobreak
\hyperdef{L}{X7D17056F79E5649F}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RZMSInducedFunction({\slshape RZMS, lambda, gamma, g, comp})\index{RZMSInducedFunction@\texttt{RZMSInducedFunction}}
\label{RZMSInducedFunction}
}\hfill{\scriptsize (operation)}}\\
\texttt{lambda} is an automorphism of the graph associated to the Rees 0- matrix semigroup \texttt{RZMS}, \texttt{gamma} an automorphism of the underlying zero group of \texttt{RZMS}, \texttt{comp} is a connected component of the graph associated to \texttt{RZMS}, and \texttt{g} is an element of the underlying zero group of \texttt{RZMS}. The function \texttt{RZMSInducedFunction} attempts to find the partial function determined by \texttt{lambda} and \texttt{gamma} from \texttt{comp} to the zero group \texttt{G\texttt{\symbol{94}}0} of \texttt{G} of the Rees 0-matrix semigroup \texttt{RZMS} over \texttt{G\texttt{\symbol{94}}0}, \texttt{I}, and \texttt{J} with respect to \texttt{P} where the image of the first element in \texttt{comp} is given by the element \texttt{g}. If a conflict is found, then \texttt{fail} is returned; see \cite[Section 2]{computing} for further details.
\textsc{Please note:} if \textsf{grape} is not loaded, then this function will not work.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> zg:=ZeroGroup(Group(()));;
gap> z:=Elements(zg)[1];
0
gap> x:=Elements(zg)[2];
()
gap> mat:=[ [ z, z, z ], [ x, z, z ], [ x, x, z ] ];;
gap> rzms:=ReesZeroMatrixSemigroup(zg, mat);;
gap> RZMSInducedFunction(rzms, (), One(AutomorphismGroup(zg)), x,
> [1,2,5,6])
[ (), (),,, (), () ]
gap> RZMSInducedFunction(rzms, (), One(AutomorphismGroup(zg)), x, [3]);
[ ,, () ]
gap> RZMSInducedFunction(rzms, (), One(AutomorphismGroup(zg)), x, [4]);
[ ,,, () ]
gap> zg:=ZeroGroup(Group([ (1,5,2,3), (1,4)(2,3) ]));;
gap> elts:=Elements(zg);;
gap> mat:=[ [ elts[1], elts[1], elts[11], elts[1], elts[1] ],
> [ elts[1], elts[13], elts[21], elts[1], elts[1] ],
> [ elts[1], elts[16], elts[1], elts[16], elts[3] ],
> [ elts[10], elts[17], elts[1], elts[1], elts[1] ],
> [ elts[1], elts[1], elts[1], elts[4], elts[1] ] ];
gap> rzms:=ReesZeroMatrixSemigroup(zg, mat);
gap> RZMSInducedFunction(rzms, (), Random(AutomorphismGroup(zg)),
> Random(elts), [1..10])=fail;
false
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RZMStoRZMSInducedFunction}}
\logpage{[ 7, 5, 7 ]}\nobreak
\hyperdef{L}{X84BA41977C43EAA3}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RZMStoRZMSInducedFunction({\slshape RZMS1, RZMS2, lambda, gamma, elts})\index{RZMStoRZMSInducedFunction@\texttt{RZMStoRZMSInducedFunction}}
\label{RZMStoRZMSInducedFunction}
}\hfill{\scriptsize (operation)}}\\
\texttt{lambda} is an automorphism of the graph associated to the Rees 0- matrix semigroup \texttt{RZMS1} composed with isomorphism from that graph to the graph of \texttt{RZMS2}, \texttt{gamma} an automorphism of the underlying zero group of \texttt{RZMS1}, and \texttt{elts} is a list of elements of the underlying zero group of \texttt{RZMS2}. The function \texttt{RZMStoRZMSInducedFunction} attempts to find the function determined by \texttt{lambda} and \texttt{gamma} from the union of the index sets \texttt{I} and \texttt{J} of \texttt{RZMS1} to the zero group \texttt{G\texttt{\symbol{94}}0} of the Rees 0-matrix semigroup \texttt{RZMS2} over the zero group \texttt{G\texttt{\symbol{94}}0}, sets \texttt{I} and \texttt{J}, and matrix \texttt{P} where the image of the first element in the \texttt{i}th connected component of the associated graph of \texttt{RZMS1} is given by \texttt{elts[i]}. If a conflict is found, then \texttt{false} is returned; see \cite[Section 2]{computing} for further details.
\textsc{Please note:} if \textsf{grape} is not loaded, then this function will not work.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [ 4, 4, 8, 8, 8, 8, 4, 8 ] ),
Transformation( [ 8, 2, 8, 2, 5, 5, 8, 8 ] ),
Transformation( [ 8, 8, 3, 7, 8, 3, 7, 8 ] ),
Transformation( [ 8, 6, 6, 8, 6, 8, 8, 8 ] ) ];;
gap> S:=Semigroup(gens);;
gap> D:=GreensDClasses(S);;
gap> rms1:=Range(IsomorphismReesMatrixSemigroupOfDClass(D[1]));
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> rms2:=Range(IsomorphismReesMatrixSemigroupOfDClass(D[4]));
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> gam:=One(AutomorphismGroup
> (UnderlyingSemigroupOfReesZeroMatrixSemigroup(Group(rms1))));
IdentityMapping( <zero group with 2 generators> )
gap> g:=One(UnderlyingSemigroupOfReesZeroMatrixSemigroup(rms2));
()
gap> RZMStoRZMSInducedFunction(rms1, rms2, (2,3)(5,6), gam, [g]);
[ (), (), (), (), (), () ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RZMSGraph}}
\logpage{[ 7, 5, 8 ]}\nobreak
\hyperdef{L}{X781757FD7938C9DD}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RZMSGraph({\slshape rzms})\index{RZMSGraph@\texttt{RZMSGraph}}
\label{RZMSGraph}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{rzms} is a Rees 0-matrix semigroup over a zero group \texttt{G\texttt{\symbol{94}}0}, 3 index sets \texttt{I} and \texttt{J}, and matrix \texttt{P}, then \texttt{RZMSGraph} returns the undirected bipartite graph with \texttt{|I|+|J|} vertices and edge \texttt{(i,j)} if and only if \texttt{i{\textless}|I|+1}, \texttt{j{\textgreater}|I|} and \texttt{p{\textunderscore}\texttt{\symbol{123}}j-|I|, i\texttt{\symbol{125}}} is not zero.
The returned object is a simple undirected graph created in \textsf{GRAPE} using the command
\[ Graph(Group(()), [1..n+m], OnPoints, adj, true); \]
where \texttt{adj} is \texttt{true} if and only if \texttt{i{\textless}|I|+1}, \texttt{j{\textgreater}|I|} and \texttt{p{\textunderscore}\texttt{\symbol{123}}j-|I|, i\texttt{\symbol{125}}} is not zero.
\textsc{Please note:} if \textsf{grape} is not loaded, then this function will not work.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> zg:=ZeroGroup(Group(()));;
gap> z:=Elements(zg)[1];
0
gap> x:=Elements(zg)[2];
()
gap> mat:=[ [ 0, 0, 0 ], [ (), 0, 0 ], [ (), (), 0 ] ];;
gap> rzms:=ReesZeroMatrixSemigroup(zg, mat);;
gap> RZMSGraph(rzms);
rec( isGraph := true, order := 6, group := Group(()),
schreierVector := [ -1, -2, -3, -4, -5, -6 ],
adjacencies := [ [ 5, 6 ], [ 6 ], [ ], [ ], [ 1 ], [ 1, 2 ] ],
representatives := [ 1, 2, 3, 4, 5, 6 ], names := [ 1, 2, 3, 4, 5, 6 ] )
gap> UndirectedEdges(last);
[ [ 1, 5 ], [ 1, 6 ], [ 2, 6 ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{RightTransStabAutoGroup}}
\logpage{[ 7, 5, 9 ]}\nobreak
\hyperdef{L}{X78060D7C8331F340}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightTransStabAutoGroup({\slshape S, elts, func})\index{RightTransStabAutoGroup@\texttt{RightTransStabAutoGroup}}
\label{RightTransStabAutoGroup}
}\hfill{\scriptsize (operation)}}\\
returns a right transversal of the stabilizer w.r.t the action \texttt{func} of the elements \texttt{elts} in the automorphism group of the zero semigroup, Rees matrix semigroup, or
Rees 0-matrix semigroup \texttt{S}. That is, \texttt{S} satisfying \texttt{IsZeroSemigroup} (\ref{IsZeroSemigroup}), \texttt{IsReesMatrixSemigroup} (\textbf{Reference: IsReesMatrixSemigroup}), or \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> S:=ZeroSemigroup(6);
<zero semigroup with 6 elements>
gap> elts:=Elements(S);
[ 0, z1, z2, z3, z4, z5 ]
gap> Length(RightTransStabAutoGroup(S, [elts[1]], OnSets));
1
gap> Length(RightTransStabAutoGroup(S, [elts[1], elts[2]], OnSets));
5
gap> Length(RightTransStabAutoGroup(S, [elts[1], elts[2]], OnTuples));
5
gap> G:=Group([ (1,2) ]);;
gap> mat:=[ [ (), (), () ], [ (), (1,2), () ], [ (), (1,2), (1,2) ],
> [ (), (), () ], [ (), (1,2), () ] ];;
gap> rms:=ReesMatrixSemigroup(G, mat);;
gap> Size(rms);
30
gap> GeneratorsOfSemigroup(rms);
[ (1,(),2), (1,(),3), (1,(),4), (1,(),5), (2,(),1), (3,(),1), (1,(1,2),1) ]
gap> Length(RightTransStabAutoGroup(rms, last, OnSets));
4
gap> Length(RightTransStabAutoGroup(rms, GeneratorsOfSemigroup(rms),
> OnTuples));
8
gap> G:=ZeroGroup(Group([ (1,3) ]));;
gap> z:=MultiplicativeZero(G);; x:=Elements(G)[2];;
gap> mat:=[ [ z, z, z ], [ z, z, z ], [ z, z, z ], [ z, z, z ], [ z, x, z ] ];;
gap> rzms:=ReesZeroMatrixSemigroup(G, mat);
gap> Size(rzms);
31
gap> Size(GeneratorsOfSemigroup(rzms));
6
gap> Length(RightTransStabAutoGroup(rzms, GeneratorsOfSemigroup(rzms),
> OnSets));
512
gap> A:=AutomorphismGroup(rzms);
<group of size 3072 with 3072 generators>
\end{Verbatim}
}
}
\section{\textcolor{Chapter }{Zero Groups}}\label{zerogp}
\logpage{[ 7, 6, 0 ]}
\hyperdef{L}{X7CF67DF77AC73EA9}{}
{
\subsection{\textcolor{Chapter }{ZeroGroupAutomorphism}}
\logpage{[ 7, 6, 1 ]}\nobreak
\hyperdef{L}{X7D528F958733E3D0}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroGroupAutomorphism({\slshape ZG, f})\index{ZeroGroupAutomorphism@\texttt{ZeroGroupAutomorphism}}
\label{ZeroGroupAutomorphism}
}\hfill{\scriptsize (function)}}\\
converts the group automorphism \texttt{f} of the underlying group of the zero group \texttt{ZG} into an automorphism of the zero group \texttt{ZG}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> G:=Random(AllGroups(20));
<pc group of size 20 with 3 generators>
gap> A:=AutomorphismGroup(G);
<group with 2 generators>
gap> f:=Random(A);
[ f1*f2^4*f3 ] -> [ f1*f2^2 ]
gap> ZG:=ZeroGroup(G);
<zero group with 4 generators>
gap> ZeroGroupAutomorphism(ZG, f);
<mapping: <zero group with 4 generators> -> <zero group with 4 generators> >
gap> IsZeroGroupAutomorphismRep(last);
true
gap> UnderlyingGroupAutoOfZeroGroupAuto(last2)=f;
true
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsZeroGroupAutomorphismRep}}
\logpage{[ 7, 6, 2 ]}\nobreak
\hyperdef{L}{X862AACCF7C528811}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsZeroGroupAutomorphismRep({\slshape f})\index{IsZeroGroupAutomorphismRep@\texttt{IsZeroGroupAutomorphismRep}}
\label{IsZeroGroupAutomorphismRep}
}\hfill{\scriptsize (Representation)}}\\
returns \texttt{true} if the object \texttt{f} is represented as an automorphism of a zero group; see \texttt{ZeroGroupAutomorphism} (\ref{ZeroGroupAutomorphism}) for an example of the usage of this command. }
\subsection{\textcolor{Chapter }{UnderlyingGroupAutoOfZeroGroupAuto}}
\logpage{[ 7, 6, 3 ]}\nobreak
\hyperdef{L}{X7DDB3B727B0C7CA5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{UnderlyingGroupAutoOfZeroGroupAuto({\slshape f})\index{UnderlyingGroupAutoOfZeroGroupAuto@\texttt{UnderlyingGroupAutoOfZeroGroupAuto}}
\label{UnderlyingGroupAutoOfZeroGroupAuto}
}\hfill{\scriptsize (attribute)}}\\
returns the underlying group automorphism of the zero group automorphism \texttt{f}. That is, the restriction of \texttt{f} to its source without the zero; see \texttt{ZeroGroupAutomorphism} (\ref{ZeroGroupAutomorphism}) for an example of the usage of this command. }
}
\section{\textcolor{Chapter }{Isomorphisms}}\label{iso}
\logpage{[ 7, 7, 0 ]}
\hyperdef{L}{X7D702EA087C1C5EF}{}
{
\subsection{\textcolor{Chapter }{IsomorphismAutomorphismGroupOfRMS}}
\logpage{[ 7, 7, 1 ]}\nobreak
\hyperdef{L}{X7965B0D07EFFBDA0}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismAutomorphismGroupOfRMS({\slshape G})\index{IsomorphismAutomorphismGroupOfRMS@\texttt{IsomorphismAutomorphismGroupOfRMS}}
\label{IsomorphismAutomorphismGroupOfRMS}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{G} is the automorphism group of a simple transformation semigroup, then \texttt{IsomorphismAutomorphismGroupOfRMS} returns a \texttt{GroupHomomorphismByImages} (\textbf{Reference: GroupHomomorphismByImages}) from the automorphism group of \texttt{G} to the automorphism group of an isomorphic Rees matrix semigroup, obtained by
using \texttt{IsomorphismReesMatrixSemigroup} (\ref{IsomorphismReesMatrixSemigroup}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([1,2,2,1,2]);;
gap> g2:=Transformation([3,4,3,4,4]);;
gap> g3:=Transformation([3,4,3,4,3]);;
gap> g4:=Transformation([4,3,3,4,4]);;
gap> cs5:=Semigroup(g1,g2,g3,g4);;
gap> AutomorphismGroup(cs5);
<group of size 16 with 3 generators>
gap> IsomorphismAutomorphismGroupOfRMS(last);
[ SemigroupHomomorphism ( <semigroup with 4 generators>-><semigroup with
4 generators>), SemigroupHomomorphism ( <semigroup with
4 generators>-><semigroup with 4 generators>),
SemigroupHomomorphism ( <semigroup with 4 generators>-><semigroup with
4 generators>) ] ->
[ [ (1,4)(2,3)(5,6), IdentityMapping( Group( [ (1,2) ] ) ),
[ (), (1,2), (1,2), (), (), () ] ],
[ (1,3,4,2), IdentityMapping( Group( [ (1,2) ] ) ),
[ (), (), (), (), (), (1,2) ] ],
[ (1,3)(2,4), IdentityMapping( Group( [ (1,2) ] ) ),
[ (), (), (), (), (), (1,2) ] ] ]
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsomorphismPermGroup}}
\logpage{[ 7, 7, 2 ]}\nobreak
\hyperdef{L}{X80B7B1C783AA1567}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismPermGroup({\slshape G})\index{IsomorphismPermGroup@\texttt{IsomorphismPermGroup}}
\label{IsomorphismPermGroup}
}\hfill{\scriptsize (attribute)}}\\
if \texttt{G} satisfies \texttt{IsAutomorphismGroupOfSimpleSemigp} (\ref{IsAutomorphismGroupOfSimpleSemigp}), then \texttt{IsomorphismPermGroup} returns an isomorphism from \texttt{G} to a permutation group by composing the result \texttt{f} of \texttt{IsomorphismAutomorphismGroupOfRMS} (\ref{IsomorphismAutomorphismGroupOfRMS}) on \texttt{G} with the result of \texttt{IsomorphismPermGroup} on \texttt{Range(f)}.
if \texttt{G} satisfies \texttt{IsAutomorphismGroupOfRMS} (\ref{IsAutomorphismGroupOfRMS}) or \texttt{IsAutomorphismGroupOfRZMS} (\ref{IsAutomorphismGroupOfRZMS}), then \texttt{IsomorphismPermGroup} returns an isomorphism from \texttt{G} to a permutation group acting either on the elements of \texttt{S} or on itself, whichever gives a permutation group of lower degree.
if \texttt{G} is a transformation semigroup that satisfies \texttt{IsGroupAsSemigroup} (\ref{IsGroupAsSemigroup}), then \texttt{IsomorphismPermGroup} returns an isomorphism from \texttt{G} to the permutation group obtained by applying \texttt{AsPermOfRange} (\ref{AsPermOfRange}) to any element of \texttt{G}.
if \texttt{G} is a group \texttt{H}-class of a transformation semigroup, then \texttt{IsomorphismPermGroup} returns an isomorphism from \texttt{G} to the permutation group obtained by applying \texttt{AsPermOfRange} (\ref{AsPermOfRange}) to any element of \texttt{G}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation([3,3,2,6,2,4,4,6]);;
gap> g2:=Transformation([5,1,7,8,7,5,8,1]);;
gap> cs1:=Semigroup(g1,g2);;
gap> AutomorphismGroup(cs1);
<group of size 12 with 2 generators>
gap> IsomorphismPermGroup(last);
[ SemigroupHomomorphism ( <semigroup with 2 generators>-><semigroup with
2 generators>), SemigroupHomomorphism ( <semigroup with
2 generators>-><semigroup with 2 generators>) ] ->
[ (1,11,2,12,3,10)(4,8,5,9,6,7), (1,6)(2,5)(3,4)(7,10)(8,12)(9,11) ]
gap> Size(cs1);
96
gap> a:=IdempotentNC([[1,3,4],[2,5],[6],[7],[8]],[3,5,6,7,8])*(3,5);;
gap> b:=IdempotentNC([[1,3,4],[2,5],[6],[7],[8]],[3,5,6,7,8])*(3,6,7,8);;
gap> S:=Semigroup(a,b);;
gap> IsGroupAsTransSemigroup(S);
true
gap> IsomorphismPermGroup(S);
SemigroupHomomorphism ( <semigroup with 2 generators>->Group(
[ (3,5), (3,6,7,8) ]))
gap> gens:=[Transformation([3,5,3,3,5,6]), Transformation([6,2,4,2,2,6])];;
gap> S:=Semigroup(gens);;
gap> H:=GroupHClassOfGreensDClass(GreensDClassOfElement(S, Elements(S)[1]));
{Transformation( [ 2, 2, 2, 2, 2, 6 ] )}
gap> IsomorphismPermGroup(H);
SemigroupHomomorphism ( {Transformation( [ 2, 2, 2, 2, 2, 6 ] )}->Group(()))
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsomorphismFpSemigroup}}
\logpage{[ 7, 7, 3 ]}\nobreak
\hyperdef{L}{X869F966B8196F28C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismFpSemigroup({\slshape S})\index{IsomorphismFpSemigroup@\texttt{IsomorphismFpSemigroup}}
\label{IsomorphismFpSemigroup}
}\hfill{\scriptsize (attribute)}}\\
returns an isomorphism to a finitely presented semigroup from the
transformation semigroup \texttt{S}. This currently works by running the function \texttt{FroidurePinExtendedAlg} (FroidurePinExtendedAlg???) in the library.
If \texttt{S} satisfies \texttt{IsMonoid} (\textbf{Reference: IsMonoid}), use the command \texttt{IsomorphismFpMonoid} (\ref{IsomorphismFpMonoid}) instead.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> gens:=[ Transformation( [1,8,11,2,5,16,13,14,3,6,15,10,7,4,9,12 ] ),
> Transformation( [1,16,9,6,5,8,13,12,15,2,3,4,7,10,11,14] ),
> Transformation( [1,3,7,9,1,15,5,11,13,11,13,3,5,15,7,9 ] ) ];
gap> S:=Semigroup(gens);
<semigroup with 3 generators>
gap> IsomorphismFpSemigroup(last);
SemigroupHomomorphismByImages ( <trans. semigroup of size 16 with
3 generators>->Semigroup( [ s1, s2, s3 ] ))
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsomorphismFpMonoid}}
\logpage{[ 7, 7, 4 ]}\nobreak
\hyperdef{L}{X7F2ADC587DF698A2}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismFpMonoid({\slshape S})\index{IsomorphismFpMonoid@\texttt{IsomorphismFpMonoid}}
\label{IsomorphismFpMonoid}
}\hfill{\scriptsize (attribute)}}\\
returns an isomorphism to a finitely presented monoid from the transformation
monoid \texttt{S}. Currently works by running the function \texttt{FroidurePinExtendedAlg} (FroidurePinExtendedAlg???) in the library.
If \texttt{S} satisfies \texttt{IsSemigroup} (\textbf{Reference: IsSemigroup}), use the command \texttt{IsomorphismFpSemigroup} (\ref{IsomorphismFpSemigroup}) instead.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> x:=Transformation([2,3,4,5,6,7,8,9,1]);;
gap> y:=Transformation([4,2,3,4,5,6,7,8,9]);;
gap> S:=Monoid(x,y);;
gap> IsomorphismFpMonoid(last);
SemigroupHomomorphismByImages ( <trans. semigroup of size 40266 with
3 generators>->Monoid( [ m1, m2 ], ... ))
gap> Length(RelationsOfFpMonoid(Range(last)));
932
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsomorphismSemigroups}}
\logpage{[ 7, 7, 5 ]}\nobreak
\hyperdef{L}{X8248C522825E2684}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismSemigroups({\slshape S, T})\index{IsomorphismSemigroups@\texttt{IsomorphismSemigroups}}
\label{IsomorphismSemigroups}
}\hfill{\scriptsize (operation)}}\\
this operation returns an isomorphism from the semigroup \texttt{S} to the semigroup \texttt{T} if one exists and returns \texttt{fail} otherwise.
\textsc{Please note:} this function currently only works for zero groups, zero semigroups, Rees
matrix semigroups, and Rees 0-matrix semigroups.
\textsc{Please note:} if \textsf{grape} is not loaded, then this function will not work when \texttt{S} and \texttt{T} satisfy \texttt{IsReesZeroMatrixSemigroup} (\textbf{Reference: IsReesZeroMatrixSemigroup}).
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> ZG1:=ZeroGroup(Group((1,2,3,5,4)));
<zero group with 2 generators>
gap> ZG2:=ZeroGroup(Group((1,2,3,4,5)));
<zero group with 2 generators>
gap> IsomorphismSemigroups(ZG1, ZG2);
SemigroupHomomorphismByImagesOfGens ( <zero group with
2 generators>-><zero group with 2 generators>)
gap> ZG2:=ZeroGroup(Group((1,2,3,4)));
<zero group with 2 generators>
gap> IsomorphismSemigroups(ZG1, ZG2);
fail
gap> IsomorphismSemigroups(ZeroSemigroup(5),ZeroSemigroup(5));
IdentityMapping( <zero semigroup with 5 elements> )
gap> IsomorphismSemigroups(ZeroSemigroup(5),ZeroSemigroup(6));
fail
gap> gens:=[ Transformation( [ 4, 4, 8, 8, 8, 8, 4, 8 ] ),
> Transformation( [ 8, 2, 8, 2, 5, 5, 8, 8 ] ),
> Transformation( [ 8, 8, 3, 7, 8, 3, 7, 8 ] ),
> Transformation( [ 8, 6, 6, 8, 6, 8, 8, 8 ] ) ];;
gap> S:=Semigroup(gens);;
gap> D:=GreensDClasses(S);;
gap> rms1:=Range(IsomorphismReesMatrixSemigroupOfDClass(D[1]));;
gap> rms2:=Range(IsomorphismReesMatrixSemigroupOfDClass(D[4]));;
gap> IsomorphismSemigroups(rms1, rms2);
[ (2,3)(5,6), IdentityMapping( <zero group with 2 generators> ),
[ ZeroGroup(()), ZeroGroup(()), ZeroGroup(()), ZeroGroup(()),
ZeroGroup(()), ZeroGroup(()) ] ]
gap> IsomorphismSemigroups(rms2, rms1);
[ (2,3)(5,6), IdentityMapping( <zero group with 2 generators> ),
[ ZeroGroup(()), ZeroGroup(()), ZeroGroup(()), ZeroGroup(()),
ZeroGroup(()), ZeroGroup(()) ] ]
gap> rms2:=Range(IsomorphismReesMatrixSemigroupOfDClass(D[2]));
Group(())
gap> IsomorphismSemigroups(rms2, rms1);
fail
gap> rms2:=RandomReesZeroMatrixSemigroup(5,5,5);
Rees Zero Matrix Semigroup over <zero group with 2 generators>
gap> IsomorphismSemigroups(rms2, rms1);
fail
gap> rms2:=RandomReesMatrixSemigroup(5,5,5);
Rees Matrix Semigroup over Group([ (1,2)(3,4,5), (2,4,3), (1,4,5,3),
(1,4,5,2) ])
gap> IsomorphismSemigroups(rms2, rms1);
fail
gap> IsomorphismSemigroups(rms1, rms2);
fail
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsomorphismReesMatrixSemigroupOfDClass}}
\logpage{[ 7, 7, 6 ]}\nobreak
\hyperdef{L}{X7FE2262679DD9D52}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismReesMatrixSemigroupOfDClass({\slshape D})\index{IsomorphismReesMatrixSemigroupOfDClass@\texttt{IsomorphismReesMatrixSemigroupOfDClass}}
\label{IsomorphismReesMatrixSemigroupOfDClass}
}\hfill{\scriptsize (attribute)}}\\
The \emph{principal factor} of the \texttt{D}-class \texttt{D} is the semigroup with elements \texttt{D} and \texttt{0} and multiplication \texttt{x*y} defined to be the product \texttt{xy} in the semigroup containing \texttt{D} if \texttt{xy} in \texttt{D} and \texttt{0} otherwise.
\texttt{IsomorphismReesMatrixSemigroupOfDClass} returns an isomorphism from the principal factor of the \texttt{D}-class \texttt{D} to a Rees matrix, Rees 0-matrix or zero semigroup, as given by the
Rees-Suschewitsch Theorem; see \cite[Theorem 3.2.3]{howie}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation( [ 4, 6, 3, 8, 5, 6, 10, 4, 3, 7 ] );;
gap> g2:=Transformation( [ 5, 6, 6, 3, 8, 6, 3, 7, 8, 4 ] );;
gap> g3:=Transformation( [ 8, 6, 3, 2, 8, 10, 9, 2, 6, 2 ] );;
gap> m23:=Monoid(g1,g2,g3);;
gap> D:=GreensDClasses(m23)[17];
{Transformation( [ 7, 6, 6, 6, 7, 4, 8, 6, 6, 6 ] )}
gap> IsomorphismReesMatrixSemigroupOfDClass(D);
SemigroupHomomorphism ( {Transformation( [ 7, 6, 6, 6, 7, 4, 8, 6, 6, 6
] )}-><zero semigroup with 3 elements>)
gap> D:=GreensDClasses(m23)[77];
{Transformation( [ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 ] )}
gap> IsomorphismReesMatrixSemigroupOfDClass(D);
SemigroupHomomorphism ( {Transformation( [ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6
] )}->Rees Matrix Semigroup over Group(()))
gap> D:=GreensDClasses(m23)[1];
{Transformation( [ 1 .. 10 ] )}
gap> IsomorphismReesMatrixSemigroupOfDClass(D);
SemigroupHomomorphism ( {Transformation( [ 1 .. 10 ] )}->Group(()))
gap> D:=GreensDClasses(m23)[23];
{Transformation( [ 6, 7, 3, 6, 6, 6, 6, 6, 7, 6 ] )}
gap> IsomorphismReesMatrixSemigroupOfDClass(D);
SemigroupHomomorphism ( {Transformation( [ 6, 7, 3, 6, 6, 6, 6, 6, 7, 6
] )}->Rees Zero Matrix Semigroup over <zero group with 3 generators>)
\end{Verbatim}
}
\subsection{\textcolor{Chapter }{IsomorphismReesMatrixSemigroup}}
\logpage{[ 7, 7, 7 ]}\nobreak
\hyperdef{L}{X7964B5C97FB9C07D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismReesMatrixSemigroup({\slshape S})\index{IsomorphismReesMatrixSemigroup@\texttt{IsomorphismReesMatrixSemigroup}}
\label{IsomorphismReesMatrixSemigroup}
}\hfill{\scriptsize (operation)}}\\
returns an isomorphism from the (completely) simple transformation semigroup \texttt{S} to a Rees matrix semigroup, as given by the Rees-Suschewitsch Theorem; see \cite[Theorem 3.2.3]{howie}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> g1:=Transformation( [ 2, 3, 4, 5, 1, 8, 7, 6, 2, 7 ] );;
gap> g2:=Transformation( [ 2, 3, 4, 5, 6, 8, 7, 1, 2, 2 ] );;
gap> cs2:=Semigroup(g1,g2);;
gap> IsomorphismReesMatrixSemigroup(cs2);
SemigroupHomomorphism ( <semigroup with
2 generators>->Rees Matrix Semigroup over Group(
[ (2,5)(3,8)(4,6), (1,6,3)(5,8) ]))
\end{Verbatim}
}
}
}
\def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}
\bibliographystyle{alpha}
\bibliography{MONOID}
\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}
\printindex
\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1924
