A finitely presented semigroup (resp. finitely presented monoid) is a quotient of a free semigroup (resp. free monoid) on a finite number of generators over a finitely generated congruence on the considered free semigroup (resp. free monoid).
Finitely presented semigroups are obtained by factoring a free semigroup by a set of relations (a generating set for the congrucence), ie, a set of pairs of words in the free semigroup.
gap> f:=FreeSemigroup("a","b");; gap> x:=GeneratorsOfSemigroup(f);; gap> s:=f/[ [x[1]*x[2],x[2]*x[1]] ]; <fp semigroup on the generators [ a, b ]> gap> GeneratorsOfSemigroup(s); [ a, b ] gap> RelationsOfFpSemigroup(s); [ [ a*b, b*a ] ]
Finitely presented monoids are obtained by factoring a free monoid by a set of relations. What is obtained is a finitely presented semigroup with one extra generator (corresponding to the identity of the monoid) and the extra relations involving this generator. In fact there are no finitely presented monoids in GAP. The quotient construction on a free monoids produce a finitely presented semigroup. This enables the user to conveniently enter a monoid presentation without specifying the identity and its action on the other generators.
gap> f:=FreeMonoid("a","b");; gap> x:=GeneratorsOfMonoid(f);; [ a, b ] gap> e:=Identity(f); <identity ...> gap> m:=f/[ [x[1]*x[2],e] ]; <fp semigroup on the generators [ <identity ...>, a, b ]>
Note that is not possible to refer to the generators by their names. These names are not variables, but just display figures. So, if one wants to access the generators by their names, one first have to introduce the respective variables and to assign the generators to them.
gap> f:=FreeSemigroup("a","b");; gap> x:=GeneratorsOfSemigroup(f);; gap> s:=f/[ [x[1]*x[2],x[2]*x[1]] ];; gap> a; Variable: 'a' must have a value gap> a:=GeneratorsOfSemigroup(s)[1]; a gap> b:=GeneratorsOfSemigroup(s)[2]; b gap> a in f; false gap> a in s; true
Also note that the generators of the free semigroup are different from the generators of the finitely presented semigroup (even though they are displayed by the same names). This means that words in the generators of the free semigroup are not elements of the finitely presented semigroup. Conversely elements of the finitely presented semigroup are not words.
gap> a*b=a^5; false gap> a^5*b^2*a=a^6*b^2; true
Such calculations comparing elements of an finitely presented semigroup may run into problems: there are finitely presented semigroups for which no algorithm exists (it is known that no such algorithm can exist) that will tell for two arbitrary words in the generators whether the corresponding elements in the finitely presented semigroup are equal. Therefore the methods used by GAP to compute in finitely presented semigroups may run into warning errors, run out of memory or run forever. If the fintely presented semigroup is (by theory) known to be finite the algorithms are guaranteed to terminate (if there is sufficient memory available), but the time needed for the calculation cannot be bounded a priori. See Knuth Bendix Procedure.
Note than elements of a finitely presented semigroup are not printed in a unique way.
gap> a^5*b^2*a; a^5*b^2*a gap> a^6*b^2; a^6*b^2
IsSubsemigroupFpSemigroup(
T ) A
true if T is a finitely presented semigroup or a
subsemigroup of a finitely presented semigroup
(generally speaking, such a semigroup can be constructed
with Semigroup(
gens)
, where gens is a list of elements
of a finitely presented semigroup).
IsFpSemigroup(
S ) P
is a synonym for IsSubsemigroupFpSemigroup(
S)
and
IsWholeFamily(
S)
(this is because a subsemigroup
of a finitely presented semigroup is not necessarily finitely presented).
IsElementOfFpSemigroup(
elm ) C
returns true if elm is an element of a finitely presented semigroup.
gap> f := FreeSemigroup("a","b");; gap> a := GeneratorsOfSemigroup( f )[ 1 ];; gap> b := GeneratorsOfSemigroup( f )[ 2 ];; gap> s := f / [ [ a^2 , a*b ] ];; gap> IsFpSemigroup( s ); true gap> t := Semigroup( [ GeneratorsOfSemigroup( s )[ 1 ] ]); <semigroup with 1 generator> gap> IsSubsemigroupFpSemigroup( t ); true gap> IsElementOfFpSemigroup( GeneratorsOfSemigroup( t )[ 1 ] ); true
F/
rels
creates a finitely presented semigroup given by the presentation ágens \midrels ñ where gens are the generators of the free semigroup F. Note that relations are entered as pairs of words in the generators of the free semigroup.
gap> f:=FreeSemigroup(3);; gap> s:=GeneratorsOfSemigroup(f);; gap> f/[ [s[1]*s[2]*s[1],s[1]] , [s[2]^4,s[1]] ]; <fp semigroup on the generators [ s1, s2, s3 ]>
F/
rels
creates a finitely presented semigroup given by the monoid presentation ágens \midrels ñ where gens are the generators of the free monoid F. Note that relations are entered as pairs of words in both the identity and the generators of the free monoid.
gap> f := FreeMonoid( 3 ); <free monoid on the generators [ m1, m2, m3 ]> gap> x := GeneratorsOfMonoid( f ); [ m1, m2, m3 ] gap> e:= Identity ( f ); <identity ...> gap> m := f/[ [x[1]^3,e] , [x[1]*x[2],x[2] ]]; <fp semigroup on the generators [ <identity ...>, m1, m2, m3 ]>
One may also call the following functions to construct finitely presented semigroups.
FactorFreeSemigroupByRelations(
F,
rels ) F
FactorFreeMonoidByRelations(
F,
rels ) F
F is a free semigroup (resp. monoid) and rels is a list of pairs of elements of F. Returns the fp semigroup which is the quotient of F by the least congruence on F generated by the pairs in rels.
In case F is a free monoid, this function constructs a new free semigroup with one more generator e (representing the identity) and adds new relations to rels of the form e*g = g, g*e = g for all the generators g of the original monoid then constructs the fp semigroup in the same way as for the free semigroup case.
Finally, if one has a finitely presented group, to find an isomorphic finitely presented semigroup, for example, to apply the Knuth-Bendix procedure, use:
IsomorphismFpSemigroup(
S ) A
Returns an isomorphism from S to an fp semigroup
48.2 Comparison of Elements of Finitely Presented Semigroups
a =
b
Two elements of a finitely presented semigroups are equal if they are equal in this semigroup. Nevertheless they may be represented as different words in the generators. Because of the fundamental problems mentioned in the introduction to this chapter such a test may take very long and cannot be guaranteed to finish.
FreeSemigroupOfFpSemigroup(
T ) A
returns the underlying free semigroup for the finitely presented
semigroup T, ie, the free semigroup over which T is defined
as a quotient
(this is the free semigroup generated by the free generators provided
by FreeGeneratorsOfFpSemigroup(
T)
).
FreeGeneratorsOfFpSemigroup(
T ) A
returns the underlying free generators corresponding to the generators of the finitely presented semigroup T.
RelationsOfFpSemigroup(
S ) A
returns the relations of the finitely presented semigroup S as
pairs of words in the free generators provided by
FreeGeneratorsOfFpSemigroup(
S)
.
gap> f := FreeSemigroup( "a" , "b" );; gap> a := GeneratorsOfSemigroup( f )[ 1 ];; gap> b := GeneratorsOfSemigroup( f )[ 2 ];; gap> s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ]; <fp semigroup on the generators [ a, b ]> gap> Size( s ); 8 gap> FreeSemigroupOfFpSemigroup( s ) = f; true gap> FreeGeneratorsOfFpSemigroup( s ); [ a, b ] gap> RelationsOfFpSemigroup( s ); [ [ a^3, a ], [ b^3, b ], [ a*b, b*a ] ]
Elements of a finitely presented semigroup are not words, but are represented using a word from the free semigroup as representative.
UnderlyingElement(
elm ) O
If elm is an element of a finitely presented semigroup, it returns the word from the free semigroup that is used as a representative for elm.
gap> w := GeneratorsOfSemigroup(s)[1] * GeneratorsOfSemigroup(s)[2]; a*b gap> IsWord (w ); false gap> ue := UnderlyingElement( w ); a*b gap> IsWord( ue ); true
ElementOfFpSemigroup(
fam,
word ) O
If fam is the elements family of a finitely presented semigroup and word is a word in the free generators underlying this finitely presented semigroup, this operation creates the element with the representative word in the free semigroup.
gap> ge:=ElementOfFpSemigroup( FamilyObj( GeneratorsOfSemigroup(s)[1]), a*b ); a*b gap> ge in f; false gap> ge in s; true
One of the important tools for the examination of finitely presented semigroups is the Knuth-Bendix procedure for strings, which manipulates a rewriting system of the semigroup and attempts to make it confluent (See Rewriting Systems. See also Sims). Once confluence is achived, it is possible to successfully test that two words represent the same element in the semigroup, by reducing both words using the rewriting system rules (since the word problem for semigroups is not solvable in general, Knuth-Bendix procedure cannot always terminate). Note that the implemented version of the Knuth bendix procedure, in GAP reyurns, if it terminates a confluent rewriting system which is reduced.
This section describes GAP functions to deal with this.
In order to apply this procedure we will build a rewriting system for the semigroup, which we will call a Knuth Bendix Rewriting System. (we need to define this because we need that the rewriting system to store some information needed for the implementation of the Knuth Bendix procedure). Also, a reduction ordering has to be specified when building a rewriting system. If non is specified, the shortlex ordering is assumed (note that the procedure may terminate with a certain ordering and not with another one).
KnuthBendixRewritingSystem(
S ) AM
returns the Knuth Bendix rewriting system of the FpSemigroup S with respect to the shortlex ordering on words.
KnuthBendixRewritingSystem(
S,
lessthanorequal)
creates the Knuth Bendix rewriting system of the finitely presented semigroup S unsing the reduction ordering given by lessthanorequal (lessthanorequal(a,b) returns true iff a is less than b in the order corresponding to lessthanorequal).
IsKnuthBendixRewritingSystem(
obj ) C
returns true if obj is a Knuth Bendix Rewriting System.
SemigroupOfKnuthBendixRewritingSystem(
rws ) A
returns the finitely presented semigroup of which rws is a rewriting system
gap> f := FreeSemigroup( "a" , "b" );; gap> a := GeneratorsOfSemigroup( f )[ 1 ];; gap> b := GeneratorsOfSemigroup( f )[ 2 ];; gap> g := f / [ [ a^2 , a*b ] , [ a^4 , b] ];; gap> kbrws := KnuthBendixRewritingSystem( g ); Knuth Bendix Rewriting System for Semigroup( [ a, b ] ) with rules [ [ a*b, a^2 ], [ a^4, b ] ] gap> MakeConfluent( kbrws ); gap> Rules( kbrws ); [ [ a*b, a^2 ], [ a^4, b ], [ b*a, a^2 ], [ b^2, a^2 ] ] gap> IsConfluent( kbrws ); true
As mentioned before, having a confluent rewriting system, one can decide whether two words represent the same element of a finitely presented semigroup.
gap> a := GeneratorsOfSemigroup( g )[ 1 ]; a gap> b := GeneratorsOfSemigroup( g )[ 2 ]; b gap> a*b*a=a^3; true gap> ReducedForm(kbrws,UnderlyingElement(a*b*a)); a^3 gap> ReducedForm(kbrws,UnderlyingElement(a^3)); a^3
This procedure gives a standard way of finding a transformation representation of a finitely presented semigroup. Usually one does not explicitly call this procedure but uses IsomorphismTransformationSemigroup or HomomorphismTransformationSemigroup (see IsomorphismTransformationSemigroup).
CosetTableOfFpSemigroup(
r ) A
r is a right congruence of an fp-semigroup S. This attribute is the coset table of FP semigroup S on a right congruence r. Given a right congruence r we represent S as a set of transformations of the congruence classes of r.
The images of the cosets under the generators are compiled in a list table such that table[i][s] contains the image of coset s under generator i.
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual