<p>This chapter describes the methods for backtrack search in the <strong class="pkg">genss</strong> package. Note that the code in this area is not yet very stable and is almost certainly going to change in subsequent versions of this package. This might also concern the interfaces and calling conventions.</p>
<p>This operation computes the setwise stabiliser of the set <var class="Arg">M</var>. So <var class="Arg">G</var> must be a group acting on some set <span class="SimpleMath">Ω</span>, this action is given by the action function <var class="Arg">op</var>. The set <var class="Arg">M</var> must consist of elements <span class="SimpleMath">Ω</span>. The result is a record with the components <code class="code">setstab</code> containing the setwise stabiliser and <code class="code">S</code> containing a stabiliser chain for it.</p>
<p>This operation uses backtrack search in a specially crafted stabiliser chain for <var class="Arg">G</var> doing not much intelligent pruning of the search tree, so expect possible long delays!</p>
<p>This operation computes the setwise stabiliser of the set <var class="Arg">M</var>. So <var class="Arg">G</var> must be a group acting on some set <span class="SimpleMath">Ω</span>, this action is given by the action function <var class="Arg">op</var>. The set <var class="Arg">M</var> must consist of elements <span class="SimpleMath">Ω</span>. The result is a record with the components <code class="code">setstab</code> containing the setwise stabiliser and <code class="code">S</code> containing a stabiliser chain for it.</p>
<p>This operation uses backtrack search in a specially crafted stabiliser chain for <var class="Arg">G</var>. It does some ideas coming from partition backtrack but does not (yet) implement a full featured partition backtrack, so expect possible longish delays!</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BacktrackSearchStabilizerChainElement</code>( <var class="Arg">S</var>, <var class="Arg">P</var>, <var class="Arg">g</var>, <var class="Arg">pruner</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">fail</code> or a group element</p>
<p>Let <span class="SimpleMath">G</span> be the group described by the stabiliser chain <var class="Arg">S</var>. The group element <var class="Arg">g</var> must be some element in an overgroup <span class="SimpleMath">hat G</span>of <span class="SimpleMath">G</span> such that the function <var class="Arg">P</var> described below is defined on the whole of <span class="SimpleMath">hat G</span></p>
<p>This operation implements a generic backtrack search in the coset <span class="SimpleMath">G<var class="Arg">g</var></span> looking for an element <span class="SimpleMath">x in G</span> such that <var class="Arg">P</var><span class="SimpleMath">(x<var class="Arg">g</var>)</span> is <code class="keyw">true</code> where <var class="Arg">P</var> is a function on <span class="SimpleMath">hat G</span>taking values <code class="keyw">true</code> and <code class="keyw">false</code>. The operation returns the group element <span class="SimpleMath">x</span> if one is found or <code class="keyw">fail</code> if none was found.</p>
<p>The search tree is given by the stabiliser chain, each node corresponds to a right coset of one of the stabilisers in the chain. The leaves correspond to right cosets of the identity group, i.e. to group elements in <span class="SimpleMath">G<var class="Arg">g</var></span></p>
<p>To make this backtrack search efficient some pruning of the search tree has to be done. To this end there is the fourth argument <var class="Arg">pruner</var> which can either be <code class="keyw">false</code> (in which case no pruning at all happens) or a <strong class="pkg">GAP</strong> function taking 5 arguments and returning either <code class="keyw">true</code> or <code class="keyw">false</code>. The function <var class="Arg">pruner</var> is called for every node in the search tree before the backtrack search descents into the subtrees. If the <var class="Arg">pruner</var> function returns <code class="keyw">false</code>, the complete subtree starting at the current node is pruned and no further search is performed there. If the result is <code class="keyw">true</code> (or <var class="Arg">pruner</var> was equal to <code class="keyw">false</code> altogether) then the subtree starting at the current node is searched recursively. Obviously, the <var class="Arg">pruner</var> function needs to know the current position in the search tree, which it is told by its arguments.</p>
<p>Each node in the search tree corresponds to a coset of some stabiliser of the stabiliser chain in its previous one. To set up some notation, let <span class="Math"> G = S_0 > S_1 > S_2 > \cdots > S_m > S_{{m+1}} = \{1\} </span> be the stabiliser chain and let <span class="Math"> O_1, O_2, \ldots, O_m </span> be the basic orbits. Then for the node corresponding to the coset <span class="SimpleMath">S_i t<varclass="Arg">g</var></span> for <span class="SimpleMath">i ≥ 1</span> and some transversal element <span class="SimpleMath">t</span> contained in <span class="SimpleMath">S_{i-1}</span> the arguments with which the <var class="Arg">pruner</var> function is called are the following: The first argument is the stabiliser chain object corresponding to <span class="SimpleMath">S_{i-1}</span>. The second argument is the index of the element in <span class="SimpleMath">O_i</span> corresponding to the transversal element <span class="SimpleMath">t</span>. The third argument is the group element <span class="SimpleMath">t<var class="Arg">g</var></span> and the fourth argument is equal to the actual transversal element <span class="SimpleMath">t</span>. The fifth argument is a word in the generators used to enumerate <span class="SimpleMath">O_i</span> expressing <span class="SimpleMath">t</span>, the word comes as a list of integers which are the generator numbers.</p>
<p>Let <span class="SimpleMath">G</span> be the group described by the stabiliser chain <var class="Arg">S</var>. This operation implements a generic backtrack search in the stabiliser chain <var class="Arg">S</var> looking for the subgroup <span class="SimpleMath">H</span> of the group <span class="SimpleMath">G</span> described by <var class="Arg">S</var> of all elements <span class="SimpleMath">x</span> for which <var class="Arg">P</var><span class="SimpleMath">(x)</span> is <code class="keyw">true</code>, where <var class="Arg">P</var> is a function on <span class="SimpleMath">G</span> taking values <code class="keyw">true</code> or <code class="keyw">false</code>. Note that of course <var class="Arg">P</var> must be such that <span class="SimpleMath">H</span> is actually a subgroup! The operation returns a stabiliser chain describing the group <span class="SimpleMath">H</span>.</p>
<p>The search tree is given by the stabiliser chain, each node corresponds to a right coset of one of the stabilisers in the chain. The leaves correspond to right cosets of the identity group, i.e. to group elements in <span class="SimpleMath">G</span></p>
<p>To make this backtrack search efficient some pruning of the search tree has to be done. To this end there is the fourth argument <var class="Arg">pruner</var> which can either be <code class="keyw">false</code> (in which case no pruning at all happens) or a <strong class="pkg">GAP</strong> function taking 5 arguments and returning either <code class="keyw">true</code> or <code class="keyw">false</code>. The function <var class="Arg">pruner</var> is called for every node in the search tree before the backtrack search descents into the subtrees. If the <var class="Arg">pruner</var> function returns <code class="keyw">false</code>, the complete subtree starting at the current node is pruned and no further search is performed there. If the result is <code class="keyw">true</code> (or <var class="Arg">pruner</var> was equal to <code class="keyw">false</code> altogether) then the subtree starting at the current node is searched recursively. Obviously, the <var class="Arg">pruner</var> function needs to know the current position in the search tree, which it is told by its arguments.</p>
<p>Each node in the search tree corresponds to a coset of some stabiliser of the stabiliser chain in its previous one. To set up some notation, let <span class="Math"> G = S_0 > S_1 > S_2 > \cdots > S_m > S_{{m+1}} = \{1\} </span> be the stabiliser chain and let <span class="Math"> O_1, O_2, \ldots, O_m </span> be the basic orbits. Then for the node corresponding to the coset <span class="SimpleMath">S_i t<varclass="Arg">g</var></span> for <span class="SimpleMath">i ≥ 1</span> and some transversal element <span class="SimpleMath">t</span> contained in <span class="SimpleMath">S_{i-1}</span> the arguments with which the <var class="Arg">pruner</var> function is called are the following: The first argument is the stabiliser chain object corresponding to <span class="SimpleMath">S_{i-1}</span>. The second argument is the index of the element in <span class="SimpleMath">O_i</span> corresponding to the transversal element <span class="SimpleMath">t</span>. The third and fourth arguments are the transversal element <span class="SimpleMath">t</span>. The fifth argument is a word in the generators used to enumerate <span class="SimpleMath">O_i</span> expressing <span class="SimpleMath">t</span>, the word comes as a list of integers which are the generator numbers.</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 und die Messung sind noch experimentell.
