% This file was created automatically from semigrp.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  semigrp.msk                GAP documentation                Thomas Breuer
%%
%A  @(#)$Id: semigrp.msk,v 1.23 2003/10/24 16:52:42 gap Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Semigroups}

This chapter describes functions for creating semigroups
and determining information about them.

%%  Support for algebraic semigroup theory in {\GAP} was designed by Andrew
%%  Solomon, based on code by Goetz Pfeiffer, and was implemented by Isabel
%%  Araujo, Robert Arthur, and Andrew Solomon.

\>IsSemigroup( <D> ) P

returns `true' if the object <D> is a semigroup.
\index{semigroup}
A *semigroup* is a magma (see~"Magmas") with associative multiplication.



\>Semigroup( <gen1>, <gen2> ... ) F
\>Semigroup( <gens> ) F

In the first form, `Semigroup' returns the semigroup generated by the
arguments <gen1>, <gen2>, \dots,
that is, the closure of these elements under multiplication.
In the second form, `Semigroup' returns the semigroup generated by the
elements in the homogeneous list <gens>;
a square matrix as only argument is treated as one generator,
not as a list of generators.

It is *not* checked whether the underlying multiplication is associative,
use `Magma' (see~"Magma") and `IsAssociative' (see~"IsAssociative")
if you want to check whether a magma is in fact a semigroup.



\beginexample
gap> a:= Transformation([2, 3, 4, 1]);
Transformation( [ 2, 3, 4, 1 ] )
gap> b:= Transformation([2, 2, 3, 4]);
Transformation( [ 2, 2, 3, 4 ] )
gap> s:= Semigroup(a, b);
<semigroup with 2 generators>
\endexample

\>Subsemigroup( <S>, <gens> ) F
\>SubsemigroupNC( <S>, <gens> ) F

are just synonyms of `Submagma' and `SubmagmaNC', respectively
(see~"Submagma").



\beginexample
gap> a:=GeneratorsOfSemigroup(s)[1];
Transformation( [ 2, 3, 4, 1 ] )
gap> t:=Subsemigroup(s,[a]);
<semigroup with 1 generator>
\endexample

\>SemigroupByGenerators( <gens> ) O

is the underlying operation of `Semigroup' (see~"Semigroup").



\>AsSemigroup( <C> ) A

If <C> is a collection whose elements form a semigroup
(see~"IsSemigroup") then `AsSemigroup' returns this semigroup.
Otherwise `fail' is returned.


\>AsSubsemigroup( <D>, <C> ) O

Let <D> be a domain and <C> a collection.
If <C> is a subset of <D> that forms a semigroup then `AsSubsemigroup'
returns this semigroup, with parent <D>.
Otherwise `fail' is returned.


\>GeneratorsOfSemigroup( <S> ) A

Semigroup generators of a semigroup <D> are the same as magma generators
(see~"GeneratorsOfMagma").



\beginexample
gap> GeneratorsOfSemigroup(s);
[ Transformation( [ 2, 3, 4, 1 ] ), Transformation( [ 2, 2, 3, 4 ] ) ]
gap> GeneratorsOfSemigroup(t);
[ Transformation( [ 2, 3, 4, 1 ] ) ]
\endexample

\>FreeSemigroup( [<wfilt>, ]<rank> )!{with examples} F
\>FreeSemigroup( [<wfilt>, ]<rank>, <name> )!{with examples} F
\>FreeSemigroup( [<wfilt>, ]<name1>, <name2>, ... )!{with examples} F
\>FreeSemigroup( [<wfilt>, ]<names> )!{with examples} F
\>FreeSemigroup( [<wfilt>, ]infinity, <name>, <init> )!{with examples} F

Called in the first form, `FreeSemigroup' returns a free semigroup on
<rank> generators.
Called in the second form, `FreeSemigroup' returns a free semigroup on
<rank> generators, printed as `<name>1', `<name>2' etc.,
that is, each name is the concatenation of the string <name> and an
integer from `1' to <range>.
Called in the third form, `FreeSemigroup' returns a free semigroup on
as many generators as arguments, printed as <name1>, <name2> etc.
Called in the fourth form, `FreeSemigroup' returns a free semigroup on
as many generators as the length of the list <names>, the $i$-th
generator being printed as `<names>[$i$]'.
Called in the fifth form, `FreeSemigroup' returns a free semigroup on
infinitely many generators, where the first generators are printed
by the names in the list <init>, and the other generators by <name>
and an appended number.

If the extra argument <wfilt> is given, it must be either
`IsSyllableWordsFamily' or `IsLetterWordsFamily' or
`IsWLetterWordsFamily' or `IsBLetterWordsFamily'. The filter then
specifies the representation used for the elements of the free group
(see~"Representations for Associative Words"). If no such filter is
given, a letter representation is used.



\beginexample
gap> f1 := FreeSemigroup( 3 );
<free semigroup on the generators [ s1, s2, s3 ]>
gap> f2 := FreeSemigroup( 3 , "generator" );
<free semigroup on the generators [ generator1, generator2, generator3 ]>
gap> f3 := FreeSemigroup( "gen1" , "gen2" );
<free semigroup on the generators [ gen1, gen2 ]>
gap> f4 := FreeSemigroup( ["gen1" , "gen2"] );
<free semigroup on the generators [ gen1, gen2 ]>
\endexample

\>SemigroupByMultiplicationTable( <A> ) F

returns the semigroup whose multiplication is defined by the square
matrix <A> (see~"MagmaByMultiplicationTable") if such a semigroup exists.
Otherwise `fail' is returned.



The following functions determine information
about semigroups:

\>IsRegularSemigroup( <S> ) P

returns `true' if <S> is regular---i.e. if every D class of <S> is regular.


\>IsRegularSemigroupElement( <S>, <x> ) O

returns `true' if <x> has a general inverse in <S>---i.e. there is an 
element $y\in S$ such that $xyx=x$ and $yxy=y$.


\>IsSimpleSemigroup( <S> ) P

is `true' if and only if the semigroup has no proper ideals.


\>IsZeroSimpleSemigroup( <S> ) P

is `true' if and only if the semigroup has no proper ideals except for 0,
where <S> is a semigroup with zero. 
If the semigroup does not find its zero, then a break-loop is entered.


\>IsZeroGroup( <S> ) P

is `true' if and only if the semigroup is a group with zero
adjoined.


\>IsReesCongruenceSemigroup( <S> ) P

returns `true' if <S> is a Rees Congruence semigroup, that is,
if all congruences of <S> are Rees Congruences.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Making transformation semigroups}

Cayley's Theorem gives special status to semigroups of
transformations, and accordingly there are special functions
to deal with them, and to create them from other finite
semigroups.

\>IsTransformationSemigroup( <obj> ) P
\>IsTransformationMonoid( <obj> ) P

	A transformation semigroup (resp. monoid) is a subsemigroup
	(resp. submonoid) of the full transformation monoid.
	Note that for a transformation semigroup to be a transformation monoid
	we necessarily require the identity transformation to be an element.


\>DegreeOfTransformationSemigroup( <S> ) A

	The number of points the semigroup acts on.

\>IsomorphismTransformationSemigroup( <S> ) A
\>HomomorphismTransformationSemigroup( <S>, <r> ) O


IsomorphismTransformationSemigroup is a generic attribute which 
is a transformation semigroup isomorphic to <S> (if such can 
be computed). In the case of an fp- semigroup, a todd-coxeter
will be attempted. For a semigroup of endomorphisms of a finite 
domain of <n> elements, it will be to a semigroup of transformations
of $\{1, \ldots, n\}$. Otherwise, it will be the right regular 
representation on $S$ or $S^1$ if $S$ has no 
MultiplicativeNeutralElement.

HomomorphismTransformationSemigroup
finds a representation of <S> as transformations of the set of
equivalence classes of the right congruence <r>.


\>IsFullTransformationSemigroup( <obj> ) P


\>FullTransformationSemigroup( <degree> ) F

Returns the full transformation semigroup of degree <degree>.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Ideals of semigroups}

Ideals of semigroups are the same as ideals of the semigroup when 
considered as a magma.
For documentation on ideals for magmas, see `Magma' ("Magma").

\>SemigroupIdealByGenerators( <S>, <gens> ) O

<S> is a semigroup, <gens> is a list of elements of <S>.
Returns the two-sided ideal of <S> generated by <gens>.


\>ReesCongruenceOfSemigroupIdeal( <I> ) A

A two sided ideal <I> of a semigroup <S>  defines a congruence on 
<S> given by $\Delta \cup I \times I$.


\>IsLeftSemigroupIdeal( <I> ) P
\>IsRightSemigroupIdeal( <I> ) P
\>IsSemigroupIdeal( <I> ) P

Categories of semigroup ideals.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Congruences for semigroups}

