Next: 8. TC in Monoids Up: Observations on Coset Enumeration Previous: 6. Sims' Approach

# 7. Simulating Todd-Coxeter with Prefix String Rewriting

In this section we want to present a procedure which emulates TC. It is based on the algebraic procedure presented in [14] for simulating TC using prefix Gröbner bases methods.

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 SIMULATION
Given: 		 (

,
TS
[1ex]

;

;

;
while

do

;

;
if
is not prefix  reducible by G
then

;

;

;

;

G;
endif
endwhile

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

Theorem 4   Let R and S be as specified above. Procedure GENERALIZED TC SIMULATION terminates iff the subgroup generated by has finite index in .

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.

Next: 8. TC in Monoids Up: Observations on Coset Enumeration Previous: 6. Sims' Approach
| ZCA Home | Reports |