Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/kan/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 23.0.2024 mit Größe 44 kB image not shown  

Quelle  chap2_mj.html   Sprache: HTML

 
 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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 <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">‣ 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">‣ 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">‣ 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</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">‣ 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">‣ 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">‣ 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 <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">‣ 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">‣ 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>

100%


¤ Dauer der Verarbeitung: 0.24 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.