4. Strategies

Already known coset enumeration procedures try to use ''clever'' strategies to select the coset to consider next. These strategies are based on information about the multiplication table.

The two frameworks would normally select the cosets in increasing order beginning with the smallest as described in Section 3. But there might be cosets which are quite large with respect to the ordering and lead to important information, e.g. that two or more cosets are identical. Using this information the enumeration process might be shortened considerably. Thus, in order to enhance the frameworks, strategies were provided to add elements to the borderset which normally would only be considered much later in the enumeration process.

It is neither obvious which elements should be considered nor when they should be added. Right now, the elements are added using the procedures additional_elements_start and additional_elements which add elements to the borderset after the first and each subsequent Gröbner basis computation, respectively, according to the following strategies:

1. NONE: No elements are added.

2. P-ALL: additional_elements_start and additional_elements add all prefixes of the head-terms of the polynomials of $G$: $\{ w \vert w \in \Sigma^{+} \mbox{ and } \exists p \in G \;\exists v \in \Sigma^{*}: wv \equiv {\sf HT}(p) \}$.

3. P-R: additional_elements_start and additional_elements add those prefixes of the head-terms of the polynomials of $G$ which, when multiplied with the generators, could lead to polynomials which can be reduced using $G$: $\{ u \vert u \in \Sigma^{+} \mbox{ and } \exists w \in \Sigma^{+}: [ \exists... ... \Sigma^{*} \; \exists r \in R: uv \equiv w \wedge vz \equiv {\sf HT}(r) ] \}$

4. P-G: additional_elements_start and additional_elements add those prefixes of the head-terms of the polynomials of $G$ which, when multiplied with polynomials of $G$, could lead to polynomials which can be reduced using $G$: $\{ u \vert u \in \Sigma^{+} \mbox{ and } \exists w \in \Sigma^{+}: [ \exists... ... \Sigma^{*} \; \exists g \in G: uv \equiv w \wedge vz \equiv {\sf HT}(g) ] \}$

5. I-ALL: additional_elements_start and additional_elements add all inverse terms of the prefixes of the head-terms of the polynomials of $G$: $\{ w^{-1} \vert w \in \Sigma^{*} \mbox{ and } \exists p \in G \;\exists v \in \Sigma^{*}: wv \equiv {\sf HT}(p) \}$.

6. I-R: additional_elements_start adds all inverse terms of the head-terms of the relators: $\{ w^{-1} \vert w \in \Sigma^{*} \mbox{ and } \exists r \in R \;\exists v \in \Sigma^{*}: wv \equiv {\sf HT}(r) \}$. additional_elements adds no elements to the borderset.

7. I-R-P: additional_elements_start adds all inverse terms of the head-terms of the relators: $\{ w^{-1} \vert w \in \Sigma^{*} \mbox{ and } \exists r \in R \;\exists v \in \Sigma^{*}: wv \equiv {\sf HT}(r) \}$. additional_elements_start and additional_elements add all prefixes of the head-terms of the polynomials of $G$: $\{ w \vert w \in \Sigma^{*} \mbox{ and } \exists p \in G \;\exists v \in \Sigma^{*}: wv \equiv {\sf HT}(p) \}$.

8. ENUM: additional_elements_start and additional_elements add elements in a special order.

9. RANDOM: additional_elements_start and additional_elements add random elements.

Only those elements are added which are neither already in the coset-set $N$ nor in the border set $B$ and which are not prefix-reducible using $G$. This reduces the maximal size of the border set $B$ and the new border set $B_{new}$, respectively.

The last two strategies for adding elements, namely ENUM and RANDOM, allow additional parameters. They are not considered further here.