Goto Chapter: Top 1 2 3 4 5 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

3 Logged Rewriting Systems
 3.1 Logged Knuth-Bendix Completion
 3.2 Logged reduction of a word

3 Logged Rewriting Systems

A logged rewrite system is associated with a group presentation. Each logged rewrite rule contains, in addition to the standard rewrite rule, a record or log component which expresses the rule in terms of the original relators of the group. We represent such a rule by a triple [ u, [L1,L2,..,Lk], v], where [u,v] is a rewrite rule and L_i = [n_i,w_i] where n_i is a group relator and w_i is a word. These three components obey the identity u = n_1^w_1 ... n_k^w_k v.

Rules of the form g^+g^- are relevant to the monoid presentation, but not to the group presentation, so are given an empty logged component.

3.1 Logged Knuth-Bendix Completion

The functions in this section are the logged versions of those in the previous chapter.

3.1-1 LoggedOnePassKB
‣ LoggedOnePassKB( loggedrules )( operation )

Given a logged rewrite system, this function finds all the rules that would be added to complete the rewrite system in OnePassKB, and also the logs which relate the new rules to the originals. The result of applying this function to loggedrules is to add new logged rules to the system without changing the monoid it defines.

In the example, we first convert the presentation for q8 into an initial set of logged rules, and then apply one pass of Knuth-Bendix.


gap> l0 := ListWithIdenticalEntries( 8, 0 );;
gap> for j in [1..8] do 
>        r := r0[j];
>        if ( j<5 ) then
>           l0[j] := [ r[1], [ [j,id] ], r[2] ];
>        else
>           l0[j] := [ r[1], [ ], r[2] ];
>        fi;
>    od;
gap> l0;
[ [ q8_M1^4, [ [ 1, <identity ...>] ], <identity. ..> ], 
  [ q8_M2^4, [ [ 2, <identity ...>] ], <identity ...> ], 
  [ q8_M1*q8_M2*q8_M1*q8_M4, [ [ 3, <identity ...> ] ], <identity ...> ],   
  [ q8_M1^2*q8_M2^2, [ [ 4, <identity ...> ] ], <identity ...> ], 
  [ q8_M1*q8_M3, [ ], <identity ...> ], [ q8_M2*q8_M4, [ ], <identity ...> ], 
  [ q8_M3*q8_M1, [ ], <identity ...> ], [ q8_M4*q8_M2, [ ], <identity ...> ] ] 
gap> l1 := LoggedOnePassKB( l0 );;
gap> Length( l1 ); 
21

3.1-2 LoggedKnuthBendix
‣ LoggedKnuthBendix( loggedrules )( operation )
‣ LoggedRewriteReduce( loggedrules )( operation )

The function LoggedRewriteReduce removes unnecessary rules from a logged rewrite system. It works on the same principle as RewriteReduce.

The function LoggedKnuthBendix repeatedly applies LoggedOnePassKB and LoggedRewriteReduce until no new rules are added and no unnecessary ones are included. The output is a reduced complete logged rewrite system.


gap> l1 := LoggedRewriteReduce( l1 );
[ [ q8_M1*q8_M3, [ ], <identity ...> ], 
  [ q8_M2^2, [ [ -4, <identity ...> ], [ 2, q8_M1^-2 ] ], q8_M1^2 ], 
  [ q8_M2*q8_M4, [ ], <identity ...> ], [ q8_M3*q8_M1, [ ], <identity ...> ], 
      [ q8_M4*q8_M2, [ ], <identity ...> ], 
  [ q8_M1^3, [ [ 1, <identity. ..> ] ], q8_M3 ], 
  [ q8_M1^2*q8_M2, [ [ 4, <identity. ..> ] ], q8_M4 ], 
  [ q8_M1*q8_M2*q8_M1, [ [ 3, <identity ...> ] ], q8_M2 ], 
  [ q8_M2*q8_M1*q8_M4, [ [ 3, q8_M3^-1 ] ], q8_M3] ]
gap> l2 := LoggedKnuthBendix( l1 );
[ [ q8_M1*q8_M3, [ ], <identity ...> ], 
  [ q8_M2*q8_M1, [ [ 3, q8_M3^-1 ], [-1, <identity. ..> ], [ 4, q8_M1^-1 ] ], 
      q8_M1*q8_M4 ], 
  [ q8_M2^2, [ [ -4, <identity ...> ], [2, q8_M1^-2] ], q8_M1^2 ], 
  [ q8_M2*q8_M3, [ [ -3, <identity ...> ] ], q8_M1*q8_M2 ], 
  [ q8_M2*q8_M4, [ ], <identity ...> ], [ q8_M3*q8_M1, [ ], <identity ...> ], 
  [ q8_M3*q8_M2, [ [ -1, <identity ...>], [4, q8_M1^-1 ] ], q8_M1*q8_M4 ],
  [ q8_M3^2, [ [ -1, <identity ...>] ], q8_M1^2 ], 
  [ q8_M3*q8_M4, [ [ -1, <identity ...>], [ -2, q8_M1^-2], 
        [ 4, <identity ...> ], [ 3, q8_M3^-1*q8_M2^-1 ], 
        [ -3, <identity. ..> ] ], q8_M1*q8_M2 ], 
  [ q8_M4*q8_M1, [ [ -4, <identity ...> ], [ 3, q8_M1^-1 ] ], q8_M1*q8_M2 ], 
  [ q8_M4*q8_M2, [ ], <identity ...> ], 
  [ q8_M4*q8_M3, [ [ -3, q8_M3^-1*q8_M4^-1] ], q8_M1*q8_M4 ], 
  [ q8_M4^2, [ [ -4, <identity. ..> ] ], q8_M1^2 ], 
  [ q8_M1^3, [ [ 1, <identity ...> ] ], q8_M3 ], 
  [ q8_M1^2*q8_M2, [ [4, <identity. ..> ] ], q8_M4 ], 
  [ q8_M1^2*q8_M4, [ [ -4, q8_M1^-2], [ 1, <identity ...> ] ], q8_M2 ] ] 

3.2 Logged reduction of a word

3.2-1 LoggedReduceWordKB
‣ LoggedReduceWordKB( word, loggedrules )( operation )
‣ LoggedOnePassReduceWord( word, loggedrules )( operation )
‣ ShorterLoggedRule( logrule1, logrule2 )( operation )

Given a word and a logged rewrite system, the function LoggedOnePassReduceWord makes one reduction of the word (as in OnePassReduceWord) and records this, using the log part of the rule used and the position in the original word of the replaced part.

The function LoggedReduceWordKB repeatedly applies OnePassLoggedReduceWord until the word can no longer be reduced. Each step of the reduction is logged, showing how the original word can be expressed in terms of the original relators and the irreducible word. When loggedrules is complete the reduced word is a unique normal form for that group element. The log of the reduction depends on the order in which the rules are applied.

The function ShorterLoggedrule decides whether one logged rule is better than another, using the same criteria as ShorterRule. In the example we perform logged reductions of w0 corresponding to the ordinary reductions performed in the previous chapter.


gap> w0; 
q8_M2^9*q8_M1^9
gap> lw1 := LoggedOnePassReduceWord( w0, l0 );
[ [ [ 1, q8_M2^-9 ], [ 2, <identity ...> ] ], q8_M2^5*q8_M1^5 ]
gap> lw2 := LoggedReduceWordKB( w0, l0 ); 
[ [ [ 1, q8_M2^-9 ], [ 2, <identity ...> ], [ 1, q8_M2^-5 ],
      [ 2, <identity ...> ] ], q8_M2*q8_M1 ]