An equivalence or a congruence on a semigroup is the
equivalence or congruence on the semigroup considered as a magma.
So, to deal with equivalences and congruences on semigroups,
magma functions are used.
For documentation on equivalences and congruences for magmas,
see `Magma' ("Magma").

\>IsSemigroupCongruence( <c> ) P

a magma congruence <c> on a semigroup.


\>IsReesCongruence( <c> ) P

returns true precisely when the congruence <c> has at most one
nonsingleton congruence class.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Quotients}

Given a semigroup and a congruence on the semigroup, one
can construct a new semigroup: the quotient semigroup.
The following functions deal with quotient semigroups in {\GAP}.

\>IsQuotientSemigroup( <S> ) C

	is the category of semigroups constructed from another semigroup 
	and a congruence on it


Elements of a quotient semigroup are equivalence classes of 
elements of `QuotientSemigroupPreimage(<S>)'
under the congruence `QuotientSemigroupCongruence(<S>)'.

It is probably most useful for calculating the elements of 
the equivalence classes by using Elements or by looking at the
images of elements of the `QuotientSemigroupPreimage(<S>)' under
`QuotientSemigroupHomomorphism(<S>)':`QuotientSemigroupPreimage(<S>)'
$\rightarrow$ <S>.

For intensive computations in a quotient semigroup, it is probably
worthwhile finding another representation as the equality test 
could involve enumeration of the elements of the congruence classes
being compared.


