  
  [1m[4m[31m2. Double Coset Rewriting Systems[0m
  
  The  [1mkan[0m  package provides functions for the computation of normal forms for
  double  coset  representatives  of  finitely  presented  groups.  This first
  version of the package has been released to support the paper [BG+06], which
  describes the algorithms used in this package.
  
  
  [1m[4m[31m2.1 Rewriting Systems[0m
  
  [1m[4m[31m2.1-1 KnuthBendixRewritingSystem[0m
  
  [1m[34m> KnuthBendixRewritingSystem( [0m[22m[34mgrp, gensorder, ordering, alph[0m[1m[34m ) ____[0moperation
  [1m[34m> ReducedConfluentRewritingSystem( [0m[22m[34mgrp, gensorder, ordering, limit[0m[1m[34m ) [0moperation
  [1m[34m> DisplayRwsRules( [0m[22m[34mrws[0m[1m[34m ) __________________________________________[0moperation
  
  Methods  for  [22m[32mKnuthBendixRewritingSystem[0m and [22m[32mReducedConfluentRewritingSystem[0m
  are  supplied  which  apply  to  a  finitely presented group. These start by
  calling  [22m[32mIsomorphismFpMonoid[0m  and  then  work with the resulting monoid. The
  parameter  [22m[32mgensorder[0m will normally be [22m[32m"shortlex"[0m or [22m[32m"wreath"[0m, while [22m[32mordering[0m
  is  an  integer  list for reordering the generators, and [22m[32malph[0m is an alphabet
  string  used when printing words. A [22m[36mpartial[0m rewriting system may be obtained
  by giving a [22m[32mlimit[0m to the number of rules calculated.
  
  In  the example the generators are by default ordered [A,a,B,b], so the list
  [22m[32mL1[0m  is  used  to  specify  the  order [22m[32m[a,A,b,B][0m to be used with the shortlex
  ordering. Specifying a limit [22m[32m0[0m means that no limit is prescribed.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> G1 := FreeGroup( 2 );;[0m
    [22m[35mgap> L1 := [2,1,4,3];;[0m
    [22m[35mgap> order := "shortlex";;[0m
    [22m[35mgap> alph1 := "AaBb";;[0m
    [22m[35mgap> rws1 := ReducedConfluentRewritingSystem( G1, L1, order, 0, alph1 );[0m
    [22m[35mRewriting System for Monoid( [ f1^-1, f1, f2^-1, f2 ], ... ) with rules[0m
    [22m[35m[ [ f1^-1*f1, <identity ...> ], [ f1*f1^-1, <identity ...> ],[0m
    [22m[35m  [ f2^-1*f2, <identity ...> ], [ f2*f2^-1, <identity ...> ] ][0m
    [22m[35mgap> DisplayRwsRules( rws1 );;[0m
    [22m[35m[ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.2 Example 1 -- free product of two cyclic groups[0m
  
  [1m[4m[31m2.2-1 DoubleCosetRewritingSystem[0m
  
  [1m[34m> DoubleCosetRewritingSystem( [0m[22m[34mgrp, genH, genK, rws[0m[1m[34m ) _______________[0mfunction
  [1m[34m> IsDoubleCosetRewritingSystem( [0m[22m[34mdcrws[0m[1m[34m ) ____________________________[0mproperty
  
  A  [22m[36mdouble coset rewriting system[0m for the double cosets HG/K requires as data
  a  finitely presented group G or [22m[32mgrp[0m, generators [22m[32mgenH, genK[0m for subgroups H,
  K, and a rewriting system [22m[32mrws[0m for G.
  
  A simple example is given by taking G to be the free group on two generators
  a,b,  a cyclic subgroup H with generator a^6, and a second cyclic subgroup K
  with generator a^4. (Similar examples using different powers of a are easily
  constructed.)  Since [22m[32mgcd(6,4)=2[0m, we have Ha^2K=HK, so the double cosets have
  representatives  [HK,  HaK,  Ha^iba^jK, Ha^ibwba^jK] where i in [0..5], j in
  [0..3], and w is any word in a,b.
  
  In the example the free group G is converted to a four generator monoid with
  relations      defining      the      inverse     of     each     generator,
  [22m[32m[[Aa,id],[aA,id],[Bb,id],[bB,id]][0m,  where  [22m[32mid[0m is the empty word. The initial
  rules  for  the double coset rewriting system comprise those of G plus those
  given  by  the  generators  of  H,K,  which  are [[Ha^6,H],[a^4K,K]]. In the
  complete  rewrite system new rules involving H or K may arise, and there may
  also be rules involving both H and K.
  
  For this example,
  
  --    there are two H-rules, [[Ha^4,HA^2],[HA^3,Ha^3]],
  
  --    there are two K-rules, [[a^3K,AK],[A^2K,a^2K]],
  
  --    and there are two H-K-rules, [[Ha^2K,HK],[HAK,HaK]].
  
  Here is how the computation may be performed.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> genG1 := GeneratorsOfGroup( G1 );;[0m
    [22m[35mgap> genH1 := [ genG1[1]^6 ];;[0m
    [22m[35mgap> genK1 := [ genG1[1]^4 ];;[0m
    [22m[35mgap> dcrws1 := DoubleCosetRewritingSystem( G1, genH1, genK1, rws1 );;[0m
    [22m[35mgap> IsDoubleCosetRewritingSystem( dcrws1 );[0m
    [22m[35mtrue[0m
    [22m[35mgap> DisplayRwsRules( dcrws1 );;[0m
    [22m[35mG-rules:[0m
    [22m[35m[ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ][0m
    [22m[35mH-rules:[0m
    [22m[35m[ [ Haaaa, HAA ],[0m
    [22m[35m  [ HAAA, Haaa ] ][0m
    [22m[35mK-rules:[0m
    [22m[35m[ [ aaaK, AK ],[0m
    [22m[35m  [ AAK, aaK ] ][0m
    [22m[35mH-K-rules:[0m
    [22m[35m[ [ HaaK, HK ],[0m
    [22m[35m  [ HAK, HaK ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.2-2 WordAcceptorOfReducedRws[0m
  
  [1m[34m> WordAcceptorOfReducedRws( [0m[22m[34mrws[0m[1m[34m ) _________________________________[0mattribute
  [1m[34m> WordAcceptorOfDoubleCosetRws( [0m[22m[34mrws[0m[1m[34m ) _____________________________[0mattribute
  [1m[34m> IsWordAcceptorOfDoubleCosetRws( [0m[22m[34maut[0m[1m[34m ) ____________________________[0mproperty
  
  Using functions from the [1mautomata[0m package, we may
  
  --    compute a [22m[36mword acceptor[0m for the rewriting system of G;
  
  --    compute a [22m[36mword acceptor[0m for the double coset rewriting system;
  
  --    test  a  list  of  words  to  see  whether  they are recognised by the
        automaton;
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> waG1 := WordAcceptorOfReducedRws( rws1 );[0m
    [22m[35mAutomaton("det",6,"aAbB",[ [ 1, 4, 1, 4, 4, 4 ], [ 1, 3, 3, 1, 3, 3 ], [ 1, 2,\[0m
    [22m[35m 2, 2, 1, 2 ], [ 1, 1, 5, 5, 5, 5 ] ],[ 6 ],[ 2, 3, 4, 5, 6 ]);;[0m
    [22m[35mgap> wadc1 := WordAcceptorOfDoubleCosetRws( dcrws1 );[0m
    [22m[35m< deterministic automaton on 6 letters with 15 states >[0m
    [22m[35mgap> Print( wadc1 );[0m
    [22m[35mAutomaton("det",15,"HKaAbB",[ [ 2, 2, 2, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ],\[0m
    [22m[35m [ 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2 ], [ 2, 2, 13, 2, 10, 5, 2, 13,\[0m
    [22m[35m 2, 7, 11, 11, 12, 2, 2 ], [ 2, 2, 9, 2, 2, 14, 2, 9, 15, 2, 2, 2, 2, 7, 15 ],\[0m
    [22m[35m [ 2, 2, 2, 2, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ], [ 2, 2, 3, 2, 3, 3, 3, 2, 3,\[0m
    [22m[35m 3, 3, 3, 3, 3, 3 ] ],[ 4 ],[ 1 ]);;[0m
    [22m[35mgap> words1 := [ "HK","HaK","HbK","HAK","HaaK","HbbK","HabK","HbaK","HbaabK"];;[0m
    [22m[35mgap> valid1 := List( words1, w -> IsRecognizedByAutomaton( wadc1, w ) );[0m
    [22m[35m[ true, true, true, false, false, true, true, true, true ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.2-3 SFAtoRatExp[0m
  
  [1m[34m> SFAtoRatExp( [0m[22m[34maut[0m[1m[34m ) _______________________________________________[0mfunction
  
  The  function [22m[32mSFAtoRatExp[0m comes from the development version of the [1mautomata[0m
  package, and has been supplied by the authors of that package. It computes a
  regular expression for the language recognised by the automaton [22m[32maut[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> lang1 := SFAtoRatExp( wadc1 );[0m
    [22m[35m((H(aaaUAA)BUH(a(aBUB)UABUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(a(aa*bUb)Ub)UA(AA\[0m
    [22m[35m*bUb))UH(aaaUAA)bUH(a(abUb)UAbUb))((a(a(aa*BUB)UB)UA(AA*BUB))(a(a(aa*BUB)UB)UA\[0m
    [22m[35m(AA*BUB)UB)*(a(a(aa*bUb)Ub)UA(AA*bUb))Ua(a(aa*bUb)Ub)UA(AA*bUb)Ub)*((a(a(aa*BU\[0m
    [22m[35mB)UB)UA(AA*BUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(aKUK)UAKUK)Ua(aKUK)UAKUK)U(H(a\[0m
    [22m[35maaUAA)BUH(a(aBUB)UABUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(aKUK)UAKUK)UH(aKUK)[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.3 Example 2 -- the trefoil group[0m
  
  [1m[4m[31m2.3-1 PartialDoubleCosetRewritingSystem[0m
  
  [1m[34m> PartialDoubleCosetRewritingSystem( [0m[22m[34mgrp, Hgens, Kgens, rws, limit[0m[1m[34m ) [0moperation
  [1m[34m> WordAcceptorOfPartialDoubleCosetRws( [0m[22m[34mgrp, prws[0m[1m[34m ) ________________[0mattribute
  
  It  may  happen  that, even when G has a finite rewriting system, the double
  coset  rewriting system is infinite. This is the case with the trefoil group
  T  with  generators  [x,y]  and  relator  [x^3  = y^2] if the wreath product
  ordering is used with X > x > Y > y. The group itself has a rewriting system
  with just 6 rules.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> FT := FreeGroup( 2 );;[0m
    [22m[35mgap> relsT := [ FT.1^3*FT.2^-2 ];;[0m
    [22m[35mgap> T := FT/relsT;;[0m
    [22m[35mgap> genT := GeneratorsOfGroup( T );;[0m
    [22m[35mgap> x := genT[1];  y := genT[2];[0m
    [22m[35mgap> alphT := "XxYy";;[0m
    [22m[35mgap> ordT := [4,3,2,1];;[0m
    [22m[35mgap> orderT := "wreath";;[0m
    [22m[35mgap> rwsT := ReducedConfluentRewritingSystem( T, ordT, orderT, 0, alphT );[0m
    [22m[35mgap> DisplayRwsRules( rwsT );;[0m
    [22m[35m[ [ Yy, id ], [ yY, id ], [ X, xxYY ], [ xxx, yy ], [ yyx, xyy ], [ Yx, yxYY ]\[0m
    [22m[35m ][0m
    [22m[35mgap> accT := WordAcceptorOfReducedRws( rwsT );[0m
    [22m[35m< deterministic automaton on 4 letters with 7 states >[0m
    [22m[35mgap> Print( accT, "\n" );[0m
    [22m[35mAutomaton("det",7,"yYxX",[ [ 6, 2, 2, 4, 6, 4, 6 ], [ 3, 2, 3, 2, 3, 2, 3 ], [\[0m
    [22m[35m 7, 2, 2, 2, 2, 7, 5 ], [ 2, 2, 2, 2, 2, 2, 2 ] ],[ 1 ],[ 1, 3, 4, 5, 6, 7 ]);\[0m
    [22m[35m;[0m
    [22m[35mgap> langT := SFAtoRatExp( accT );[0m
    [22m[35m(yxUx)((xyUy)x)*((xyUy)y*UxY*UY*)Uyy*UY*[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  Taking  subgroups  H,  K to be generated by x and y respectively, the double
  coset  rewriting system has an infinite number of H-rules. It turns out that
  only  a finite number of these are needed to produce the required automaton.
  The   function   [22m[32mPartialDoubleCosetRewritingSystem[0m  allows  a  limit  to  be
  specified  on  the  number  of  rules to be computed. In the listing below a
  limit of 20 is used, but in fact 10 is sufficient.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> prwsT := PartialDoubleCosetRewritingSystem( T, [x], [y], rwsT, 20 );;[0m
    [22m[35m#I WARNING: reached supplied limit 20 on number of rules[0m
    [22m[35mgap> DisplayRwsRules( prwsT );[0m
    [22m[35mG-rules:[0m
    [22m[35m[ [ X, xxYY ], [ Yx, yxYY ], [ Yy, id ], [ yY, id ], [ xxx, yy ], [ yyx, xyy ]\[0m
    [22m[35m ][0m
    [22m[35mH-rules:[0m
    [22m[35m[ [ Hx, H ],[0m
    [22m[35m  [ HY, Hy ],[0m
    [22m[35m  [ Hyy, H ],[0m
    [22m[35m  [ Hyxyy, Hyx ],[0m
    [22m[35m  [ HyxY, Hyxy ],[0m
    [22m[35m  [ Hyxyxyy, Hyxyx ],[0m
    [22m[35m  [ Hyxxyy, Hyxx ],[0m
    [22m[35m  [ HyxxY, Hyxxy ],[0m
    [22m[35m  [ HyxyxY, Hyxyxy ],[0m
    [22m[35m  [ Hyxyxyxyy, Hyxyxyx ],[0m
    [22m[35m  [ Hyxyxxyy, Hyxyxx ],[0m
    [22m[35m  [ Hyxxyxyy, Hyxxyx ],[0m
    [22m[35m  [ HyxxyxYY, Hyxxyx ] ][0m
    [22m[35mK-rules:[0m
    [22m[35m[ [ YK, K ],[0m
    [22m[35m  [ yK, K ] ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  This  list  of  partial  rules  is  then  used  by  a modified word acceptor
  function.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> paccT := WordAcceptorOfPartialDoubleCosetRws( T, prwsT );;[0m
    [22m[35m< deterministic automaton on 6 letters with 6 states >[0m
    [22m[35mgap> Print( paccT, "\n" );[0m
    [22m[35mAutomaton("det",6,"HKyYxX",[ [ 2, 2, 2, 6, 2, 2 ], [ 2, 2, 1, 2, 2, 1 ], [ 2, \[0m
    [22m[35m2, 5, 2, 2, 5 ], [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 6, 2, 3, 2 ], [ 2, 2, 2, 2, 2, \[0m
    [22m[35m2 ] ],[ 4 ],[ 1 ]);;[0m
    [22m[35mgap> plangT := SFAtoRatExp( paccT );[0m
    [22m[35mH(yx(yx)*x)*(yx(yx)*KUK)[0m
    [22m[35mgap> wordsT := ["HK", "HxK", "HyK", "HYK", "HyxK", "HyxxK", "HyyH", "HyxYK"];;[0m
    [22m[35mgap> validT := List( wordsT, w -> IsRecognizedByAutomaton( paccT, w ) );[0m
    [22m[35m[ true, false, false, false, true, true, false, false ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.4 Example 3 -- an infinite rewriting system[0m
  
  [1m[4m[31m2.4-1 KBMagRewritingSystem[0m
  
  [1m[34m> KBMagRewritingSystem( [0m[22m[34mfpgrp[0m[1m[34m ) ___________________________________[0mattribute
  [1m[34m> KBMagWordAcceptor( [0m[22m[34mfpgrp[0m[1m[34m ) ______________________________________[0mattribute
  [1m[34m> KBMagFSAtoAutomataDFA( [0m[22m[34mfsa, alph[0m[1m[34m ) ______________________________[0moperation
  [1m[34m> WordAcceptorByKBMag( [0m[22m[34mgrp, alph[0m[1m[34m ) ________________________________[0moperation
  [1m[34m> WordAcceptorByKBMagOfDoubleCosetRws( [0m[22m[34mgrp, dcrws[0m[1m[34m ) _______________[0moperation
  
  When  the  group  G  has  an  infinite  rewriting  system,  the double coset
  rewriting  system  will  also  be infinite. In this case we try the function
  [22m[32mKBMagWordAcceptor[0m  which  calls the package [1mKBMAG[0m to compute a word acceptor
  for  G,  and  [22m[32mKBMagFSAtoAutomataDFA[0m  to  convert  this  to  a  deterministic
  automaton  as  used by the [1mautomata[0m package. The resulting [22m[32mdfa[0m forms part of
  the  double  coset  automaton, together with sufficient H-rules, K-rules and
  H-K-rules  found  by  the  function [22m[32mPartialDoubleCosetRewritingSystem[0m. (Note
  that these five attributes and operations will not be available if the [1mkbmag[0m
  package has not been loaded.)
  
  In  the  following  example  we  take a two generator group G3 with relators
  [a^3,b^3,(a*b)^3],  the  normal  forms  of  whose  elements  are some of the
  strings  with  a or a^-1 alternating with b or b^-1. The automatic structure
  computed by [1mKBMAG[0m has a word acceptor with 17 states.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> F3 := FreeGroup("a","b");;[0m
    [22m[35mgap> rels3 := [ F3.1^3, F3.2^3, (F3.1*F3.2)^3 ];;[0m
    [22m[35mgap> G3 := F3/rels3;;[0m
    [22m[35mgap> alph3 := "AaBb";;[0m
    [22m[35mgap> waG3 := WordAcceptorByKBMag( G3, alph3 );;[0m
    [22m[35mgap> Print( waG3, "\n");[0m
    [22m[35mAutomaton("det",18,"aAbB",[ [ 2, 18, 18, 8, 10, 12, 13, 18, 18, 18, 18, 18, 18\[0m
    [22m[35m, 8, 17, 12, 18, 18 ], [ 3, 18, 18, 9, 11, 9, 12, 18, 18, 18, 18, 18, 18, 11, \[0m
    [22m[35m18, 11, 18, 18 ], [ 4, 6, 6, 18, 18, 18, 18, 18, 6, 12, 16, 18, 12, 18, 18, 18\[0m
    [22m[35m, 12, 18 ], [ 5, 5, 7, 18, 18, 18, 18, 14, 15, 5, 18, 18, 7, 18, 18, 18, 15, 1\[0m
    [22m[35m8 ] ],[ 1 ],[ 1 .. 17 ]);;[0m
    [22m[35mgap> langG3 := SFAtoRatExp( waG3 );[0m
    [22m[35m((abUAb)AUbA)(bA)*(b(aU@)UB(aB)*(a(bU@)U@)U@)U(abUAb)(aU@)U((aBUB)(aB)*AUba(Ba\[0m
    [22m[35m)*BA)(bA)*(b(aU@)U@)U(aBUB)(aB)*(a(bU@)U@)Uba(Ba)*(BU@)UbUaUA(B(aB)*(a(bU@)UAU\[0m
    [22m[35m@)U@)U@[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.4-2 DCrules[0m
  
  [1m[34m> DCrules( [0m[22m[34mdcrws[0m[1m[34m ) ________________________________________________[0moperation
  [1m[34m> Hrules( [0m[22m[34mdcrws[0m[1m[34m ) _________________________________________________[0mattribute
  [1m[34m> Krules( [0m[22m[34mdcrws[0m[1m[34m ) _________________________________________________[0mattribute
  [1m[34m> HKrules( [0m[22m[34mdcrws[0m[1m[34m ) ________________________________________________[0mattribute
  
  We take H to be generated by ab and K to be generated by ba. If we specify a
  limits of 50, 75, 100, 200 for the number of rules in a partial double coset
  rewrite  system,  we  obtain  lists  of  H-rules,  K-rules  and H-K-rules of
  increasing  length.  The  numbers  of  states in the resulting automata also
  increase.  We  may  deduce  by hand (but not computationally -- see [BG+06])
  three infinite sets of rules and a limit for the automata.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> lim := 100;;[0m
    [22m[35mgap> genG3 := GeneratorsOfGroup( G3 );;[0m
    [22m[35mgap> a := genG3[1];;  b := genG3[2];; [0m
    [22m[35mgap> gH3 := [ a*b ];;  gK3 := [ b*a ];;[0m
    [22m[35mgap> rwsG3 := KnuthBendixRewritingSystem( G3, "shortlex", [2,1,4,3], alph3 );;[0m
    [22m[35mgap> dcrws3 := PartialDoubleCosetRewritingSystem( G3, gH3, gK3, rwsG3, lim );;[0m
    [22m[35m#I using PartialDoubleCosetRewritingSystem with limit 100[0m
    [22m[35m#I  51 rules, and 1039 pairs[0m
    [22m[35m#I WARNING: reached supplied limit 100 on number of rules[0m
    [22m[35mgap> Print( Length( Rules( dcrws3 ) ), " rules found.\n" );[0m
    [22m[35m101 rules found.[0m
    [22m[35mgap> dcaut3 := WordAcceptorByKBMagOfDoubleCosetRws( G3, dcrws3 );;[0m
    [22m[35mgap> Print( "Double Coset Minimalized automaton:\n", dcaut3 );[0m
    [22m[35mDouble Coset Minimalized automaton:[0m
    [22m[35mAutomaton("det",40,"HKaAbB",[ [ 2, 2, 2, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2\[0m
    [22m[35m, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ], [ \[0m
    [22m[35m2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, \[0m
    [22m[35m1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1 ], [ 2, 2, 2, 2, 3, 22, 2, 2, 2, 2, 2\[0m
    [22m[35m, 2, 2, 2, 2, 2, 2, 2, 39, 2, 39, 2, 25, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2\[0m
    [22m[35m, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 40, 3, 27, 2, 8, 2, 10, 2, 12, 2, 14, 2, 16, 2, \[0m
    [22m[35m18, 2, 20, 2, 2, 2, 2, 24, 2, 27, 2, 29, 2, 31, 2, 33, 2, 35, 2, 37, 2, 2 ], [\[0m
    [22m[35m 2, 2, 2, 2, 19, 2, 2, 26, 2, 9, 2, 11, 2, 13, 2, 15, 2, 17, 2, 38, 2, 3, 2, 2\[0m
    [22m[35m6, 3, 2, 7, 2, 28, 2, 30, 2, 32, 2, 34, 2, 36, 2, 2, 26 ], [ 2, 2, 2, 2, 2, 2,\[0m
    [22m[35m 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 23, 23, 2, 2, 2, 2, 2, 2, \[0m
    [22m[35m2, 2, 2, 2, 2, 2, 2, 21, 6 ] ],[ 4 ],[ 1 ]);;[0m
    [22m[35mgap> dclang3 := SFAtoRatExp( dcaut3 );;[0m
    [22m[35mgap> Print( "Double Coset language of acceptor:\n", dclang3, "\n" );[0m
    [22m[35mDouble Coset language of acceptor:[0m
    [22m[35m(HbAbAbAbAbAbAbUHAb)(Ab)*(A(Ba(Ba)*bKUK)UK)UHbAbA(bA(bA(bA(bAKUK)UK)UK)UK)UH(A\[0m
    [22m[35m(B(aB)*(abUA)KUK)UaKUb(a(Ba)*BA(bA(bA(bA(bA(bA(bA(bA)*(bKUK)UK)UK)UK)UK)UK)UK)\[0m
    [22m[35mUAK)UK)[0m
    [22m[35mgap> ok := DCrules(dcrws3);;[0m
    [22m[35mgap> alph3e := dcrws3!.alphabet;;[0m
    [22m[35mgap> Print("H-rules:\n");  DisplayAsString( Hrules(dcrws3), alph3e, true );[0m
    [22m[35mH-rules:[0m
    [22m[35m[ HB, Ha ][0m
    [22m[35m[ HaB, Hb ][0m
    [22m[35m[ Hab, H ][0m
    [22m[35m[ HbAB, HAba ][0m
    [22m[35m[ HbAbAB, HAbAba ][0m
    [22m[35m[ HbAbAbAB, HAbAbAba ][0m
    [22m[35m[ HbAbAbAbAB, HAbAbAbAba ][0m
    [22m[35m[ HbAbAbAbAbAB, HAbAbAbAbAba ][0m
    [22m[35m[ HbAbAbAbAbAbAB, HAbAbAbAbAbAba ][0m
    [22m[35mgap> Print("K-rules:\n");  DisplayAsString( Krules(dcrws3), alph3e, true );[0m
    [22m[35mK-rules:[0m
    [22m[35m[ BK, aK ][0m
    [22m[35m[ BaK, bK ][0m
    [22m[35m[ baK, K ][0m
    [22m[35m[ BAbK, abAK ][0m
    [22m[35m[ BAbAbK, abAbAK ][0m
    [22m[35m[ BAbAbAbK, abAbAbAK ][0m
    [22m[35m[ BAbAbAbAbK, abAbAbAbAK ][0m
    [22m[35m[ BAbAbAbAbAbK, abAbAbAbAbAK ][0m
    [22m[35m[ BAbAbAbAbAbAbK, abAbAbAbAbAbAK ][0m
    [22m[35mgap> Print("HK-rules:\n");  DisplayAsString( HKrules(dcrws3), alph3e, true );[0m
    [22m[35mHK-rules:[0m
    [22m[35m[ HbK, HAK ][0m
    [22m[35m[ HbAbK, HAbAK ][0m
    [22m[35m[ HbAbAbK, HAbAbAK ][0m
    [22m[35m[ HbAbAbAbK, HAbAbAbAK ][0m
    [22m[35m[ HbAbAbAbAbK, HAbAbAbAbAK ][0m
    [22m[35m[ HbAbAbAbAbAbK, HAbAbAbAbAbAK ][0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.4-3 NextWord[0m
  
  [1m[34m> NextWord( [0m[22m[34mdcrws, word[0m[1m[34m ) _________________________________________[0moperation
  [1m[34m> WordToString( [0m[22m[34mword, alph[0m[1m[34m ) ______________________________________[0moperation
  [1m[34m> DisplayAsString( [0m[22m[34mword, alph[0m[1m[34m ) ___________________________________[0moperation
  [1m[34m> IdentityDoubleCoset( [0m[22m[34mdcrws[0m[1m[34m ) ____________________________________[0moperation
  
  These  functions  may  be used to find normal forms of increasing length for
  double coset representatives.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> len := 30;;[0m
    [22m[35mgap> L3 := 0*[1..len];;[0m
    [22m[35mgap> L3[1] := IdentityDoubleCoset( dcrws3 );;[0m
    [22m[35mgap> for i in [2..len] do[0m
    [22m[35mgap>     L3[i] := NextWord( dcrws3, L3[i-1] );[0m
    [22m[35mgap> od;[0m
    [22m[35mgap> ## List of 30 normal forms for double cosets:[0m
    [22m[35mgap> DisplayAsString( L3, alph3e, true );[0m
    [22m[35m[ HK, HAK, HaK, HAbK, HbAK, HABAK, HAbAK, HABabK, HAbAbK, HbAbAK, HbaBAK, HABa\[0m
    [22m[35mBAK, HAbAbAK, HABaBabK, HAbABabK, HAbAbAbK, HbAbAbAK, HbaBAbAK, HbaBaBAK, HABa\[0m
    [22m[35mBaBAK, HAbAbAbAK, HABaBaBabK, HAbABaBabK, HAbAbABabK, HAbAbAbAbK, HbAbAbAbAK, \[0m
    [22m[35mHbaBAbAbAK, HbaBaBAbAK, HbaBaBaBAK, HABaBaBaBAK ][0m
    [22m[35mgap> w := NextWord( dcrws3, L3[30] );[0m
    [22m[35mm1*m3*m6*m3*m6*m3*m6*m3*m6*m3*m2[0m
    [22m[35mgap> s := WordToString( w, alph3e );[0m
    [22m[35m"HAbAbAbAbAK"[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
