49 Semigroups

returns true if the object D is a semigroup. A semigroup is a magma (see Magmas) with associative multiplication.

In the first form, Semigroup returns the semigroup generated by the arguments gen1, gen2, ..., 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.

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>

are just synonyms of Submagma and SubmagmaNC, respectively (see Submagma).

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

is the underlying operation of Semigroup (see Semigroup).

If C is a collection whose elements form a semigroup (see IsSemigroup) then AsSemigroup returns this semigroup. Otherwise fail is returned.

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.

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

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

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 name1, name2 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.

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 ]>

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:

returns true if S is regular---i.e. if every D class of S is regular.

returns true if x has a general inverse in S---i.e. there is an element y Î S such that xyx=x and yxy=y.

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

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.

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

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

49.1 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.

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.

The number of points the semigroup acts on.

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, ¼, n}. Otherwise, it will be the right regular representation on S or S¹ if S has no MultiplicativeNeutralElement.

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

49.2 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).

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

A two sided ideal I of a semigroup S defines a congruence on S given by DÈI ×I.

Categories of semigroup ideals.

Categories for generic semigroup ideal enumerators. Note: this does not imply that the UnderlyingDomain of the enumerator is a semigroup ideal, only that the object being enumerated is being enumerated as a semigroup ideal. In particular, semigroups are generally enumerated as a right or left ideal of themselves.

49.3 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).

a magma congruence c on a semigroup.

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

49.4 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.

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) ® 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.

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

for a quotient semigroup S.

49.5 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¹ = yS¹, L-related if and only if S¹x=S¹y and J-related if and only if S¹xS¹=S¹yS¹; finally, H = R ÙL, and D = R °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¹ Í yS¹; similarly, x is less than or equal to y under L if S¹x Í S¹y; finally x is less than or equal to y under J if S¹xS¹ Í S¹tS¹. We extend this preorder to a partial order on equivalence classes in the natural way.

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

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

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.

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.

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.

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.

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

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

return the R, L, J, H, or D Green's classes, respectively for semigroup semigroup.

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.

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

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 Howie76, Prop. 3.2).

49.6 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 (s, i, l)*(t, j , m) = (s P_lj t, i, m) 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.

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

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

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

returns true if the object T is a (whole) Rees matrix semigroup.

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

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.

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

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

For an element x of a Rees Matrix semigroup, of the form (s, i, 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.

returns true if x is the zero of the Rees 0-matrix semigroup.

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₁ be the ideal of all J classes less than or equal to D, I₂ the ideal of all J classes strictly less than D, and r the Rees congruence associated with I₂. Then I/r is zero-simple. Then AssociatedReesMatrixSemigroupOfDClass( D ) returns this zero-simple semigroup as a Rees matrix semigroup.

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

[Top] [Up] [Previous] [Next] [Index]

GAP 4 manual
May 2002