% 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