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:
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 .
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.