|
|
|
|
Quelle chap3_mj.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/kbmag/doc/chap3_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 (kbmag) - Chapter 3: The Knuth-Bendix program on cosets</ 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= "chap3" 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="chap4_mj.html">4</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="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X7828AE2881251C6A" name="X7828AE2881251C6A"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X7828AE2881251C6A">3 <span class="Heading">The Knuth-Bendix program on cosets</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X8128360785343F6A">3.1 <span class="Heading">Subgroups, cosets and subgroup presentations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X834DC6477EE1482B">3.1-1 SubgroupOfKBMAGRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7CDC9FDA855596C4">3.1-2 ResetRewritingSystemOnCosets</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X7828AE2881251C6A">3.2 <span class="Heading">The Knuth-Bendix program on cosets</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X822268027EF50066">3.2-1 KnuthBendixOnCosets</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X857B2B40860C7F33">3.2-2 RewritingSystemOfSubgroupOfKBMAGRewritingSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7832C01283EA446E">3.2-3 IsConfluentOnCosets</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X83CE52E17BB34E5F">3.3 <span class="Heading">The automatic cosets program</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7A2595DB84579665">3.3-1 AutomaticStructureOnCosets</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7823571D7CD7F81D">3.3-2 PresentationOfSubgroupOfKBMAGRewritingSystem</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X83A702237F6BA69A">3.4 <span class="Heading">Word reduction on cosets</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7C27E5EE8462A720">3.4-1 IsReducedCosetRepresentative</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X794181377A59DAC1">3.4-2 ReducedCosetRepresentative</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X827BF1CF85337C8B">3.5 <span class="Heading">Counting and enumerating irreducible words for cosets</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X83A0356F839C696F">3.5-1 Index</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X84596FE47AFBCC91">3.5-2 EnumerateReducedCosetRepresentatives</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7D0F6F3781DF343D">3.5-3 GrowthFunctionOfCosetRepresentatives</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X79BA526D818D1DE7">3.6 <span class="Heading">Examples of the use of Rewriting System on Cosets</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X8388E29680F31ABD">3.6-1 <span class="Heading">Example 1</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3_mj.html#X7A18778D836BC971">3.6-2 <span class="Heading">Example 2</span></a>
</span>
</div></div>
</div>
<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>
<p><a id="X8128360785343F6A" name="X8128360785343F6A"></a></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>
<p><a id="X834DC6477EE1482B" name="X834DC6477EE1482B"></a></p>
<h5>3.1-1 SubgroupOfKBMAGRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SubgroupOfKBMAGRewritingSystem</code>( <var class="Arg">rws</var>, <var class="Arg">H</var> )</td><td class="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>
<p><a id="X7CDC9FDA855596C4" name="X7CDC9FDA855596C4"></a></p>
<h5>3.1-2 ResetRewritingSystemOnCosets</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X7828AE2881251C6A" name="X7828AE2881251C6A"></a></p>
<h4>3.2 <span class="Heading">The Knuth-Bendix program on cosets</span></h4>
<p><a id="X822268027EF50066" name="X822268027EF50066"></a></p>
<h5>3.2-1 KnuthBendixOnCosets</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p><a id="X857B2B40860C7F33" name="X857B2B40860C7F33"></a></p>
<h5>3.2-2 RewritingSystemOfSubgroupOfKBMAGRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X7832C01283EA446E" name="X7832C01283EA446E"></a></p>
<h5>3.2-3 IsConfluentOnCosets</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X83CE52E17BB34E5F" name="X83CE52E17BB34E5F"></a></p>
<h4>3.3 <span class="Heading">The automatic cosets program</span></h4>
<p><a id="X7A2595DB84579665" name="X7A2595DB84579665"></a></p>
<h5>3.3-1 AutomaticStructureOnCosets</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AutomaticStructureOnCosets</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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X7823571D7CD7F81D" name="X7823571D7CD7F81D"></a></p>
<h5>3.3-2 PresentationOfSubgroupOfKBMAGRewritingSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X83A702237F6BA69A" name="X83A702237F6BA69A"></a></p>
<h4>3.4 <span class="Heading">Word reduction on cosets</span></h4>
<p><a id="X7C27E5EE8462A720" name="X7C27E5EE8462A720"></a></p>
<h5>3.4-1 IsReducedCosetRepresentative</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X794181377A59DAC1" name="X794181377A59DAC1"></a></p>
<h5>3.4-2 ReducedCosetRepresentative</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p><a id="X827BF1CF85337C8B" name="X827BF1CF85337C8B"></a></p>
<h4>3.5 <span class="Heading">Counting and enumerating irreducible words for cosets</span></h4>
<p><a id="X83A0356F839C696F" name="X83A0356F839C696F"></a></p>
<h5>3.5-1 Index</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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 <code class="func">Index</code> will return the correct index of <span class="SimpleMath">\(H\)</span> in <span class="SimpleMath">\(G\)</span>.</p>
<p><a id="X84596FE47AFBCC91" name="X84596FE47AFBCC91"></a></p>
<h5>3.5-2 EnumerateReducedCosetRepresentatives</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p><a id="X7D0F6F3781DF343D" name="X7D0F6F3781DF343D"></a></p>
<h5>3.5-3 GrowthFunctionOfCosetRepresentatives</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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 <span class="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 <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>
<p><a id="X79BA526D818D1DE7" name="X79BA526D818D1DE7"></a></p>
<h4>3.6 <span class="Heading">Examples of the use of Rewriting System on Cosets</span></h4>
<p>Here are two examples to illustrate the operations described above.</p>
<p><a id="X8388E29680F31ABD" name="X8388E29680F31ABD"></a></p>
<h5>3.6-1 <span class="Heading">Example 1</span></h5>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeGroup( "a", "b", "c" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := F.1;; b := F.2;; c := F.3;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := F/[b^3,c^3,(b*c)^4,(b*c^-1)^5,a^-1*b^-1*c*b*c*b^-1*c*b*c^-1];</span>
<fp group on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := KBMAGRewritingSystem( G );</span>
rec(
isRWS := true,
silent := true,
generatorOrder := [_g1,_g2,_g3,_g4,_g5,_g6],
inverses := [_g2,_g1,_g4,_g3,_g6,_g5],
ordering := "shortlex",
equations := [
[_g3^2,_g4],
[_g5^2,_g6],
[_g3*_g5*_g3*_g5,_g6*_g4*_g6*_g4],
[_g3*_g6*_g3*_g6*_g3,_g5*_g4*_g5*_g4*_g5],
[_g2*_g4*_g5*_g3*_g5,_g5*_g4*_g6*_g3]
]
)
<span class="GAPprompt">gap></span> <span class="GAPinput">S := SubgroupOfKBMAGRewritingSystem( R, [ a^3, c*a^2 ] ); </span>
rec(
isRWS := true,
silent := true,
generatorOrder := [_x1,_X1,_x2,_X2],
inverses := [_X1,_x1,_X2,_x2],
ordering := "shortlex",
equations := [
]
)
<span class="GAPprompt">gap></span> <span class="GAPinput">KnuthBendixOnCosetsWithSubgroupRewritingSystem( R, S );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Index( R, S );</span>
18
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReducedCosetRepresentative( R, S, b*a*b*a );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedFormOfCosetRepresentative( R, S, b*a*b*a );</span>
b^-1*a^-1
<span class="GAPprompt">gap></span> <span class="GAPinput">EnumerateReducedCosetRepresentatives( R, S, 0, 4 );</span>
[ <identity ...>, a, a*b, a*b*c, a*b^-1, a^-1, a^-1*b, a^-1*b*c, a^-1*b^-1,
b, b*c, b*c*a, b*c*a^-1, b*c^-1, b^-1, b^-1*a, b^-1*a^-1, b^-1*a^-1*b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SS := RewritingSystemOfSubgroupOfKBMAGRewritingSystem( R, S );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( SS );</span>
60
</pre></div>
<p><a id="X7A18778D836BC971" name="X7A18778D836BC971"></a></p>
<h5>3.6-2 <span class="Heading">Example 2</span></h5>
<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
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_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="chap4_mj.html">4</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
¤
*© Formatika GbR, Deutschland
|
|
2026-11-04
|
|
|
|
|
Neuigkeiten |
| Aktuelles |
| Motto des Tages |
|
Open Source Software |
|
|
|
Jenseits des Üblichen ....
|
|
Besucherstatistik |
|
|
| Statistik |
| #Sources=1104857 |
| #Domains=439723 |
|
|