\>HomomorphismQuotientSemigroup( <cong> ) F

for a congruence <cong> and a semigroup <S>. 
Returns the homomorphism from <S> to the quotient of <S> 
by <cong>.


\>QuotientSemigroupPreimage( <S> ) A
\>QuotientSemigroupCongruence( <S> ) A
\>QuotientSemigroupHomomorphism( <S> ) A

	for a quotient semigroup <S>.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Green's Relations}

Green's equivalence relations play a very important role in semigroup
theory. In this section we describe how they can be used in {\GAP}.

The five Green's relations are <R>, <L>, <J>, <H>, <D>:
two elements <x>, <y> from <S> are <R>-related if and only if
$xS^1 = yS^1$, <L>-related if and only if $S^1x=S^1y$ and <J>-related
if and only if $S^1xS^1=S^1yS^1$; finally, $H = R \wedge L$, and
$D = R \circ L$.

Recall that relations <R>, <L> and <J> induce a partial order among
the elements of the semigroup: for two elements <x>, <y> from <S>,
we say that <x> is  less than or equal to <y> in the order on <R>
if $xS^1 \subseteq yS^1$;
similarly, $x$ is less than or equal to $y$ under $L$ if
$S^1x\subseteq S^1y$;
finally <x> is less than or equal to <y> under <J> if
$S^1xS^1 \subseteq S^1tS^1$.
We extend this preorder to a partial order on equivalence classes in
the natural way.



\>GreensRRelation( <semigroup> ) A
\>GreensLRelation( <semigroup> ) A
\>GreensJRelation( <semigroup> ) A
\>GreensDRelation( <semigroup> ) A
\>GreensHRelation( <semigroup> ) A

The Green's relations (which are equivalence relations)
are attributes of the semigroup <semigroup>.

