<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>
<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><tdclass="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="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="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="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="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>
<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>
<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>
<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>
<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="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="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="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>
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.
