3. The Subgroup Problem

This section outlines the subgroup problem for groups and its connections to string rewriting techniques.

Definition 1   Given a subgroup ${\cal H}$ of a group ${\cal G}$ the generalized word problem or the subgroup problem for ${\cal H}$ is to determine, given $w \in {\cal G}$, whether $w \in {\cal H}$.

For a finite subset S of a group ${\cal G}$ and $S^{-1} = \{ s^{-1} \mid s \in S \}$ let $\left< S \right> = \{ s_1 \circ\ldots \circ s_n \mid n \in \mathbb{N} , s_i \in S \cup S^{-1} \}$ denote the subgroup generated by S. A subgroup ${\cal H}$ of a group ${\cal G}$ is called finitely generated if there exists a finite subset S of ${\cal G}$ such that ${\cal H}= \left< S \right>$. We say a group ${\cal G}$ has solvable generalized word problem if for every finite subset S of ${\cal G}$ the subgroup problem for $\left< S \right>$ is decidable.

The word problem for a group ${\cal G}$ is just the generalized word problem for the trivial subgroup in ${\cal G}$ since u = v holds in ${\cal G}$ if and only if $u \circ v^{-1} = \lambda$ holds in ${\cal G}$, i.e.  $u \circ v^{-1} \in \left< \lambda \right>$. Thus the existence of a group with undecidable word problem yields undecidability for the generalized word problem for this group as well. On the other hand, decidable word problem for a group does not imply decidable generalized word problem (for an overview on various decision problems for groups see e.g. [10]).

Subgroups of groups can be characterized by one-sided congruences on the group. In the following we restrict ourselves to the case of right congruences (left congruences can be introduced in a similar fashion). Let ${\cal H}$ be a subgroup of a group ${\cal G}$. Then for $u,v \in {\cal G}$ we can define

$$u \sim_{{\cal H}} v \mbox{ if and only if } {\cal H}u = {\cal H}v$$

where ${\cal H}u = \{ g \circ u \mid g \in {\cal H}\}$. It is easy to prove that $\sim_{{\cal H}}$ is a right congruence. The subgroup ${\cal H}$ itself is the congruence class of $\lambda$. This right congruence is a congruence if and only if ${\cal H}$ is a normal subgroup.

Let us take a look at how the right congruence of the subgroup ${\cal H}$ generated by S in the group ${\cal G}$ presented by $(\bar{\Sigma}, T = T_I \cup T_R)$ can be described using string rewriting techniques. To S we associate the set of rules $T_S = \{ s \longrightarrow\lambda \mid s \in S \}$. We study the rewriting relation induced by the combined reduction relation $\Longrightarrow_{S, T} = \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{T_S}\,$ } \cup \longrightarrow_T$ which presents the right congruence $\sim_{{\cal H}}$ in that $\sim_{{\cal H}} = \mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{S,T}\,$ }$. Since we have $w \in {\cal H}$ if and only if $w \mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{S,T}\,$ } \lambda$, this problem becomes immediately solvable for appropriate reduction relations, e.g. in the case of $\lambda$-confluence for $\Longrightarrow_{S, T}$. Following a short presentation of TC, three different string rewriting approaches will be outlined and their output compared to TC.