6. Sims' Approach

In Section 2.8. of [15] Sims gives an approach similar to the one in the previous section but allowing arbitrary presentations $(\bar{\Sigma}, T = T_I \cup T_R)$ for the group ${\cal G}$. Instead of defining a specialized completion procedure for prefix string rewriting he encodes the set T_S into an ordinary string rewriting system by adding a new symbol $ and transforming the rules to a new set $T_{\$S} = \{ \$s \longrightarrow\$ \mid s \in S \}$. Then the extended string rewriting system $(\bar{\Sigma} \cup \{ \$ \}, T_{\$S} \cup T_I \cup T_R)$ is completed using KB.

For the cosets of the subgroup of the Dyck group D(3,3,2) as presented in Example 2 we get the following situation: $\bar{\Sigma} = \{ a,b, a^{-1}, b^{-1} \}$, $T_R \cup T_I = \{ aaa \longrightarrow\lambda, bbb \longrightarrow\lambda, abab ... ...arrow\lambda, bb^{-1} \longrightarrow\lambda, b^{-1}b \longrightarrow\lambda \}$, and $T_{\$S} = \{ \$a \longrightarrow\$ \}$. Completing the string rewriting system $( \{ a, a^{-1}, b, b^{-1}, \$ \}, T_R \cup T_I \cup T_{\$S})$ with respect to the length-lexicographical ordering induced by the precedence $b^{-1} \succ a^{-1} \succ b \succ a \succ \$ using KB results in the convergent set of rules $R_{KB} = \{ aa^{-1} \longrightarrow\lambda, bb^{-1} \longrightarrow\lambda, b... ...-1}ab^{-1} \longrightarrow ab^{-1}a, a^{-1}ba^{-1} \longrightarrow ab^{-1}a \}$. For the sets T_C and T from the previous section we then have $T_C = \{ \ell \longrightarrow r \mid \$\ell \longrightarrow\$r \in R_{KB} \}$ and $T = R_{KB} \backslash T_C$.

Let us continue with a comparison of TC and KB as presented in this setting: When running KB for the free group on $T_I \cup T_{\$S}$ we are in fact computing a Nielsen reduced set for the subgroup generated by S. The situation is slightly different in the general case, as in contrary to TC, although we are simulating coset enumeration, it no longer must terminate for finite index. This is due to the fact that in any case KB will try to complete the defining relators $T_R \cup T_{I}$ and there are examples where we have finite index but no finite convergent system for $T_R \cup T_{I}$ exists. However, if we know that the index is finite, it is possible to find a bound on how far we have to run KB to gain enough information to describe the cosets. More information on this can be found in Section 3.10. in [15] where the following example is taken from. Notice that this example cannot be handled by the approach of Kuhn and Madlener in the previous section for the chosen string rewriting system presenting the group is not convergent.

Example 3   Let our group ${\cal G}$ be presented by the string rewriting system $\Gamma = \{ x, y, Y \}$⁶ and the set of rules $T = \{ xx \longrightarrow\lambda, yY \longrightarrow\lambda, Yy \longrightarrow\lambda, yxyxyxy \longrightarrow xYxYxYx \}$. The subgroup is encoded by $T_{\$S} = \{ \$y \longrightarrow\$x, \$yxYxyxYx \longrightarrow\$xyxYxyxY \}$. Running KB on input $\Gamma \cup \{ \$ \}$ and $T \cup T_{\$S}$ with the length-lexicographical ordering induced by the precedence $Y \succ y \succ x \succ \$ diverges. However Sims outlines how to use the knowledge that we have finite index to stop the calculation after considering all overlaps up to length 17 and verifying that there are 24 cosets.

Next we provide a procedure which can handle the finite index case without applying additional knowledge.