5. Kuhn and Madlener's Approach

In [4] a procedure for completing the reduction relation $\Longrightarrow_{S, T}$ as described in Section 3 is provided for the case that the group presentation $(\bar{\Sigma}, T = T_I \cup T_R)$ is convergent. The basic idea is to interpret the rules defining the group as the (possibly infinite) set of prefix string rewriting rules $P_T = \{ x\ell \longrightarrow xr \mid x \in \Gamma^*, \ell \longrightarrow r \... ... no proper prefix of } x\ell \mbox{ is } \longrightarrow_T-\mbox{reducible} \}$. Then $\mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{S,T}\,$ } = \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm p}}_{T_S \cup P_T}\,$ }$. A completion procedure for this reduction relation has T_S and T as input and on termination a set T_C as output which is constructed as follows: T_C is initialized as T_S. The completion step then considers critical situations between rules $\ell_1 \longrightarrow r_1, \ell_2 \longrightarrow r_2 \in T_C$ of the form $\ell_1 \equiv\ell_2 y$ or between rules $\ell_1 \longrightarrow r_1 \in T$ and $\ell_2 \longrightarrow r_2 \in T_C$ of the form $x\ell_1 \equiv\ell_2 y$ with $\vert x\vert<\vert\ell_2\vert$. The overlaps between rules in T can be omitted as T is already convergent. If critical situations cannot be resolved, the newly arising rules are added to T_C. On termination the (still possibly infinite) set $T_C \cup P_T$ is convergent as a prefix string rewriting system. It is known that for subgroups of finite index the procedure terminates. In this case the interreduced version of the set $T_C \cup P_T$ is finite and corresponds to the set R_TC arising from the coset table for TC as described in the previous section. Of course in order to treat Example 2 we have to use a convergent group presentation for ${\cal G}$ instead of the defining relators presented in the previous section. Completing $\{ aaa \longrightarrow\lambda, bbb \longrightarrow\lambda, abab \longrightarrow... ...arrow\lambda, bb^{-1} \longrightarrow\lambda, b^{-1}b \longrightarrow\lambda \}$ with respect to the length-lexicographical ordering induced by the precedence $b^{-1} \succ a^{-1} \succ b \succ a$ gives us the convergent string rewriting system $( \{ a,b,a^{-1},b^{-1} \}, \{$ $aa^{-1} \longrightarrow\lambda$, $a^{-1}a \longrightarrow\lambda$, $bb^{-1} \longrightarrow\lambda$, $b^{-1}b \longrightarrow\lambda$, $aa \longrightarrow a^{-1}$, $bab \longrightarrow a^{-1}$, $bb \longrightarrow b^{-1}$, $a^{-1}a^{-1} \longrightarrow a$, $a^{-1}b^{-1} \longrightarrow ba$, $b^{-1}a^{-1} \longrightarrow ab$, $b^{-1}b^{-1} \longrightarrow b$, $b^{-1}ab \longrightarrow ba^{-1}$, $bab^{-1} \longrightarrow a^{-1}b$, $aba \longrightarrow b^{-1}$, $a^{-1}ba \longrightarrow ab^{-1}$, $aba^{-1} \longrightarrow b^{-1}a$, $ba^{-1}b \longrightarrow ab^{-1}a$, $b^{-1}ab^{-1} \longrightarrow ab^{-1}a$, $a^{-1}ba^{-1} \longrightarrow ab^{-1}a$ $\})$ and on input $T_S = \{ a \longrightarrow\lambda \}$ on termination we get the set $T_C = \{ a \longrightarrow\lambda, a^{-1} \longrightarrow\lambda, ba \longrightarrow b^{-1}, b^{-1}a \longrightarrow ba^{-1} \}$ and the convergent prefix string rewriting system $T_C \cup P_T$ can be prefix interreduced to the set of rules R_TC in Example 2.

While sometimes also successful for subgroups of infinite index, this method is no longer applicable to groups given by arbitrary presentations. This would also require that on completing T_C we additionally have to resolve critical situations arising from overlaps of rules in T. This is essentially what happens in Sims' approach.