| products/Sources/formale Sprachen/GAP/pkg/kan/doc/chap2_mj.html |
 |
<?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>
< script type= "text/javascript"
src= "https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< 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" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap2" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap1_mj.html">[Previous Chapter]</a> <a href="chap3_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap2.html">[MathJax off]</a></p>
<p><a id="X7F197C8D835A6F45" name="X7F197C8D835A6F45"></a></p>
<div class="ChapSects"><a href="chap2_mj.html#X7F197C8D835A6F45">2 <span class="Heading">Double Coset Rewriting Systems</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7CA8FCFD81AA1890">2.1 <span class="Heading">Rewriting Systems</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X87A3823483E4FF86">2.1-1 KnuthBendixRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7AF0265982B42E47">2.1-2 NextWord</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X80B18B248603B3D6">2.2 <span class="Heading">Example 2 -- free product of two cyclic groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X825D1F4D85DE122D">2.2-1 DoubleCosetRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X82E14C4284D89ADF">2.2-2 DisplayAsString</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X83FF05087E7B133A">2.2-3 WordAcceptorOfReducedRws</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X82FE46C27FE55A84">2.3 <span class="Heading">Example 3 -- the trefoil group</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X83DE506B828F4B0D">2.3-1 PartialDoubleCosetRewritingSystem</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7ED711187E2ECAC7">2.4 <span class="Heading">Example 4 -- an infinite rewriting system</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8722C57284F51940">2.4-1 KBMagRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X815C08FD87D014B5">2.4-2 DCrules</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X84B36973833F3B54">2.4-3 WordToString</a></span>
</div></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_mj.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">an style='color: green'>8227; KnuthBendixRewritingSystem</code>( <var class="Arg">grp</var>, <var class="Arg">gensorder</var>, <var class="Arg">ordering</var>, <var class="Arg">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">an style='color: green'>8227; ReducedConfluentRewritingSystem</code>( <var class="Arg">grp</var>, <var class="Arg">gensorder</var>, <var class="Arg">ordering</var>, <var class="Arg">lim</var>, <var class="Arg">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">an style='color: green'>8227; 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">ordering</code> will normally be <code class="code">"shortlex"</code> or <code class="code">"wreath"</code>, while <code class="code">gensorder</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, <span class="SimpleMath">\(A,B\)</span> denote the inverses of <span class="SimpleMath">\(a,b\)</span>.</p>
<p>We take as an example the fundamental group of the oriented surface of genus 2. The generators are by default ordered <code class="code">[A,a,B,b,C,c,D,d]</code>, so the list <code class="code">L = [2,1,4,3,6,5,8,7]</code> is used to specify the order <code class="code">[a,A,b,B,c,C,d,D]</code> to be used with the wreath ordering. Specifying a limit <code class="code">0</code> means that no limit is prescribed.</p>
<p>The operation <code class="code">DisplayRwsRules</code> prints out the rules using the letters in the given alphabet <code class="code">alph4</code> rather than using the generators of the monoid. (As from September 2023 the rules are first converted to a set, so that the output is the same in the latest released version and in the development version.)</p>
<p>An additional method for <code class="code">ReducedForm(G,g)</code> is provided for a finitely presented group <code class="code">G</code> with a rewriting system and an element <code class="code">g</code> of <code class="code">G</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F4 := FreeGroup( 4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rels := [ Comm(F4.1,F4.2) * Comm(F4.3,F4.4) ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H4 := F4/rels;; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">L := [2,1,4,3,6,5,8,7];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">order := "wreath";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alph4 := "aAbBcCdD";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rws4 := ReducedConfluentRewritingSystem( H4, L, order, 0, alph4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayRwsRules( rws4 );</span>
[ [ aA, id ], [ Aa, id ], [ bB, id ], [ Bb, id ], [ cC, id ], [ cd, dcBAba ], \
[ Cc, id ], [ Cd, dABabC ], [ CD, BAbaDC ], [ dD, id ], [ Dd, id ], [ cBAbaD, \
Dc ] ]
true
<span class="GAPprompt">gap></span> <span class="GAPinput">a := H4.1;; b := H4.2;; c := H4.3;; d := H4.4;; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedForm( H4, c*d);</span>
f4*f3*f2^-1*f1^-1*f2*f1
</pre></div>
<p><a id="X7AF0265982B42E47" name="X7AF0265982B42E47"></a></p>
<h5>2.1-2 NextWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; NextWord</code>( <var class="Arg">rws</var>, <var class="Arg">w</var>, <var class="Arg">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">an style='color: green'>8227; NextWords</code>( <var class="Arg">rws</var>, <var class="Arg">w</var>, <var class="Arg">length</var>, <var class="Arg">limit</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The <code class="code">NextWord</code> operation finds the next recognizable word after <code class="code">w</code> using the rewriting system <code class="code">rws</code>. The third parameter is the maximum number of words that will be tested before giving up. (If no limit is provided the number <span class="SimpleMath">\(100,000\)</span> is used.)</p>
<p>The <code class="code">NextWords</code> operation applies <code class="code">NextWord</code> repeatedly and returns a list of the specified length of recognizable words. (If, at any stage, the limit is reached, a truncated list is returned.)</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">free4 := FreeMonoidOfRewritingSystem( rws4 );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens4 := GeneratorsOfMonoid( free4 );</span>
[ f1, f1^-1, f2, f2^-1, f3, f3^-1, f4, f4^-1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NextWord( rws4, gens4[5]*gens4[7] ); </span>
f3*f4^-1
<span class="GAPprompt">gap></span> <span class="GAPinput">NextWords( rws4, last, 20, 100 );</span>
[ f3^-1*f1, f3^-1*f1^-1, f3^-1*f2, f3^-1*f2^-1, f3^-1^2, f4*f1, f4*f1^-1,
f4*f2, f4*f2^-1, f4*f3, f4*f3^-1, f4^2, f4^-1*f1, f4^-1*f1^-1, f4^-1*f2,
f4^-1*f2^-1, f4^-1*f3, f4^-1*f3^-1, f4^-1^2, f1^3 ]
</pre></div>
<p><a id="X80B18B248603B3D6" name="X80B18B248603B3D6"></a></p>
<h4>2.2 <span class="Heading">Example 2 -- 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">an style='color: green'>8227; DoubleCosetRewritingSystem</code>( <var class="Arg">G</var>, <var class="Arg">H</var>, <var class="Arg">K</var>, <var class="Arg">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">an style='color: green'>8227; 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 <span class="SimpleMath">\(H \backslash G / K\)</span> requires as data a finitely presented group <span class="SimpleMath">\(G\)</span>; subgroups <span class="SimpleMath">\(H, K\)</span> of <span class="SimpleMath">\(G\)</span>; and a rewriting system <code class="code">rws</code> for <span class="SimpleMath">\(G\)</span>.</p>
<p>A simple example is given by taking <span class="SimpleMath">\(G\)</span> to be the free group on two generators <span class="SimpleMath">\(a,b\)</span>, a cyclic subgroup <span class="SimpleMath">\(H\)</span> with generator <span class="SimpleMath">\(a^6\)</span>, and a second cyclic subgroup <span class="SimpleMath">\(K\)</span> with generator <span class="SimpleMath">\(a^4\)</span>. (Similar examples using different powers of <span class="SimpleMath">\(a\)</span> are easily constructed.) Since <code class="code">gcd(6,4)=2</code>, we have <span class="SimpleMath">\(Ha^2K=HK\)</span>, so the double cosets have representatives <span class="SimpleMath">\([HK, HaK, Ha^iba^jK, Ha^ibwba^jK]\)</span> where <span class="SimpleMath">\(i \in [0..5]\)</span>, <span class="SimpleMath">\(j \in [0..3]\)</span>, and <span class="SimpleMath">\(w\)</span> is any word in <span class="SimpleMath">\(a,b\)</span>.</p>
<p>In the example the free group <span class="SimpleMath">\(G\)</span> 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 <span class="SimpleMath">\(G\)</span> plus those given by the generators of <span class="SimpleMath">\(H,K\)</span>, which are <span class="SimpleMath">\([[Ha^6,H],[a^4K,K]]\)</span>. In the complete rewrite system new rules involving <span class="SimpleMath">\(H\)</span> or <span class="SimpleMath">\(K\)</span> may arise, and there may also be rules involving both <span class="SimpleMath">\(H\)</span> and <span class="SimpleMath">\(K\)</span>.</p>
<p>For this example,</p>
<ul>
<li><p>there are two <span class="SimpleMath">\(H\)</span>-rules, <span class="SimpleMath">\([[Ha^4,HA^2],[HA^3,Ha^3]]\)</span>,</p>
</li>
<li><p>there are two <span class="SimpleMath">\(K\)</span>-rules, <span class="SimpleMath">\([[a^3K,AK],[A^2K,a^2K]]\)</span>,</p>
</li>
<li><p>and there are two <span class="SimpleMath">\(H\)</span>-<span class="SimpleMath">\(K\)</span>-rules, <span class="SimpleMath">\([[Ha^2K,HK],[HAK,HaK]]\)</span>.</p>
</li>
</ul>
<p>Here is how the computation may be performed.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G1 := FreeGroup( 2 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">L1 := [2,1,4,3];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">order := "shortlex";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alph1 := "AaBb";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rws1 := ReducedConfluentRewritingSystem( G1, L1, order, 0, alph1 );</span>
Rewriting System for Monoid( [ f1, f1^-1, f2, f2^-1 ], ... ) with rules
[ [ f1*f1^-1, <identity ...> ], [ f1^-1*f1, <identity ...> ],
[ f2*f2^-1, <identity ...> ], [ f2^-1*f2, <identity ...> ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayRwsRules( rws1 );;</span>
[ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">genG1 := GeneratorsOfGroup( G1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H1 := Subgroup( G1, [ genG1[1]^6 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">K1 := Subgroup( G1, [ genG1[1]^4 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dcrws1 := DoubleCosetRewritingSystem( G1, H1, K1, rws1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDoubleCosetRewritingSystem( dcrws1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayRwsRules( dcrws1 );;</span>
G-rules:
[ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ]
H-rules:
[ [ HAAA, Haaa ],
[ Haaaa, HAA ] ]
K-rules:
[ [ AAK, aaK ],
[ aaaK, AK ] ]
H-K-rules:
[ [ HAK, HaK ],
[ HaaK, HK ] ]
</pre></div>
<p>An example of obtaining the reduced form of a word using this rewriting system is given in the following section.</p>
<p><a id="X82E14C4284D89ADF" name="X82E14C4284D89ADF"></a></p>
<h5>2.2-2 DisplayAsString</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; DisplayAsString</code>( <var class="Arg">word</var>, <var class="Arg">alph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation displays a double coset using letters of the alphabet obtained by concatenating <code class="code">"HK"</code> with the alphabet for the monoid obtained above. In the example a double coset <code class="code">w</code> and its reduced form <code class="code">rw</code> are displayed.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">free := FreeMonoidOfRewritingSystem( dcrws1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mon := MonoidOfRewritingSystem( dcrws1 );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfMonoid( free );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := gens[1];; K := gens[2];; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := gens[3];; a := gens[4];; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">B := gens[5];; b := gens[6];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alph2 := Concatenation( "HK", alph1 ); </span>
"HKAaBb"
<span class="GAPprompt">gap></span> <span class="GAPinput">w := H*a^5*b^3*a^5*K;</span>
m1*m4^5*m6^3*m4^5*m2
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayAsString( w, alph2 ); </span>
HaaaaabbbaaaaaK
<span class="GAPprompt">gap></span> <span class="GAPinput">rw := ReducedForm( dcrws1, w );</span>
m1*m3*m6^3*m4*m2
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayAsString( rw, alph2 ); </span>
HAbbbaK
</pre></div>
<p><a id="X83FF05087E7B133A" name="X83FF05087E7B133A"></a></p>
<h5>2.2-3 WordAcceptorOfReducedRws</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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">an style='color: green'>8227; 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">an style='color: green'>8227; 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 <span class="SimpleMath">\(G\)</span>;</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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">waG1 := WordAcceptorOfReducedRws( rws1 );</span>
Automaton("det",6,"aAbB",[ [ 1, 4, 1, 4, 4, 4 ], [ 1, 3, 3, 1, 3, 3 ], [ 1, 2,\
2, 2, 1, 2 ], [ 1, 1, 5, 5, 5, 5 ] ],[ 6 ],[ 2, 3, 4, 5, 6 ]);;
<span class="GAPprompt">gap></span> <span class="GAPinput">wadc1 := WordAcceptorOfDoubleCosetRws( dcrws1 );</span>
< deterministic automaton on 6 letters with 15 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( wadc1 );</span>
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 ]);;
<span class="GAPprompt">gap></span> <span class="GAPinput">words1 := [ "HK","HaK","HbK","HAK","HaaK","HbbK","HabK","HbaK","HbaabK"];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">valid1 := List( words1, w -> IsRecognizedByAutomaton( wadc1, w ) );</span>
[ true, true, true, false, false, true, true, true, true ]
<span class="GAPprompt">gap></span> <span class="GAPinput">lang1 := FAtoRatExp( wadc1 );</span>
((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></div>
<p><a id="X82FE46C27FE55A84" name="X82FE46C27FE55A84"></a></p>
<h4>2.3 <span class="Heading">Example 3 -- 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">an style='color: green'>8227; PartialDoubleCosetRewritingSystem</code>( <var class="Arg">grp</var>, <var class="Arg">Hgens</var>, <var class="Arg">Kgens</var>, <var class="Arg">rws</var>, <var class="Arg">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">an style='color: green'>8227; WordAcceptorOfPartialDoubleCosetRws</code>( <var class="Arg">grp</var>, <var class="Arg">prws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>It may happen that, even when <span class="SimpleMath">\(G\)</span> has a finite rewriting system, the double coset rewriting system is infinite. This is the case with the trefoil group <span class="SimpleMath">\(T\)</span> with generators <span class="SimpleMath">\([c,d]\)</span> and relator <span class="SimpleMath">\([c^3 = d^2]\)</span> when the wreath product ordering is used with <span class="SimpleMath">\(C > c > D > d\)</span>. The group itself has a rewriting system with just 6 rules.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FT := FreeGroup( 2 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">relsT := [ FT.1^3*FT.2^-2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := FT/relsT;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">genT := GeneratorsOfGroup( T );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">U := Subgroup( T, [ genT[1] ] );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">V := Subgroup( T, [ genT[2] ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alphT := "cCdD";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ordT := [3,4,1,2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">orderT := "wreath";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rwsT := ReducedConfluentRewritingSystem( T, ordT, orderT, 0, alphT );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayRwsRules( rwsT );;</span>
[ [ C, ccDD ], [ dD, id ], [ Dc, dcDD ], [ Dd, id ], [ ccc, dd ], [ \
ddc, cdd ]\
]
<span class="GAPprompt">gap></span> <span class="GAPinput">accT := WordAcceptorOfReducedRws( rwsT );</span>
< deterministic automaton on 4 letters with 7 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( "accT = ", accT );</span>
accT = Automaton("det",7,"dDcC",[ [ 6, 2, 2, 4, 6, 4, 6 ], [ 3, 2, 3, 2, 3, 2,\
3 ], [ 7, 2, 2, 2, 2, 7, 5 ], [ 2, 2, 2, 2, 2, 2, 2 ] ],[ 1 ],[ 1, 3, 4, 5, 6\
, 7 ]);;
<span class="GAPprompt">gap></span> <span class="GAPinput">langT := FAtoRatExp( accT );</span>
(dcUc)((cdUd)c)*((cdUd)(dd*U@)Uc(DD*U@)UDD*U@)Ud(dd*U@)UDD*U@
</pre></div>
<p>In the following example we reduce the word <span class="SimpleMath">\(w = d^5c^5\)</span> to <span class="SimpleMath">\(dc^2d^6\)</span> and check that only the latter is recognised by the automaton <code class="code">accT</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">free := FreeMonoidOfRewritingSystem( rwsT );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfMonoid( free );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">c := gens[1];; C := gens[2];; d := gens[3];; D := gens[4];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">w := d^5*c^5; </span>
f2^5*f1^5
<span class="GAPprompt">gap></span> <span class="GAPinput">sw := WordToString( w, alphT ); </span>
"dddddccccc"
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRecognizedByAutomaton( accT, sw ); </span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">rw := ReducedForm( rwsT, w );</span>
f2*f1^2*f2^6
<span class="GAPprompt">gap></span> <span class="GAPinput">srw := WordToString( rw, alphT ); </span>
"dccdddddd"
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRecognizedByAutomaton( accT, srw );</span>
true
</pre></div>
<p>In earlier versions of <strong class="pkg">Kan</strong>, from about 1.01 up to 1.21, the complementary automaton and language were returned in the example above. This error has now been rectified.</p>
<p>In even earlier versions of <strong class="pkg">Kan</strong> (in 0.95 for example) a shorter rational expression for the language was obtained from <strong class="pkg">Automata</strong>. In what follows, we check that the two expressions define the same language.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">alph := AlphabetOfRatExpAsList( langT );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1 := RatExpOnnLetters( alph, [ ], [1] );; ## y</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a2 := RatExpOnnLetters( alph, [ ], [2] );; ## Y</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a3 := RatExpOnnLetters( alph, [ ], [3] );; ## x</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a4 := RatExpOnnLetters( alph, [ ], [4] );; ## X</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s1 := RatExpOnnLetters( alph, "star", a1 );; ## y*</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s2 := RatExpOnnLetters( alph, "star", a2 );; ## Y*</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1a3 := RatExpOnnLetters( alph, "product", [ a1, a3 ] );; ## yx </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u1 := RatExpOnnLetters( alph, "union", [ a1a3, a3 ] );; ## yxUx</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a3a1 := RatExpOnnLetters( alph, "product", [ a3, a1 ] );; ## xy</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u2 := RatExpOnnLetters( alph, "union", [ a3a1, a1 ] );; ## xyUy</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u2a3 := RatExpOnnLetters( alph, "product", [ u2, a3 ] );; ## (xyUy)x</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">su2a3 := RatExpOnnLetters( alph, "star", u2a3 );; ## ((xyUy)x)*</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u2s1 := RatExpOnnLetters( alph, "product", [ u2, s1 ] );; ## (xyUy)y*</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a3s2 := RatExpOnnLetters( alph, "product", [ a3, s2 ] );; ## xY*</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u3 := RatExpOnnLetters( alph, "union", [u2s1,a3s2,s2] );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">prod := RatExpOnnLetters( alph, "product", [u1,su2a3,u3] );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1s1 := RatExpOnnLetters( alph, "product", [ a1, s1 ] );; ## yy*</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">r := RatExpOnnLetters( alph, "union", [ prod, a1s1, s2] );</span>
(yxUx)((xyUy)x)*((xyUy)y*UxY*UY*)Uyy*UY*
<span class="GAPprompt">gap></span> <span class="GAPinput">AreEqualLang( langT, r ); </span>
true
</pre></div>
<p>If we now take subgroups <span class="SimpleMath">\(H=\langle c \rangle\)</span> and <span class="SimpleMath">\(K = \langle d \rangle\)</span> we find that the double coset rewriting system has an infinite number of <span class="SimpleMath">\(H\)</span>-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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">prwsT := PartialDoubleCosetRewritingSystem( T, U, V, rwsT, 20 );;</span>
#I WARNING: reached supplied limit 20 on number of rules
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayRwsRules( prwsT );</span>
G-rules:
[ [ C, ccDD ], [ dD, id ], [ Dc, dcDD ], [ Dd, id ], [ ccc, dd ], [ ddc, cdd ]\
]
H-rules:
[ [ Hc, H ],
[ HD, Hd ],
[ Hdd, H ],
[ Hdcdd, Hdc ],
[ HdcD, Hdcd ],
[ Hdcdcdd, Hdcdc ],
[ Hdccdd, Hdcc ],
[ HdccD, Hdccd ],
[ HdcdcD, Hdcdcd ],
[ Hdcdcdcdd, Hdcdcdc ],
[ Hdcdccdd, Hdcdcc ],
[ Hdccdcdd, Hdccdc ],
[ HdccdcDD, Hdccdc ] ]
K-rules:
[ [ dK, K ],
[ DK, K ] ]
</pre></div>
<p>This list of partial rules is then used to produce a modified word acceptor function.</p>
<p>We then construct the double coset <span class="SimpleMath">\(Hd^5c^5K\)</span> and find its reduced form (compare this with the earlier example).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">paccT := WordAcceptorOfPartialDoubleCosetRws( T, prwsT );;</span>
< deterministic automaton on 6 letters with 6 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( paccT, "\n" );</span>
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 ]);;
<span class="GAPprompt">gap></span> <span class="GAPinput">plangT := FAtoRatExp( paccT );</span>
H(yx(yx)*x)*(yx(yx)*KUK)
<span class="GAPprompt">gap></span> <span class="GAPinput">wordsT := ["HK", "HxK", "HyK", "HYK", "HyxK", "HyxxK", "HyyH", "HyxYK"];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">validT := List( wordsT, w -> IsRecognizedByAutomaton( paccT, w ) );</span>
[ true, false, false, false, true, true, false, false ]
<span class="GAPprompt">gap></span> <span class="GAPinput">pfree := FreeMonoidOfRewritingSystem( prwsT );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pgens := GeneratorsOfMonoid( pfree );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := pgens[1];; K := pgens[2];; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">c := pgens[3];; C := pgens[4];; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">d := pgens[5];; D := pgens[6];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">palphT := Concatenation( "HK", alphT ); </span>
"HKcCdD"
<span class="GAPprompt">gap></span> <span class="GAPinput">pw := H*d^5*c^5*K;; DisplayAsString( pw, palphT );</span>
HdddddcccccK
<span class="GAPprompt">gap></span> <span class="GAPinput">rpw := ReducedForm( prwsT, pw );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">spw := WordToString( rpw, palphT ); </span>
"HdccK"
<span class="GAPprompt">gap></span> <span class="GAPinput">ok := IsRecognizedByAutomaton( paccT, spw ); </span>
true
</pre></div>
<p><a id="X7ED711187E2ECAC7" name="X7ED711187E2ECAC7"></a></p>
<h4>2.4 <span class="Heading">Example 4 -- 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">an style='color: green'>8227; 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">an style='color: green'>8227; 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">an style='color: green'>8227; KBMagFSAtoAutomataDFA</code>( <var class="Arg">fsa</var>, <var class="Arg">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">an style='color: green'>8227; WordAcceptorByKBMag</code>( <var class="Arg">grp</var>, <var class="Arg">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">an style='color: green'>8227; WordAcceptorByKBMagOfDoubleCosetRws</code>( <var class="Arg">grp</var>, <var class="Arg">dcrws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>When the group <span class="SimpleMath">\(G\)</span> has an infinite rewriting system, the double coset rewriting system will also be infinite. In this case we may use the function <code class="code">KBMagWordAcceptor</code> which calls <strong class="pkg">KBMag</strong> to compute a word acceptor for <span class="SimpleMath">\(G\)</span>, 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 <span class="SimpleMath">\(H\)</span>-rules, <span class="SimpleMath">\(K\)</span>-rules and <span class="SimpleMath">\(H\)</span>-<span class="SimpleMath">\(K\)</span>-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 <span class="SimpleMath">\(G4\)</span> with relators <span class="SimpleMath">\([a^3,b^3,(a*b)^3]\)</span>, the normal forms of whose elements are some of the strings with <span class="SimpleMath">\(a\)</span> or <span class="SimpleMath">\(a^{-1}\)</span> alternating with <span class="SimpleMath">\(b\)</span> or <span class="SimpleMath">\(b^{-1}\)</span>. The automatic structure computed by <strong class="pkg">KBMag</strong> has a word acceptor with 17 states.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F4 := FreeGroup("a","b");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rels4 := [ F4.1^3, F4.2^3, (F4.1*F4.2)^3 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G4 := F4/rels4;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alph4 := "AaBb";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">waG4 := WordAcceptorByKBMag( G4, alph4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( waG4, "\n");</span>
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 ]);;
<span class="GAPprompt">gap></span> <span class="GAPinput">langG4 := FAtoRatExp( waG4 );</span>
((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@
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRecognizedByAutomaton( waG4, "Aba" );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRecognizedByAutomaton( waG4, "AbaB" );</span>
false
</pre></div>
<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">an style='color: green'>8227; 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">an style='color: green'>8227; 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">an style='color: green'>8227; 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">an style='color: green'>8227; HKrules</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>We now take <span class="SimpleMath">\(H\)</span> to be generated by <span class="SimpleMath">\(ab\)</span> and <span class="SimpleMath">\(K\)</span> to be generated by <span class="SimpleMath">\(ba\)</span>. 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 <span class="SimpleMath">\(H\)</span>-rules, <span class="SimpleMath">\(K\)</span>-rules and <span class="SimpleMath">\(H\)</span>-<span class="SimpleMath">\(K\)</span>-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_mj.html#biBBrGhHeWe">[BGHW06]</a>) three infinite sets of rules and a limit for the automata.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">lim := 100;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">genG4 := GeneratorsOfGroup( G4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := genG4[1];; b := genG4[2];; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H4 := Subgroup( G4, [ a*b ] );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">K4 := Subgroup( G4, [ b*a ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rwsG4 := KnuthBendixRewritingSystem( G4, "shortlex", [2,1,4,3], alph4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dcrws4 := PartialDoubleCosetRewritingSystem( G4, H4, K4, rwsG4, limit );;</span>
#I using PartialDoubleCosetRewritingSystem with limit 100
#I 51 rules, and 1039 pairs
#I WARNING: reached supplied limit 100 on number of rules
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( Length( Rules( dcrws4 ) ), " rules found.\n" );</span>
101 rules found.
<span class="GAPprompt">gap></span> <span class="GAPinput">dcaut4 := WordAcceptorByKBMagOfDoubleCosetRws( G4, dcrws4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( "Double Coset Minimalized automaton:\n", dcaut4 );</span>
Double Coset Minimalized automaton:
Automaton("det",44,"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\
, 2, 2 ], [ 2, 2, 1, 2, 1, 2, 1, 1, 2, 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, 1, 2, 2, 1 ], [ 2, 2, 2,\
2, 3, 24, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 43, 2, 43, 2, 27, 2, 2, 2\
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 44, 3, 29, 2\
, 8, 2, 10, 2, 12, 2, 14, 2, 16, 2, 18, 2, 20, 2, 22, 2, 2, 2, 2, 26, 2, 29, 2\
, 31, 2, 33, 2, 35, 2, 37, 2, 39, 2, 41, 2, 2 ], [ 2, 2, 2, 2, 21, 2, 2, 28, 2\
, 9, 2, 11, 2, 13, 2, 15, 2, 17, 2, 19, 2, 42, 2, 3, 2, 28, 3, 2, 7, 2, 30, 2,\
32, 2, 34, 2, 36, 2, 38, 2, 40, 2, 2, 28 ], [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2\
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 25, 25, 2, 2, 2, 2, 2, 2, 2, 2, 2,\
2, 2, 2, 2, 2, 2, 23, 6 ] ],[ 4 ],[ 1 ]);;
<span class="GAPprompt">gap></span> <span class="GAPinput">dclang4 := FAtoRatExp( dcaut4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( "Double Coset language of acceptor:\n", dclang4, "\n" );</span>
Double Coset language of acceptor:
(HbAbAbAbAbAbAbAbUHAb)(Ab)*(A(Ba(Ba)*bKUK)UK)UHbAbA(bA(bA(bA(bA(bAKUK)UK)UK)UK\
)UK)UH(A(B(aB)*(abUA)KUK)UaKUb(a(Ba)*BA(bA(bA(bA(bA(bA(bA(bA(bA)*(bKUK)UK)UK)U\
K)UK)UK)UK)UK)UAK)UK)
<span class="GAPprompt">gap></span> <span class="GAPinput">ok := DCrules(dcrws4);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alph4e := dcrws4!.alphabet;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print("H-rules:\n"); DisplayAsString( Hrules(dcrws4), alph4e, true );</span>
H-rules:
[ HB, Ha ]
[ HaB, Hb ]
[ Hab, H ]
[ HbAB, HAba ]
[ HbAbAB, HAbAba ]
[ HbAbAbAB, HAbAbAba ]
[ HbAbAbAbAB, HAbAbAbAba ]
[ HbAbAbAbAbAB, HAbAbAbAbAba ]
[ HbAbAbAbAbAbAB, HAbAbAbAbAbAba ]
[ HbAbAbAbAbAbAbAB, HAbAbAbAbAbAbAba ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Print("K-rules:\n"); DisplayAsString( Krules(dcrws4), alph4e, true );;</span>
K-rules:
[ BK, aK ]
[ BaK, bK ]
[ baK, K ]
[ BAbK, abAK ]
[ BAbAbK, abAbAK ]
[ BAbAbAbK, abAbAbAK ]
[ BAbAbAbAbK, abAbAbAbAK ]
[ BAbAbAbAbAbK, abAbAbAbAbAK ]
[ BAbAbAbAbAbAbK, abAbAbAbAbAbAK ]
[ BAbAbAbAbAbAbAbK, abAbAbAbAbAbAbAK ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Print("HK-rules:\n"); DisplayAsString( HKrules(dcrws4), alph4e, true );;</span>
HK-rules:
[ HbK, HAK ]
[ HbAbK, HAbAK ]
[ HbAbAbK, HAbAbAK ]
[ HbAbAbAbK, HAbAbAbAK ]
[ HbAbAbAbAbK, HAbAbAbAbAK ]
[ HbAbAbAbAbAbK, HAbAbAbAbAbAK ]
[ HbAbAbAbAbAbAbK, HAbAbAbAbAbAbAK ]
</pre></div>
<p><a id="X84B36973833F3B54" name="X84B36973833F3B54"></a></p>
<h5>2.4-3 WordToString</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; WordToString</code>( <var class="Arg">word</var>, <var class="Arg">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">an style='color: green'>8227; IdentityDoubleCoset</code>( <var class="Arg">dcrws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The <code class="code">NextWord</code> operation (see <a href="chap2_mj.html#X7AF0265982B42E47"><span class="RefLink">2.1-2</span></a>) may be used to find normal forms of increasing length for double coset representatives. In the example below a limit of <span class="SimpleMath">\(50,000\)</span> (for the number of words tested) is specified since the <span class="SimpleMath">\(29\)</span> numbers of words tested can be shown to be:</p>
<p class="center">\[
\begin{array}{c}
[\ 1,\ 1,\ 6,\ 9,\ 12,\ 4,\ 91,\ 12,\ 153,\ 12,\ 192,\ 52,\ 1435,\ 192,\ 12,\ 2457,\ 192,\\
12,\ 3072,\ 820,\ 22939,\ 3072,\ 19,\ 12,\ 39321,\ 3072,\ 192,\ 12,\ 49152\ ]
\end{array}
\]</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">idc := IdentityDoubleCoset( dcrws4 );</span>
m1*m2
<span class="GAPprompt">gap></span> <span class="GAPinput">## List of the next 29 normal forms for double cosets: </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">L4 := NextWords( dcrws4, idc, 29, 50000 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayAsString( L4, alph4e, true );</span>
[ HAK, HaK, HAbK, HbAK, HABAK, HAbAK, HABabK, HAbAbK, HbAbAK, HbaBAK, HABaBAK,\
HAbAbAK, HABaBabK, HAbABabK, HAbAbAbK, HbAbAbAK, HbaBAbAK, HbaBaBAK, HABaBaBA\
K, HAbAbAbAK, HABaBaBabK, HAbABaBabK, HAbAbABabK, HAbAbAbAbK, HbAbAbAbAK, HbaB\
AbAbAK, HbaBaBAbAK, HbaBaBaBAK, HABaBaBaBAK ]
<span class="GAPprompt">gap></span> <span class="GAPinput">w := NextWord( dcrws4, L4[29] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( w, "\n" );</span>
m1*(m3*m6)^4*m3*m2
<span class="GAPprompt">gap></span> <span class="GAPinput">s := WordToString( w, alph4e );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( s, "\n" );</span>
HAbAbAbAbAK
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap1_mj.html">[Previous Chapter]</a> <a href="chap3_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.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>
¤ Dauer der Verarbeitung: 0.14 Sekunden
(vorverarbeitet am 2026-11-04)
¤
*© Formatika GbR, Deutschland
|
|