This chapter describes the methods for backtrack search in the genss 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.
‣ SetwiseStabilizer( G, op, M ) | ( operation ) |
Returns: a record
This operation computes the setwise stabiliser of the set M. So G must be a group acting on some set Ω, this action is given by the action function op. The set M must consist of elements Ω. The result is a record with the components setstab containing the setwise stabiliser and S containing a stabiliser chain for it.
This operation uses backtrack search in a specially crafted stabiliser chain for G doing not much intelligent pruning of the search tree, so expect possible long delays!
‣ SetwiseStabilizerPartitionBacktrack( G, op, M ) | ( operation ) |
Returns: a record
This operation computes the setwise stabiliser of the set M. So G must be a group acting on some set Ω, this action is given by the action function op. The set M must consist of elements Ω. The result is a record with the components setstab containing the setwise stabiliser and S containing a stabiliser chain for it.
This operation uses backtrack search in a specially crafted stabiliser chain for G. It does some ideas coming from partition backtrack but does not (yet) implement a full featured partition backtrack, so expect possible longish delays!
‣ BacktrackSearchStabilizerChainElement( S, P, g, pruner ) | ( operation ) |
Returns: fail or a group element
Let G be the group described by the stabiliser chain S. The group element g must be some element in an overgroup hat Gof G such that the function P described below is defined on the whole of hat G
This operation implements a generic backtrack search in the coset Gg looking for an element x in G such that P(xg) is true where P is a function on hat Gtaking values true and false. The operation returns the group element x if one is found or fail if none was found.
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 Gg
To make this backtrack search efficient some pruning of the search tree has to be done. To this end there is the fourth argument pruner which can either be false (in which case no pruning at all happens) or a GAP function taking 5 arguments and returning either true or false. The function pruner is called for every node in the search tree before the backtrack search descents into the subtrees. If the pruner function returns false, the complete subtree starting at the current node is pruned and no further search is performed there. If the result is true (or pruner was equal to false altogether) then the subtree starting at the current node is searched recursively. Obviously, the pruner function needs to know the current position in the search tree, which it is told by its arguments.
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 G = S_0 > S_1 > S_2 > \cdots > S_m > S_{{m+1}} = \{1\} be the stabiliser chain and let O_1, O_2, \ldots, O_m be the basic orbits. Then for the node corresponding to the coset S_i tg for i ≥ 1 and some transversal element t contained in S_{i-1} the arguments with which the pruner function is called are the following: The first argument is the stabiliser chain object corresponding to S_{i-1}. The second argument is the index of the element in O_i corresponding to the transversal element t. The third argument is the group element tg and the fourth argument is equal to the actual transversal element t. The fifth argument is a word in the generators used to enumerate O_i expressing t, the word comes as a list of integers which are the generator numbers.
‣ BacktrackSearchStabilizerChainSubgroup( S, P, pruner ) | ( operation ) |
Returns: fail or a stabiliser chain
Let G be the group described by the stabiliser chain S. This operation implements a generic backtrack search in the stabiliser chain S looking for the subgroup H of the group G described by S of all elements x for which P(x) is true, where P is a function on G taking values true or false. Note that of course P must be such that H is actually a subgroup! The operation returns a stabiliser chain describing the group H.
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 G
To make this backtrack search efficient some pruning of the search tree has to be done. To this end there is the fourth argument pruner which can either be false (in which case no pruning at all happens) or a GAP function taking 5 arguments and returning either true or false. The function pruner is called for every node in the search tree before the backtrack search descents into the subtrees. If the pruner function returns false, the complete subtree starting at the current node is pruned and no further search is performed there. If the result is true (or pruner was equal to false altogether) then the subtree starting at the current node is searched recursively. Obviously, the pruner function needs to know the current position in the search tree, which it is told by its arguments.
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 G = S_0 > S_1 > S_2 > \cdots > S_m > S_{{m+1}} = \{1\} be the stabiliser chain and let O_1, O_2, \ldots, O_m be the basic orbits. Then for the node corresponding to the coset S_i tg for i ≥ 1 and some transversal element t contained in S_{i-1} the arguments with which the pruner function is called are the following: The first argument is the stabiliser chain object corresponding to S_{i-1}. The second argument is the index of the element in O_i corresponding to the transversal element t. The third and fourth arguments are the transversal element t. The fifth argument is a word in the generators used to enumerate O_i expressing t, the word comes as a list of integers which are the generator numbers.
generated by GAPDoc2HTML