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

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