Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

52 Finitely Presented Semigroups and Monoids

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 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), i.e., 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, i.e. a set of pairs of words in the free monoid.

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 monoid on the generators [ a, b ]> gap> RelationsOfFpMonoid(m); [ [ a*b, <identity ...> ] ]

Notice that for **GAP** a finitely presented monoid is not a finitely presented semigroup.

gap> IsFpSemigroup(m); false

However, one can build a finitely presented semigroup isomorphic to that finitely presented monoid (see `IsomorphismFpSemigroup`

(52.2-3)).

Also 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> Unbind(a); gap> f:=FreeSemigroup("a","b");; gap> x:=GeneratorsOfSemigroup(f);; gap> s:=f/[ [x[1]*x[2],x[2]*x[1]] ];; gap> a; Error, 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

The generators of the free semigroup (resp. free monoid) are different from the generators of the finitely presented semigroup (resp. finitely presented monoid) (even though they are displayed by the same names). This means that words in the generators of the free semigroup (resp. free monoid) are not elements of the finitely presented semigroup (resp. finitely presented monoid). Conversely elements of the finitely presented semigroup (resp. finitely presented monoid) are not words of the free semigroup (resp. free monoid).

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. The same can be said for monoids. (See 52.6.)

gap> a*b=a^5; false gap> a^5*b^2*a=a^6*b^2; true

Note that elements of a finitely presented semigroup (or monoid) 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 ) | ( filter ) |

true if `t` is a finitely presented semigroup or a subsemigroup of a finitely presented semigroup (generally speaking, such a subsemigroup can be constructed with `Semigroup(`

, where `gens`)`gens` is a list of elements of a finitely presented semigroup).

`‣ IsSubmonoidFpMonoid` ( t ) | ( filter ) |

true if `t` is a finitely presented monoid or a submonoid of a finitely presented monoid (generally speaking, such a semigroup can be constructed with `Monoid(`

, where `gens`)`gens` is a list of elements of a finitely presented monoid).

A submonoid of a monoid has the same identity as the monoid.

`‣ IsFpSemigroup` ( s ) | ( filter ) |

is a synonym for `IsSubsemigroupFpSemigroup(`

and `s`)`IsWholeFamily(`

(this is because a subsemigroup of a finitely presented semigroup is not necessarily finitely presented).`s`)

`‣ IsFpMonoid` ( m ) | ( filter ) |

is a synonym for `IsSubmonoidFpMonoid(`

and `m`)`IsWholeFamily(`

(this is because a submonoid of a finitely presented monoid is not necessarily finitely presented).`m`)

`‣ IsElementOfFpSemigroup` ( elm ) | ( category ) |

returns true if `elm` is an element of a finitely presented semigroup.

`‣ IsElementOfFpMonoid` ( elm ) | ( category ) |

returns true if `elm` is an element of a finitely presented monoid.

`‣ FpGrpMonSmgOfFpGrpMonSmgElement` ( elm ) | ( operation ) |

returns the finitely presented group, monoid or semigroup to which `elm` belongs

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 ] ]); <commutative semigroup with 1 generator> gap> IsSubsemigroupFpSemigroup( t ); true gap> IsElementOfFpSemigroup( GeneratorsOfSemigroup( t )[ 1 ] ); true

`52.2-1 \/`

`‣ \/` ( F, rels ) | ( method ) |

creates a finitely presented semigroup given by the presentation \(\langle gens \mid \textit{rels} \rangle\) where \(gens\) are the generators of the free semigroup `F`, and the relations `rels` are entered as pairs of words in the generators of the free semigroup.

The same result is obtained with the infix operator `/`

, i.e., as `F` `/`

`rels`.

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

`‣ FactorFreeSemigroupByRelations` ( f, rels ) | ( function ) |

for a free semigroup `f` and `rels` is a list of pairs of elements of `f`. Returns the finitely presented semigroup which is the quotient of `f` by the least congruence on `f` generated by the pairs in `rels`.

gap> FactorFreeSemigroupByRelations(f, > [[s[1]*s[2]*s[1],s[1]],[s[2]^4,s[1]]]); <fp semigroup on the generators [ s1, s2, s3 ]>

`‣ IsomorphismFpSemigroup` ( s ) | ( attribute ) |

for a semigroup `s` returns an isomorphism from `s` to a finitely presented semigroup

gap> f := FreeGroup(2);; gap> g := f/[f.1^4,f.2^5]; <fp group on the generators [ f1, f2 ]> gap> phi := IsomorphismFpSemigroup(g); MappingByFunction( <fp group on the generators [ f1, f2 ]>, <fp semigroup on the generators [ <identity ...>, f1^-1, f1, f2^-1, f2 ]>, function( x ) ... end, function( x ) ... end ) gap> s := Range(phi); <fp semigroup on the generators [ <identity ...>, f1^-1, f1, f2^-1, f2 ]>

`52.3-1 \=`

`‣ \=` ( a, b ) | ( method ) |

Two elements `a`, `b` of a finitely presented semigroup are equal if they are equal in the 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 a very long time and cannot be guaranteed to finish (see 52.6).

Elements of a finitely presented semigroup are not words, but are represented using a word from the free semigroup as representative.

`‣ UnderlyingElement` ( elm ) | ( operation ) |

