5. Conclusions

In this paper we have stated that there are strong links between the three fields combinatorial group theory, string rewriting theory and Gröbner basis theory when studying group theoretical problems as the word problem and the subgroup problem. The procedure EXTENDED TC SIMULATION has been presented in the setting of free group rings combining a generalization of the MATPHI procedure from [8] and prefix Gröbner bases from [15]. The implementation of the procedure (done in the system MRC developed at Kaiserslautern) will be compared to TC implementations.

Let us close this section by sketching how this result closes the gap in comparing TC to KB type procedures in string rewriting. The case of the trivial subgroup has successfully been treated in [2,25] while for the general case a partial solution was presented in [25] which did not necessarily terminate for subgroups of finite index. Now using Knuth-Bendix techniques for prefix string rewriting systems we can give a procedure analogous to EXTENDED TC SIMULATION and hence to TC. We say the rule $\ell \longrightarrow r$ with $\ell>r$ prefix rewrites the word $u \in \bar{\Sigma}^*$ to v if $\ell$ is a prefix of u, say $u \equiv\ell w$, and $v \equiv rw$. Note that in this setting no free reduction steps are applied due to the fact that pure prefix string rewriting takes place in the free monoid. Therefore, we have to add the inverse relators $\{ aa^{-1}, a^{-1}a \mid a \in \Sigma \}$ to the defining relators of the group. Let PREFIXKB be an algorithm which given a finite set of rules $\ell \longrightarrow r$, $\ell,r \in \bar{\Sigma}^*$, $\ell>r$ computes the reduced equivalent convergent system.

llGiven: 		 

$F_R = \{ r \longrightarrow\lambda \mid r \in R \} \cup \{ aa^{-1} \longrightarrow\lambda, a^{-1}a \longrightarrow\lambda \mid a \in \Sigma \}$,
		 

$F_U = \{ u \longrightarrow\lambda \mid u \in U \}$.
[1ex]

$N := \emptyset$;
if  

$R = \emptyset$
then 

$G := {\sf prefix.kb}(F_U)$;
else 		 

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

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

$G := {\sf prefix.kb}(F_R \cup F_U)$;
		while 

$B \neq \emptyset$
do
				 

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

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

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

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

$H := \{ \tau r \longrightarrow\tau \mid r \longrightarrow\lambda \in F_R \}$;
				 		   

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

$S := \{ w \in N \mid w \mbox{ is not prefix string reducible by }$G$\}$;
				 		   

$N := N \backslash S$;
		 		endif
		endwhile 
endif

A thorough comparison of all three methods is provided in [24].