Constructing canonical presentations for subgroups of context-free groups in polynomial time (extended abstract)

ABSTRACT

Canonical presentations of groups are of interest, since they provide structurally simple algorithms for computing normal forms. A class of groups that has received much attention is the class of context-free groups. This class of groups can be characterized algebraically as well as through some language-theoretical properties as well as through certain combinatorial properties of presentations. Here we use the fact that a finitely generated group is context-free if and only if it admits a finite canonical presentation of a certain form that we call a virtually free presentation. Since finitely generated subgroups of context-free groups are again context-free, they admit presentations of the same form. We present a polynomial-time algorithm that, given a finite virtually free presentation of a context-free group G and a finite subset U of G as input, computes a virtually free presentation for the subgroup U of G that is generated by U.

REFERENCES

• 1: Jean-Michel Autebert , Luc Boasson , Geraud Sénizergues, Groups and NTS languages, Journal of Computer and System Sciences, v.35 n.2, p.243-267, Oct. 1987 [doi>10.1016/0022-0000(87)90015-8]
• 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: G. Bauer; Zur Darstellun9 yon Monoiden dutch konfluente Reduktionssysteme; Doctoral Dissertation, Fachbereich Informatik, Universit~t Kaiserslautern, 1981.
• 4: Ronald V. Book , Friedrich Otto, String-rewriting systems, Springer-Verlag, London, 1993
• 5: R. Cremanns; Prefiz-rewritin9 on virtually free groups; Preprint no. 1/94, Fachbereich Mathematik/informatik, Universit/it GH Kassel, 1994.
• 6: W. Dicks, M.J. Dunwoody; Groups Acting On Graphs; Cambridge University Press: Cambridge, 1989.
• 7: N. Kuhn; Zur Entscheidbarkeit des Unter- 9ruppenproblems far Gruppen mit kanonischen Darstellungen; Doctoral Dissertation, Fachbereich Informatik, Universit/it Kaiserslautern, 1991.
• 8: N. Kuhn , K. Madlener, A method for enumerating cosets of a group presented by a canonical system, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.338-350, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74580]
• 9: Norbert Kuhn , Klaus Madlener , Friedrich Otto, Computing presentations for subgroups of context-free groups, Papers from the international symposium on Symbolic and algebraic computation, p.240-250, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143321]
• 10: Ph. LeChenadec; Canonical Forms In Finitely Presented Algebras; Pitman: London, 1986.
• 11: R.C. Lyndon, P.E. Schupp; Combinatorial Group Theory; Springer: Berlin, 1977.
• 12: K. Madlener , P. Narendran , F. Otto, A specialized completion procedure for monadic string-rewriting systems presenting groups, Proceedings of the 18th international colloquium on Automata, languages and programming, p.279-290, June 1991, Madrid, Spain
• 13: C.F. Miller III; On Group-Theoretic Decision Problems And Their Classification; Annals of Math. Studies 68, Princeton University Press, Princeton, 1971.
• 14: D.E. Muller, P.E. Schupp; Groups, the theory of ends and context-free languages; Journal Computer System Sciences 26 (1983) 295-310.
• 15: F. Otto; Conjugacy in monoids with a special Church-Rosser presentation is decidable; Semigroup Forum 29 (1984) 223-240.
• 16: Géraud Sénizergues, An Effective Version of Stallings' Theorem in the Case of Context-Free Groups, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.478-495, July 05-09, 1993

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Languages, Theory, Verification