<p>The setup described in this chapter is intended for situations, in which lots of different methods are available to fulfill a certain task, but in which it is not possible in the beginning to decide, which one to use. Therefore this setup regulates, rather than just which method to choose, in which order the various methods are tried. The methods themselves return whether they were successful and, if not, whether it is sensible to try them again at a later stage.</p>
<p>The design is intentionally kept as simple as possible and at the same time as versatile as possible, thereby providing a useful framework for many situations as described above.</p>
<p>Note the differences to the <strong class="pkg">GAP</strong> method selection, which is designed with the idea in mind that it will be quite clear in most situations, which one is <q>the best</q> method for a given set of input data, and that we do not want to try different things. On the other hand, the <strong class="pkg">GAP</strong> method selection is quite complicated, which is to some extend necessary to make sure, that lots of different information about the objects in question can be used to really find the best method.</p>
<p>Our setup here in particular has to fulfill the requirement, that in the end, with lots of methods installed, one still has to be able to have an overview and to <q>prove</q>, that the whole system always does the right thing.</p>
<h4>4.1 <span class="Heading">What are methods?</span></h4>
<p>Recognition methods lie in the filter <code class="func">IsRecogMethod</code> (<a href="chap4.html#X80EC4782856AAD35"><span class="RefLink">4.1-1</span></a>) and can be created via the function <code class="func">RecogMethod</code> (<a href="chap4.html#X7E18720E87B4B2DE"><span class="RefLink">4.1-2</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsRecogMethod</code></td><td class="tdright">( category )</td></tr></table></div>
<p>The category of recognition methods, that is of the objects created via <code class="func">RecogMethod</code> (<a href="chap4.html#X7E18720E87B4B2DE"><span class="RefLink">4.1-2</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RecogMethod</code>( <var class="Arg">stamp</var>, <var class="Arg">comment</var>, <var class="Arg">func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Return a recognition method <code class="code">method</code> in the filter <code class="func">IsRecogMethod</code> (<a href="chap4.html#X80EC4782856AAD35"><span class="RefLink">4.1-1</span></a>), where <var class="Arg">stamp</var> is a string describing the method uniquely, <var class="Arg">comment</var> is a string explaining how the method works, and <var class="Arg">func</var> is the method itself. The components <var class="Arg">stamp</var> and <var class="Arg">comment</var> can be accessed via the attributes <code class="func">Stamp</code> (<a href="chap4.html#X7EF3EAEF78786349"><span class="RefLink">4.1-4</span></a>) and <code class="func">Comment</code> (<a href="chap4.html#X7A2F979E86F77A6F"><span class="RefLink">4.1-5</span></a>).</p>
<p>A recognition method returns one of the following four values:</p>
<dl>
<dt><strong class="Mark"><code class="keyw">Success</code></strong></dt>
<dd><p>means that the method was successful and no more methods have to be tried.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">NeverApplicable</code></strong></dt>
<dd><p>means that the method was not successful and that there is no point to call the method again in this situation whatsoever.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">TemporaryFailure</code></strong></dt>
<dd><p>means that the method temporarily failed, that it however could be sensible to call it again in this situation at a later stage. This value is typical for a Las Vegas algorithm using randomised methods, which has failed, but which may succeed when called again.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">NotEnoughInformation</code></strong></dt>
<dd><p>means that the method for some reason refused to do its work. However, it is possible that it will become applicable later such that it makes sense to call it again, for example when more information is available.</p>
</dd>
</dl>
<p>A recognition method <code class="code">method</code> should always be stored into the component <code class="code">Stamp(method)</code> of one of the following records: <code class="func">FindHomMethodsGeneric</code> (<a href="chap4.html#X78B948847D596167"><span class="RefLink">4.4-4</span></a>), <code class="func">FindHomMethodsPerm</code> (<a href="chap4.html#X7A94720080D344DA"><span class="RefLink">4.4-1</span></a>), <code class="func">FindHomMethodsMatrix</code> (<a href="chap4.html#X79B60CEF8292F142"><span class="RefLink">4.4-2</span></a>), and <code class="func">FindHomMethodsProjective</code> (<a href="chap4.html#X7D796A2179E9026A"><span class="RefLink">4.4-3</span></a>). To this end one can use the function <code class="func">BindRecogMethod</code> (<a href="chap4.html#X87AA2A587E4E00C2"><span class="RefLink">4.1-3</span></a>).</p>
<p>A <em>method database</em> is a list of records, where each record has the following components:</p>
<dl>
<dt><strong class="Mark"><code class="code">method</code></strong></dt>
<dd><p>A recognition method created with <code class="func">RecogMethod</code> (<a href="chap4.html#X7E18720E87B4B2DE"><span class="RefLink">4.1-2</span></a>).</p>
</dd>
<dt><strong class="Mark"><code class="code">rank</code></strong></dt>
<dd><p>An integer used to sort the various methods. Higher numbers mean that the method is tried earlier. See <code class="func">CallMethods</code> (<a href="chap4.html#X7BC2692183B6C4E6"><spanclass="RefLink">4.3-1</span></a>) for information on how the methods are called.</p>
</dd>
</dl>
<p>The databases are always sorted such that the ranks are decreasing. Use <code class="func">AddMethod</code> (<a href="chap4.html#X845DB71C806CADDC"><span class="RefLink">4.2-1</span></a>) to add a method to a database according to its rank.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddMethod</code>( <var class="Arg">methodDb</var>, <var class="Arg">method</var>, <var class="Arg">rank</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Add the recognition method <var class="Arg">method</var> with rank <var class="Arg">rank</var> to the method database <var class="Arg">methodDb</var>. Return nothing. <var class="Arg">method</var> is inserted into <var class="Arg">methodDb</var> such that the ranks of its entries are in decreasing order. For information on recognition methods and method databases see <code class="func">RecogMethod</code> (<a href="chap4.html#X7E18720E87B4B2DE"><span class="RefLink">4.1-2</span></a>) and Section <a href="chap4.html#X854385507D03A016"><span class="RefLink">4.2</span></a>, respectively.</p>
<p>The following databases contain the methods for finding homomorphisms for permutation, matrix, and projective groups.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CallMethods</code>( <var class="Arg">db</var>, <var class="Arg">limit</var>[, <var class="Arg">furtherargs</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record <code class="code">ms</code> describing this method selection procedure.</p>
<p>The argument <var class="Arg">db</var> must be a method database in the sense of Section <a href="chap4.html#X854385507D03A016"><span class="RefLink">4.2</span></a>. <var class="Arg">limit</var> must be a non-negative integer. <var class="Arg">furtherargs</var> stands for an arbitrary number of additional arguments, which are handed down to the called methods. Of course they must fulfill the conventions defined for the methods in the database <var class="Arg">db</var>.</p>
<p>The function first creates a <q>method selection</q> record keeping track of the things that happened during the method trying procedure, which is also used during this procedure. Then it calls methods with the algorithm described below and in the end returns the method selection record in its final state.</p>
<p>The method selection record has the following components:</p>
<dl>
<dt><strong class="Mark"><code class="code">inapplicableMethods</code></strong></dt>
<dd><p>a record, in which for every method that returned <code class="keyw">NeverApplicable</code> the value 1 is bound to the component with name the stamp of the method.</p>
</dd>
<dt><strong class="Mark"><code class="code">failedMethods</code></strong></dt>
<dd><p>a record, in which for every time a method returned <code class="keyw">TemporaryFailure</code> the value bound to the component with name the stamp of the method is increased by 1 (not being bound means zero).</p>
</dd>
<dt><strong class="Mark"><code class="code">successMethod</code></strong></dt>
<dd><p>the stamp of the method that succeeded, if one did. This component is only bound after successful completion.</p>
</dd>
<dt><strong class="Mark"><code class="code">result</code></strong></dt>
<dd><p>a boolean value which is either <code class="keyw">Success</code> or <code class="keyw">TemporaryFailure</code> depending on whether a successful method was found or the procedure gave up respectively. This component is only bound after completion of the method selection procedure.</p>
</dd>
<dt><strong class="Mark"><code class="code">tolerance</code></strong></dt>
<dd><p>the number of times all methods failed until one succeeded. See below.</p>
</dd>
</dl>
<p>The algorithm used by <code class="func">CallMethods</code> is extremely simple: It sets a counter <code class="code">tolerance</code> to zero. The main loop starts at the beginning of the method database and runs through the methods in turn. Provided a method did not yet return <code class="keyw">NeverApplicable</code> and did not yet return <code class="keyw">TemporaryFailure</code> more than <code class="code">tolerance</code> times before, it is tried. According to the value returned by the method, the following happens:</p>
<dl>
<dt><strong class="Mark"><code class="keyw">NeverApplicable</code></strong></dt>
<dd><p>this is marked in the method selection record and the main loop starts again at the beginning of the method database.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">TemporaryFailure</code></strong></dt>
<dd><p>this is counted in the method selection record and the main loop starts again at the beginning of the method database.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">NotEnoughInformation</code></strong></dt>
<dd><p>the main loop goes to the next method in the method database.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">Success</code></strong></dt>
<dd><p>this is marked in the method selection record and the procedure returns successfully.</p>
</dd>
</dl>
<p>If the main loop reaches the end of the method database without calling a method (because all methods have already failed or are not applicable), then the counter <code class="code">tolerance</code> is increased by one and everything starts all over again. This is repeated until <code class="code">tolerance</code> is greater than the <code class="code">limit</code> which is the second argument of <code class="func">CallMethods</code>. The last value of the <code class="code">tolerance</code> counter is returned in the component <code class="code">tolerance</code> of the method selection record.</p>
<p>Note that the main loop starts again at the beginning of the method database after each failed method call! However, this does not lead to an infinite loop, because the failure is recorded in the method selection record such that the method is skipped until the <code class="code">tolerance</code> increases. Once the <code class="code">tolerance</code> has been increased methods having returned <code class="keyw">TemporaryFailure</code> will be called again. The idea behind this approach is that even failed methods can collect additional information about the arguments changing them accordingly. This might give methods that come earlier and were not applicable up to now the opportunity to begin working. Therefore one can install very good methods that depend on some already known knowledge which will only be acquired during the method selection procedure by other methods, with a high rank.</p>
<h4>4.4 <span class="Heading">Global records storing functions</span></h4>
<p>The following global records store the methods for finding homomorphisms for group recognition. We collect them in these records such that we do not use up too many global variable names.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FindHomMethodsGeneric</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>In this global record the functions that are methods for finding homomorphisms for generic group recognition are stored. We collect them all in this record such that we do not use up too many global variable names.</p>
<p>The following global records hold the functions for writing group elements as straight line programs (SLPs) in terms of the generators after successful group recognition. We collect them in these records such that we do not use up too many global variable names.</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.
