7. Simulating Todd-Coxeter with Prefix String Rewriting

Informally the procedure works as follows:

The input consists of the group presentation in terms of the sets , and , and the generators of the subgroup encoded in the set of rules . Additionally we will use the following sets:

- A set of potential coset representatives of the subgroup generated by in .
- A set that serves as a test set for possible coset representatives.
- A set
*H*that is used to approximate the infinite generating set*N*(*R*). - A prefix interreduced set of rules
*G*that is used to decide whether or not the elements in*B*are indeed coset representatives of the respective approximated subgroup.

The set *N*, which on termination will contain the coset representatives,
is initialized as the set containing
the empty string only, which is the coset representative of the subgroup
itself.
During the computation this set remains prefix-closed.
The set *B* of possible candidates for further cosets
is initialized as
.
The set *G*, which on termination will encode the non-trivial part of the coset table,
is computed by prefix interreducing the set
.
Hence, the rules in *G* can be used to decide the membership for the subgroup of
that is generated
by .
This completes the initialization phase.

Now as long as there still are candidates for new cosets in *B* the following actions
are performed:
We choose and remove the smallest element from *B* (with respect to the
length-lexicographical ordering) and call it .
If
is not prefix-reducible by *G*, then it is
added to *N* and all elements of the form
are added to
*B*, where
.
Next
is determined, which in TC
corresponds to the process of marking the first and the last slot of each
relator table with the newly found coset representative .
Finally the set ,
which corresponds to the subgroup of
that is generated by
,
is prefix interreduced.
Hence, we approximate the potentially infinite generating set of the
subgroup
of .
Based on the new set *G* some elements of *N* may become
prefix reducible.
These have to be removed from *N*, as they are no longer coset
representatives.
This corresponds to the collapse of cosets in TC.

llGENERALIZED TC SIMULATIONGiven:( ,T_{S}[1ex] ; ; ;whiledo; ;ifis not prefix reducible byGthen; ; ; ; G;endifendwhile

The following theorem is a direct conclusion of the results stated in [14].

Applying this procedure to Example 3 it terminates with 24 cosets in *N*
and the set *G* encodes the non-trivial part of the
coset table.