Groups can be studied using methods from different fields such as combinatorial group theory or string rewriting. Recently techniques from Gröbner basis theory for free monoid rings (non-commutative polynomial rings) respectively free group rings have been added to the set of methods due to the fact that monoid and group presentations (in terms of string rewriting systems) can be linked to special polynomials called binomials. In the same mood, the aim of this paper is to discuss the relation between Nielsen reduced sets of generators and the Todd-Coxeter coset enumeration procedure on the one side and the Gröbner basis theory for free group rings on the other. While it is well-known that there is a strong relationship between Buchberger's algorithm and the Knuth-Bendix completion procedure, and there are interpretations of the Todd-Coxeter coset enumeration procedure using the Knuth-Bendix procedure for special cases, our aim is to show how a verbatim interpretation of the Todd-Coxeter procedure can be obtained by linking recent Gröbner techniques like prefix Gröbner bases and the FGLM algorithm as a tool to study the duality of ideals. As a side product our procedure computes Nielsen reduced generating sets for subgroups in finitely generated free groups.

Following the course set by A. Markov (1951), S. Adjan (1958), and M. Rabin (1958), C. Ó'Dúnlaing (1983) has shown that certain properties of finitely generated Thue congruences are undecidable in general. Here we prove that many of these undecidability results remain valid even when only finitely generated Thue congruences on a fixed two-letter alphabet Σ 2 are considered. In contrast to a construction given by P. Schupp (1976) which applies to groups only, we use a modified version of a technical lemma from A. Markov's original paper. Based on this technical result we can carry the result of A. Sattler-Klein (1996), which says that certain Markov properties remain undecidable even when they are restricted to finitely generated Thue congruences that are decidable, over to the alphabet Σ 2 .

FollowingBuchberger's approach to computing a Grobner basis of a polynomial ideal in polynomial rings, a completion procedure for finitely generated right ideals in Z['H] is given, where '1-l is an ordered monoid presented by a finite, convergent semi-Thue system (X, T). plication to the subgroup problem is discussed.

We apply rewriting techniques to the generalized word problem for groups. Let R be a finite string-rewriting system on an alphabet Σ such that the monoid MR presented by (Σ:R) is a group, and let U ⊆ Σ→ be a finite set. The generalized word problem GWP is defined by GWP(w.U) if w ∈ , where is the subgroup of MR generated by U. With U we associate a prefix rewriting relation ⇒P on Σ* such that w P λ if GWP(w.U) holds. If ⇒P is λ-confluent then w ⇒ P λ if w ∈ . Then ⇒P yields a decision procedure for GWP. For groups given through confluent string-rewriting systems R, we develop a necessary and sufficient condition for ⇒P being λ-confluent and show that this condition becomes decidable in case of R being length-reducing, in addition.

The application of rewriting techniques to enumerate cosets of subgroups in groups is investigated. Given a class of groups G having canonical string rewriting presentations we consider the GWP for this class which is defined by GWP(w,U) iff w ∈ for w ∈ G, finite U⊆G, G ∈ G where is the subgroup of G generated by U. We show how to associate to U two rewriting relations @@@@U and @@@@U on strings such that w ∈ iff w @@@@U λ iff w @@@@U λ (λ the empty word), both representing the left congruence generated by . We derive general critical pair criteria for confluence and λ-confluence for these relations. Using these criteria completion procedures can be constructed which enumerate cosets like the Todd-Coxeter algorithm without explicit definition of all cosets. The procedures are shown to be terminating if the index of the subgroup is finite or for groups with finite canonical monadic group presentations. If the completion procedure terminates it returns a prefix rewriting system which is confluent on Σ*, thus deciding the GWP and the index problem for this class of groups. The normal forms of the rewriting relations form a minimal Schreier-representative system of in G.