5. Conclusions

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
with
*prefix rewrites* the word
to *v* if
is a prefix of *u*, say
,
and
.
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
to the defining relators of the group.
Let PREFIXKB be an algorithm which given a finite set of rules
,
,
computes the reduced equivalent convergent system.

llGiven:, . [1ex] ;ifthen;else; ; ;whiledo; ;ifis not prefix string reducible byGthen; ; ; ; G; ;endifendwhileendif

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