2. String Rewriting Methods

First we give some basic definitions for string rewriting systems (for a general reference of the terms and techniques described here see [2]). A string rewriting system T over a finite alphabet $\Gamma$ is a subset of $\Gamma^* \times \Gamma^*$. The elements $\ell \longrightarrow r$ of T are called rules. The single-step reduction relation on $\Gamma^*$ induced by T is defined as follows: For any u,v in $\Gamma^*$, $u \longrightarrow_T v$ if and only if there exist x,y in $\Gamma^*$ and $\ell \longrightarrow r$ in T such that $u \equiv x\ell y$ and $v \equiv xry$. v is then called a proper descendant of u. The reflexive transitive symmetric closure is denoted by $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$. If $u \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v$ holds then one says that u reduces to v. In case u has no proper descendant u is called irreducible. An irreducible descendant of u is called a T-normal form. Such normal forms need neither exist nor be unique. The reduction relation $\longrightarrow_T$ is called Noetherian or terminating if and only if there is no infinite chain $u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v_1 \mbox{... ...} v_2 \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } \ldots$. In this case normal forms always exist. It is called confluent if for all u,v,w in $\Gamma^*$, $u \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v$ and $u \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } w$ imply the existence of z in $\Gamma^*$ such that $v \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } z$ and $w \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } z$. Then normal forms are unique in case they exist. A string rewriting system is called convergent or complete if it is both, Noetherian and confluent, i.e., unique normal forms exist. By Newman's lemma we know that under the hypothesis that a reduction relation is Noetherian, a string rewriting system is confluent if and only if it is locally confluent, i.e., for all u,v,w in $\Gamma^*$, $u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v$ and $u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } w$ imply the existence of z in $\Gamma^*$ such that $v \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } z$ and $w \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } z$. For finite string rewriting systems the global property of being locally confluent can be localized to enable a finite confluence test by standard critical pair sets. The process of trying to turn a Noetherian string rewriting system into a convergent one by resolving the not locally confluent situations is called completion and is performed by the Knuth-Bendix completion procedure (abbreviated by KB) which is based on resolving critical pairs. Since the word problem for string rewriting systems is undecidable, such a completion procedure in general will not terminate. Nevertheless, using a fair³ strategy, it always enumerates a convergent string rewriting system presenting the same monoid as the input system.

Henceforth in this paper, we will only consider string rewriting systems $(\Gamma, T)$ such that for $\ell \longrightarrow r \in T$ we have $\ell > r$ for some well-founded admissible ordering > on $\Gamma^*$. This ordering will be the length-lexicographic in the examples given here.

Now any group presentation in terms of generators $\Sigma$ and relators R gives rise to a string rewriting system by setting $\Gamma = \bar{\Sigma}$ and $T = T_I \cup T_R$ where $T_I = \{ aa^{-1} \longrightarrow\lambda, a^{-1}a \longrightarrow\lambda \mid a \in \Sigma \}$ and $T_R = \{ r \longrightarrow\lambda \mid r \in R \}$. Running KB on this input results in a (possibly infinite) completion of the presentation with respect to the chosen completion ordering on $\bar{\Sigma}^*$. If the resulting convergent system is finite many questions concerning the group can be answered (see e.g. [2]).

Another specialized string rewriting technique used to study subgroups of groups is prefix string rewriting. Any string rewriting system $(\Gamma, T)$ can be interpreted as a prefix string rewriting system with a single-step reduction relation on $\Gamma^*$ induced by T as follows: For any u,v in $\Gamma^*$, $u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{T}\,$ } v$ if and only if there exist y in $\Gamma^*$ and $\ell \longrightarrow r$ in T such that $u \equiv\ell y$ and $v \equiv ry$. The notions irreducible, T-normal form, Noetherian, confluent and convergent with respect to prefix string rewriting carry over naturally. A completion procedure with respect to prefix string rewriting is nothing else than an interreduction of the respective set of rules by prefix rewriting and in contrary to KB always terminates for the finite string rewriting systems we are looking at in this paper.