for an element `elm` of a finitely presented semigroup, it returns the word from the free semigroup that is used as a representative for `elm`.

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> 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, w ) | ( operation ) |

for a family `fam` of elements of a finitely presented semigroup and a word `w` in the free generators underlying this finitely presented semigroup, this operation creates the element of the finitely presented semigroup with the representative `w` in the free semigroup.

gap> fam := FamilyObj( GeneratorsOfSemigroup(s)[1] );; gap> ge := ElementOfFpSemigroup( fam, a*b ); a*b gap> ge in f; false gap> ge in s; true

`‣ FreeSemigroupOfFpSemigroup` ( s ) | ( attribute ) |

returns the underlying free semigroup for the finitely presented semigroup `s`, ie, the free semigroup over which `s` is defined as a quotient (this is the free semigroup generated by the free generators provided by `FreeGeneratorsOfFpSemigroup(`

).`s`)

`‣ FreeGeneratorsOfFpSemigroup` ( s ) | ( attribute ) |

returns the underlying free generators corresponding to the generators of the finitely presented semigroup `s`.

`‣ RelationsOfFpSemigroup` ( s ) | ( attribute ) |

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> fs := FreeSemigroupOfFpSemigroup( s );; gap> f = fs; true gap> FreeGeneratorsOfFpSemigroup( s ); [ a, b ] gap> RelationsOfFpSemigroup( s ); [ [ a^3, a ], [ b^3, b ], [ a*b, b*a ] ]

The functionality available for finitely presented monoids is essentially the same as that available for finitely presented semigroups, and thus the previous sections apply (with the obvious changes) to finitely presented monoids.

`52.5-1 \/`

`‣ \/` ( F, rels ) | ( method ) |

creates a finitely presented monoid given by the monoid presentation \(\langle \textit{gens} \mid \textit{rels} \rangle\) where `gens` are the generators of the free monoid `F`, and the relations `rels` are entered as pairs of words in both the identity and the generators of the free monoid.

The same result is obtained with the infix operator `/`

, i.e., as

.`F`/`rels`

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 monoid on the generators [ m1, m2, m3 ]>

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. This is, at the moment, the method that **GAP** uses to check equality in finitely presented semigroups and monoids.

`‣ ReducedConfluentRewritingSystem` ( S[, ordering] ) | ( attribute ) |

returns a reduced confluent rewriting system of the finitely presented semigroup or monoid `S` with respect to the reduction ordering `ordering` (see 34).

The default for `ordering` is the length plus lexicographic ordering on words, also called the shortlex ordering; for the definition see for example [Sim94].

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

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 or for a monoid, in **GAP**, uses the Knuth-Bendix procedure for strings, which manipulates a rewriting system of the semigroup or monoid and attempts to make it confluent (See 38. See also Sims [Sim94]). (Since the word problem for semigroups/monoids 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 or monoid, which we will call a *Knuth-Bendix Rewriting System* (we need to define this because we need the rewriting system to store some information needed for the implementation of the Knuth-Bendix procedure).

Actually, Knuth-Bendix Rewriting Systems do not only serve this purpose. Indeed these are objects which are mutable and which can be manipulated (see 38).

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 none is specified, the shortlex ordering is assumed (note that the procedure may terminate with a certain ordering and not with another one).

On Unix systems it is possible to replace the built-in Knuth-Bendix by other routines, for example the package **kbmag** offers such a possibility.

`‣ KB_REW` | ( global variable ) |

`‣ GAPKB_REW` | ( global variable ) |

`KB_REW`

is a global record variable whose components contain functions used for Knuth-Bendix. By default `KB_REW`

is assigned to `GAPKB_REW`

, which contains the KB functions provided by the GAP library.

`‣ KnuthBendixRewritingSystem` ( s, wordord ) | ( operation ) |

`‣ KnuthBendixRewritingSystem` ( m, wordord ) | ( operation ) |

in the first form, for a semigroup `s` and a reduction ordering for the underlying free semigroup, it returns the Knuth-Bendix rewriting system of the finitely presented semigroup `s` using the reduction ordering `wordord`. In the second form, for a monoid `m` and a reduction ordering for the underlying free monoid, it returns the Knuth-Bendix rewriting system of the finitely presented monoid `m` using the reduction ordering `wordord`.

`‣ SemigroupOfRewritingSystem` ( rws ) | ( attribute ) |

returns the semigroup over which `rws` is a rewriting system

`‣ MonoidOfRewritingSystem` ( rws ) | ( attribute ) |

returns the monoid over which `rws` is a rewriting system

`‣ FreeSemigroupOfRewritingSystem` ( rws ) | ( attribute ) |

returns the free semigroup over which `rws` is a rewriting system

`‣ FreeMonoidOfRewritingSystem` ( rws ) | ( attribute ) |

returns the free monoid over which `rws` is a rewriting system

gap> f1 := FreeSemigroupOfRewritingSystem(rws); <free semigroup on the generators [ a, b ]> gap> f1=f; true gap> g1 := SemigroupOfRewritingSystem(rws); <fp semigroup on the generators [ a, b ]> gap> g1=g; true

As mentioned before, having a confluent rewriting system, one can decide whether two words represent the same element of a finitely presented semigroup (or finitely presented monoid).

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

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`

(53.7-5).

`‣ CosetTableOfFpSemigroup` ( r ) | ( attribute ) |

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

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML