Quelle  chap3_mj.html   Sprache: 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 3: Development History</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="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="chapBib_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X810C43BC7F63C4B4" name="X810C43BC7F63C4B4"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X810C43BC7F63C4B4">3 <span class="Heading">Development History</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X8192EA4C7B7CC5CD">3.1 <span class="Heading">Versions of the package</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.html#X83D1530487593182">3.2 <span class="Heading">What needs doing next?</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X852CC057809CE3EE">3.2-1 DoubleCosetsAutomaton</a></span>
</div></div>
</div>

<h3>3 <span class="Heading">Development History</span></h3>

<p><a id="X8192EA4C7B7CC5CD" name="X8192EA4C7B7CC5CD"></a></p>

<h4>3.1 <span class="Heading">Versions of the package</span></h4>

<p>The first version of the package, written for <strong class="pkg">GAP</strong> 3, formed part of Anne Heyworth's thesis <a href="chapBib_mj.html#biBanne-thesis">[Hey99]</a> in 1999, but was not made generally available.</p>

<p>Version 0.91 was prepared to run under <strong class="pkg">GAP</strong> 4.4.6, in July 2005.</p>

<p>Version 0.94 differed in two significant ways.</p>


<ul>
<li><p>The manual was produced using the <strong class="pkg">GAPDoc</strong> package.</p>

</li>
<li><p>The test file <code class="file">kan/tst/kan_manual.tst</code> set the <code class="code">AssertionLevel</code> to <code class="code">0</code> to avoid recursion in the <strong class="pkg">Automata</strong> package.</p>

</li>
</ul>
<p>Version 1.11, of December 2014 was required when the <strong class="pkg">Kan</strong> website moved yet again. At the same time a bitbucket repository for the package was started.</p>

<p><strong class="pkg">Kan</strong> became an accepted <strong class="pkg">GAP</strong> package in May 2015.</p>

<p>Version 1.28, of May 2017, saw a great many changes to the examples, with the various rewriting systems used to perform reduction of words to reduced form.</p>

<p>Only minor changes have been made in recent years.</p>

<p><a id="X83D1530487593182" name="X83D1530487593182"></a></p>

<h4>3.2 <span class="Heading">What needs doing next?</span></h4>

<p>There are too many items to list here, but some of the most important are as follows.</p>


<ul>
<li><p>Implement iterators and enumerators for double cosets.</p>

</li>
<li><p>At present the methods for <code class="code">DoubleCosetsNC</code> and <code class="code">RightCosetsNC</code> in this package return automata, rather than lists of cosets or coset enumerators. This needs to be fixed.</p>

</li>
<li><p>Provide methods for operations such as <code class="code">DoubleCosetRepsAndSizes</code>.</p>

</li>
<li><p>Convert the rest of the original <strong class="pkg">GAP</strong> 3 version of <strong class="pkg">Kan</strong> to <strong class="pkg">GAP</strong> 4.</p>

</li>
</ul>
<p><a id="X852CC057809CE3EE" name="X852CC057809CE3EE"></a></p>

<h5>3.2-1 DoubleCosetsAutomaton</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DoubleCosetsAutomaton</code>( <var class="Arg">G</var>, <var class="Arg">U</var>, <var class="Arg">V</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; RightCosetsAutomaton</code>( <var class="Arg">G</var>, <var class="Arg">V</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Alternative methods for <code class="code">DoubleCosetsNC(G,U,V)</code> and <code class="code">RightCosetsNC(G,V)</code> <em>should be</em> provided in the cases where the group <code class="code">G</code> has a rewriting system or is known to be infinite. At present the functions <code class="code">RightCosetsAutomaton</code> and <code class="code">DoubleCosetsAutomaton</code> return minimized automata, and <code class="code">Iterators</code> for these are not yet available.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeGroup(2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rels := [ F.2^2, (F.1*F.2)^2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G5 := F/rels;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">genG5 := GeneratorsOfGroup( G5 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := genG5[1];  b := genG5[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">U := Subgroup( G5, [a^2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">V := Subgroup( G5, [b] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">L := [2,1,4,3];; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rws5 := ReducedConfluentRewritingSystem( G5, L, "shortlex", 0, "aAbB" );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dc5 := DoubleCosetsAutomaton( G5, U, V );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( dc5 );</span>
Automaton("det",5,"HKAaBb",[ [ 2, 2, 2, 5, 2 ], [ 2, 2, 1, 2, 1 ], [ 2, 2, 2, \
2, 3 ], [ 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2 ] ],[ 4 ],[ 1 ])\
;;
<span class="GAPprompt">gap></span> <span class="GAPinput">rc5 := RightCosetsAutomaton( G5, V );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print( rc5 );</span>
Automaton("det",6,"HKAaBb",[ [ 2, 2, 2, 6, 2, 2 ], [ 2, 2, 1, 2, 1, 1 ], [ 2, \
2, 3, 2, 2, 3 ], [ 2, 2, 2, 2, 5, 5 ], [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, \
2 ] ],[ 4 ],[ 1 ]);;

</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="chapBib_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>