Abstract:
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 grou p 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 disc uss the relation between Nielsen reduced sets of generators and the Todd-Coxeter cos et enumeration procedure on the one side and the Gröbner basis theory for free gro up 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 inte rpretation of the Todd-Coxeter procedure can be obtained by linking recent Gröbner techniq ues like prefix Gröbner bases and the FGLM algorithm as a tool to study the duality of i deals. As a side product our procedure computes Nielsen reduced generating sets for sub groups in finitely generated free groups.

Klaus Madlener, Birgit Reinert, Teo Mora
Fachbereich Informatik
Postfach 3049
67653 Kaiserslautern, Germany