3. Frameworks

As already mentioned in the previous section, computing the prefix Gröbner basis after each addition of a new coset is much to costly for all but very small examples. As a consequence it is necessary to define a certain number of cosets before recomputing the multiplication table, i.e. the prefix Gröbner basis. This might lead to the introduction of a large number of unnecessary cosets but for larger examples it is much faster than the simple approach as fewer Gröbner basis computations are necessary.

Two different frameworks have been considered which are described in
Section 3.1 and 3.2.
They are compared to two strategies for Todd-Coxeter enumeration in
Section 3.3.
The frameworks use the procedures * additional_elements_start* and
* additional_elements* which add elements,
which normally would not be considered during the enumeration process
until much later,
to the border set after the first and after each subsequent
Gröbner basis computation, respectively.
These are described in Section 4.

Both frameworks depend on the organization of the borderset. The borderset is currently organized as a queue with an additional data structure ordered set used to check whether elements are already in the borderset. The queue implies that always the first element of the queue is selected and new elements are added to the end. As the characters of the alphabet are added to the borderset in the same order in which they are read from the input, the elements are considered from smallest to largest with respect to a length-lexicographical ordering with the precedence small to large as read from the input. According to the algorithm, elements are skipped which can not lead to new cosets.