50.4 Rewriting Systems and the Knuth Bendix Procedure

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

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

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

returns the semigroup over which rws is a rewriting system

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

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