\>IsGreensRelation( <bin-relation> ) P
\>IsGreensRRelation( <equiv-relation> ) P
\>IsGreensLRelation( <equiv-relation> ) P
\>IsGreensJRelation( <equiv-relation> ) P
\>IsGreensHRelation( <equiv-relation> ) P
\>IsGreensDRelation( <equiv-relation> ) P



\>IsGreensClass( <equiv-class> ) P
\>IsGreensRClass( <equiv-class> ) P
\>IsGreensLClass( <equiv-class> ) P
\>IsGreensJClass( <equiv-class> ) P
\>IsGreensHClass( <equiv-class> ) P
\>IsGreensDClass( <equiv-class> ) P

return `true' if the equivalence class <equiv-class> is
a Green's class of any type, or of <R>, <L>, <J>, <H>, <D> type,
respectively, or `false' otherwise.


\>IsGreensLessThanOrEqual( <C1>, <C2> ) O

returns `true' if the greens class <C1> is less than or equal to <C2> 
under the respective ordering (as defined above), and `false' otherwise. 

Only defined for R, L and J classes.


\>RClassOfHClass( <H> ) A
\>LClassOfHClass( <H> ) A

are attributes reflecting the natural ordering over the various Green's
classes. `RClassOfHClass' and `LClassOfHClass' return the <R> and 
<L> classes	respectively in which an <H> class is contained.   


%Declaration{IsGreensRClassEnumerator}
\>EggBoxOfDClass( <Dclass> ) A

returns for a Green's D class <Dclass> a matrix whose  rows  represent  R
classes and columns represent L classes. The entries are the H classes.


\>DisplayEggBoxOfDClass( <Dclass> ) F

displays a ``picture'' of the D class <Dclass>, as an array of 1s and 0s.
A 1 represents a group H class.


\>GreensRClassOfElement( <S>, <a> ) O
\>GreensLClassOfElement( <S>, <a> ) O
\>GreensDClassOfElement( <S>, <a> ) O
\>GreensJClassOfElement( <S>, <a> ) O
\>GreensHClassOfElement( <S>, <a> ) O

Creates the <> class of the element <a> in the semigroup <S>
where <> is one of L, R, D, J or H.

\>GreensRClasses( <semigroup> ) A
\>GreensLClasses( <semigroup> ) A
\>GreensJClasses( <semigroup> ) A
\>GreensDClasses( <semigroup> ) A
\>GreensHClasses( <semigroup> ) A

return the <R>, <L>, <J>, <H>, or <D> Green's classes, respectively for
semigroup <semigroup>. EquivlanceClasses for a Green's relation lead to one of 
these functions.


\>GroupHClassOfGreensDClass( <Dclass> ) A

for a D class <Dclass> of a semigroup,
returns a group H class of the D class, or `fail' if there is no
group H class.


\>IsGroupHClass( <Hclass> ) P

returns `true' if the Greens H class <Hclass> is a group, which  in  turn
is true if and only if <Hclass>^2 intersects <Hclass>.


\>IsRegularDClass( <Dclass> ) P

returns `true' if the Greens D class <Dclass> is regular. A  D  class  is
regular if and only if each of its elements is regular, which in turn  is
true if and only if any one element of <Dclass> is  regular.  Idempotents
are regular since $eee=e$ so it follows that a Greens D class  containing
an idempotent is regular. Conversely, it is true that a regular  D  class
must contain at least one idempotent. (See~\cite{Howie76}, Prop.~3.2).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Rees Matrix Semigroups}

In this section we describe {\GAP} functions for Rees matrix semigroups
and Rees 0-matrix semigroups.
The importance of this construction is that 
Rees Matrix semigroups over groups 
are exactly the completely simple semigroups, and Rees 0-matrix
semigroups over groups are the completely 0-simple semigroups 

Recall that a Rees Matrix semigroup is constructed from a semigroup (the
underlying semigroup), and a matrix.
A Rees Matrix semigroup element is a triple (<s>, <i>, <lambda>)
where <s> is an element of the underlying semigroup <S> and
<i>, <lambda> are indices.
This can be thought of as a matrix with zero everywhere
except for an occurrence of <s> at row <i> and column <lambda>.
The multiplication is defined by 
$(i, s, \lambda)*(j, t, \mu) =   (i, s P_{\lambda j} t, \mu)$ where
$P$ is the defining matrix of the semigroup.
In the case that the underlying semigroup has a zero we can make the
ReesZeroMatrixSemigroup, wherein all elements whose <s> entry is the
zero of the underlying semigroup are identified to the unique zero of
the Rees 0-matrix semigroup.



\>ReesMatrixSemigroup( <S>, <matrix> ) F

for a semigroup <S> and <matrix> whose entries are in <S>.
Returns the Rees Matrix semigroup with multiplication defined by
<matrix>. 


\>ReesZeroMatrixSemigroup( <S>, <matrix> ) F

for a semigroup <S> with zero, and  <matrix> over  <S> 
returns the Rees 0-Matrix semigroup such that all elements
$(i, 0, \lambda)$ are identified to zero.

The zero in <S> is found automatically.   If
one cannot be found, an error is signalled.   


\>IsReesMatrixSemigroup( <T> ) P

returns `true' if the object <T> is a (whole) Rees matrix semigroup.


\>IsReesZeroMatrixSemigroup( <T> ) P

returns `true' if the object <T> is a (whole) Rees 0-matrix semigroup.


\>ReesMatrixSemigroupElement( <R>, <a>, <i>, <lambda> ) F
\>ReesZeroMatrixSemigroupElement( <R>, <a>, <i>, <lambda> ) F

for a Rees matrix semigroup <R>, <a> in `UnderlyingSemigroup(<R>)', 
<i> and <lambda> in the row (resp. column) ranges of <R>,
returns the element of <R> corresponding to the
matrix with zero everywhere and <a> in row <i> and column <x>.


\>IsReesMatrixSemigroupElement( <e> ) C
\>IsReesZeroMatrixSemigroupElement( <e> ) C

is the category of elements of a Rees (0-) matrix  semigroup.
Returns true if <e> is an element of a Rees Matrix semigroup.


\>SandwichMatrixOfReesMatrixSemigroup( <R> ) A
\>SandwichMatrixOfReesZeroMatrixSemigroup( <R> ) A

each return the defining matrix of the Rees (0-) matrix semigroup.


\>RowIndexOfReesMatrixSemigroupElement( <x> ) A
\>RowIndexOfReesZeroMatrixSemigroupElement( <x> ) A
\>ColumnIndexOfReesMatrixSemigroupElement( <x> ) A
\>ColumnIndexOfReesZeroMatrixSemigroupElement( <x> ) A
\>UnderlyingElementOfReesMatrixSemigroupElement( <x> ) A
\>UnderlyingElementOfReesZeroMatrixSemigroupElement( <x> ) A

For an element <x> of a Rees Matrix semigroup, of the form
`(<i>, <s>, <lambda>)',
the row index is <i>, the column index is <lambda> and the 
underlying element is <s>.
If we think of an element as a matrix then this corresponds to
the row where the non-zero entry is, the column where the
non-zero entry is and the entry at that position, respectively. 


\>ReesZeroMatrixSemigroupElementIsZero( <x> ) P

returns `true' if <x> is the zero of the Rees 0-matrix semigroup.


\>AssociatedReesMatrixSemigroupOfDClass( <D> ) A

Given a regular <D> class of a finite semigroup, it can be viewed as a
Rees matrix semigroup by identifying products which do not lie in the
<D> class with zero, and this is what it is returned.

Formally, let $I_1$ be the ideal of all J classes less than or equal to
<D>, $I_2$ the ideal of all J classes *strictly* less than <D>,
and $\rho$ the Rees congruence associated with $I_2$.  Then $I/\rho$
is zero-simple.  Then `AssociatedReesMatrixSemigroupOfDClass( <D> )'
returns this zero-simple semigroup as a Rees matrix semigroup.


\>IsomorphismReesMatrixSemigroup( <obj> ) A

an isomorphism  to a Rees matrix semigroup over a group (resp. zero
group).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E