A method for enumerating cosets of a group presented by a canonical system

ABSTRACT

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 ∈ <U> for w ∈ G, finite U⊆G, G ∈ G where <U> 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 ∈ <U> iff w @@@@U &lgr; iff w @@@@U &lgr; (&lgr; the empty word), both representing the left congruence generated by <U>. We derive general critical pair criteria for confluence and &lgr;-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 &Sgr;*, 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 <U> in G.

REFERENCES

• 1: Atkinson, M. (ed.): Computational Group Theory. Academic Press London (1984).
• 2: J Avenhaus , K Madlener, The Nielsen reduction and P-complete problems in free groups, Theoretical Computer Science, v.32 n.1-2, p.61-76, July 1984 [doi>10.1016/0304-3975(84)90024-0]
• 3: Avenhaus, J., Madlener, K., Otto, F.: Groups presented by finite two-monadic Church-Rosser Thue Systems. Trans. of the American Math. Soc., 297 (1986), 427-443.
• 4: J. Avenhaus , D. Wi:Gbmann, Using rewriting techniques to solve the generalized word problem in polycyclic groups, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.322-337, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74579]
• 5: Bauer, G.' Zur Darstellung yon Monoiden durch konfiuente Regelsysteme. Dissertation Universit~t Kaiserslautern (1981 ).
• 6: Ronald V. Book, Thue systems as rewriting systems, Proc. of the first international conference on Rewriting techniques and applications, p.63-94, December 1985, Dijon, France
• 7: Book, R., Jantzen, M., Wrathall, C.: Monadic Thue Systems. Theoretical Comp. Science 19 (1982), 231-251.
• 8: Dehn, M.' Uber unendliche diskontinuierliche Gruppen. Math. Ann., 71 (1911), 116-144.
• 9: Gilman, R.' Presentations of Groups and Monoids. J. Alg. 57 (1979), 544-554.
• 10: Robert H. Gilman, Computations with Rational Subsets of Confluent Groups, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.207-212, July 09-11, 1984
• 11: Lyndon, R.C., Schupp, P.E.: Combinatorial group theory. Springer- Verlag, Berlin (1977).
• 12: K. Madlener , F. Otto, Groups presented by certain classes of finite length-reducing string rewriting systems, on Rewriting techniques and applications, p.133-144, May 1987, Bordeaux, France
• 13: Miller, C.F. Iii: On group-theoretic decision problems and their classifications. Ann. of Math. Studies 68, Princeton: Princeton University Press.
• 14: Nielsen, J.:Om Regning med ikke kommutative Faktoren og dens Anvendelse i Gruppeteorien. Matematisk Tidsskrift B, (1921), 77-94.
• 15: F. Otto, On deciding the confluence of a finite string-rewriting system on a given congruence class, Journal of Computer and System Sciences, v.35 n.3, p.285-310, Dec. 1987 [doi>10.1016/0022-0000(87)90017-1]
• 16: Wigmann, D.: Anwendungen yon Rewriting- Techniken in polyzyklischen Gruppen.. Dissertation, Universit~it Kaiserslautern (1989).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Decision problems

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory