<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Kan) - Chapter 2: Double Coset Rewriting Systems</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X7F197C8D835A6F45" name="X7F197C8D835A6F45"></a></p>
<div class="ChapSects"><a href="chap2.html#X7F197C8D835A6F45">2 <span class="Heading">Double Coset Rewriting Systems</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7CA8FCFD81AA1890">2.1 <span class="Heading">Rewriting Systems</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X87A3823483E4FF86">2.1-1 KnuthBendixRewritingSystem</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X846F0B22859B601A">2.2 <span class="Heading">Example 1 -- free product of two cyclic groups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X825D1F4D85DE122D">2.2-1 DoubleCosetRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X83FF05087E7B133A">2.2-2 WordAcceptorOfReducedRws</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X838CC08E7E92EBC0">2.3 <span class="Heading">Example 2 -- the trefoil group</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X83DE506B828F4B0D">2.3-1 PartialDoubleCosetRewritingSystem</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X86DACE357868DC1B">2.4 <span class="Heading">Example 3 -- an infinite rewriting system</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X8722C57284F51940">2.4-1 KBMagRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X815C08FD87D014B5">2.4-2 DCrules</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7AF0265982B42E47">2.4-3 NextWord</a></span>
</div>
</div>
<h3>2 <span class="Heading">Double Coset Rewriting Systems</span></h3>
<p>The <strong class="pkg">kan</strong> package provides functions for the computation of normal forms for double coset representatives of finitely presented groups. The first version of the package was released to support the paper <a href="chapBib.html#biBBrGhHeWe">[BGHW06]</a>, which describes the algorithms used in this package.</p>
<p><a id="X7CA8FCFD81AA1890" name="X7CA8FCFD81AA1890"></a></p>
<h4>2.1 <span class="Heading">Rewriting Systems</span></h4>
<p><a id="X87A3823483E4FF86" name="X87A3823483E4FF86"></a></p>
<h5>2.1-1 KnuthBendixRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KnuthBendixRewritingSystem</code>( <var class="Arg">grp, gensorder, ordering, alph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ReducedConfluentRewritingSystem</code>( <var class="Arg">grp, gensorder, ordering, limit</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DisplayRwsRules</code>( <var class="Arg">rws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Methods for <code class="code">KnuthBendixRewritingSystem</code> and <code class="code">ReducedConfluentRewritingSystem</code> are supplied which apply to a finitely presented group. These start by calling <code class="code">IsomorphismFpMonoid</code> and then work with the resulting monoid. The parameter <code class="code">gensorder</code> will normally be <code class="code">"shortlex"</code> or <code class="code">"wreath"</code>, while <code class="code">ordering</code> is an integer list for reordering the generators, and <code class="code">alph</code> is an alphabet string used when printing words. A <em>partial</em> rewriting system may be obtained by giving a <code class="code">limit</code> to the number of rules calculated. As usual, A,B denote the inverses of a,b.</p>
<p>In the example the generators are by default ordered [A,a,B,b], so the list <code class="code">L1</code> is used to specify the order <code class="code">[a,A,b,B]</code> to be used with the shortlex ordering. Specifying a limit <code class="code">0</code> means that no limit is prescribed.</p>
<table class="example">
<tr><td><pre>
gap> G1 := FreeGroup( 2 );;
gap> L1 := [2,1,4,3];;
gap> order := "shortlex";;
gap> alph1 := "AaBb";;
gap> rws1 := ReducedConfluentRewritingSystem( G1, L1, order, 0, alph1 );
Rewriting System for Monoid( [ f1^-1, f1, f2^-1, f2 ], ... ) with rules
[ [ f1^-1*f1, <identity ...> ], [ f1*f1^-1, <identity ...> ],
[ f2^-1*f2, <identity ...> ], [ f2*f2^-1, <identity ...> ] ]
gap> DisplayRwsRules( rws1 );;
[ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ]
</pre></td></tr></table>
<p><a id="X846F0B22859B601A" name="X846F0B22859B601A"></a></p>
<h4>2.2 <span class="Heading">Example 1 -- free product of two cyclic groups</span></h4>
<p><a id="X825D1F4D85DE122D" name="X825D1F4D85DE122D"></a></p>
<h5>2.2-1 DoubleCosetRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DoubleCosetRewritingSystem</code>( <var class="Arg">grp, genH, genK, rws</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsDoubleCosetRewritingSystem</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A <em>double coset rewriting system</em> for the double cosets H backslash G / K requires as data a finitely presented group G =<code class="code">grp</code>, generators <code class="code">genH, genK</code> for subgroups H, K, and a rewriting system <code class="code">rws</code> for G.</p>
<p>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 <code class="code">gcd(6,4)=2</code>, 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.</p>
<p>In the example the free group G is converted to a four generator monoid with relations defining the inverse of each generator, <code class="code">[[Aa,id],[aA,id],[Bb,id],[bB,id]]</code>, where <code class="code">id</code> 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.</p>
<p>For this example,</p>
<ul>
<li><p>there are two H-rules, [[Ha^4,HA^2],[HA^3,Ha^3]],</p>
</li>
<li><p>there are two K-rules, [[a^3K,AK],[A^2K,a^2K]],</p>
</li>
<li><p>and there are two H-K-rules, [[Ha^2K,HK],[HAK,HaK]].</p>
</li>
</ul>
<p>Here is how the computation may be performed.</p>
<table class="example">
<tr><td><pre>
gap> genG1 := GeneratorsOfGroup( G1 );;
gap> genH1 := [ genG1[1]^6 ];;
gap> genK1 := [ genG1[1]^4 ];;
gap> dcrws1 := DoubleCosetRewritingSystem( G1, genH1, genK1, rws1 );;
gap> IsDoubleCosetRewritingSystem( dcrws1 );
true
gap> DisplayRwsRules( dcrws1 );;
G-rules:
[ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ]
H-rules:
[ [ Haaaa, HAA ],
[ HAAA, Haaa ] ]
K-rules:
[ [ aaaK, AK ],
[ AAK, aaK ] ]
H-K-rules:
[ [ HaaK, HK ],
[ HAK, HaK ] ]
</pre></td></tr></table>
<p><a id="X83FF05087E7B133A" name="X83FF05087E7B133A"></a></p>
<h5>2.2-2 WordAcceptorOfReducedRws</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordAcceptorOfReducedRws</code>( <var class="Arg">rws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordAcceptorOfDoubleCosetRws</code>( <var class="Arg">rws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsWordAcceptorOfDoubleCosetRws</code>( <var class="Arg">aut</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Using functions from the <strong class="pkg">automata</strong> package, we may</p>
<ul>
<li><p>compute a <em>word acceptor</em> for the rewriting system of G;</p>
</li>
<li><p>compute a <em>word acceptor</em> for the double coset rewriting system;</p>
</li>
<li><p>test a list of words to see whether they are recognised by the automaton;</p>
</li>
<li><p>obtain a rational expression for the language of the automaton.</p>
</li>
</ul>
<table class="example">
<tr><td><pre>
gap> waG1 := WordAcceptorOfReducedRws( rws1 );
Automaton("nondet",6,"aAbB",[ [ [ 1 ], [ 4 ], [ 1 ], [ 4 ], [ 4 ], [ 4 ] ], [ \
[ 1 ], [ 3 ], [ 3 ], [ 1 ], [ 3 ], [ 3 ] ], [ [ 1 ], [ 6 ], [ 6 ], [ 6 ], [ 1 \
], [ 6 ] ], [ [ 1 ], [ 5 ], [ 5 ], [ 5 ], [ 5 ], [ 1 ] ] ],[ 2 ],[ 1 ]);;
gap> wadc1 := WordAcceptorOfDoubleCosetRws( dcrws1 );
< deterministic automaton on 6 letters with 15 states >
gap> Print( wadc1 );
Automaton("det",15,"HKaAbB",[ [ 2, 2, 2, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ],\
[ 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2 ], [ 2, 2, 13, 2, 10, 5, 2, 13,\
2, 7, 11, 11, 12, 2, 2 ], [ 2, 2, 9, 2, 2, 14, 2, 9, 15, 2, 2, 2, 2, 7, 15 ],\
[ 2, 2, 2, 2, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ], [ 2, 2, 3, 2, 3, 3, 3, 2, 3,\
3, 3, 3, 3, 3, 3 ] ],[ 4 ],[ 1 ]);;
gap> words1 := [ "HK","HaK","HbK","HAK","HaaK","HbbK","HabK","HbaK","HbaabK"];;
gap> valid1 := List( words1, w -> IsRecognizedByAutomaton( wadc1, w ) );
[ true, true, true, false, false, true, true, true, true ]
gap> lang1 := FAtoRatExp( wadc1 );
((H(aaaUAA)BUH(a(aBUB)UABUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(a(aa*bUb)Ub)UA(AA\
*bUb))UH(aaaUAA)bUH(a(abUb)UAbUb))((a(a(aa*BUB)UB)UA(AA*BUB))(a(a(aa*BUB)UB)UA\
(AA*BUB)UB)*(a(a(aa*bUb)Ub)UA(AA*bUb))Ua(a(aa*bUb)Ub)UA(AA*bUb)Ub)*((a(a(aa*BU\
B)UB)UA(AA*BUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(aKUK)UAKUK)Ua(aKUK)UAKUK)U(H(a\
aaUAA)BUH(a(aBUB)UABUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(aKUK)UAKUK)UH(aKUK)
</pre></td></tr></table>
<p><a id="X838CC08E7E92EBC0" name="X838CC08E7E92EBC0"></a></p>
<h4>2.3 <span class="Heading">Example 2 -- the trefoil group</span></h4>
<p><a id="X83DE506B828F4B0D" name="X83DE506B828F4B0D"></a></p>
<h5>2.3-1 PartialDoubleCosetRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PartialDoubleCosetRewritingSystem</code>( <var class="Arg">grp, Hgens, Kgens, rws, limit</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordAcceptorOfPartialDoubleCosetRws</code>( <var class="Arg">grp, prws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>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.</p>
<table class="example">
<tr><td><pre>
gap> FT := FreeGroup( 2 );;
gap> relsT := [ FT.1^3*FT.2^-2 ];;
gap> T := FT/relsT;;
gap> genT := GeneratorsOfGroup( T );;
gap> x := genT[1]; y := genT[2];
gap> alphT := "XxYy";;
gap> ordT := [4,3,2,1];;
gap> orderT := "wreath";;
gap> rwsT := ReducedConfluentRewritingSystem( T, ordT, orderT, 0, alphT );
gap> DisplayRwsRules( rwsT );;
[ [ Yy, id ], [ yY, id ], [ X, xxYY ], [ xxx, yy ], [ yyx, xyy ], [ Yx, yxYY ]\
]
gap> accT := WordAcceptorOfReducedRws( rwsT );
< deterministic automaton on 4 letters with 7 states >
gap> Print( accT );
Automaton("nondet",7,"yYxX",[ [ [ 1 ], [ 4 ], [ 1 ], [ 4, 7 ], [ 4 ], [ 4 ], [\
4, 7 ] ], [ [ 1 ], [ 3 ], [ 3 ], [ 1 ], [ 3 ], [ 3 ], [ 1 ] ], [ [ 1 ], [ 5 ]\
, [ 1 ], [ 5 ], [ 5, 6 ], [ 1 ], [ 1 ] ], [ [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ],\
[ 1 ], [ 1 ] ] ],[ 2 ],[ 1 ]);;
gap> langT := FAtoRatExp( accT );
(xx*(xyUy)Uy)(xx*(xyUy)Uyy*yUy)*(xx*((xYUY)Y*(yUxUX)Ux(xUX)UX)(yUYUxUX)*U(yy*(\
YUxUX)UYUX)(yUYUxUX)*)Uxx*((xYUY)Y*(yUxUX)Ux(xUX)UX)(yUYUxUX)*U(YY*(yUxUX)UX)(\
yUYUxUX)*(yxUx)((xyUy)x)*
gap> r := RationalExpression( "((xyUy)y*UxY*UY*)Uyy*UY*" );
(xyUy)y*UxY*UY*Uyy*UY*
gap> AreEqualLang( langT, r );
The given languages are not over the same alphabet
false
</pre></td></tr></table>
<p>In a previous version the expression <code class="code">r</code>, which does not involve the letter <code class="code">X</code>, was returned as the language <code class="code">langT</code>. This discrepancy should be investigated.</p>
<p>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 <code class="code">PartialDoubleCosetRewritingSystem</code> 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.</p>
<table class="example">
<tr><td><pre>
gap> prwsT := PartialDoubleCosetRewritingSystem( T, [x], [y], rwsT, 20 );;
#I WARNING: reached supplied limit 20 on number of rules
gap> DisplayRwsRules( prwsT );
G-rules:
[ [ X, xxYY ], [ Yx, yxYY ], [ Yy, id ], [ yY, id ], [ xxx, yy ], [ yyx, xyy ]\
]
H-rules:
[ [ Hx, H ],
[ HY, Hy ],
[ Hyy, H ],
[ Hyxyy, Hyx ],
[ HyxY, Hyxy ],
[ Hyxyxyy, Hyxyx ],
[ Hyxxyy, Hyxx ],
[ HyxxY, Hyxxy ],
[ HyxyxY, Hyxyxy ],
[ Hyxyxyxyy, Hyxyxyx ],
[ Hyxyxxyy, Hyxyxx ],
[ Hyxxyxyy, Hyxxyx ],
[ HyxxyxYY, Hyxxyx ] ]
K-rules:
[ [ YK, K ],
[ yK, K ] ]
</pre></td></tr></table>
<p>This list of partial rules is then used by a modified word acceptor function.</p>
<table class="example">
<tr><td><pre>
gap> paccT := WordAcceptorOfPartialDoubleCosetRws( T, prwsT );;
< deterministic automaton on 6 letters with 6 states >
gap> Print( paccT, "\n" );
Automaton("det",6,"HKyYxX",[ [ 2, 2, 2, 6, 2, 2 ], [ 2, 2, 1, 2, 2, 1 ], [ 2, \
2, 5, 2, 2, 5 ], [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 6, 2, 3, 2 ], [ 2, 2, 2, 2, 2, \
2 ] ],[ 4 ],[ 1 ]);;
gap> plangT := FAtoRatExp( paccT );
H(yx(yx)*x)*(yx(yx)*KUK)
gap> wordsT := ["HK", "HxK", "HyK", "HYK", "HyxK", "HyxxK", "HyyH", "HyxYK"];;
gap> validT := List( wordsT, w -> IsRecognizedByAutomaton( paccT, w ) );
[ true, false, false, false, true, true, false, false ]
</pre></td></tr></table>
<p><a id="X86DACE357868DC1B" name="X86DACE357868DC1B"></a></p>
<h4>2.4 <span class="Heading">Example 3 -- an infinite rewriting system</span></h4>
<p><a id="X8722C57284F51940" name="X8722C57284F51940"></a></p>
<h5>2.4-1 KBMagRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KBMagRewritingSystem</code>( <var class="Arg">fpgrp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KBMagWordAcceptor</code>( <var class="Arg">fpgrp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KBMagFSAtoAutomataDFA</code>( <var class="Arg">fsa, alph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordAcceptorByKBMag</code>( <var class="Arg">grp, alph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordAcceptorByKBMagOfDoubleCosetRws</code>( <var class="Arg">grp, dcrws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>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 <code class="code">KBMagWordAcceptor</code> which calls the package <strong class="pkg">KBMAG</strong> to compute a word acceptor for G, and <code class="code">KBMagFSAtoAutomataDFA</code> to convert this to a deterministic automaton as used by the <strong class="pkg">automata</strong> package. The resulting <code class="code">dfa</code> forms part of the double coset automaton, together with sufficient H-rules, K-rules and H-K-rules found by the function <code class="code">PartialDoubleCosetRewritingSystem</code>. (Note that these five attributes and operations will not be available if the <strong class="pkg">kbmag</strong> package has not been loaded.)</p>
<p>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 <strong class="pkg">KBMAG</strong> has a word acceptor with 17 states.</p>
<table class="example">
<tr><td><pre>
gap> F3 := FreeGroup("a","b");;
gap> rels3 := [ F3.1^3, F3.2^3, (F3.1*F3.2)^3 ];;
gap> G3 := F3/rels3;;
gap> alph3 := "AaBb";;
gap> waG3 := WordAcceptorByKBMag( G3, alph3 );;
gap> Print( waG3, "\n");
Automaton("det",18,"aAbB",[ [ 2, 18, 18, 8, 10, 12, 13, 18, 18, 18, 18, 18, 18\
, 8, 17, 12, 18, 18 ], [ 3, 18, 18, 9, 11, 9, 12, 18, 18, 18, 18, 18, 18, 11, \
18, 11, 18, 18 ], [ 4, 6, 6, 18, 18, 18, 18, 18, 6, 12, 16, 18, 12, 18, 18, 18\
, 12, 18 ], [ 5, 5, 7, 18, 18, 18, 18, 14, 15, 5, 18, 18, 7, 18, 18, 18, 15, 1\
8 ] ],[ 1 ],[ 1 .. 17 ]);;
gap> langG3 := FAtoRatExp( waG3 );
((abUAb)AUbA)(bA)*(b(aU@)UB(aB)*(a(bU@)U@)U@)U(abUAb)(aU@)U((aBUB)(aB)*AUba(Ba\
)*BA)(bA)*(b(aU@)U@)U(aBUB)(aB)*(a(bU@)U@)Uba(Ba)*(BU@)UbUaUA(B(aB)*(a(bU@)UAU\
@)U@)U@
</pre></td></tr></table>
<p><a id="X815C08FD87D014B5" name="X815C08FD87D014B5"></a></p>
<h5>2.4-2 DCrules</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DCrules</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Hrules</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Krules</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HKrules</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>We now 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 <a href="chapBib.html#biBBrGhHeWe">[BGHW06]</a>) three infinite sets of rules and a limit for the automata.</p>
<table class="example">
<tr><td><pre>
gap> lim := 100;;
gap> genG3 := GeneratorsOfGroup( G3 );;
gap> a := genG3[1];; b := genG3[2];;
gap> gH3 := [ a*b ];; gK3 := [ b*a ];;
gap> rwsG3 := KnuthBendixRewritingSystem( G3, "shortlex", [2,1,4,3], alph3 );;
gap> dcrws3 := PartialDoubleCosetRewritingSystem( G3, gH3, gK3, rwsG3, lim );;
#I using PartialDoubleCosetRewritingSystem with limit 100
#I 51 rules, and 1039 pairs
#I WARNING: reached supplied limit 100 on number of rules
gap> Print( Length( Rules( dcrws3 ) ), " rules found.\n" );
101 rules found.
gap> dcaut3 := WordAcceptorByKBMagOfDoubleCosetRws( G3, dcrws3 );;
gap> Print( "Double Coset Minimalized automaton:\n", dcaut3 );
Double Coset Minimalized automaton:
Automaton("det",40,"HKaAbB",[ [ 2, 2, 2, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2\
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ], [ \
2, 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, \
1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1 ], [ 2, 2, 2, 2, 3, 22, 2, 2, 2, 2, 2\
, 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\
, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 40, 3, 27, 2, 8, 2, 10, 2, 12, 2, 14, 2, 16, 2, \
18, 2, 20, 2, 2, 2, 2, 24, 2, 27, 2, 29, 2, 31, 2, 33, 2, 35, 2, 37, 2, 2 ], [\
2, 2, 2, 2, 19, 2, 2, 26, 2, 9, 2, 11, 2, 13, 2, 15, 2, 17, 2, 38, 2, 3, 2, 2\
6, 3, 2, 7, 2, 28, 2, 30, 2, 32, 2, 34, 2, 36, 2, 2, 26 ], [ 2, 2, 2, 2, 2, 2,\
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, \
2, 2, 2, 2, 2, 2, 2, 21, 6 ] ],[ 4 ],[ 1 ]);;
gap> dclang3 := FAtoRatExp( dcaut3 );;
gap> Print( "Double Coset language of acceptor:\n", dclang3, "\n" );
Double Coset language of acceptor:
(HbAbAbAbAbAbAbUHAb)(Ab)*(A(Ba(Ba)*bKUK)UK)UHbAbA(bA(bA(bA(bAKUK)UK)UK)UK)UH(A\
(B(aB)*(abUA)KUK)UaKUb(a(Ba)*BA(bA(bA(bA(bA(bA(bA(bA)*(bKUK)UK)UK)UK)UK)UK)UK)\
UAK)UK)
gap> ok := DCrules(dcrws3);;
gap> alph3e := dcrws3!.alphabet;;
gap> Print("H-rules:\n"); DisplayAsString( Hrules(dcrws3), alph3e, true );
H-rules:
[ HB, Ha ]
[ HaB, Hb ]
[ Hab, H ]
[ HbAB, HAba ]
[ HbAbAB, HAbAba ]
[ HbAbAbAB, HAbAbAba ]
[ HbAbAbAbAB, HAbAbAbAba ]
[ HbAbAbAbAbAB, HAbAbAbAbAba ]
[ HbAbAbAbAbAbAB, HAbAbAbAbAbAba ]
gap> Print("K-rules:\n"); DisplayAsString( Krules(dcrws3), alph3e, true );
K-rules:
[ BK, aK ]
[ BaK, bK ]
[ baK, K ]
[ BAbK, abAK ]
[ BAbAbK, abAbAK ]
[ BAbAbAbK, abAbAbAK ]
[ BAbAbAbAbK, abAbAbAbAK ]
[ BAbAbAbAbAbK, abAbAbAbAbAK ]
[ BAbAbAbAbAbAbK, abAbAbAbAbAbAK ]
gap> Print("HK-rules:\n"); DisplayAsString( HKrules(dcrws3), alph3e, true );
HK-rules:
[ HbK, HAK ]
[ HbAbK, HAbAK ]
[ HbAbAbK, HAbAbAK ]
[ HbAbAbAbK, HAbAbAbAK ]
[ HbAbAbAbAbK, HAbAbAbAbAK ]
[ HbAbAbAbAbAbK, HAbAbAbAbAbAK ]
</pre></td></tr></table>
<p><a id="X7AF0265982B42E47" name="X7AF0265982B42E47"></a></p>
<h5>2.4-3 NextWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NextWord</code>( <var class="Arg">dcrws, word</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordToString</code>( <var class="Arg">word, alph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DisplayAsString</code>( <var class="Arg">word, alph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IdentityDoubleCoset</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>These functions may be used to find normal forms of increasing length for double coset representatives.</p>
<table class="example">
<tr><td><pre>
gap> len := 30;;
gap> L3 := 0*[1..len];;
gap> L3[1] := IdentityDoubleCoset( dcrws3 );;
gap> for i in [2..len] do
gap> L3[i] := NextWord( dcrws3, L3[i-1] );
gap> od;
gap> ## List of 30 normal forms for double cosets:
gap> DisplayAsString( L3, alph3e, true );
[ HK, HAK, HaK, HAbK, HbAK, HABAK, HAbAK, HABabK, HAbAbK, HbAbAK, HbaBAK, HABa\
BAK, HAbAbAK, HABaBabK, HAbABabK, HAbAbAbK, HbAbAbAK, HbaBAbAK, HbaBaBAK, HABa\
BaBAK, HAbAbAbAK, HABaBaBabK, HAbABaBabK, HAbAbABabK, HAbAbAbAbK, HbAbAbAbAK, \
HbaBAbAbAK, HbaBaBAbAK, HbaBaBaBAK, HABaBaBaBAK ]
gap> w := NextWord( dcrws3, L3[30] );
m1*m3*m6*m3*m6*m3*m6*m3*m6*m3*m2
gap> s := WordToString( w, alph3e );
"HAbAbAbAbAK"
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1698
