Observations on Coset Enumeration
Reports On Computer Algebra No 23. Centre for Computer Algebra. University of Kaiserslautern. November 1998. (Gzippped Postscript, 70 Kbytes, 52 pp)

Abstract:
Todd and Coxeter's method for enumerating cosets of finitely generated subgroups in finitely presented groups (abbreviated by Tc here) is one famous method from combinatorial group theory for studying the subgroup problem. Since prefix string rewriting is also an appropriate method to study this problem, prefix string rewriting methods have been compared to {\sc Tc}. We recall and compare two of them briefly, one by Kuhn and Madlener [KuMa89] and one by Sims [Si94]. A new approach using prefix string rewriting in free groups is derived from the algebraic method presented by Reinert, Mora and Madlener in [ReMoMa98] which directly emulates Tc. It is extended to free monoids and an algebraic characterization for the ``cosets'' enumerated in this setting is provided.

Birgit Reinert
Universität Kaiserslautern
Fachbereich Informatik
Postfach 3049
67653 Kaiserslautern, Germany

reinert@informatik.uni-kl.de
back to publications 1998