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 $\bar{\Sigma}$, $T_I = \{ aa^{-1} \longrightarrow\lambda, a^{-1}a \longrightarrow\lambda \mid a \in \Sigma \}$ and $T_R = \{ r \longrightarrow\lambda \mid r \in R \}$, and the generators of the subgroup encoded in the set of rules $T_S = \{ s \longrightarrow\lambda \mid s \in S \}$. Additionally we will use the following sets:

• A set $N\subseteq {\cal F}$ of potential coset representatives of the subgroup generated by $S \cup N(R)$ in ${\cal F}$.
• A set $B\subseteq {\cal F}$ 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 $B:=\{a\mid a\in\bar{\Sigma}\}$. The set G, which on termination will encode the non-trivial part of the coset table, is computed by prefix interreducing the set $T_I \cup T_R \cup T_S$. Hence, the rules in G can be used to decide the membership for the subgroup of ${\cal F}$ that is generated by $S \cup R$. 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 $\tau$. If $\tau$ is not prefix-reducible by G, then it is added to N and all elements of the form $\tau a$ are added to B, where $a \in\bar{\Sigma}$. Next $H:=\{\tau \ell \longrightarrow\tau r \mid \ell \longrightarrow r \in T_I \cup T_R\}$ 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 $\tau$. Finally the set $G\cup H$, which corresponds to the subgroup of ${\cal F}$ that is generated by $S \cup \{\tau \circ r \circ\tau^{-1}\mid \tau \in N, r\in R\}$, is prefix interreduced. Hence, we approximate the potentially infinite generating set of the subgroup $\langle S \cup N(R)\rangle$ of ${\cal F}$. 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: 		 (

$\bar{\Sigma}, T = T_I \cup T_R)$,
TS 
[1ex] 

$N := \{ \lambda \}$;


$B:=\{a\mid a\in\bar{\Sigma}\}$;


$G := {\sf prefix.interreduce}(T \cup T_S)$;
while 

$B \neq \emptyset$
do
		 

$\tau := {\sf min}_{<}(B)$;
		 

$B := B \backslash \{ \tau \}$;
		 if  $\tau$
is not prefix  reducible by G
		  then 		  

$N := N \cup \{ \tau \}$;
		 		  

$B := B \cup \{ \tau a \mid a \in \bar{\Sigma} \}$;
		 		   

$H := \{ \tau \ell \longrightarrow\tau r \mid \ell \longrightarrow r \in T \}$;
		 		   

$G := {\sf prefix.interreduce}(G \cup H)$;
		 		   

$N := N \backslash \{ w \in N \mid w \mbox{ is reducible by }$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 $S \cup N(R)$ has finite index in ${\cal F}$.

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.