This chapter describes functions to construct rewriting systems for finitely presented groups which store rewriting information. The main example used throughout this manual is a presentation of the quaternion group \(q8 = F/[a^4, b^4, abab^{-1}, a^2b^2]\).
‣ FreeRelatorGroup( grp ) | ( attribute ) |
‣ FreeRelatorHomomorphism( grp ) | ( attribute ) |
The function FreeRelatorGroup returns a free group on the set of relators of the fp-group G. If HasName(G) is true then a name is automatically assigned to this free group by concatenating _R.
The function FreeRelatorHomomorphism returns the group homomorphism from the free group on the relators to the free group on the generators of G, mapping each generator to the corresponding word.
gap> relq8 := [ f^4, g^4, f*g*f*g^-1, f^2*g^2 ];; gap> q8 := F/relq8;; gap> SetName( q8, "q8" );; gap> q8R := FreeRelatorGroup( q8 ); q8_R gap> genq8R := GeneratorsOfGroup( q8R ); [ q8_R1, q8_R2, q8_R3, q8_R4] gap> homq8R := FreeRelatorHomomorphism( q8 ); [ q8_R1, q8_R2, q8_R3, q8_R4 ] -> [ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2 ]
‣ MonoidPresentationFpGroup( grp ) | ( attribute ) |
‣ ArrangementOfMonoidGenerators( grp ) | ( attribute ) |
‣ MonoidPresentationLabels( grp ) | ( attribute ) |
‣ FreeGroupOfPresentation( mon ) | ( attribute ) |
‣ GroupRelatorsOfPresentation( mon ) | ( attribute ) |
‣ InverseRelatorsOfPresentation( mon ) | ( attribute ) |
‣ HomomorphismOfPresentation( mon ) | ( attribute ) |
A monoid presentation for a finitely presented group G has two monoid generators \(g,G\) for each group generator \(g\). The relators of the monoid presentation comprise the group relators, and relators \(gG, Gg\) specifying the inverses. The function MonoidPresentationFpGroup returns the monoid presentation derived in this way from an fp-presentation.
The function FreeGroupOfPresentation returns the free group on the monoid generators.
The function GroupRelatorsOfPresentation returns those relators of the monoid which correspond to the relators of the group. All negative powers in the group relators are converted to positive powers of the \(G\)'s. The function InverseRelatorsOfPresentation returns relators which specify the inverse pairs of the monoid generators.
The function HomomorphismOfPresentation returns the homomorphism from the free group of the monoid presentation to the free group of the group presentation.
The attribute ArrangementOfMonoidGenerators will be discussed before the second example in the next section.
In the example below, the four monoid generators \(a,b,A,B\) are named q8_M1, q8_M2, q8_M3, q8_M4 respectively.
gap> mq8 := MonoidPresentationFpGroup( q8 ); monoid presentation with group relators [ q8_M1^4, q8_M2^4, q8_M1*q8_M2*q8_M1*q8_M4, q8_M1^2*q8_M2^2 ] gap> fmq8 := FreeGroupOfPresentation( mq8 ); <free group on the generators [ q8_M1, q8_M2, q8_M3, q8_M4 ]> gap> genfmq8 := GeneratorsOfGroup( fmq8 );; gap> gprels := GroupRelatorsOfPresentation( mq8 ); [ q8_M1^4, q8_M2^4, q8_M1*q8_M2*q8_M1*q8_M4, q8_M1^2*q8_M2^2 ] gap> invrels := InverseRelatorsOfPresentation( mq8 ); [ q8_M1*q8_M3, q8_M2*q8_M4, q8_M3*q8_M1, q8_M4*q8_M2 ] gap> hompres := HomomorphismOfPresentation( mq8 ); [ q8_M1, q8_M2, q8_M3, q8_M4 ] -> [ f1, f2, f1^-1, f2^-1 ]
‣ PrintLnUsingLabels( args ) | ( function ) |
‣ PrintUsingLabels( args ) | ( function ) |
The labels q8_M1, q8_M2, q8_M3, q8_M4 are rather unhelpful in lengthy output, so it is convenient to use \([a,b,A,B]\) as above. Then the function PrintUsingLabels takes as input a word in the monoid, the generators of the monoid, and a set of labels for these generators. This function also treats lists of words and lists of lists in a similar way. The function PrintLnUsingLabels does exactly the same, and then appends a newline.
gap> q8labs := [ "a", "b", "A", "B" ];; gap> SetMonoidPresentationLabels( q8, q8labs );; gap> PrintLnUsingLabels( gprels, genfmq8, q8labs ); [ a^4, b^4, a*b*a*B, a^2*b^2 ]
‣ InitialRulesOfPresentation( mon ) | ( function ) |
The initial rules for \(mq8\) are the four rules of the form \(a^{-1} \to A\); the four rules of the form \(aA \to id\); and the four relator rules of the form \(a^4 \to id\).
gap> q0 := InitialRulesOfPresentation( mq8 );; gap> PrintLnUsingLabels( q0, genfmq8, q8labs ); [ [ a^-1, A ], [ b^-1, B ], [ A^-1, a ], [ B^-1, b ], [ a*A, id ], [ b*B, id ], [ A*a, id ], [ B*b, id ], [ a^4, id ], [ a^2*b^2, id ], [ a*b*a*B, id ], [ b^4, id ] ]
These functions duplicate the standard Knuth Bendix functions which are available in the GAP library. There are two reasons for this: (1) these functions were first written before the standard functions were available; (2) we require logged versions of the functions, and these are most conveniently extended versions of the non-logged code.
‣ RewritingSystemFpGroup( grp ) | ( attribute ) |
This function attempts to return a complete rewrite system for the fp-group G obtained using the group's monoid presentation mon, with a length-lexicographical ordering on the words in fgmon, by applying Knuth-Bendix completion. Such a rewrite system can be obtained for all finite groups. The rewrite rules are (partially) ordered, starting with the inverse relators, followed by the rules which reduce the word length the most.
In our q8 example there are 20 rewrite rules in the rewriting system rws:
| \(a^{-1} \to A, \quad b^{-1} \to B, \quad A^{-1} \to a, \quad B^{-1} \to b, \) |
| \(aA \to \rm{id}, \quad bB \to \rm{id}, \quad Aa \to \rm{id}, \quad Bb \to \rm{id}, \) |
| \(ba \to aB, \quad b^2 \to a^2,\quad bA \to ab, \quad Ab \to aB, \quad A^2 \to a^2,\quad AB \to ab, \) |
| \(Ba \to ab, \quad BA \to aB, \quad B^2 \to a^2, \quad a^3 \to a, \quad a^2b \to B, \quad a^2B \to b. \) |
gap> rws := RewritingSystemFpGroup( q8 );; gap> Length( rws ); 20 gap> PrintLnUsingLabels( rws, genfmq8, q8labs ); [ [ a^-1, A ], [ b^-1, B ], [ A^-1, a ], [ B^-1, b ], [ a*A, id ], [ b*B, id ], [ A*a, id ], [ B*b, id ], [ b*a, a*B ], [ b^2, a^2 ], [ b*A, a*b ], [ A*b, a*B ], [ A^2, a^2 ], [ A*B, a*b ], [ B*a, a*b ], [ B*A, a*B ], [ B^2, a^2 ], [ a^3, A ], [ a^2*b, B ], [ a^2*B, b ] ]
The default ordering of the \(2n\) monoid generators is \( [g_1^+,g_2^+,\ldots,g_n^+,g_1^-,g_2^-,\ldots,g_n^-] \). In the case of the two-generator abelian group \(T = \langle a,b ~|~ [a,b] \rangle\) the Knuth-Bendix process starts to generate infinite sets of relations such as \(\{ab^ma^{-1} \to b^m,~ m \geqslant 1\}\).
If, using the ArrangementOfMonoidGenerators function, we specify the alternative ordering \( [g_1^+,g_1^-,g_2^+,g_2^-] \), then a finite set of rules is obtained.
gap> T := F/[Comm(f,g)]; <fp group of size infinity on the generators [ f1, f2 ]> gap> SetName( T, "T" ); gap> SetArrangementOfMonoidGenerators( T, [1,-1,2,-2] ); gap> Tlabs := [ "x", "X", "y", "Y" ];; gap> mT := MonoidPresentationFpGroup( T ); monoid presentation with group relators [ T_M2*T_M4*T_M1*T_M3 ] gap> fgmT := FreeGroupOfPresentation( mT );; gap> genfgmT := GeneratorsOfGroup( fgmT );; gap> SetMonoidPresentationLabels( T, Tlabs );; gap> rwsT := RewritingSystemFpGroup( T );; gap> PrintLnUsingLabels( rwsT, genfgmT, Tlabs ); [ [ x^-1, X ], [ X^-1, x ], [ y^-1, Y ], [ Y^-1, y ], [ x*X, id ], [ X*x, id ], [ y*Y, id ], [ Y*y, id ], [ y*x, x*y ], [ y*X, X*y ], [ Y*x, x*Y ], [ Y*X, X*Y ] ]
The last four rules show that generators \(x\) and \(y\) commute.
‣ OnePassReduceWord( word, rules ) | ( operation ) |
‣ ReduceWordKB( word, rules ) | ( operation ) |
These functions are called by the function RewritingSystemFpGroup.
Assuming that word is an element of a free monoid and rules is a list of ordered pairs of such words, the function OnePassReduceWord searches the list of rules until it finds that the left-hand side of a rule is a subword of word, whereupon it replaces that subword with the right-hand side of the matching rule. The search is continued from the next rule in rules, but using the new word. When the end of rules is reached, one pass is considered to have been made and the reduced word is returned. If no matches are found then the original word is returned.
The function ReduceWordKB repeatedly applies the function OnePassReduceWord until the word remaining contains no left-hand side of a rule as a subword. If rules is a complete rewrite system, then the irreducible word that is returned is unique, otherwise the order of the rules in rules will determine which irreducible word is returned. In our \(q8\) example we see that \(b^9a^{-9}\) reduces to \(ab\).
gap> a := genfmq8[1];; b := genfmq8[2];; gap> A := genfmq8[3];; B := genfmq8[4];; gap> w0 := b^9 * a^-9;; gap> PrintLnUsingLabels( w0, genfmq8, q8labs ); b^9*a^-9 gap> w1 := OnePassReduceWord( w0, rws );; gap> PrintLnUsingLabels( w1, genfmq8, q8labs ); B*b^5*a*b*a^-8 gap> w2 := ReduceWordKB( w0, rws );; gap> PrintLnUsingLabels( w2, genfmq8, q8labs ); a*b
‣ OnePassKB( mon, rules ) | ( operation ) |
The function OnePassKB implements the main loop of the Knuth-Bendix completion algorithm. Rules are compared with each other; all critical pairs are calculated; and the irreducible critical pairs are orientated with respect to the length-lexicographical ordering and added to the rewrite system.
The function ShorterRule gives an ordering on rules. Rules \((g_lg_2,id)\) that identify two generators (or one generator with the inverse of another) come first in the ordering. Otherwise one precedes another if it reduces the length of a word by a greater amount.
One pass of this procedure for our \(q8\) example adds \(10\) relators to the original \(12\).
gap> q1 := OnePassKB( mq8, q0 );; gap> Length( q1 ); 22 gap> PrintLnUsingLabels( q1, genfmq8, q8labs ); [ [ a^-1, A ], [ b^-1, B ], [ A^-1, a ], [ B^-1, b ], [ a*A, id ], [ b*B, id ], [ A*a, id ], [ B*b, id ], [ b^2, a^2 ], [ a^3, A ], [ a^2*b, B ], [ a*b*a, b ], [ a*b^2, A ], [ b*a*B, A ], [ b^3, B ], [ a*b^2, a^3 ], [ b*a*B, a^3 ], [ b^3, a^2*b ], [ a^4, id ], [ a^2*b^2, id ], [ a*b*a*B, id ], [ b^4, id ] ]
‣ RewriteReduce( mon, rules ) | ( operation ) |
The function RewriteReduce will remove unnecessary rules from a rewrite system. A rule is deemed to be unnecessary if it is implied by the other rules, i.e. if both sides can be reduced to the same thing by the remaining rules.
In the example the \(22\) rules in \(q1\) are reduced to \(13\).
gap> q2 := RewriteReduce( mq8, q1 );; gap> Length( q2 ); 13 gap> PrintLnUsingLabels( q2, genfmq8, q8labs ); [ [ a^-1, A ], [ b^-1, B ], [ A^-1, a ], [ B^-1, b ], [ a*A, id ], [ b*B, id ], [ A*a, id ], [ B*b, id ], [ b^2, a^2 ], [ a^3, A ], [ a^2*b, B ], [ a*b*a, b ], [ b*a*B, A ] ]
‣ KnuthBendix( mon, rules ) | ( operation ) |
The function KnuthBendix implements the Knuth-Bendix algorithm, attempting to complete a rewrite system with respect to a length-lexicographic ordering. It calls first OnePassKB, which adds rules, and then (for efficiency) RewriteReduce which removes any unnecessary ones. This procedure is repeated until OnePassKB adds no more rules. It will not always terminate, but for many examples (all finite groups) it will be successful. The rewrite system returned is complete, that is: it will rewrite any given word in the free monoid to a unique irreducible; there is one irreducible for each element of the quotient monoid; and any two elements of the free monoid which are in the same class will rewrite to the same irreducible.
The function ShorterRule gives an ordering on rules. Rules \((g_lg_2,id)\) that identify two generators (or one generator with the inverse of another) come first in the ordering. Otherwise one precedes another if it reduces the length of a word by a greater amount.
In the example the function KnuthBendix requires three instances of OnePassKB and RewriteReduce to form the complete rewrite system \(rws\) for the group shown above.
gap> q3 := KnuthBendix( mq8, q0 );; gap> Length( q3 ); 20 gap> PrintLnUsingLabels( q3, genfmq8, q8labs ); [ [ a^-1, A ], [ b^-1, B ], [ A^-1, a ], [ B^-1, b ], [ a*A, id ], [ b*B, id ], [ A*a, id ], [ B*b, id ], [ b*a, a*B ], [ b^2, a^2 ], [ b*A, a*b ], [ A*b, a*B ], [ A^2, a^2 ], [ A*B, a*b ], [ B*a, a*b ], [ B*A, a*B ], [ B^2, a^2 ], [ a^3, A ], [ a^2*b, B ], [ a^2*B, b ] ]
‣ ElementsOfMonoidPresentation( mon ) | ( attribute ) |
The function ElementsOfMonoidPresentation returns a list of normal forms for the elements of the group given by the monoid presentation mon. The normal forms are the least elements in each equivalence class (with respect to length-lex order). When rules is a complete rewrite system for G the list returned is a set of normal forms for the group elements. For q8 this list is
\[ [\; {\rm id},\; a^+,\; b^+,\; a^-,\; b^-,\; a^{+2},\; a^+b^+,\; a^+b^-\; ]. \]
gap> elmq8 := ElementsOfMonoidPresentation( q8 );; gap> PrintLnUsingLabels( elmq8, genfmq8, q8labs ); [ id, a, b, A, B, a^2, a*b, a*B ]
generated by GAPDoc2HTML