** Next:** 6. Sims' Approach
** Up:** Observations on Coset Enumeration
** Previous:** 4. The Todd-Coxeter Coset

#

5. Kuhn and Madlener's Approach

In [4] a procedure for completing the reduction relation
as described
in Section 3 is
provided for the case that the group presentation
is *convergent*.
The basic idea is to interpret the rules defining the group as the (possibly infinite)
set of prefix string rewriting rules
.
Then
.
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
of the form
or
between rules
and
of the form
with
.
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
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
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
instead of the defining relators presented in the previous section.
Completing
with
respect to the length-lexicographical ordering induced by the precedence
gives us the convergent string rewriting system
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
and on input
on termination we get the set
and the convergent prefix string rewriting system
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.

** Next:** 6. Sims' Approach
** Up:** Observations on Coset Enumeration
** Previous:** 4. The Todd-Coxeter Coset
| ZCA Home |
Reports |