<h3>3 <span class="Heading">The Knuth-Bendix program on cosets</span></h3>
<p>It is possible to use the Knuth-Bendix and Automatic Structure program on cosets of a specified subgroup <span class="SimpleMath">\(H\)</span> of <span class="SimpleMath">\(G\)</span>. Most of the functions in the preceding chapter have analogues for cosets rather than for elements. It is also possible sometimes to compute a complete rewriting system or a subgroup presentation of <span class="SimpleMath">\(H\)</span>.</p>
<h4>3.1 <span class="Heading">Subgroups, cosets and subgroup presentations</span></h4>
<p>The functions in this section are currently only applicable when the rewriting system is defined from a group <span class="SimpleMath">\(G\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubgroupOfKBMAGRewritingSystem</code>( <var class="Arg">rws</var>, <var class="Arg">H</var> )</td><tdclass="tdright">( function )</td></tr></table></div>
<p>The subgroup <span class="SimpleMath">\(H\)</span> of the group <span class="SimpleMath">\(G\)</span> (= <code class="code">SemigroupOfRewritingSystem(rws)</code> ) from which <span class="SimpleMath">\({\sf rws}\)</span> is defined can be specified either as a subgroup of <span class="SimpleMath">\(G\)</span>; or as a list of elements of <span class="SimpleMath">\(G\)</span> that generate <span class="SimpleMath">\(H\)</span>; or as a subgroup of <span class="SimpleMath">\(F\)</span> = <code class="code">FreeStructureOfRewritingSystem(rws)</code> that maps onto <span class="SimpleMath">\(H\)</span>; or as a list of elements of <span class="SimpleMath">\(F\)</span> that generate a subgroup mapping onto <span class="SimpleMath">\(H\)</span>.</p>
<p><code class="func">SubgroupOfKBMAGRewritingSystem</code> returns a rewriting system <code class="code">subrws</code> for <span class="SimpleMath">\(H\)</span>, but <code class="code">subrws</code> has no rules, and is only intended to be used as a parameter in the functions that follow.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ResetRewritingSystemOnCosets</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function resets <code class="code">subrws</code> back to its form as it was before the application of <code class="func">KnuthBendixOnCosets</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>) or <code class="func">AutomaticStructureOnCosets</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>). The normal form and reduction algorithms on cosets will be unavailable after this call.</p>
<p>Any optional control parameters set for <span class="SimpleMath">\({\sf rws}\)</span> will automatically be used when applying the Knuth-Bendix and Automatic Structure functions on cosets, that are now to be described.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KnuthBendixOnCosets</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</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">‣ KnuthBendixOnCosetsWithSubgroupRewritingSystem</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="code">KnuthBendixOnCosets</code> runs the external Knuth-Bendix program on the rewriting system <span class="SimpleMath">\({\sf rws}\)</span> with respect to the cosets of the subgroup corresponding to <code class="code">subrws</code>. It returns <code class="code">true</code> if it finds a confluent rewriting system on coset representatives, and otherwise <code class="code">false</code>.</p>
<p>If <code class="func">KnuthBendixOnCosets</code> halts without finding a confluent system, but still manages to output the current system and update <span class="SimpleMath">\({\sf rws}\)</span>, then it is possible to use the resulting rewriting system to reduce coset representatives, and count and enumerate the irreducible coset representatives; it cannot be guaranteed that the irreducible coset representatives are all in normal form, however.</p>
<p><code class="func">KnuthBendixOnCosetsWithSubgroupRewritingSystem</code> does the same and, in addition, tries to compute a confluent rewriting system for the subgroup <span class="SimpleMath">\(H\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RewritingSystemOfSubgroupOfKBMAGRewritingSystem</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Use this after a successful call of <code class="func">KnuthBendixOnCosetsWithSubgroupRewritingSystem</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>). It returns a confluent rewriting system for <span class="SimpleMath">\(H\)</span> on a generating set corresponding to the generators of <span class="SimpleMath">\(H\)</span> that were used to define <code class="code">subrws</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsConfluentOnCosets</code>( <var class="Arg">rws</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation returns <code class="code">true</code> if <span class="SimpleMath">\({\sf rws}\)</span> is a rewriting system on cosets that is known to be confluent.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomaticStructureOnCosets</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var>[, <varclass="Arg">large</var>, <var class="Arg">filestore</var>, <var class="Arg">diff1</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">‣ AutomaticStructureOnCosetsWithSubgroupPresentation</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var>[, <var class="Arg">large</var>, <var class="Arg">filestore</var>, <var class="Arg">diff1</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">AutomaticStructureOnCosets</code> runs the external automatic cosets program on the rewriting system <span class="SimpleMath">\({\sf rws}\)</span> with respect to the cosets of the subgroup <span class="SimpleMath">\(H\)</span> from which <code class="code">subrws</code> was defined. It returns <code class="code">true</code> if successful and <code class="code">false</code> otherwise.</p>
<p>The optional parameters to <code class="func">AutomaticStructureOnCosets</code> are the same as for <code class="func">AutomaticStructure</code> (<a href="chap2_mj.html#X828FA0177E4C5733"><span class="RefLink">2.6-1</span></a>).</p>
<p>The ordering of <span class="SimpleMath">\({\sf rws}\)</span> must be <strong class="button">shortlex</strong>.</p>
<p><code class="func">AutomaticStructureOnCosetsWithSubgroupPresentation</code> does the same and, in addition, tries to compute a presentation of the subgroup <span class="SimpleMath">\(H\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PresentationOfSubgroupOfKBMAGRewritingSystem</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Use this after a successful call of <code class="func">AutomaticStructureOnCosetsWithSubgroupPresentation</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>). It returns a presentation for <span class="SimpleMath">\(H\)</span>, but this is not on the generators used to define <span class="SimpleMath">\(H\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsReducedCosetRepresentative</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var>, <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation tests whether the word <span class="SimpleMath">\(w\)</span> in the generators of the freestructure <code class="code">FreeStructure(rws)</code> of the rewriting system system <span class="SimpleMath">\({\sf rws}\)</span> is reduced or not as a coset representative of the subgroup <span class="SimpleMath">\(H\)</span> of <span class="SimpleMath">\(G\)</span>. It returns <code class="code">true</code> or <code class="code">false</code>.</p>
<p><code class="func">IsReducedCosetRepresentative</code> can only be used after <code class="func">KnuthBendixOnCosets</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>) or <code class="func">AutomaticStructureOnCosets</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>) has been run successfully on <span class="SimpleMath">\({\sf rws}\)</span> and <code class="code">subrws</code>. In the former case, if <code class="code">KnuthBendixOnCosets</code> halted without a confluent set of rules, then irreducible words are not necessarily in normal form (but reducible words are definitely not in normal form). If <code class="code">KnuthBendixOnCosets</code> completes with a confluent rewriting system or <code class="code">AutomaticStructureOnCosets</code> completes successfully, then it is guaranteed that all irreducible words are in normal form.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReducedCosetRepresentative</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var>, <var class="Arg">w</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">‣ ReducedFormOfCosetRepresentative</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var>, <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="code">ReducedCosetRepresentative</code> reduces the word <span class="SimpleMath">\(w\)</span> in the generators of the free structure <code class="code">FreeStructure(rws)</code> of the rewriting system <span class="SimpleMath">\({\sf rws}\)</span> as a coset representative of the subgroup <span class="SimpleMath">\(H\)</span> from which <code class="code">subrws</code> was defined, and returns the result.</p>
<p><code class="func">ReducedFormOfCosetRepresentative</code> can only be used after <code class="func">KnuthBendixOnCosets</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>) or <code class="func">AutomaticStructureOnCosets</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>) has been run successfully on <span class="SimpleMath">\({\sf rws}\)</span> and <code class="code">subrws</code>. In the former case, if <code class="code">KnuthBendixOnCosets</code> halted without a confluent set of rules, then the irreducible word returned is not necessarily in normal form. If <code class="code">KnuthBendixOnCosets</code> completes with a confluent rewriting system or <code class="code">AutomaticStructureOnCosets</code> completes successfully, then it is guaranteed that all irreducible words are in normal form.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Index</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns the number of irreducible words for coset representatives of the subgroup <span class="SimpleMath">\(H\)</span> of <span class="SimpleMath">\(G\)</span> corresponding to <code class="code">subrws</code>.</p>
<p><code class="func">Index</code> can only be used after <code class="func">KnuthBendixOnCosets</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>) or <code class="func">AutomaticStructureOnCosets</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>) has been run successfully on <span class="SimpleMath">\({\sf rws}\)</span> and <code class="code">subrws</code>. In the former case, if <code class="code">KnuthBendixOnCosets</code> halted without a confluent set of rules, then the number of irreducible words may be greater than the number of words in normal form (which is equal to the index of <span class="SimpleMath">\(H\)</span> in <span class="SimpleMath">\(G\)</span>). If <code class="code">KnuthBendixOnCosets</code> completes with a confluent rewriting system or <code class="code">AutomaticStructureOnCosets</code> completes successfully, then it is guaranteed that <codeclass="func">Index</code> will return the correct index of <span class="SimpleMath">\(H\)</span> in <span class="SimpleMath">\(G\)</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnumerateReducedCosetRepresentatives</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var>, <var class="Arg">min</var>, <var class="Arg">max</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Enumerate all irreducible words for coset representatives of <span class="SimpleMath">\(H\)</span> in <span class="SimpleMath">\(G\)</span>, that have lengths between <code class="code">min</code> and <code class="code">max</code> (inclusive), which should be non-negative integers. The result is returned as a list of words. The enumeration is by depth-first search of a finite state automaton, and so the words in the list returned are ordered lexicographically (not by <strong class="button">shortlex</strong>). <code class="func">EnumerateReducedCosetRepresentatives</code> can only be used after <code class="func">KnuthBendixOnCosets</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>) or <code class="func">AutomaticStructureOnCosets</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>) has been run successfully on <span class="SimpleMath">\({\sf rws}\)</span> and <code class="code">subrws</code>. In the former case, if <code class="code">KnuthBendixOnCosets</code> halted without a confluent set of rules, then not all irreducible words in the list returned will necessarily be in normal form. If <code class="code">KnuthBendixOnCosets</code> completes with a confluent rewriting system or <code class="code">AutomaticStructureOnCosets</code> completes successfully, then it is guaranteed that all words in the list will be in normal form.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrowthFunctionOfCosetRepresentatives</code>( <var class="Arg">rws</var>, <var class="Arg">subrws</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the growth function of the set of irreducible words for coset representatives of <spanclass="SimpleMath">\(H\)</span> in <span class="SimpleMath">\(G\)</span>, where <code class="code">subrws</code> and <span class="SimpleMath">\({\sf rws}\)</span> are the rewriting systems for <span class="SimpleMath">\(H\)</span> and <span class="SimpleMath">\(G\)</span>. This is a rational function, of which the coefficient of <span class="SimpleMath">\(x^n\)</span> in its Taylor expansion is equal to the number of coset representatives words of length <span class="SimpleMath">\(n\)</span>.</p>
<p>If the coefficients in this rational function are larger than about <span class="SimpleMath">\(16000\)</span> then strange error messages will appear and <code class="code">fail</code> will be returned.</p>
<p><code class="func">GrowthFunctionOfCosetRepresentatives</code> can only be used after <codeclass="func">KnuthBendixOnCosets</code> (<a href="chap3_mj.html#X822268027EF50066"><span class="RefLink">3.2-1</span></a>) or <code class="func">AutomaticStructureOnCosets</code> (<a href="chap3_mj.html#X7A2595DB84579665"><span class="RefLink">3.3-1</span></a>) has been run successfully on <span class="SimpleMath">\({\sf rws}\)</span> and <code class="code">subrws</code>. In the former case, if <code class="code">KnuthBendixOnCosets</code> halted without a confluent set of rules, then not all irreducible words in the list returned will necessarily be in normal form. If <code class="code">KnuthBendixOnCosets</code> completes with a confluent rewriting system or <code class="code">AutomaticStructureOnCosets</code> completes successfully, then it is guaranteed that all words in the list will be in normal form.</p>
<p>We find a free subgroup of the Fibonacci group <span class="SimpleMath">\(F(2,8)\)</span>. This example may take about <span class="SimpleMath">\(20\)</span> minutes to run on a typical WorkStation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeGroup( 8 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := F.1; b := F.2; c := F.3; d := F.4; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">e := F.5; f := F.6; g := F.7; h := F.8;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := F/[a*b*c^-1, b*c*d^-1, c*d*e^-1, d*e*f^-1,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> e*f*g^-1, f*g*h^-1, g*h*a^-1, h*a*b^-1];</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := KBMAGRewritingSystem( G );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := SubgroupOfKBMAGRewritingSystem( R, [a,e] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AutomaticStructureOnCosetsWithSubgroupPresentation( R, S );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := PresentationOfSubgroupOfKBMAGRewritingSystem( R, S );</span>
<fp group on the generators [ f1, f3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelatorsOfFpGroup( P );</span>
[ ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Index( R, S ); </span>
infinity
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.