gap> lw2 := LoggedReduceWordKB( w0, l2 ); 
[ [ [ 3, q8_M3^-1*q8_M2^-8 ], [ -1, q8_M2^-8 ], [ 4, q8_M1^-1*q8_M2^-8 ], 
      [ -4, <identity ...> ], [ 2, q8_M1^-2 ], 
      [ -4, q8_M1^-1*q8_M2^-6*q8_M1^-2 ], [ 3, q8_M1^-2*q8_M2^-6*q8_M1^-2 ], 
      [ 1, q8_M2^-1*q8_M1^-2*q8_M2^-6*q8_M1^-2 ], [ 4, <identity ...> ], 
      [ 3, q8_M3^-1*q8_M2^-4*q8_M4^-1 ], [ -1, q8_M2^-4*q8_M4^-1 ], 
      [ 4, q8_M1^-1*q8_M2^-4*q8_M4^-1 ], [ -4, q8_M4^-1 ], 
      [ 2, q8_M1^-2*q8_M4^-1 ], 
      [ -3, q8_M1^-1*q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-2*q8_M4^-1 ], 
      [ -4, <identity ...> ], [ 3, q8_M1^-1 ], 
      [ 1, q8_M2^-1*q8_M1^-2*q8_M4^-1*q8_M1^-1*q8_M2^-1*(q8_M2^-1*q8_M1^-1)^2 
         ], [ 4, q8_M4^-1*q8_M1^-1*q8_M2^-1*(q8_M2^-1*q8_M1^-1)^2 ], 
      [ 3, q8_M3^-1*q8_M1^-1 ], [ -1, q8_M1^-1 ], [ 4, q8_M1^-2 ], 
      [ -4, q8_M4^-1*q8_M1^-2 ], [ 2, q8_M1^-2*q8_M4^-1*q8_M1^-2 ], 
      [ -4, q8_M1^-2 ], [ 3, q8_M1^-3 ], [ -4, q8_M1^-2*q8_M2^-1*q8_M1^-3 ], 
      [ 1, <identity ...> ], [ 3, q8_M3^-2 ], [ -1, q8_M3^-1 ], 
      [ 4, q8_M1^-1*q8_M3^-1 ], [ -4, <identity ...> ], [ 3, q8_M1^-1 ], 
      [ 3, q8_M3^-1*q8_M1^-1 ], [ -1, q8_M1^-1 ], [ 4, q8_M1^-2 ], 
      [ -4, q8_M1^-2 ], [ 3, q8_M1^-3 ], [ 1, <identity ...> ], 
      [ -1, <identity ...> ], [ 4, q8_M1^-1 ] ], q8_M1*q8_M4 ]

3.2-2 LoggedRewritingSystemFpGroup
‣ LoggedRewritingSystemFpGroup( loggedrules )( attribute )

Given a group presentation, the function LoggedRewritingSystemFpGroup determines a logged rewrite system based on the relators. The initial logged rewrite system associated with a group presentation consists of two types of rule. These are logged versions of the two types of rule in the monoid presentation. For each relator rel of the group there is a logged rule [ rel, [ [ 1, rel] ], id]. For each inverse relator there is a logged rule [gen*inv, [], id ]. It then attempts a completion of the logged rewrite system. The rules in the final system are partially ordered by the function ShorterLoggedRule.


gap> LoggedRewritingSystemFpGroup( q8 );
[ [ q8_M4*q8_M2, [ ], <identity ...> ], [ q8_M3*q8_Ml, [ ], <identity ...> ], 
    [ q8_M2*q8_M4, [ ], <identity ...> ], 
  [ q8_Ml*q8_M3, [ ], <identity ...> ], 
  [ q8_Ml^2*q8_M4, [ [ -8, q8_Ml^-2 ], [ 5, <identity ...> ] ], q8_M2 ], 
  [ q8_Ml^2*q8_M2, [ [ 8, <identity ...> ] ], q8_M4 ], 
  [ q8_Ml^3, [ [ 5, <identity ...> ] ], q8_M3 ], 
  [ q8_M4^2, [ [ -8, <identity ...> ] ], q8_Ml^2 ], 
  [ q8_M4*q8_M3, [ [ -7, q8_M3^-1*q8_M4^-1 ] ], q8_Ml*q8_M4 ], 
  [ q8_M4*q8_Ml, [ [ -8, <identity. ..> ], [ 7, q8_Ml^-1 ] ], q8_Ml*q8_M2 ], 
  [ q8_M3*q8_M4, 
      [ [ -5, <identity ...>], [ -6, q8_Ml^-2 ], [ 8, <identity ...> ], 
          [ 7, q8_M3^-1*q8_M2^-1 ], [ -7, <identity. ..> ] ], q8_Ml*q8_M2 ], 
  [ q8_M3^2, [ [ -5, <identity ...>] ], q8_Ml^2 ], 
  [ q8_M3*q8_M2, [ [ -5, <identity. ..> ], [ 8, q8_Ml^-1 ] ], q8_Ml*q8_M4 ], 
  [ q8_M2*q8_M3, [ [ -7, <identity ...> ] ], q8_M1*q8_M2 ], 
  [ q8_M2^2, [ [ -a, <identity ...> ], [ 6, q8_M1^-2 ] ], q8_M1^2 ], 
  [ q8_M2*q8_M1, [ [ 7, q8_M3^-1 ], [ -5, <identity ...> ], [ a, q8_M1^-1 ] ], 
      q8_M1*q8_M4 ] ] 

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML