50 Finitely Presented Semigroups

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 congruence), 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 has 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 finitely 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 Rewriting Systems and the 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
    

    Sections

    1. Creating Finitely Presented Semigroups and Monoids
    2. Comparison of Elements of Finitely Presented Semigroups
    3. Preimages in the Free Semigroup
    4. Rewriting Systems and the Knuth Bendix Procedure
    5. Todd-Coxeter Procedure

    50.1 Creating Finitely Presented Semigroups and Monoids

  • 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

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

    50.3 Preimages in the Free Semigroup

  • 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 )

    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
    

    50.4 Rewriting Systems and the Knuth Bendix Procedure

    If a finitely presented semigroup has a confluent rewriting system then it has a solvable word problem, that is, there is an algorithm to decide when two words in the free underlying semigroup represent the same element of the finitely presented semigroup. Indeed, once we have a confluent rewriting system, 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.

  • ReducedConfluentRewritingSystem( S ) A
  • ReducedConfluentRewritingSystem( S, lessthanorequal ) A

    returns a reduced confluent rewriting system of the finitely presented semigroup S with respect to the lexicorgraphic ordering on words.

    In the second form it returns a reduced confluent rewriting system of the finitely presented semigroup S with respect to the reduction ordering given by lessthanorequal (lessthanorequal(a,b) returns true iff a is less than b in the order corresponding to lessthanorequal).

    Note that, in this case, the object returned is an immutable rewriting system. This is so because once we have a confluent rewriting system for a finitely presented semigroup we do not want to allow it to change (it was most probably very time consuming to get it in the first place). Furthermore, this is also an attribute storing object. Also this might not terminate. In particular, if the semigroup S does not have a solvable word problem then it this will certainly never end.

    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> rws := ReducedConfluentRewritingSystem(g);
    Rewriting System for Semigroup( [ a, b ] ) with rules 
    [ [ a*b, a^2 ], [ a^4, b ], [ b*a, a^2 ], [ b^2, a^2 ] ]
    

    The creation of a reduced confluent rewriting system for a semigroup, in GAP, uses 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). (Since the word problem for semigroups is not solvable in general, Knuth-Bendix procedure cannot always terminate).

    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). Actually, Knuth Bendix Rewriting Systems are not only useful to get a reduced confluent rewriting system for the semigroup. These are objects which are mutable and which can be manipulated (see rewriting systems).

    Note that the implemented version of the Knuth Bendix procedure, in GAP returns, if it terminates, a confluent rewriting system which is reduced.

    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, lteq ) A

    returns the Knuth Bendix rewriting system of the FpSemigroup S with respect to the reduction ordering on words given by lteq.

  • KnuthBendixRewritingSystem(S,lessthanorequal)

    creates the Knuth Bendix rewriting system of the finitely presented semigroup S using the reduction ordering given by lessthanorequal.

  • SemigroupOfRewritingSystem( rws ) A

    returns the semigroup over which rws is a rewriting system

  • FreeSemigroupOfRewritingSystem( rws ) A

    returns the free semigroup over which rws is a rewriting system

    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(rws,UnderlyingElement(a*b*a));
    a^3
    gap> ReducedForm(rws,UnderlyingElement(a^3));  
    a^3
    

    50.5 Todd-Coxeter Procedure

    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
    February 2000